Changeset b9cb911 in mainline for kernel/generic/include/adt/cht.h

Timestamp:

2012-08-20T18:40:19Z (13 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

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

Children:

7cfe5c0

Parents:

85d31de9

Message:

cht: API comments.

File:

• kernel/generic/include/adt/cht.h (modified) (3 diffs)

kernel/generic/include/adt/cht.h

@@ -49 +49 @@
          * 
          * The function pointer (rcu_link.func) is used to store the item's 
-         * memoized hash.
+         * mixed memoized hash. If in use by RCU (ie waiting for deferred 
+         * destruction) the hash will contain the value of 
+         * cht_t.op->remove_callback.
          */
         union {
@@ -61 +63 @@
 /** Set of operations for a concurrent hash table. */
 typedef struct cht_ops {
+        /** Returns the hash of the item.
+         * 
+         * Applicable also to items that were logically deleted from the table
+         * but have yet to be physically removed by means of remove_callback().
+         */
         size_t (*hash)(const cht_link_t *item);
+        /** Returns the hash value of the key used to search for entries. */
         size_t (*key_hash)(void *key);
+        /** Returns true if the two items store equal search keys. */
         bool (*equal)(const cht_link_t *item1, const cht_link_t *item2);
+        /** Returns true if the item contains an equal search key. */
         bool (*key_equal)(void *key, const cht_link_t *item);
+        /** Invoked to free a removed item once all references to it are dropped. */
         void (*remove_callback)(cht_link_t *item);
 } cht_ops_t;
 
-
+/** Groups hash table buckets with their count.
+ * 
+ * It allows both the number of buckets as well as the bucket array
+ * to be swapped atomically when resing the table.
+ */
 typedef struct cht_buckets {
+        /** The number of buckets is 2^order. */
         size_t order;
+        /** Array of single linked list bucket heads along with any marks. */
         cht_ptr_t head[1];
 } cht_buckets_t;
@@ -76 +93 @@
 /** Concurrent hash table structure. */
 typedef struct {
+        /** Item specific operations. */
         cht_ops_t *op;
         
+        /** Buckets currently in use. */
         cht_buckets_t *b;
+        /** Resized table buckets that will replace b once resize is complete. */
         cht_buckets_t *new_b;
+        /** Invalid memoized hash value. 
+         * 
+         * If cht_link.hash contains this value the item had been logically
+         * removed and is waiting to be freed. Such hashes (and the associated
+         * items) are disregarded and skipped or the actual hash must be 
+         * determined via op->hash().
+         */
         size_t invalid_hash;
 
+        /** Minimum number of buckets is 2^min_order. */
         size_t min_order;
+        /** Maximum number of items per bucket before the table grows. */
         size_t max_load;
+        /** Table is resized in the background in a work queue. */
         work_t resize_work;
+        /** If positive the table should grow or shrink.
+         * 
+         * If not 0 resize work had already been posted to the system work queue.
+         */
         atomic_t resize_reqs;
         
+        /** Number of items in the table that have not been logically deleted. */
         atomic_t item_cnt;
 } cht_t;