Changeset 82cbf8c6 in mainline for kernel/generic/src/lib/ra.c

Timestamp:

2017-10-08T19:37:24Z (7 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

2fd26bb

Parents:

81b9d3e

Message:

Replace the old hash table implementation in the kernel with the newer one

This replaces the original hash table implementation with the resizable one
already used in uspace. Along the way, the IRQ hash table code was streamlined
and cleaned up.

File:

• kernel/generic/src/lib/ra.c (modified) (15 diffs)

kernel/generic/src/lib/ra.c

@@ -50 +50 @@
 #include <panic.h>
 #include <adt/list.h>
+#include <adt/hash.h>
 #include <adt/hash_table.h>
 #include <align.h>
@@ -57 +58 @@
 static slab_cache_t *ra_segment_cache;
 
-#define USED_BUCKETS    1024
-
-static size_t used_hash(sysarg_t *key)
-{
-        return ((*key >> 2) & (USED_BUCKETS - 1));
-}
-
-static bool used_compare(sysarg_t *key, size_t keys, link_t *item)
-{
-        ra_segment_t *seg;
-
-        seg = hash_table_get_instance(item, ra_segment_t, fu_link);
-        return seg->base == *key;
-}
-
-static hash_table_operations_t used_ops = {
+/** Return the hash of the key stored in the item */
+static size_t used_hash(const ht_link_t *item)
+{
+        ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
+        return hash_mix(seg->base);
+}
+
+/** Return the hash of the key */
+static size_t used_key_hash(void *key)
+{
+        uintptr_t *base = (uintptr_t *) key;
+        return hash_mix(*base);
+}
+
+/** Return true if the key is equal to the item's lookup key */
+static bool used_key_equal(void *key, const ht_link_t *item)
+{
+        uintptr_t *base = (sysarg_t *) key;
+        ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
+        return seg->base == *base;
+}
+
+static hash_table_ops_t used_ops = {
         .hash = used_hash,
-        .compare = used_compare,
-        .remove_callback = NULL,
+        .key_hash = used_key_hash,
+        .key_equal = used_key_equal
 };
 
@@ -97 +105 @@
 
         link_initialize(&seg->segment_link);
-        link_initialize(&seg->fu_link);
+        link_initialize(&seg->fl_link);
 
         seg->base = base;
@@ -160 +168 @@
         list_initialize(&span->segments);
 
-        hash_table_create(&span->used, USED_BUCKETS, 1, &used_ops);
+        hash_table_create(&span->used, 0, 0, &used_ops);
 
         for (i = 0; i <= span->max_order; i++)
@@ -171 +179 @@
 
         /* Insert the first segment into the respective free list. */
-        list_append(&seg->fu_link, &span->free[span->max_order]);
+        list_append(&seg->fl_link, &span->free[span->max_order]);
 
         return span;
@@ -232 +240 @@
                 /* Take the first segment from the free list. */
                 seg = list_get_instance(list_first(&span->free[order]),
-                    ra_segment_t, fu_link);
+                    ra_segment_t, fl_link);
 
                 assert(seg->flags & RA_SEGMENT_FREE);
@@ -274 +282 @@
                             &seg->segment_link);
                         pred_order = fnzb(ra_segment_size_get(pred));
-                        list_append(&pred->fu_link, &span->free[pred_order]);
+                        list_append(&pred->fl_link, &span->free[pred_order]);
                 }
                 if (succ) {
@@ -282 +290 @@
                             &seg->segment_link);
                         succ_order = fnzb(ra_segment_size_get(succ));
-                        list_append(&succ->fu_link, &span->free[succ_order]);
+                        list_append(&succ->fl_link, &span->free[succ_order]);
                 }
 
                 /* Now remove the found segment from the free list. */
-                list_remove(&seg->fu_link);
+                list_remove(&seg->fl_link);
                 seg->base = newbase;
                 seg->flags &= ~RA_SEGMENT_FREE;
 
                 /* Hash-in the segment into the used hash. */
-                sysarg_t key = seg->base;
-                hash_table_insert(&span->used, &key, &seg->fu_link);
+                hash_table_insert(&span->used, &seg->uh_link);
 
                 *base = newbase;
@@ -304 +311 @@
 {
         sysarg_t key = base;
-        link_t *link;
+        ht_link_t *link;
         ra_segment_t *seg;
         ra_segment_t *pred;
@@ -318 +325 @@
                     PRIxn ", size=%" PRIdn ").", base, size);
         }
-        seg = hash_table_get_instance(link, ra_segment_t, fu_link);
+        seg = hash_table_get_inst(link, ra_segment_t, uh_link);
 
         /*
          * Hash out the segment.
          */
-        hash_table_remove(&span->used, &key, 1);
+        hash_table_remove_item(&span->used, link);
 
         assert(!(seg->flags & RA_SEGMENT_FREE));
@@ -333 +340 @@
          */
         if (list_first(&span->segments) != &seg->segment_link) {
-                pred = hash_table_get_instance(seg->segment_link.prev,
+                pred = hash_table_get_inst(seg->segment_link.prev,
                     ra_segment_t, segment_link);
 
@@ -345 +352 @@
                          * away.
                          */
-                        list_remove(&pred->fu_link);
+                        list_remove(&pred->fl_link);
                         list_remove(&pred->segment_link);
                         seg->base = pred->base;
@@ -355 +362 @@
          * Check whether the segment can be coalesced with its right neighbor.
          */
-        succ = hash_table_get_instance(seg->segment_link.next, ra_segment_t,
+        succ = hash_table_get_inst(seg->segment_link.next, ra_segment_t,
             segment_link);
         assert(succ->base > seg->base);
@@ -364 +371 @@
                  * and throw it away.
                  */
-                list_remove(&succ->fu_link);
+                list_remove(&succ->fl_link);
                 list_remove(&succ->segment_link);
                 ra_segment_destroy(succ);
@@ -372 +379 @@
         seg->flags |= RA_SEGMENT_FREE;
         order = fnzb(ra_segment_size_get(seg));
-        list_append(&seg->fu_link, &span->free[order]);
+        list_append(&seg->fl_link, &span->free[order]);
 }