Macros
#define	LOAD_FACTOR 1

#define	S_ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))

#define	BUCKET_FOREACH(ht, bt, j, kv)

#define	BUCKET_FOREACH_SAFE(ht, bt, j, count, kv)

Functions
static ut32	hashfn (HtName_(Ht) *ht, const KEY_TYPE k)

static ut32	bucketfn (HtName_(Ht) *ht, const KEY_TYPE k)

static KEY_TYPE	dupkey (HtName_(Ht) *ht, const KEY_TYPE k)

static VALUE_TYPE	dupval (HtName_(Ht) *ht, const VALUE_TYPE v)

static ut32	calcsize_key (HtName_(Ht) *ht, const KEY_TYPE k)

static ut32	calcsize_val (HtName_(Ht) *ht, const VALUE_TYPE v)

static void	freefn (HtName_(Ht) ht, HT_(Kv) kv)

static ut32	next_idx (ut32 idx)

static ut32	compute_size (ut32 idx, ut32 sz)

static bool	is_kv_equal (HtName_(Ht) ht, const KEY_TYPE key, const ut32 key_len, const HT_(Kv) kv)

static	HT_ (Kv)

static	HtName_ (Ht)

RZ_API void Ht_()	free (HtName_(Ht) *ht)

static void	internal_ht_grow (HtName_(Ht) *ht)

static void	check_growing (HtName_(Ht) *ht)

RZ_API bool Ht_()	insert_kv (HtName_(Ht) ht, HT_(Kv) kv, bool update)

static bool	insert_update (HtName_(Ht) *ht, const KEY_TYPE key, VALUE_TYPE value, bool update)

RZ_API bool Ht_()	insert (HtName_(Ht) *ht, const KEY_TYPE key, VALUE_TYPE value)

RZ_API bool Ht_()	update (HtName_(Ht) *ht, const KEY_TYPE key, VALUE_TYPE value)

RZ_API bool Ht_()	update_key (HtName_(Ht) *ht, const KEY_TYPE old_key, const KEY_TYPE new_key)

RZ_API VALUE_TYPE Ht_()	find (HtName_(Ht) ht, const KEY_TYPE key, bool found)

RZ_API bool Ht_()	delete (HtName_(Ht) *ht, const KEY_TYPE key)

RZ_API void Ht_()	foreach (HtName_(Ht) ht, HT_(ForeachCallback) cb, void user)

Variables
static const ut32	ht_primes_sizes []

Macro Definition Documentation

◆ BUCKET_FOREACH

#define BUCKET_FOREACH	(	ht,
		bt,
		j,
		kv
	)

Value:

if ((bt)->arr) \

for ((j) = 0, (kv) = (bt)->arr; (j) < (bt)->count; (j)++, (kv) = next_kv(ht, kv))

syscall_preprocessing.arr

arr

Definition: syscall_preprocessing.py:15

next_kv

static SdbKv * next_kv(HtPP *ht, SdbKv *kv)

Definition: sdb.c:13

Definition at line 85 of file ht_inc.c.

◆ BUCKET_FOREACH_SAFE

#define BUCKET_FOREACH_SAFE	(	ht,
		bt,
		j,
		count,
		kv
	)

Value:

    if ((bt)->arr) \
        for ((j) = 0, (kv) = (bt)->arr, (count) = (ht)->count; \
            (j) < (bt)->count; \
            (j) = (count) == (ht)->count ? j + 1 : j, (kv) = (count) == (ht)->count ? next_kv(ht, kv) : kv, (count) = (ht)->count)

Definition at line 89 of file ht_inc.c.

◆ LOAD_FACTOR

#define LOAD_FACTOR 1

Definition at line 6 of file ht_inc.c.

◆ S_ARRAY_SIZE

#define S_ARRAY_SIZE ( x ) (sizeof(x) / sizeof(x[0]))

Definition at line 7 of file ht_inc.c.

Function Documentation

◆ bucketfn()

static ut32 bucketfn	(	HtName_(Ht) *	ht,
		const KEY_TYPE	k
	)

inlinestatic

Definition at line 26 of file ht_inc.c.

                                                                 {
     return hashfn(ht, k) % ht->size;
 }

References hashfn(), and k.

Referenced by delete(), and update_key().

◆ calcsize_key()

static ut32 calcsize_key	(	HtName_(Ht) *	ht,
		const KEY_TYPE	k
	)

inlinestatic

Definition at line 38 of file ht_inc.c.

                                                                     {
     return ht->opt.calcsizeK ? ht->opt.calcsizeK(k) : 0;
 }

References k.

Referenced by delete(), insert_update(), and update_key().

◆ calcsize_val()

static ut32 calcsize_val	(	HtName_(Ht) *	ht,
		const VALUE_TYPE	v
	)

