hash_table.c File Reference

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <immintrin.h>
#include <stdio.h>
#include "tokenizer/hash_table.h"
#include "tokenizer/murmurhash3.h"

Go to the source code of this file.

Macros
#define	CK_TOKENIZER_HASH_SEED   0x9747b28c

Functions
uint32_t	ck_tokenizer_hash (const char *key, size_t len)
uint32_t	ck_tokenizer_hash_str (const char *key)
void	ck_tokenizer_hash_table_clear (CKTokenizerHashTable *table, bool free_values)
bool	ck_tokenizer_hash_table_contains (CKTokenizerHashTable *table, const char *key)
size_t	ck_tokenizer_hash_table_count (CKTokenizerHashTable *table)
CKTokenizerHashTable *	ck_tokenizer_hash_table_create (size_t bucket_count)
int	ck_tokenizer_hash_table_delete (CKTokenizerHashTable *table, const char *key, bool free_value)
void	ck_tokenizer_hash_table_free (CKTokenizerHashTable *table, bool free_values)
int	ck_tokenizer_hash_table_insert (CKTokenizerHashTable *table, const char *key, void *value)
int	ck_tokenizer_hash_table_iterate (CKTokenizerHashTable *table, CKTokenizerHashCallback callback, void *user_data)
size_t	ck_tokenizer_hash_table_keys (CKTokenizerHashTable *table, const char **out_keys, size_t max_keys)
void *	ck_tokenizer_hash_table_lookup (CKTokenizerHashTable *table, const char *key)
void *	ck_tokenizer_hash_table_lookup_avx (CKTokenizerHashTable *table, const char *key)
static CKTokenizerHashEntry *	create_entry (const char *key, const void *value, size_t value_size)
static void	free_entry (CKTokenizerHashEntry *entry, bool free_value)
static int	simd_strcmp (const char *s1, const char *s2)

Macro Definition Documentation

CK_TOKENIZER_HASH_SEED

#define CK_TOKENIZER_HASH_SEED   0x9747b28c

Definition at line 16 of file hash_table.c.

Function Documentation

ck_tokenizer_hash()

uint32_t ck_tokenizer_hash	(	const char *	key,
		size_t	len
	)

Definition at line 18 of file hash_table.c.

                                                        {
    return ck_murmurhash3(key, (uint32_t)len, CK_TOKENIZER_HASH_SEED);
}

References ck_murmurhash3(), and CK_TOKENIZER_HASH_SEED.

ck_tokenizer_hash_str()

uint32_t ck_tokenizer_hash_str

(

const char *

key

)

Definition at line 22 of file hash_table.c.

                                                {
    return ck_murmurhash3_str(key, CK_TOKENIZER_HASH_SEED);
}

References ck_murmurhash3_str(), and CK_TOKENIZER_HASH_SEED.

Referenced by ck_tokenizer_hash_table_delete(), ck_tokenizer_hash_table_insert(), ck_tokenizer_hash_table_lookup(), and ck_tokenizer_hash_table_lookup_avx().

ck_tokenizer_hash_table_clear()

void ck_tokenizer_hash_table_clear	(	CKTokenizerHashTable *	table,
		bool	free_values
	)

Clear all entries (but keep bucket array).

Parameters

table	Hash table
free_values	If true, free all value pointers

Definition at line 312 of file hash_table.c.

                                                                                  {
    if (!table) {
        return;
    }
 
    for (size_t i = 0; i < table->size; i++) {
        CKTokenizerHashEntry *entry = table->entries[i];
        while (entry) {
            CKTokenizerHashEntry *next = entry->next;
            free_entry(entry, free_values);
            entry = next;
        }
        table->entries[i] = NULL;
    }
 
    table->count = 0;
}

References CKTokenizerHashTable::count, CKTokenizerHashTable::entries, free_entry(), CKTokenizerHashEntry::next, and CKTokenizerHashTable::size.

Referenced by ck_tokenizer_reset().

ck_tokenizer_hash_table_contains()

bool ck_tokenizer_hash_table_contains	(	CKTokenizerHashTable *	table,
		const char *	key
	)

Check if key exists.

Parameters

table	Hash table
key	Key to check

Returns

true if key exists

