structure: CHash: rework, remove unused features

4 files changed, 126 insertions, 145 deletions

diff --git a/structure/CHash_decl.h b/structure/CHash_decl.h
index d7c216a..ef4cea6 100644
--- a/structure/CHash_decl.h
+++ b/structure/CHash_decl.h
@@ -31,8 +31,7 @@
 
 typedef struct {
     CHashLink *buckets;
-    size_t numBuckets;
-    size_t numEntries;
+    size_t num_buckets;
 } CHash;
 
 typedef struct {
@@ -40,20 +39,19 @@ typedef struct {
     CHashLink link;
 } CHashRef;
 
-static CHashLink CHashNullLink ();
-static CHashRef CHashNullRef ();
+static CHashLink CHashNullLink (void);
+static CHashRef CHashNullRef (void);
+static int CHashIsNullLink (CHashLink link);
+static int CHashIsNullRef (CHashRef ref);
+static CHashRef CHashDerefMayNull (CHashArg arg, CHashLink link);
+static CHashRef CHashDerefNonNull (CHashArg arg, CHashLink link);
 
-static int CHash_Init (CHash *o, size_t numBuckets);
+static int CHash_Init (CHash *o, size_t num_buckets);
 static void CHash_Free (CHash *o);
-static CHashRef CHash_Deref (CHashArg arg, CHashLink link);
 static int CHash_Insert (CHash *o, CHashArg arg, CHashRef entry, CHashRef *out_existing);
 static void CHash_InsertMulti (CHash *o, CHashArg arg, CHashRef entry);
 static void CHash_Remove (CHash *o, CHashArg arg, CHashRef entry);
 static CHashRef CHash_Lookup (const CHash *o, CHashArg arg, CHashKey key);
-static CHashRef CHash_GetFirst (const CHash *o, CHashArg arg);
-static CHashRef CHash_GetNext (const CHash *o, CHashArg arg, CHashRef entry);
 static CHashRef CHash_GetNextEqual (const CHash *o, CHashArg arg, CHashRef entry);
-static size_t CHash_NumEntries (const CHash *o);
-static int CHash_IsEmpty (const CHash *o);
 
 #include "CHash_footer.h"
diff --git a/structure/CHash_footer.h b/structure/CHash_footer.h
index cca38a7..33c3fe0 100644
--- a/structure/CHash_footer.h
+++ b/structure/CHash_footer.h
@@ -27,7 +27,7 @@
  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-// Preprocessor inputs:
+// preprocessor inputs
 #undef CHASH_PARAM_NAME
 #undef CHASH_PARAM_ENTRY
 #undef CHASH_PARAM_LINK
@@ -35,9 +35,10 @@
 #undef CHASH_PARAM_ARG
 #undef CHASH_PARAM_NULL
 #undef CHASH_PARAM_DEREF
-#undef CHASH_PARAM_HASHFUN
-#undef CHASH_PARAM_KEYSEQUAL
-#undef CHASH_PARAM_GETKEY
+#undef CHASH_PARAM_ENTRYHASH
+#undef CHASH_PARAM_KEYHASH
+#undef CHASH_PARAM_COMPARE_ENTRIES
+#undef CHASH_PARAM_COMPARE_KEY_ENTRY
 #undef CHASH_PARAM_ENTRY_NEXT
 
 // types
@@ -48,20 +49,23 @@
 #undef CHashArg
 #undef CHashKey
 
-// static values
+// non-object public functions
 #undef CHashNullLink
 #undef CHashNullRef
+#undef CHashIsNullLink
+#undef CHashIsNullRef
+#undef CHashDerefMayNull
+#undef CHashDerefNonNull
 
 // public functions
 #undef CHash_Init
 #undef CHash_Free
-#undef CHash_Deref
 #undef CHash_Insert
 #undef CHash_InsertMulti
 #undef CHash_Remove
 #undef CHash_Lookup
-#undef CHash_GetFirst
-#undef CHash_GetNext
 #undef CHash_GetNextEqual
-#undef CHash_NumEntries
-#undef CHash_IsEmpty
+
+// private things
+#undef CHash_next
+#undef CHash_assert_valid_entry
diff --git a/structure/CHash_header.h b/structure/CHash_header.h
index 56bfc9b..b59bdc6 100644
--- a/structure/CHash_header.h
+++ b/structure/CHash_header.h
@@ -35,33 +35,37 @@
 // CHASH_PARAM_ARG - type of argument pass through to comparisons
 // CHASH_PARAM_NULL - invalid link
 // CHASH_PARAM_DEREF(arg, link) - dereference a non-null link
-// CHASH_PARAM_HASHFUN(arg, key) - hash function, return size_t
-// CHASH_PARAM_KEYSEQUAL(arg, key1, key2) - compares equality of two keys
-// CHASH_PARAM_GETKEY(arg, entry) - get key of entry
+// CHASH_PARAM_ENTRYHASH(arg, entry) - hash function for entries; returns size_t
+// CHASH_PARAM_KEYHASH(arg, key) - hash function for keys; returns size_t
+// CHASH_PARAM_COMPARE_ENTRIES(arg, entry1, entry2) - compares two entries; returns 1 for equality, 0 otherwise
+// CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key1, entry2) - compares key and entry; returns 1 for equality, 0 otherwise
 // CHASH_PARAM_ENTRY_NEXT - next member in entry
 
 // types
 #define CHash CHASH_PARAM_NAME
 #define CHashEntry CHASH_PARAM_ENTRY
 #define CHashLink CHASH_PARAM_LINK
-#define CHashRef MERGE(CHASH_PARAM_NAME, Ref)
+#define CHashRef MERGE(CHash, Ref)
 #define CHashArg CHASH_PARAM_ARG
 #define CHashKey CHASH_PARAM_KEY
 
-// static values
+// non-object public functions
 #define CHashNullLink MERGE(CHash, NullLink)
 #define CHashNullRef MERGE(CHash, NullRef)
+#define CHashIsNullLink MERGE(CHash, IsNullLink)
+#define CHashIsNullRef MERGE(CHash, IsNullRef)
+#define CHashDerefMayNull MERGE(CHash, DerefMayNull)
+#define CHashDerefNonNull MERGE(CHash, DerefNonNull)
 
 // public functions
 #define CHash_Init MERGE(CHash, _Init)
 #define CHash_Free MERGE(CHash, _Free)
-#define CHash_Deref MERGE(CHash, _Deref)
 #define CHash_Insert MERGE(CHash, _Insert)
 #define CHash_InsertMulti MERGE(CHash, _InsertMulti)
 #define CHash_Remove MERGE(CHash, _Remove)
 #define CHash_Lookup MERGE(CHash, _Lookup)
-#define CHash_GetFirst MERGE(CHash, _GetFirst)
-#define CHash_GetNext MERGE(CHash, _GetNext)
 #define CHash_GetNextEqual MERGE(CHash, _GetNextEqual)
-#define CHash_NumEntries MERGE(CHash, _NumEntries)
-#define CHash_IsEmpty MERGE(CHash, _IsEmpty)
+
+// private things
+#define CHash_next(entry) ((entry).ptr->CHASH_PARAM_ENTRY_NEXT)
+#define CHash_assert_valid_entry MERGE(CHash, _assert_valid_entry)
diff --git a/structure/CHash_impl.h b/structure/CHash_impl.h
index dadc312..dc37473 100644
--- a/structure/CHash_impl.h
+++ b/structure/CHash_impl.h
@@ -29,32 +29,69 @@
 
 #include "CHash_header.h"
 
-static CHashLink CHashNullLink ()
+static void CHash_assert_valid_entry (CHashArg arg, CHashRef entry)
+{
+    ASSERT(entry.link != CHashNullLink())
+    ASSERT(entry.ptr == CHASH_PARAM_DEREF(arg, entry.link))
+}
+
+static CHashLink CHashNullLink (void)
 {
     return CHASH_PARAM_NULL;
 }
 
-static CHashRef CHashNullRef ()
+static CHashRef CHashNullRef (void)
+{
+    CHashRef entry = {NULL, CHashNullLink()};
+    return entry;
+}
+
+static int CHashIsNullLink (CHashLink link)
+{
+    return (link == CHashNullLink());
+}
+
+static int CHashIsNullRef (CHashRef ref)
+{
+    return CHashIsNullLink(ref.link);
+}
+
+static CHashRef CHashDerefMayNull (CHashArg arg, CHashLink link)
+{
+    if (link == CHashNullLink()) {
+        return CHashNullRef();
+    }
+    
+    CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link};
+    ASSERT(entry.ptr)
+    
+    return entry;
+}
+
+static CHashRef CHashDerefNonNull (CHashArg arg, CHashLink link)
 {
-    CHashRef entry = {NULL, CHASH_PARAM_NULL};
+    ASSERT(link != CHashNullLink())
+    
+    CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link};
+    ASSERT(entry.ptr)
+    
     return entry;
 }
 
