relatively prime to 2^sizeof(size_t). The result is two words.
Discard the most significant word, and return the most significant
N bits of the least significant word. As suggested by Knuth, our
- choice for A is the integer part of 2^32 / phi, where phi is the
- golden ratio.
+ choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
+ is the golden ratio.
We don't need to do anything special for full-width multiplication
because we're only interested in the least significant word of the
- product, and unsigned arithmetic in C is modulo the word size. */
+ product, and unsigned arithmetic in C is modulo the word size. */
static inline size_t
hash1 (const void *p, unsigned long max, unsigned long logmax)
{
+#if HOST_BITS_PER_LONG == 32
const unsigned long A = 0x9e3779b9u;
- const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
+#elif HOST_BITS_PER_LONG == 64
+ const unsigned long A = 0x9e3779b97f4a7c16ul;
+#else
+ const unsigned long A
+ = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
+#endif
+ const unsigned long shift = HOST_BITS_PER_LONG - logmax;
return ((A * (unsigned long) p) >> shift) & (max - 1);
}
-/* Allocate an empty pointer set. */
+/* Allocate an empty pointer set. */
struct pointer_set_t *
pointer_set_create (void)
{
return result;
}
-/* Reclaims all memory associated with PSET. */
+/* Reclaims all memory associated with PSET. */
void pointer_set_destroy (struct pointer_set_t *pset)
{
XDELETEVEC (pset->slots);
XDELETE (pset);
}
-/* Returns nonzero if PSET contains P. P must be nonnull.
-
- Collisions are resolved by linear probing. More complicated
- collision management schemes are only useful when the load factor
- significantly exceeds 0.5, and we never let that happen. */
-int
-pointer_set_contains (struct pointer_set_t *pset, void *p)
-{
- size_t n = hash1 (p, pset->n_slots, pset->log_slots);
-
- while (true)
- {
- if (pset->slots[n] == p)
- return 1;
- else if (pset->slots[n] == 0)
- return 0;
- else
- {
- ++n;
- if (n == pset->n_slots)
- n = 0;
- }
- }
-}
-
/* Subroutine of pointer_set_insert. Inserts P into an empty
element of SLOTS, an array of length N_SLOTS. Returns nonzero
- if P was already present in N_SLOTS. */
+ if P was already present in N_SLOTS. */
static int
insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
{
}
/* Inserts P into PSET if it wasn't already there. Returns nonzero
- if it was already there. P must be nonnull. */
+ if it was already there. P must be nonnull. */
int
pointer_set_insert (struct pointer_set_t *pset, void *p)
{
return 1;
/* We've inserted a new element. Expand the table if necessary to keep
- the load factor small. */
+ the load factor small. */
++pset->n_elements;
if (pset->n_elements > pset->n_slots / 4)
{