hash_table.h File Reference

#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

Go to the source code of this file.

Data Structures
struct	CKTokenizerHashEntry
struct	CKTokenizerHashTable

Macros
#define	CK_TOKENIZER_HT_BUCKETS_LARGE   65536
#define	CK_TOKENIZER_HT_BUCKETS_MEDIUM   8192
#define	CK_TOKENIZER_HT_BUCKETS_SMALL   1024
#define	CK_TOKENIZER_HT_BUCKETS_XL   262144

Typedefs
typedef int(*	CKTokenizerHashCallback) (const char *key, void *value, void *user_data)

Functions
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)

Macro Definition Documentation

CK_TOKENIZER_HT_BUCKETS_LARGE

#define CK_TOKENIZER_HT_BUCKETS_LARGE   65536

Definition at line 142 of file hash_table.h.

CK_TOKENIZER_HT_BUCKETS_MEDIUM

#define CK_TOKENIZER_HT_BUCKETS_MEDIUM   8192

Definition at line 141 of file hash_table.h.

CK_TOKENIZER_HT_BUCKETS_SMALL

#define CK_TOKENIZER_HT_BUCKETS_SMALL   1024

Definition at line 140 of file hash_table.h.

CK_TOKENIZER_HT_BUCKETS_XL

#define CK_TOKENIZER_HT_BUCKETS_XL   262144

Definition at line 143 of file hash_table.h.

Typedef Documentation

CKTokenizerHashCallback

typedef int(* CKTokenizerHashCallback) (const char *key, void *value, void *user_data)

Iterate over all entries.

Parameters

table	Hash table
callback	Function to call for each entry
user_data	User-provided data for callback

Returns

0 if all entries processed, non-zero to stop

Definition at line 112 of file hash_table.h.

Function Documentation

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 316 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 272 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 268 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 84 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 239 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 144 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 162 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 276 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 297 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 202 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(), find_longest_match_hash(), lookup_token_exact(), spm_count_unknown_run(), spm_find_candidates_at_pos(), and spm_find_special_token_at_pos().