shithub: sl

ref: a70379d7e4b822f532fb0a8ccdd1624a90b64a68
dir: /src/htable.c/

/*
  functions common to all hash table instantiations
*/

#include "sl.h"
#include "htable.h"
#include "hashing.h"

static sl_constfn sl_v
nextipow2(sl_v i)
{
	if(i == 0)
		return 1;
	i |= i >> 1;
	i |= i >> 2;
	i |= i >> 4;
	i |= i >> 8;
	i |= i >> 16;
#if defined(BITS64)
	i |= i >> 32;
#endif
	i++;
	return i ? i : TOP_BIT;
}

sl_htable *
htable_new(sl_htable *h, int size)
{
	if(size <= HT_N_INLINE/2){
		size = HT_N_INLINE;
		h->table = &h->_space[0];
	}else{
		size = nextipow2(size);
		size *= 2; // 2 pointers per key/value pair
		size *= 2; // aim for 50% occupancy
		if((h->table = MEM_ALLOC(size * sizeof(*h->table))) == nil)
			return nil;
	}
	h->size = size;
	h->i = 0;
	for(int i = 0; i < size; i++)
		h->table[i] = HT_NOTFOUND;
	return h;
}

void
htable_free(sl_htable *h)
{
	if(h->table != &h->_space[0])
		MEM_FREE(h->table);
}

// empty and reduce size
void
htable_reset(sl_htable *h, int sz)
{
	sz = nextipow2(sz);
	if(h->size > sz*4 && h->table != &h->_space[0]){
		MEM_FREE(h->table);
		htable_new(h, sz);
	}else{
		for(usize i = 0, hsz = h->size; i < hsz; i++)
			h->table[i] = HT_NOTFOUND;
	}
}