Changeset 04d66804 in mainline for kernel/generic/src/adt/cht.c

Timestamp:

2012-11-20T17:35:55Z (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:

669f3d32

Parents:

0adfc9d

Message:

cht: Expanded cht_insert_unique() to return a duplicate if found.

File:

• kernel/generic/src/adt/cht.c (modified) (7 diffs)

kernel/generic/src/adt/cht.c

@@ -414 +414 @@
 static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash, 
         marked_ptr_t old_head, size_t old_idx);
-static bool insert_impl(cht_t *h, cht_link_t *item, bool unique);
+static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item);
 static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode,
         bool *resizing);
-static bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash, 
-        const wnd_t *cwnd);
+static bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, 
+        cht_link_t *cur, cht_link_t **dup_item);
 static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash, 
         cht_link_t *start);
@@ -886 +886 @@
 void cht_insert(cht_t *h, cht_link_t *item)
 {
-        insert_impl(h, item, false);
+        insert_impl(h, item, NULL);
 }
 
@@ -908 +908 @@
  * @code
  * item = malloc(..);
- * if (!cht_insert_unique(h, item)) {
- *     // Whoops, someone beat us to it - an equal item had already been inserted.
+ * if (!cht_insert_unique(h, item, &dup_item)) {
+ *     // Whoops, someone beat us to it - an equal item 'dup_item'
+ *     // had already been inserted.
  *     free(item); 
  * } else {
@@ -918 +919 @@
  * 
  */
-bool cht_insert_unique(cht_t *h, cht_link_t *item)
-{
-        return insert_impl(h, item, true);
-}
-
-/** Inserts the item into the table and checks for duplicates if unique is true.*/
-static bool insert_impl(cht_t *h, cht_link_t *item, bool unique)
+bool cht_insert_unique(cht_t *h, cht_link_t *item, cht_link_t **dup_item)
+{
+        ASSERT(rcu_read_locked());
+        ASSERT(dup_item);
+        return insert_impl(h, item, dup_item);
+}
+
+/** Inserts the item into the table and checks for duplicates if dup_item. */
+static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item)
 {
         rcu_read_lock();
@@ -959 +962 @@
                 }
                 
-                if (unique && has_duplicates(h, item, hash, &wnd)) {
+                if (dup_item && has_duplicate(h, item, hash, wnd.cur, dup_item)) {
                         rcu_read_unlock();
                         return false;
@@ -1032 +1035 @@
 }
 
-/** Returns true the chain starting at wnd hash an item equal to \a item.
+/** Returns true if the chain starting at cur has an item equal to \a item.
  * 
  * @param h    CHT to operate on.
  * @param item Item whose duplicates the function looks for.
  * @param hash Hash of \a item.
- * @param[in] wnd  wnd.cur is the first node with a hash greater to or equal
- *             to item's hash.
+ * @param[in] cur  The first node with a hash greater to or equal to item's hash.
+ * @param[out] dup_item The first duplicate item encountered.
  * @return True if a non-deleted item equal to \a item exists in the table.
  */
-static inline bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash, 
-        const wnd_t *wnd)
-{
-        ASSERT(wnd->cur);
-        ASSERT(wnd->cur == &sentinel || hash <= node_hash(h, wnd->cur)
-                || node_hash(h, wnd->cur) == h->invalid_hash);
-        
-        /* hash < node_hash(h, wnd->cur) */
-        if (hash != node_hash(h, wnd->cur) && h->invalid_hash != node_hash(h, wnd->cur))
+static inline bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash, 
+        cht_link_t *cur, cht_link_t **dup_item)
+{
+        ASSERT(cur);
+        ASSERT(cur == &sentinel || hash <= node_hash(h, cur)
+                || node_hash(h, cur) == h->invalid_hash);
+        
+        /* hash < node_hash(h, cur) */
+        if (hash != node_hash(h, cur) && h->invalid_hash != node_hash(h, cur))
                 return false;
 
@@ -1058 +1061 @@
          */
         read_barrier();
-        return NULL != find_duplicate(h, item, hash, wnd->cur);
+        
+        *dup_item = find_duplicate(h, item, hash, cur);
+        return NULL != *dup_item;
 }