Definition at line 268 of file hash_table.c.

                                                                                    {
    return ck_tokenizer_hash_table_lookup(table, key) != NULL;
}

References ck_tokenizer_hash_table_lookup().

ck_tokenizer_hash_table_count()

size_t ck_tokenizer_hash_table_count

(

CKTokenizerHashTable *

table

)

Get the number of entries.

Parameters

table

Hash table

Returns

Number of entries

Definition at line 264 of file hash_table.c.

                                                                  {
    return table ? table->count : 0;
}

References CKTokenizerHashTable::count.

ck_tokenizer_hash_table_create()

CKTokenizerHashTable* ck_tokenizer_hash_table_create

(

size_t

bucket_count

)

Create a hash table.

Parameters

bucket_count

Number of buckets (0 = auto-size)

Returns

Newly allocated hash table, or NULL on error

Definition at line 80 of file hash_table.c.

                                                                          {
    if (bucket_count == 0) {
        bucket_count = CK_TOKENIZER_HT_BUCKETS_SMALL;
    }
 
    CKTokenizerHashTable *table = (CKTokenizerHashTable *)malloc(sizeof(CKTokenizerHashTable));
    if (!table) {
        return NULL;
    }
 
    table->entries = (CKTokenizerHashEntry **)calloc(bucket_count, sizeof(CKTokenizerHashEntry *));
    if (!table->entries) {
        free(table);
        return NULL;
    }
 
    table->size = bucket_count;
    table->count = 0;
    table->load_factor = 0.75f;
 
    return table;
}

References CK_TOKENIZER_HT_BUCKETS_SMALL, CKTokenizerHashTable::count, CKTokenizerHashTable::entries, CKTokenizerHashTable::load_factor, and CKTokenizerHashTable::size.

Referenced by ck_tokenizer_create(), and ck_true_bpe_create().

ck_tokenizer_hash_table_delete()

int ck_tokenizer_hash_table_delete	(	CKTokenizerHashTable *	table,
		const char *	key,
		bool	free_value
	)

Delete a key.

Parameters

table	Hash table
key	Key to delete
free_value	If true, free the value pointer

Returns

0 if found and deleted, -1 if not found

Definition at line 235 of file hash_table.c.

                                                    {
    if (!table || !key) {
        return -1;
    }
 
    uint32_t bucket = ck_tokenizer_hash_str(key) % table->size;
    CKTokenizerHashEntry *entry = table->entries[bucket];
    CKTokenizerHashEntry *prev = NULL;
 
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            if (prev) {
                prev->next = entry->next;
            } else {
                table->entries[bucket] = entry->next;
            }
            free_entry(entry, free_value);
            table->count--;
            return 0;
        }
        prev = entry;
        entry = entry->next;
    }
 
    return -1;
}

References ck_tokenizer_hash_str(), CKTokenizerHashTable::count, CKTokenizerHashTable::entries, free_entry(), CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, and CKTokenizerHashTable::size.

ck_tokenizer_hash_table_free()

void ck_tokenizer_hash_table_free	(	CKTokenizerHashTable *	table,
		bool	free_values
	)

Free a hash table.

Parameters

table	Hash table to free
free_values	If true, also free all value pointers

Definition at line 140 of file hash_table.c.

                                                                                 {
    if (!table) {
        return;
    }
 
    for (size_t i = 0; i < table->size; i++) {
        CKTokenizerHashEntry *entry = table->entries[i];
        while (entry) {
            CKTokenizerHashEntry *next = entry->next;
            free_entry(entry, free_values);
            entry = next;
        }
    }
 
    free(table->entries);
    free(table);
}

References CKTokenizerHashTable::entries, free_entry(), CKTokenizerHashEntry::next, and CKTokenizerHashTable::size.

Referenced by ck_tokenizer_create(), ck_tokenizer_free(), ck_true_bpe_create(), and ck_true_bpe_free().

ck_tokenizer_hash_table_insert()

int ck_tokenizer_hash_table_insert	(	CKTokenizerHashTable *	table,
		const char *	key,
		void *	value
	)

Insert a key-value pair.

Parameters

table	Hash table
key	Key string
value	Value pointer

Returns

0 on success, -1 on error