-static int CHash_Init (CHash *o, size_t numBuckets)
+static int CHash_Init (CHash *o, size_t num_buckets)
 {
-    if (numBuckets == 0) {
-        numBuckets = 1;
+    if (num_buckets == 0) {
+        num_buckets = 1;
     }
     
-    o->numBuckets = numBuckets;
-    o->numEntries = 0;
+    o->num_buckets = num_buckets;
     
-    o->buckets = (CHashLink *)BAllocArray(o->numBuckets, sizeof(o->buckets[0])); 
+    o->buckets = (CHashLink *)BAllocArray(o->num_buckets, sizeof(o->buckets[0])); 
     if (!o->buckets) {
         return 0;
     }
     
-    for (size_t i = 0; i < o->numBuckets; i++) {
+    for (size_t i = 0; i < o->num_buckets; i++) {
         o->buckets[i] = CHashNullLink();
     }
     
@@ -66,172 +103,110 @@ static void CHash_Free (CHash *o)
     BFree(o->buckets);
 }
 
-static CHashRef CHash_Deref (CHashArg arg, CHashLink link)
-{
-    if (link == CHashNullLink()) {
-        return CHashNullRef();
-    }
-    
-    CHashRef entry;
-    entry.ptr = CHASH_PARAM_DEREF(arg, link);
-    entry.link = link;
-    
-    ASSERT(entry.ptr)
-    
-    return entry;
-}
-
 static int CHash_Insert (CHash *o, CHashArg arg, CHashRef entry, CHashRef *out_existing)
 {
-    CHashKey key = CHASH_PARAM_GETKEY(arg, entry);
-    size_t index = CHASH_PARAM_HASHFUN(arg, key) % o->numBuckets;
+    CHash_assert_valid_entry(arg, entry);
+    
+    size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
     
-    CHashRef e = CHash_Deref(arg, o->buckets[index]);
-    while (e.link != CHashNullLink()) {
-        if (CHASH_PARAM_KEYSEQUAL(arg, key, CHASH_PARAM_GETKEY(arg, e))) {
+    CHashLink link = o->buckets[index];
+    while (link != CHashNullLink()) {
+        CHashRef cur = CHashDerefNonNull(arg, link);
+        if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) {
             if (out_existing) {
-                *out_existing = e;
+                *out_existing = cur;
+                return 0;
             }
-            return 0;
         }
-        e = CHash_Deref(arg, e.ptr->CHASH_PARAM_ENTRY_NEXT);
+        link = CHash_next(cur);
     }
     
-    entry.ptr->CHASH_PARAM_ENTRY_NEXT = o->buckets[index];
+    CHash_next(entry) = o->buckets[index];
     o->buckets[index] = entry.link;
     
-    o->numEntries++;
-    
-    if (out_existing) {
-        *out_existing = entry;
-    }
     return 1;
 }
 
 static void CHash_InsertMulti (CHash *o, CHashArg arg, CHashRef entry)
 {
-    CHashKey key = CHASH_PARAM_GETKEY(arg, entry);
-    size_t index = CHASH_PARAM_HASHFUN(arg, key) % o->numBuckets;
+    CHash_assert_valid_entry(arg, entry);
+    
+    size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
     
     CHashRef prev = CHashNullRef();
-    CHashRef cur = CHash_Deref(arg, o->buckets[index]);
-    while (cur.link != CHashNullLink()) {
-        if (CHASH_PARAM_KEYSEQUAL(arg, CHASH_PARAM_GETKEY(arg, cur), key)) {
+    CHashLink link = o->buckets[index];
+    while (link != CHashNullLink()) {
+        CHashRef cur = CHashDerefNonNull(arg, link);
+        if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) {
             break;
         }
         prev = cur;
-        cur = CHash_Deref(arg, cur.ptr->CHASH_PARAM_ENTRY_NEXT);
+        link = CHash_next(cur);
     }
     
-    if (cur.link == CHashNullLink() || prev.link == CHashNullLink()) {
-        entry.ptr->CHASH_PARAM_ENTRY_NEXT = o->buckets[index];
+    if (link == CHashNullLink() || prev.link == CHashNullLink()) {
+        CHash_next(entry) = o->buckets[index];
         o->buckets[index] = entry.link;
     } else {
-        entry.ptr->CHASH_PARAM_ENTRY_NEXT = cur.link;
-        prev.ptr->CHASH_PARAM_ENTRY_NEXT = entry.link;
+        CHash_next(entry) = link;
+        CHash_next(prev) = entry.link;
     }
-    
-    o->numEntries++;
 }
 
 static void CHash_Remove (CHash *o, CHashArg arg, CHashRef entry)
 {
-    CHashKey key = CHASH_PARAM_GETKEY(arg, entry);
-    size_t index = CHASH_PARAM_HASHFUN(arg, key) % o->numBuckets;
+    CHash_assert_valid_entry(arg, entry);
+    
+    size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets;
     
     CHashRef prev = CHashNullRef();
-    CHashRef cur = CHash_Deref(arg, o->buckets[index]);
-    while (cur.link != entry.link) {
+    CHashLink link = o->buckets[index];
+    while (link != entry.link) {
+        CHashRef cur = CHashDerefNonNull(arg, link);
         prev = cur;
-        cur = CHash_Deref(arg, cur.ptr->CHASH_PARAM_ENTRY_NEXT);
-        ASSERT(cur.link != CHashNullLink());
+        link = CHash_next(cur);
+        ASSERT(link != CHashNullLink())
     }
     
     if (prev.link == CHashNullLink()) {
-        o->buckets[index] = entry.ptr->CHASH_PARAM_ENTRY_NEXT;
+        o->buckets[index] = CHash_next(entry);
     } else {
-        prev.ptr->CHASH_PARAM_ENTRY_NEXT = entry.ptr->CHASH_PARAM_ENTRY_NEXT;
+        CHash_next(prev) = CHash_next(entry);
     }
-    
-    o->numEntries--;
 }
 
 static CHashRef CHash_Lookup (const CHash *o, CHashArg arg, CHashKey key) 
 {
-    size_t index = CHASH_PARAM_HASHFUN(arg, key) % o->numBuckets;
+    size_t index = CHASH_PARAM_KEYHASH(arg, key) % o->num_buckets;
     
     CHashLink link = o->buckets[index];
     while (link != CHashNullLink()) {
-        CHashRef e = CHash_Deref(arg, link);
-        if (CHASH_PARAM_KEYSEQUAL(arg, CHASH_PARAM_GETKEY(arg, e), key)) {
-            return e;
+        CHashRef cur = CHashDerefNonNull(arg, link);
+        if (CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) {
+            return cur;
         }
-        link = e.ptr->CHASH_PARAM_ENTRY_NEXT;
+        link = CHash_next(cur);
     }
     
     return CHashNullRef();
 }
 
-static CHashRef CHash_GetFirst (const CHash *o, CHashArg arg)
-{
-    size_t i = 0;
-    while (i < o->numBuckets && o->buckets[i] == CHashNullLink()) {
-        i++;
-    }
-    
-    if (i == o->numBuckets) {
-        return CHashNullRef();
-    }
-    
-    return CHash_Deref(arg, o->buckets[i]);
-}
-
-static CHashRef CHash_GetNext (const CHash *o, CHashArg arg, CHashRef entry)
-{
-    CHashLink next = entry.ptr->CHASH_PARAM_ENTRY_NEXT;
-    if (next != CHashNullLink()) {
-        return CHash_Deref(arg, next);
-    }
-    
-    CHashKey key = CHASH_PARAM_GETKEY(arg, entry);
-    size_t i = CHASH_PARAM_HASHFUN(arg, key) % o->numBuckets;
-    i++;
-    
-    while (i < o->numBuckets && o->buckets[i] == CHashNullLink()) {
-        i++;
-    }
-    
-    if (i == o->numBuckets) {
-        return CHashNullRef();
-    }
-    
-    return CHash_Deref(arg, o->buckets[i]);
-}
-
 static CHashRef CHash_GetNextEqual (const CHash *o, CHashArg arg, CHashRef entry)
 {
-    CHashLink next = entry.ptr->CHASH_PARAM_ENTRY_NEXT;
+    CHash_assert_valid_entry(arg, entry);
+    
+    CHashLink next = CHash_next(entry);
     
     if (next == CHashNullLink()) {
         return CHashNullRef();
     }
     
-    CHashRef next_ref = CHash_Deref(arg, next);
-    if (!CHASH_PARAM_KEYSEQUAL(arg, CHASH_PARAM_GETKEY(arg, next_ref), CHASH_PARAM_GETKEY(arg, entry))) {
+    CHashRef next_ref = CHashDerefNonNull(arg, next);
+    if (!CHASH_PARAM_COMPARE_ENTRIES(arg, next_ref, entry)) {
         return CHashNullRef();
     }
     
     return next_ref;
 }
 
-static size_t CHash_NumEntries (const CHash *o)
-{
-    return o->numEntries;
-}
-
-static int CHash_IsEmpty (const CHash *o)
-{
-    return o->numEntries == 0;
-}
-
 #include "CHash_footer.h"