inlinestatic

Definition at line 42 of file ht_inc.c.

                                                                       {
     return ht->opt.calcsizeV ? ht->opt.calcsizeV(v) : 0;
 }

References v.

Referenced by insert_update().

◆ check_growing()

static void check_growing ( HtName_(Ht) * ht )

static

Definition at line 186 of file ht_inc.c.

                                             {
     if (ht->count >= LOAD_FACTOR * ht->size) {
         internal_ht_grow(ht);
     }
 }

References internal_ht_grow(), and LOAD_FACTOR.

Referenced by insert_kv(), and insert_update().

◆ compute_size()

static ut32 compute_size	(	ut32	idx,
		ut32	sz
	)

inlinestatic

Definition at line 59 of file ht_inc.c.

                                                    {
     // when possible, use the precomputed prime numbers which help with
     // collisions, otherwise, at least make the number odd with |1
     return idx != UT32_MAX && idx < S_ARRAY_SIZE(ht_primes_sizes) ? ht_primes_sizes[idx] : (sz | 1);
 }

References ht_primes_sizes, setup::idx, S_ARRAY_SIZE, and UT32_MAX.

Referenced by internal_ht_grow().

◆ delete()

RZ_API bool Ht_() delete	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key
	)

Definition at line 336 of file ht_inc.c.

                                                               {
     HT_(Bucket) *bt = &ht->table[bucketfn(ht, key)];
     ut32 key_len = calcsize_key(ht, key);
     HT_(Kv) * kv;
     ut32 j;
  
     BUCKET_FOREACH(ht, bt, j, kv) {
         if (is_kv_equal(ht, key, key_len, kv)) {
             freefn(ht, kv);
             void *src = next_kv(ht, kv);
             memmove(kv, src, (bt->count - j - 1) * ht->opt.elem_size);
             bt->count--;
             ht->count--;
             return true;
         }
     }
     return false;
 }

References BUCKET_FOREACH, bucketfn(), calcsize_key(), freefn(), HT_(), is_kv_equal(), key, next_kv(), and src.

◆ dupkey()

static KEY_TYPE dupkey	(	HtName_(Ht) *	ht,
		const KEY_TYPE	k
	)

inlinestatic

Definition at line 30 of file ht_inc.c.

                                                                   {
     return ht->opt.dupkey ? ht->opt.dupkey(k) : (KEY_TYPE)k;
 }

References k, and KEY_TYPE.

Referenced by HtName_(), and insert_update().

◆ dupval()

static VALUE_TYPE dupval	(	HtName_(Ht) *	ht,
		const VALUE_TYPE	v
	)

inlinestatic

Definition at line 34 of file ht_inc.c.

                                                                       {
     return ht->opt.dupvalue ? ht->opt.dupvalue(v) : (VALUE_TYPE)v;
 }

References v, and VALUE_TYPE.

Referenced by insert_update().

◆ find()

RZ_API VALUE_TYPE Ht_() find	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key,
		bool *	found
	)

Definition at line 330 of file ht_inc.c.

                                                                                {
     HT_(Kv) *res = Ht_(find_kv)(ht, key, found);
     return res ? res->value : HT_NULL_VALUE;
 }

References found, HT_(), Ht_, HT_NULL_VALUE, and key.

Referenced by rz_str_nstr(), and update_key().

◆ foreach()

RZ_API void Ht_() foreach	(	HtName_(Ht) *	ht,
		HT_(ForeachCallback)	cb,
		void *	user
	)

Definition at line 355 of file ht_inc.c.

                                                                                 {
     ut32 i;
  
     for (i = 0; i < ht->size; ++i) {
         HT_(Bucket) *bt = &ht->table[i];
         HT_(Kv) * kv;
         ut32 j, count;
  
         BUCKET_FOREACH_SAFE(ht, bt, j, count, kv) {
             if (!cb(user, kv->key, kv->value)) {
                 return;
             }
         }
     }
 }

References BUCKET_FOREACH_SAFE, cb, count, HT_(), and i.

◆ free()

RZ_API void Ht_() free ( HtName_(Ht) * ht )

Definition at line 130 of file ht_inc.c.

                                         {
     if (!ht) {
         return;
     }
  
     ut32 i;
     for (i = 0; i < ht->size; i++) {
         HT_(Bucket) *bt = &ht->table[i];
         HT_(Kv) * kv;
         ut32 j;
  
         if (ht->opt.freefn) {
             BUCKET_FOREACH(ht, bt, j, kv) {
                 ht->opt.freefn(kv);
             }
         }
  
         free(bt->arr);
     }
     free(ht->table);
     free(ht);
 }

References BUCKET_FOREACH, HT_(), and i.

◆ freefn()

static void freefn	(	HtName_(Ht) *	ht,
		HT_(Kv) *	kv
	)

