Requiring some sort of kh_xxx() setup function in order to have and use read-only hashtables of fixed size

[rcarbone]

I have a static (maybe strange) requirement for khash. Let me explain.

I keep in a static table an array of structured items, say [rock_t], of fixed and well-known size [ROCK_SIZE]. Each item in the table has an unique string key and other useful information for my applications. This table is generated automatically by another program and is alphabetically sorted by keys.

For performance reasons due the high volume of queries for keys I would avoid linear search in this table in favour of hash-lookups. What I made was to map the static table to a klib-based hashtable by putting all [rock_t] items from the static alphabetically ordered table in a new allocated khash table. The khash table have [keys] of type [char ] and [vals] of type [rock_t ]. All went fine (see attached rock-dynamic.c C source file). It produces the following output: rocco@nuc.carbo.net 833> ./rock-dynamic The mapping process succeeded!!! Both tables have the same size of [6] items Checking now all keys ... key [AAA] ... Ok! key [BBB] ... Ok! key [CCC] ... Ok! key [DDD] ... Ok! key [EEE] ... Ok! key [FFF] ... Ok!

These days, in order to avoid any sort of dynamic memory allocation/deallocation that should be performed at initialization/termination time, I tried to perform same mapping operations using a fixed-size klib-based hashtable.

In details I defined a variable of the given type, instead of getting a pointer by kh_init(), and I tried to initialise it to some reasonable (unsupported ???) values.

At the time any attempt still does not work (see attached file rock-static.c) that produces the following output: rocco@nuc.carbo.net 834> ./rock-static The mapping process failed!!! Source static table size [6] Destination hashtable size [4]

n_buckets = 6 size = 6 n_occupied = 4 upper_bound = 6 flags = 0xaaaaa0a0

I suspect the problem is related to the correct definition (in terms of size) and initialisation of the [flags] field of the hashtable.

There is any hope to have it a function in khash that does it correctly for me? Something like: extern int khsetup##name(kh_##name##_t *h, khint_t fixed_size);

Thanks /rocco

rock-dynamic.c.gz rock-static.c.gz

[attractivechaos]

n_bucket has to be power-of-2. It can't be 6. Just use kh_resize().