julstrat / strmap

Simple alternative to hcreate_r, hsearch_r, hdestroy_r GNU extensions

strmap

strmap - simple alternative to hcreate_r, hdestroy_r, hsearch_r GNU extensions.

Implementation

• Open addressing with linear probing for collision resolution.
• Auto grow feature.
• Back shift key deletion algorithm.
• STRMAP *sm_create_from() - creates new strmap from existing.
• foreach read-only keys iterator.
• Probes mean, variance statistics.
• String polynomial hash function

hash(sn) = s[0]*257n-1 + s[1]*257n-2 + s[2]*257n-3 + ... + s[n-1]*2570

Benchmark

• robin_hood: strmap vs robin-hood-hashing. ASCII letters and digits permutations - 8000000 keys.

Load factor: 0.7
Mean: 1.16595
Variance: 9.43266

• words: English words - 466550 keys.

Load factor: 0.7
Mean: 1.32653
Variance: 14.8107

• bench: ASCII letters and digits permutations - 3700000 keys.

Load factor: 0.7
Mean: 1.26022
Variance: 11.3293

API

    STRMAP *sm_create(size_t size);

Create a string map which can contain at least size elements.

---

    STRMAP *sm_create_from(const STRMAP * sm, size_t size);

Create strmap from existing.

---

    SM_RESULT sm_lookup(const STRMAP * sm, const char *key,
                        SM_ENTRY * item);

Retrieves user associated data for given key.

---

    SM_RESULT sm_insert(STRMAP * sm, const char *key, const void *data,
                        SM_ENTRY * item);

Insert key and user data.

---

    SM_RESULT sm_update(STRMAP * sm, const char *key, const void *data,
                        SM_ENTRY * item);

Update user data for given key.

---

    SM_RESULT sm_upsert(STRMAP * sm, const char *key, const void *data,
                        SM_ENTRY * item);

Update user data for given key or insert if key not exists.

---

    SM_RESULT sm_remove(STRMAP * sm, const char *key, SM_ENTRY * item);

Remove key

Based on M. A. Kolosovskiy, "Simple implementation of deletion from open-address hash table".

---

    void sm_foreach(const STRMAP * sm, void (*action) (SM_ENTRY item, void *ctx), void *ctx);

For each callback.

---

    void sm_clear(STRMAP * sm);

Remove all keys.

---

    size_t sm_size(const STRMAP * sm);

Return number of keys.

---

    double sm_probes_mean(const STRMAP * sm);
    double sm_probes_var(const STRMAP * sm);

Probes mean, variance.

---

    double sm_load_factor(const STRMAP * sm);

Load factor.

---

    void sm_free(STRMAP * sm);

Remove all keys and free memory allocated for the map structure.

---

    size_t poly_hashs(const char *key);

String hash.