inlinestatic

Definition at line 46 of file ht_inc.c.

                                                           {
     if (ht->opt.freefn) {
         ht->opt.freefn(kv);
     }
 }

Referenced by delete(), HtName_(), ls_newf(), rz_rbtree_aug_delete(), rz_rbtree_delete(), rz_rbtree_free(), rz_skiplist_new(), rz_type_db_edit_base_type(), and update_key().

◆ hashfn()

static ut32 hashfn	(	HtName_(Ht) *	ht,
		const KEY_TYPE	k
	)

inlinestatic

Definition at line 22 of file ht_inc.c.

                                                               {
     return ht->opt.hashfn ? ht->opt.hashfn(k) : KEY_TO_HASH(k);
 }

References k, and KEY_TO_HASH.

Referenced by bucketfn(), and HtName_().

◆ HT_()

static HT_ ( Kv )

inlinestatic

Definition at line 77 of file ht_inc.c.

                                                                           {
     return (HT_(Kv) *)((char *)bt->arr + i * ht->opt.elem_size);
 }

References i.

Referenced by delete(), find(), foreach(), free(), HtName_(), insert_kv(), insert_update(), internal_ht_grow(), and update_key().

◆ HtName_()

RZ_API HtName_ ( Ht )

static

Definition at line 104 of file ht_inc.c.

                                                                                     {
     HtName_(Ht) *ht = calloc(1, sizeof(*ht));
     if (!ht) {
         return NULL;
     }
     ht->size = size;
     ht->count = 0;
     ht->prime_idx = prime_idx;
     ht->table = calloc(ht->size, sizeof(*ht->table));
     if (!ht->table) {
         free(ht);
         return NULL;
     }
     ht->opt = *opt;
     // if not provided, assume we are dealing with a regular HtName_(Ht), with
     // HT_(Kv) as elements
     if (ht->opt.elem_size == 0) {
         ht->opt.elem_size = sizeof(HT_(Kv));
     }
     return ht;
 }

References calloc(), free(), HT_(), and NULL.

Referenced by internal_ht_grow().

◆ insert()

RZ_API bool Ht_() insert	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key,
		VALUE_TYPE	value
	)

Definition at line 246 of file ht_inc.c.

                                                                                 {
     return insert_update(ht, key, value, false);
 }

References insert_update(), key, and value.

◆ insert_kv()

RZ_API bool Ht_() insert_kv	(	HtName_(Ht) *	ht,
		HT_(Kv) *	kv,
		bool	update
	)

Definition at line 218 of file ht_inc.c.

                                                                         {
     HT_(Kv) *kv_dst = reserve_kv(ht, kv->key, kv->key_len, update);
     if (!kv_dst) {
         return false;
     }
  
     memcpy(kv_dst, kv, ht->opt.elem_size);
     check_growing(ht);
     return true;
 }

References check_growing(), HT_(), memcpy(), and update().

Referenced by internal_ht_grow().

◆ insert_update()

static bool insert_update	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key,
		VALUE_TYPE	value,
		bool	update
	)

static

Definition at line 229 of file ht_inc.c.

                                                                                                {
     ut32 key_len = calcsize_key(ht, key);
     HT_(Kv) *kv_dst = reserve_kv(ht, key, key_len, update);
     if (!kv_dst) {
         return false;
     }
  
     kv_dst->key = dupkey(ht, key);
     kv_dst->key_len = key_len;
     kv_dst->value = dupval(ht, value);
     kv_dst->value_len = calcsize_val(ht, value);
     check_growing(ht);
     return true;
 }

References calcsize_key(), calcsize_val(), check_growing(), dupkey(), dupval(), HT_(), key, update(), and value.

Referenced by insert(), update(), and update_key().

◆ internal_ht_grow()

static void internal_ht_grow ( HtName_(Ht) * ht )

static

Definition at line 154 of file ht_inc.c.

                                                {
     HtName_(Ht) * ht2;
     HtName_(Ht) swap;
     ut32 idx = next_idx(ht->prime_idx);
     ut32 sz = compute_size(idx, ht->size * 2);
     ut32 i;
  
     ht2 = internal_ht_new(sz, idx, &ht->opt);
     if (!ht2) {
         // we can't grow the ht anymore. Never mind, we'll be slower,
         // but everything can continue to work
         return;
     }
  
     for (i = 0; i < ht->size; i++) {
         HT_(Bucket) *bt = &ht->table[i];
         HT_(Kv) * kv;
         ut32 j;
  
         BUCKET_FOREACH(ht, bt, j, kv) {
             Ht_(insert_kv)(ht2, kv, false);
         }
     }
     // And now swap the internals.
     swap = *ht;
     *ht = *ht2;
     *ht2 = swap;
  
     ht2->opt.freefn = NULL;
     Ht_(free)(ht2);
 }