Definition at line 158 of file hash_table.c.

                                                {
    if (!table || !key) {
        return -1;
    }
 
    uint32_t bucket = ck_tokenizer_hash_str(key) % table->size;
    CKTokenizerHashEntry *entry = table->entries[bucket];
 
    /* Check if key already exists */
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            /* Update existing entry - just replace value pointer */
            entry->value = value;
            return 0;
        }
        entry = entry->next;
    }
 
    /* Create new entry with NULL value (caller manages memory) */
    CKTokenizerHashEntry *new_entry = (CKTokenizerHashEntry *)malloc(sizeof(CKTokenizerHashEntry));
    if (!new_entry) {
        return -1;
    }
 
    new_entry->key = strdup(key);
    if (!new_entry->key) {
        free(new_entry);
        return -1;
    }
 
    new_entry->value = value;
    new_entry->next = table->entries[bucket];
    table->entries[bucket] = new_entry;
    table->count++;
 
    return 0;
}

References ck_tokenizer_hash_str(), CKTokenizerHashTable::count, CKTokenizerHashTable::entries, CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, CKTokenizerHashTable::size, and CKTokenizerHashEntry::value.

Referenced by ck_tokenizer_add_token(), and ck_true_bpe_add_token().

ck_tokenizer_hash_table_iterate()

int ck_tokenizer_hash_table_iterate	(	CKTokenizerHashTable *	table,
		CKTokenizerHashCallback	callback,
		void *	user_data
	)

Definition at line 272 of file hash_table.c.

                                                     {
    if (!table || !callback) {
        return -1;
    }
 
    for (size_t i = 0; i < table->size; i++) {
        CKTokenizerHashEntry *entry = table->entries[i];
        while (entry) {
            int ret = callback(entry->key, entry->value, user_data);
            if (ret != 0) {
                return ret;
            }
            entry = entry->next;
        }
    }
 
    return 0;
}

References CKTokenizerHashTable::entries, CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, CKTokenizerHashTable::size, and CKTokenizerHashEntry::value.

ck_tokenizer_hash_table_keys()

size_t ck_tokenizer_hash_table_keys	(	CKTokenizerHashTable *	table,
		const char **	out_keys,
		size_t	max_keys
	)

Get all keys as an array.

Parameters

table	Hash table
out_keys	Output array for keys (must be pre-allocated)
max_keys	Maximum keys to write

Returns

Number of keys written

Definition at line 293 of file hash_table.c.

                                                     {
    if (!table || !out_keys) {
        return 0;
    }
 
    size_t written = 0;
    for (size_t i = 0; i < table->size && written < max_keys; i++) {
        CKTokenizerHashEntry *entry = table->entries[i];
        while (entry && written < max_keys) {
            out_keys[written++] = entry->key;
            entry = entry->next;
        }
    }
 
    return written;
}

References CKTokenizerHashTable::entries, CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, and CKTokenizerHashTable::size.

ck_tokenizer_hash_table_lookup()

void* ck_tokenizer_hash_table_lookup	(	CKTokenizerHashTable *	table,
		const char *	key
	)

Look up a key.

Parameters

table	Hash table
key	Key to look up

Returns

Value pointer, or NULL if not found

Definition at line 198 of file hash_table.c.

                                                                                   {
    if (!table || !key) {
        return NULL;
    }
 
    uint32_t bucket = ck_tokenizer_hash_str(key) % table->size;
    CKTokenizerHashEntry *entry = table->entries[bucket];
 
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
 
    return NULL;
}

References ck_tokenizer_hash_str(), CKTokenizerHashTable::entries, CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, CKTokenizerHashTable::size, and CKTokenizerHashEntry::value.

Referenced by ck_tokenizer_add_special_token(), ck_tokenizer_add_token(), ck_tokenizer_hash_table_contains(), ck_tokenizer_lookup(), ck_tokenizer_lookup_exact(), ck_true_bpe_add_merge_by_tokens(), ck_true_bpe_add_token(), ck_true_bpe_lookup(), find_longest_match_hash(), spm_count_unknown_run(), and spm_find_candidates_at_pos().

ck_tokenizer_hash_table_lookup_avx()

