Changeset 0b7bcb8 in mainline for kernel/generic/src/adt/cht.c

Timestamp:

2012-08-03T16:08:39Z (12 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

5e5cef3

Parents:

fbe17545

Message:

cht: Slightly changed CHT interface. It now allows to specify the maximum desired load of the table before it resizes.

File:

• kernel/generic/src/adt/cht.c (modified) (8 diffs)

kernel/generic/src/adt/cht.c

@@ -49 +49 @@
 
 
-/* Logarithm of the min bucket count. 2^6 == 64 buckets. */
+/* Logarithm of the min bucket count. Must be at least 3. 2^6 == 64 buckets. */
 #define CHT_MIN_ORDER 6
 /* Logarithm of the max bucket count. */
@@ -55 +55 @@
 /* Minimum number of hash table buckets. */
 #define CHT_MIN_BUCKET_CNT (1 << CHT_MIN_ORDER)
-/* Must be a power of 2. */
+/* Does not have to be a power of 2. */
 #define CHT_MAX_LOAD 2 
 
@@ -83 +83 @@
 } wnd_t;
 
-/* Fwd decl. */
+
 static size_t size_to_order(size_t bucket_cnt, size_t min_order);
 static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid);
@@ -153 +153 @@
 
 
-bool cht_create(cht_t *h, size_t init_size, size_t min_size, cht_ops_t *op)
+bool cht_create(cht_t *h, size_t init_size, size_t min_size, size_t max_load, 
+        cht_ops_t *op)
 {
         ASSERT(h);
@@ -170 +171 @@
                 return false;
         
+        h->max_load = (max_load == 0) ? CHT_MAX_LOAD : max_load;
         h->min_order = min_order;
         h->new_b = 0;
@@ -1360 +1362 @@
         size_t bucket_cnt = (1 << h->b->order);
         
-        bool need_shrink = (items == CHT_MAX_LOAD * bucket_cnt / 4);
-        bool missed_shrink = (items == CHT_MAX_LOAD * bucket_cnt / 8);
+        bool need_shrink = (items == h->max_load * bucket_cnt / 4);
+        bool missed_shrink = (items == h->max_load * bucket_cnt / 8);
         
         if ((need_shrink || missed_shrink) && h->b->order > h->min_order) {
@@ -1377 +1379 @@
         size_t bucket_cnt = (1 << h->b->order);
         
-        bool need_grow = (items == CHT_MAX_LOAD * bucket_cnt);
-        bool missed_grow = (items == 2 * CHT_MAX_LOAD * bucket_cnt);
+        bool need_grow = (items == h->max_load * bucket_cnt);
+        bool missed_grow = (items == 2 * h->max_load * bucket_cnt);
         
         if ((need_grow || missed_grow) && h->b->order < CHT_MAX_ORDER) {
@@ -1406 +1408 @@
                 size_t cur_items = (size_t) atomic_get(&h->item_cnt);
                 size_t bucket_cnt = (1 << h->b->order);
-                size_t max_items = CHT_MAX_LOAD * bucket_cnt;
+                size_t max_items = h->max_load * bucket_cnt;
 
                 if (cur_items >= max_items && h->b->order < CHT_MAX_ORDER) {