Changeset 0b7bcb8 in mainline

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.

Location:

kernel

Files:

• generic/include/adt/cht.h (modified) (2 diffs)
• generic/src/adt/cht.c (modified) (8 diffs)
• test/cht/cht1.c (modified) (2 diffs)

kernel/generic/include/adt/cht.h

@@ -75 +75 @@
         cht_buckets_t *new_b;
 
+        size_t max_load;
         work_t resize_work;
         atomic_t resize_reqs;
@@ -88 +89 @@
 #define cht_read_unlock()   rcu_read_unlock()
 
-extern bool cht_create(cht_t *h, size_t init_size, size_t min_size, cht_ops_t *op);
+extern bool cht_create(cht_t *h, size_t init_size, size_t min_size, 
+        size_t max_load, cht_ops_t *op);
 extern void cht_destroy(cht_t *h);
 

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) {

kernel/test/cht/cht1.c

@@ -235 +235 @@
 {
         cht_t h;
-        if (!cht_create(&h, 5, 0, &val_ops))
+        if (!cht_create(&h, 5, 0, 0, &val_ops))
                 return "Could not create the table.";
         
@@ -445 +445 @@
         cht_t h;
         
-        if (!cht_create(&h, 0, 0, &stress_ops)) {
+        if (!cht_create(&h, 0, 0, 0, &stress_ops)) {
                 TPRINTF("Failed to create the table\n");
                 return false;