ref: 83185ad9f68ed39250938c91877deedb16cb67d6
parent: fcdc5b4a8db42f064830bb5fa25f6f020fa121c6
author: Sigrid Solveig Haflínudóttir <sigrid@ftrv.se>
date: Thu Jan 2 00:32:59 EST 2025
htable.inc: take macros from outside instead of defining one This makes debugging possible since the file/line mapping is now pointing at htable.inc, rather than always at a single line with a macro call.
--- a/equalhash.c
+++ b/equalhash.c
@@ -1,8 +1,9 @@
#include "flisp.h"
#include "equalhash.h"
#include "equal.h"
-#include "htable.inc"
-#define _equal_lispvalue_(x, y) equal_lispvalue((value_t)(x), (value_t)(y))
+#define HTNAME(suffix) equalhash##suffix
+#define HFUNC hash_lispvalue
+#define EQFUNC(x, y) equal_lispvalue((value_t)(x), (value_t)(y))
-HTIMPL(equalhash, hash_lispvalue, _equal_lispvalue_)
+#include "htable.inc"
--- a/htable.inc
+++ b/htable.inc
@@ -1,8 +1,6 @@
//-*- mode:c -*-
-/*
- include this file and call HTIMPL to generate an implementation
-*/
+// define HTNAME, HFUNC and EQFUNC, then include this header
#define hash_size(h) ((h)->size/2)
@@ -9,139 +7,138 @@
// compute empirical max-probe for a given size
#define max_probe(size) ((size) <= (HT_N_INLINE*2) ? (HT_N_INLINE/2) : (size)>>3)
-#define HTIMPL(HTNAME, HFUNC, EQFUNC) \
-static void ** \
-HTNAME##_lookup_bp(htable_t *h, void *key) \
-{ \- value_t hv; \
- size_t i, orig, index, iter; \
- size_t newsz, sz = hash_size(h); \
- size_t maxprobe = max_probe(sz); \
- void **tab = h->table; \
- void **ol; \
- \
- hv = HFUNC((uintptr_t)key); \
-retry_bp: \
- iter = 0; \
- index = (hv & (sz-1)) * 2; \
- sz *= 2; \
- orig = index; \
- \
- do{ \- if(tab[index+1] == HT_NOTFOUND){ \- tab[index] = key; \
- return &tab[index+1]; \
- } \
- if(EQFUNC(key, tab[index])) \
- return &tab[index+1]; \
- index = (index+2) & (sz-1); \
- iter++; \
- if(iter > maxprobe) \
- break; \
- }while(index != orig); \
- \
- /* table full */ \
- /* quadruple size, rehash, retry the insert */ \
- /* it's important to grow the table really fast; otherwise we waste */ \
- /* lots of time rehashing all the keys over and over. */ \
- sz = h->size; \
- ol = h->table; \
- if(sz >= (1<<19) || (sz <= (1<<8))) \
- newsz = sz<<1; \
- else if(sz <= HT_N_INLINE) \
- newsz = HT_N_INLINE; \
- else \
- newsz = sz<<2; \
- tab = (void**)MEM_ALLOC(newsz*sizeof(void*)); \
- if(tab == nil) \
- return nil; \
- for(i = 0; i < newsz; i++) \
- tab[i] = HT_NOTFOUND; \
- h->table = tab; \
- h->size = newsz; \
- for(i = 0; i < sz; i += 2) { \- if(ol[i+1] != HT_NOTFOUND) \
- (*HTNAME##_lookup_bp(h, ol[i])) = ol[i+1]; \
- } \
- if(ol != &h->_space[0]) \
- MEM_FREE(ol); \
- sz = hash_size(h); \
- maxprobe = max_probe(sz); \
- tab = h->table; \
- goto retry_bp; \
-} \
- \
-void \
-HTNAME##_put(htable_t *h, void *key, void *val) \
-{ \- void **bp = HTNAME##_lookup_bp(h, key); \
- *bp = val; \
-} \
- \
-void ** \
-HTNAME##_bp(htable_t *h, void *key) \
-{ \- return HTNAME##_lookup_bp(h, key); \
-} \
- \
-/* returns bp if key is in hash, otherwise nil */ \
-/* if return is non-nil and *bp == HT_NOTFOUND then key was deleted */ \
-static void ** \
-HTNAME##_peek_bp(htable_t *h, void *key) \
-{ \- size_t sz = hash_size(h); \
- size_t maxprobe = max_probe(sz); \
- void **tab = h->table; \
- size_t index = (HFUNC((uintptr_t)key) & (sz-1)) * 2; \
- sz *= 2; \
- size_t orig = index; \
- size_t iter = 0; \
- \
- do { \- if(tab[index] == HT_NOTFOUND) \
- return nil; \
- if(EQFUNC(key, tab[index])) \
- return &tab[index+1]; \
- \
- index = (index+2) & (sz-1); \
- iter++; \
- if(iter > maxprobe) \
- break; \
- }while(index != orig); \
- \
- return nil; \
-} \
- \
-void *\
-HTNAME##_get(htable_t *h, void *key) \
-{ \- void **bp = HTNAME##_peek_bp(h, key); \
- if(bp == nil) \
- return HT_NOTFOUND; \
- return *bp; \
-} \
- \
-int \
-HTNAME##_has(htable_t *h, void *key) \
-{ \- return HTNAME##_get(h, key) != HT_NOTFOUND; \
-} \
- \
-int \
-HTNAME##_remove(htable_t *h, void *key) \
-{ \- void **bp = HTNAME##_peek_bp(h, key); \
- if(bp != nil){ \- *bp = HT_NOTFOUND; \
- return 1; \
- } \
- return 0; \
-} \
- \
-void \
-HTNAME##_adjoin(htable_t *h, void *key, void *val) \
-{ \- void **bp = HTNAME##_lookup_bp(h, key); \
- if(*bp == HT_NOTFOUND) \
- *bp = val; \
+static void **
+HTNAME(_lookup_bp)(htable_t *h, void *key)
+{+ value_t hv;
+ size_t i, orig, index, iter;
+ size_t newsz, sz = hash_size(h);
+ size_t maxprobe = max_probe(sz);
+ void **tab = h->table;
+ void **ol;
+
+ hv = HFUNC((uintptr_t)key);
+retry_bp:
+ iter = 0;
+ index = (hv & (sz-1)) * 2;
+ sz *= 2;
+ orig = index;
+
+ do{+ if(tab[index+1] == HT_NOTFOUND){+ tab[index] = key;
+ return &tab[index+1];
+ }
+ if(EQFUNC(key, tab[index]))
+ return &tab[index+1];
+ index = (index+2) & (sz-1);
+ iter++;
+ if(iter > maxprobe)
+ break;
+ }while(index != orig);
+
+ /* table full */
+ /* quadruple size, rehash, retry the insert */
+ /* it's important to grow the table really fast; otherwise we waste */
+ /* lots of time rehashing all the keys over and over. */
+ sz = h->size;
+ ol = h->table;
+ if(sz >= (1<<19) || (sz <= (1<<8)))
+ newsz = sz<<1;
+ else if(sz <= HT_N_INLINE)
+ newsz = HT_N_INLINE;
+ else
+ newsz = sz<<2;
+ tab = (void**)MEM_ALLOC(newsz*sizeof(void*));
+ if(tab == nil)
+ return nil;
+ for(i = 0; i < newsz; i++)
+ tab[i] = HT_NOTFOUND;
+ h->table = tab;
+ h->size = newsz;
+ for(i = 0; i < sz; i += 2) {+ if(ol[i+1] != HT_NOTFOUND)
+ (*HTNAME(_lookup_bp)(h, ol[i])) = ol[i+1];
+ }
+ if(ol != &h->_space[0])
+ MEM_FREE(ol);
+ sz = hash_size(h);
+ maxprobe = max_probe(sz);
+ tab = h->table;
+ goto retry_bp;
+}
+
+void
+HTNAME(_put)(htable_t *h, void *key, void *val)
+{+ void **bp = HTNAME(_lookup_bp)(h, key);
+ *bp = val;
+}
+
+void **
+HTNAME(_bp)(htable_t *h, void *key)
+{+ return HTNAME(_lookup_bp)(h, key);
+}
+
+/* returns bp if key is in hash, otherwise nil */
+/* if return is non-nil and *bp == HT_NOTFOUND then key was deleted */
+static void **
+HTNAME(_peek_bp)(htable_t *h, void *key)
+{+ size_t sz = hash_size(h);
+ size_t maxprobe = max_probe(sz);
+ void **tab = h->table;
+ size_t index = (HFUNC((uintptr_t)key) & (sz-1)) * 2;
+ sz *= 2;
+ size_t orig = index;
+ size_t iter = 0;
+
+ do {+ if(tab[index] == HT_NOTFOUND)
+ return nil;
+ if(EQFUNC(key, tab[index]))
+ return &tab[index+1];
+
+ index = (index+2) & (sz-1);
+ iter++;
+ if(iter > maxprobe)
+ break;
+ }while(index != orig);
+
+ return nil;
+}
+
+void *
+HTNAME(_get)(htable_t *h, void *key)
+{+ void **bp = HTNAME(_peek_bp)(h, key);
+ if(bp == nil)
+ return HT_NOTFOUND;
+ return *bp;
+}
+
+int
+HTNAME(_has)(htable_t *h, void *key)
+{+ return HTNAME(_get)(h, key) != HT_NOTFOUND;
+}
+
+int
+HTNAME(_remove)(htable_t *h, void *key)
+{+ void **bp = HTNAME(_peek_bp)(h, key);
+ if(bp != nil){+ *bp = HT_NOTFOUND;
+ return 1;
+ }
+ return 0;
+}
+
+void
+HTNAME(_adjoin)(htable_t *h, void *key, void *val)
+{+ void **bp = HTNAME(_lookup_bp)(h, key);
+ if(*bp == HT_NOTFOUND)
+ *bp = val;
}
--- a/ptrhash.c
+++ b/ptrhash.c
@@ -5,8 +5,6 @@
#include "flisp.h"
-#define OP_EQ(x, y) ((x) == (y))
-
#if defined(BITS64)
static uint64_t
_pinthash(uint64_t key)
@@ -34,6 +32,8 @@
}
#endif
-#include "htable.inc"
+#define HTNAME(suffix) ptrhash##suffix
+#define HFUNC _pinthash
+#define EQFUNC(x, y) ((x) == (y))
-HTIMPL(ptrhash, _pinthash, OP_EQ)
+#include "htable.inc"