Changeset 82cbf8c6 in mainline for kernel/generic/include/adt/hash_table.h

Timestamp:

2017-10-08T19:37:24Z (8 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/include/adt/hash_table.h (modified) (3 diffs)

kernel/generic/include/adt/hash_table.h

@@ -1 +1 @@
 /*
  * Copyright (c) 2006 Jakub Jermar
+ * Copyright (c) 2012 Adam Hraska
+ * 
  * All rights reserved.
  *
@@ -27 +29 @@
  */
 
-/** @addtogroup genericadt
+/** @addtogroup libc
  * @{
  */
@@ -33 +35 @@
  */
 
-#ifndef KERN_HASH_TABLE_H_
-#define KERN_HASH_TABLE_H_
+#ifndef LIBC_HASH_TABLE_H_
+#define LIBC_HASH_TABLE_H_
 
 #include <adt/list.h>
-#include <typedefs.h>
+#include <stdbool.h>
+#include <macros.h>
+
+/** Opaque hash table link type. */
+typedef struct ht_link {
+        link_t link;
+} ht_link_t;
 
 /** Set of operations for hash table. */
 typedef struct {
-        /** Hash function.
-         *
-         * @param key   Array of keys needed to compute hash index. All keys must
-         *              be passed.
-         *
-         * @return Index into hash table.
-         */
-        size_t (* hash)(sysarg_t key[]);
+        /** Returns the hash of the key stored in the item (ie its lookup key). */
+        size_t (*hash)(const ht_link_t *item);
         
-        /** Hash table item comparison function.
-         *
-         * @param key   Array of keys that will be compared with item. It is not
-         *              necessary to pass all keys.
-         *
-         * @return true if the keys match, false otherwise.
-         */
-        bool (*compare)(sysarg_t key[], size_t keys, link_t *item);
+        /** Returns the hash of the key. */
+        size_t (*key_hash)(void *key);
+        
+        /** True if the items are equal (have the same lookup keys). */
+        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
+
+        /** Returns true if the key is equal to the item's lookup key. */
+        bool (*key_equal)(void *key, const ht_link_t *item);
 
         /** Hash table item removal callback.
+         * 
+         * Must not invoke any mutating functions of the hash table.
          *
          * @param item Item that was removed from the hash table.
          */
-        void (*remove_callback)(link_t *item);
-} hash_table_operations_t;
+        void (*remove_callback)(ht_link_t *item);
+} hash_table_ops_t;
 
 /** Hash table structure. */
 typedef struct {
-        list_t *entry;
-        size_t entries;
-        size_t max_keys;
-        hash_table_operations_t *op;
+        hash_table_ops_t *op;
+        list_t *bucket;
+        size_t bucket_cnt;
+        size_t full_item_cnt;
+        size_t item_cnt;
+        size_t max_load;
+        bool apply_ongoing;
 } hash_table_t;
 
-#define hash_table_get_instance(item, type, member) \
-        list_get_instance((item), type, member)
+#define hash_table_get_inst(item, type, member) \
+        member_to_inst((item), type, member)
 
-extern void hash_table_create(hash_table_t *h, size_t m, size_t max_keys,
-    hash_table_operations_t *op);
-extern void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item);
-extern link_t *hash_table_find(hash_table_t *h, sysarg_t key[]);
-extern void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys);
-extern void hash_table_remove_item(hash_table_t *h, link_t *item);
+extern bool hash_table_create(hash_table_t *, size_t, size_t, 
+        hash_table_ops_t *);
+extern void hash_table_destroy(hash_table_t *);
+
+extern bool hash_table_empty(hash_table_t *);
+extern size_t hash_table_size(hash_table_t *);
+
+extern void hash_table_clear(hash_table_t *);
+extern void hash_table_insert(hash_table_t *, ht_link_t *);
+extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
+extern ht_link_t *hash_table_find(const hash_table_t *, void *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
+extern size_t hash_table_remove(hash_table_t *, void *);
+extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
+extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), 
+        void *);
+
 
 #endif