Merge pull request #13649 from donaldsharp/unlock_the_node_or_else

[mirror_frr.git] / lib / typesafe.c

diff --git a/lib/typesafe.c b/lib/typesafe.c
index 76705fad0d3607937921c860b2f9cf228b95486b..c0774479852da261af67d70572da58b55f2c77fa 100644 (file)
--- a/lib/typesafe.c
+++ b/lib/typesafe.c
@@ -1,17 +1,6 @@
+// SPDX-License-Identifier: ISC
 /*
  * Copyright (c) 2019  David Lamparter, for NetDEF, Inc.
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
 #ifdef HAVE_CONFIG_H
@@ -20,6 +9,7 @@
 
 #include <stdlib.h>
 #include <string.h>
+#include <assert.h>
 
 #include "typesafe.h"
 #include "memory.h"
@@ -29,6 +19,46 @@ DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket");
 DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow");
 DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array");
 
+struct slist_item typesafe_slist_sentinel = { NULL };
+
+bool typesafe_list_member(const struct slist_head *head,
+                         const struct slist_item *item)
+{
+       struct slist_item *fromhead = head->first;
+       struct slist_item **fromnext = (struct slist_item **)&item->next;
+
+       while (fromhead != _SLIST_LAST) {
+               if (fromhead == item || fromnext == head->last_next)
+                       return true;
+
+               fromhead = fromhead->next;
+               if (!*fromnext || *fromnext == _SLIST_LAST)
+                       break;
+               fromnext = &(*fromnext)->next;
+       }
+
+       return false;
+}
+
+bool typesafe_dlist_member(const struct dlist_head *head,
+                          const struct dlist_item *item)
+{
+       const struct dlist_item *fromhead = head->hitem.next;
+       const struct dlist_item *fromitem = item->next;
+
+       if (!item->prev || !item->next)
+               return false;
+
+       while (fromhead != &head->hitem && fromitem != item) {
+               if (fromitem == &head->hitem || fromhead == item)
+                       return true;
+               fromhead = fromhead->next;
+               fromitem = fromitem->next;
+       }
+
+       return false;
+}
+
 #if 0
 static void hash_consistency_check(struct thash_head *head)
 {
@@ -55,6 +85,15 @@ void typesafe_hash_grow(struct thash_head *head)
        uint32_t newsize = head->count, i, j;
        uint8_t newshift, delta;
 
+       /* note hash_grow is called after head->count++, so newsize is
+        * guaranteed to be >= 1.  So the minimum argument to builtin_ctz
+        * below is 2, which returns 1, and that makes newshift >= 2.
+        *
+        * Calling hash_grow with a zero head->count would result in a
+        * malformed hash table that has tabshift == 1.
+        */
+       assert(head->count > 0);
+
        hash_consistency_check(head);
 
        newsize |= newsize >> 1;