#include "config.h"
#include "system.h"
#include "pointer-set.h"
struct pointer_set_t
{
size_t log_slots;
size_t n_slots;
size_t n_elements;
void **slots;
};
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;
#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);
}
struct pointer_set_t *
pointer_set_create (void)
{
struct pointer_set_t *result = XNEW (struct pointer_set_t);
result->n_elements = 0;
result->log_slots = 8;
result->n_slots = (size_t) 1 << result->log_slots;
result->slots = XCNEWVEC (void *, result->n_slots);
return result;
}
void
pointer_set_destroy (struct pointer_set_t *pset)
{
XDELETEVEC (pset->slots);
XDELETE (pset);
}
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;
}
}
}
static inline size_t
insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
{
size_t n = hash1 (p, n_slots, log_slots);
while (true)
{
if (slots[n] == p || slots[n] == 0)
return n;
else
{
++n;
if (n == n_slots)
n = 0;
}
}
}
int
pointer_set_insert (struct pointer_set_t *pset, void *p)
{
size_t n;
if (pset->n_elements > pset->n_slots / 4)
{
size_t new_log_slots = pset->log_slots + 1;
size_t new_n_slots = pset->n_slots * 2;
void **new_slots = XCNEWVEC (void *, new_n_slots);
size_t i;
for (i = 0; i < pset->n_slots; ++i)
{
void *value = pset->slots[i];
n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
new_slots[n] = value;
}
XDELETEVEC (pset->slots);
pset->n_slots = new_n_slots;
pset->log_slots = new_log_slots;
pset->slots = new_slots;
}
n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
if (pset->slots[n])
return 1;
pset->slots[n] = p;
++pset->n_elements;
return 0;
}
void pointer_set_traverse (struct pointer_set_t *pset,
bool (*fn) (void *, void *), void *data)
{
size_t i;
for (i = 0; i < pset->n_slots; ++i)
if (pset->slots[i] && !fn (pset->slots[i], data))
break;
}
struct pointer_map_t
{
size_t log_slots;
size_t n_slots;
size_t n_elements;
void **keys;
void **values;
};
struct pointer_map_t *
pointer_map_create (void)
{
struct pointer_map_t *result = XNEW (struct pointer_map_t);
result->n_elements = 0;
result->log_slots = 8;
result->n_slots = (size_t) 1 << result->log_slots;
result->keys = XCNEWVEC (void *, result->n_slots);
result->values = XCNEWVEC (void *, result->n_slots);
return result;
}
void pointer_map_destroy (struct pointer_map_t *pmap)
{
XDELETEVEC (pmap->keys);
XDELETEVEC (pmap->values);
XDELETE (pmap);
}
void **
pointer_map_contains (struct pointer_map_t *pmap, void *p)
{
size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
while (true)
{
if (pmap->keys[n] == p)
return &pmap->values[n];
else if (pmap->keys[n] == 0)
return NULL;
else
{
++n;
if (n == pmap->n_slots)
n = 0;
}
}
}
void **
pointer_map_insert (struct pointer_map_t *pmap, void *p)
{
size_t n;
if (pmap->n_elements > pmap->n_slots / 4)
{
size_t new_log_slots = pmap->log_slots + 1;
size_t new_n_slots = pmap->n_slots * 2;
void **new_keys = XCNEWVEC (void *, new_n_slots);
void **new_values = XCNEWVEC (void *, new_n_slots);
size_t i;
for (i = 0; i < pmap->n_slots; ++i)
if (pmap->keys[i])
{
void *key = pmap->keys[i];
n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
new_keys[n] = key;
new_values[n] = pmap->values[i];
}
XDELETEVEC (pmap->keys);
XDELETEVEC (pmap->values);
pmap->n_slots = new_n_slots;
pmap->log_slots = new_log_slots;
pmap->keys = new_keys;
pmap->values = new_values;
}
n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
if (!pmap->keys[n])
{
++pmap->n_elements;
pmap->keys[n] = p;
}
return &pmap->values[n];
}
void pointer_map_traverse (struct pointer_map_t *pmap,
bool (*fn) (void *, void **, void *), void *data)
{
size_t i;
for (i = 0; i < pmap->n_slots; ++i)
if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
break;
}