References BUCKET_FOREACH, compute_size(), free(), HT_(), Ht_, HtName_(), i, setup::idx, insert_kv(), next_idx(), NULL, and swap.

Referenced by check_growing().

◆ is_kv_equal()

static bool is_kv_equal	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key,
		const ut32	key_len,
		const HT_(Kv) *	kv
	)

inlinestatic

Definition at line 65 of file ht_inc.c.

                                                                                                              {
     if (key_len != kv->key_len) {
         return false;
     }
  
     bool res = key == kv->key;
     if (!res && ht->opt.cmp) {
         res = !ht->opt.cmp(key, kv->key);
     }
     return res;
 }

References key.

Referenced by delete(), and update_key().

◆ next_idx()

static ut32 next_idx ( ut32 idx )

inlinestatic

Definition at line 52 of file ht_inc.c.

                                       {
     if (idx != UT32_MAX && idx < S_ARRAY_SIZE(ht_primes_sizes) - 1) {
         return idx + 1;
     }
     return UT32_MAX;
 }

References ht_primes_sizes, setup::idx, S_ARRAY_SIZE, and UT32_MAX.

Referenced by internal_ht_grow(), and rz_bin_le_get_sections().

◆ update()

RZ_API bool Ht_() update	(	HtName_(Ht) *	ht,
		const KEY_TYPE	key,
		VALUE_TYPE	value
	)

Definition at line 252 of file ht_inc.c.

                                                                                 {
     return insert_update(ht, key, value, true);
 }

References insert_update(), key, and value.

Referenced by insert_kv(), and insert_update().

◆ update_key()

RZ_API bool Ht_() update_key	(	HtName_(Ht) *	ht,
		const KEY_TYPE	old_key,
		const KEY_TYPE	new_key
	)

Definition at line 257 of file ht_inc.c.

                                                                                               {
     // First look for the value associated with old_key
     bool found;
     VALUE_TYPE value = Ht_(find)(ht, old_key, &found);
     if (!found) {
         return false;
     }
  
     // Associate the existing value with new_key
     bool inserted = insert_update(ht, new_key, value, false);
     if (!inserted) {
         return false;
     }
  
     // Remove the old_key kv, paying attention to not double free the value
     HT_(Bucket) *bt = &ht->table[bucketfn(ht, old_key)];
     const int old_key_len = calcsize_key(ht, old_key);
     HT_(Kv) * kv;
     ut32 j;
  
     BUCKET_FOREACH(ht, bt, j, kv) {
         if (is_kv_equal(ht, old_key, old_key_len, kv)) {
             if (!ht->opt.dupvalue) {
                 // do not free the value part if dupvalue is not
                 // set, because the old value has been
                 // associated with the new key and it should not
                 // be freed
                 kv->value = HT_NULL_VALUE;
                 kv->value_len = 0;
             }
             freefn(ht, kv);
  
             void *src = next_kv(ht, kv);
             memmove(kv, src, (bt->count - j - 1) * ht->opt.elem_size);
             bt->count--;
             ht->count--;
             return true;
         }
     }
  
     return false;
 }

References BUCKET_FOREACH, bucketfn(), calcsize_key(), find(), found, freefn(), HT_(), Ht_, HT_NULL_VALUE, insert_update(), is_kv_equal(), next_kv(), src, value, and VALUE_TYPE.

Variable Documentation

◆ ht_primes_sizes

const ut32 ht_primes_sizes[]

static

Initial value:

= {
    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131,
    163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861,
    5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023,
    25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523,
    108631, 130363, 156437, 187751, 225307, 270371, 324449,
    389357, 467237, 560689, 672827, 807403, 968897, 1162687,
    1395263, 1674319, 2009191, 2411033, 2893249, 3471899,
    4166287, 4999559, 5999471, 7199369
}

Definition at line 10 of file ht_inc.c.

Referenced by compute_size(), HtName_(), and next_idx().

Macros

Functions

Variables

Macro Definition Documentation

◆ BUCKET_FOREACH

◆ BUCKET_FOREACH_SAFE

◆ LOAD_FACTOR

◆ S_ARRAY_SIZE

Function Documentation

◆ bucketfn()

◆ calcsize_key()

◆ calcsize_val()

◆ check_growing()

◆ compute_size()

◆ delete()

◆ dupkey()

◆ dupval()

◆ find()

◆ foreach()

◆ free()

◆ freefn()

◆ hashfn()

◆ HT_()

◆ HtName_()

◆ insert()

◆ insert_kv()

◆ insert_update()

◆ internal_ht_grow()

◆ is_kv_equal()

◆ next_idx()

◆ update()

◆ update_key()

Variable Documentation

◆ ht_primes_sizes