void* ck_tokenizer_hash_table_lookup_avx	(	CKTokenizerHashTable *	table,
		const char *	key
	)

Definition at line 217 of file hash_table.c.

                                                                                       {
    if (!table || !key) {
        return NULL;
    }
 
    uint32_t bucket = ck_tokenizer_hash_str(key) % table->size;
    CKTokenizerHashEntry *entry = table->entries[bucket];
 
    while (entry) {
        if (simd_strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
 
    return NULL;
}

References ck_tokenizer_hash_str(), CKTokenizerHashTable::entries, CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, simd_strcmp(), CKTokenizerHashTable::size, and CKTokenizerHashEntry::value.

create_entry()

static CKTokenizerHashEntry* create_entry ( const char *  key, const void *  value, size_t  value_size  )

static

Definition at line 103 of file hash_table.c.

                                                                                                 {
    CKTokenizerHashEntry *entry = (CKTokenizerHashEntry *)malloc(sizeof(CKTokenizerHashEntry));
    if (!entry) {
        return NULL;
    }
 
    entry->key = strdup(key);
    if (!entry->key) {
        free(entry);
        return NULL;
    }
 
    if (value) {
        entry->value = malloc(value_size);
        if (!entry->value) {
            free(entry->key);
            free(entry);
            return NULL;
        }
        memcpy(entry->value, value, value_size);
    } else {
        entry->value = NULL;
    }
 
    entry->next = NULL;
    return entry;
}

References CKTokenizerHashEntry::key, CKTokenizerHashEntry::next, and CKTokenizerHashEntry::value.

free_entry()

static void free_entry ( CKTokenizerHashEntry *  entry, bool  free_value  )

static

Definition at line 131 of file hash_table.c.

                                                                     {
    if (!entry) return;
    free(entry->key);
    if (free_value && entry->value) {
        free(entry->value);
    }
    free(entry);
}

References CKTokenizerHashEntry::key, and CKTokenizerHashEntry::value.

Referenced by ck_tokenizer_hash_table_clear(), ck_tokenizer_hash_table_delete(), and ck_tokenizer_hash_table_free().

simd_strcmp()

static int simd_strcmp ( const char *  s1, const char *  s2  )

inlinestatic

Definition at line 28 of file hash_table.c.

                                                              {
    size_t len1 = strlen(s1);
    size_t len2 = strlen(s2);
 
    /* Fallback to regular strcmp for short strings */
    if (len1 < 64 || len2 < 64) {
        return strcmp(s1, s2);
    }
 
#if defined(__AVX512F__) && defined(__AVX512BW__) && defined(__AVX512DQ__)
    /* AVX-512 path */
    while (1) {
        /* Load 64 bytes from each string into AVX-512 registers */
        __m512i chunk1 = _mm512_loadu_si512((const __m512i *)s1);
        __m512i chunk2 = _mm512_loadu_si512((const __m512i *)s2);
 
        /* Compare the chunks byte by byte */
        __mmask64 cmp_mask = _mm512_cmpeq_epu8_mask(chunk1, chunk2);
 
        /* Check if all bytes are equal */
        if (cmp_mask != 0xFFFFFFFFFFFFFFFF) {
            /* Find the first differing byte */
            int first_diff = __builtin_ctzll(~cmp_mask);
            return (unsigned char)s1[first_diff] - (unsigned char)s2[first_diff];
        }
 
        /* Check if we hit a null character in s1 or s2 */
        __mmask64 null_mask1 = _mm512_test_epi8_mask(chunk1, _mm512_set1_epi8('\0'));
        __mmask64 null_mask2 = _mm512_test_epi8_mask(chunk2, _mm512_set1_epi8('\0'));
 
        if (null_mask1 || null_mask2) {
            if (len1 == len2) {
                return 0;
            } else {
                return (len1 < len2) ? -1 : 1;
            }
        }
 
        /* Advance the pointers by 64 bytes for the next iteration */
        s1 += 64;
        s2 += 64;
    }
#else
    /* SSE/AVX fallback - just use regular strcmp for simplicity */
    (void)s1;
    (void)s2;
    (void)len1;
    (void)len2;
    return strcmp(s1, s2);
#endif
}

Referenced by ck_tokenizer_hash_table_lookup_avx().