Skip to content

Latest commit

 

History

History
120 lines (104 loc) · 3.21 KB

README.md

File metadata and controls

120 lines (104 loc) · 3.21 KB

C/C++ CI Build status GitHub license

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

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.