Changes in kernel/generic/include/adt/hash_table.h [9d58539:82cbf8c6] in mainline

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