musl/src/search/hsearch.c

#define _GNU_SOURCE
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include "libc.h"

/*
open addressing hash table with 2^n table size
quadratic probing is used in case of hash collision
tab indices and hash are size_t
after resize fails with ENOMEM the state of tab is still usable

with the posix api items cannot be iterated and length cannot be queried
*/

#define MINSIZE 8
#define MAXSIZE ((size_t)-1/2 + 1)

struct __tab {
	ENTRY *entries;
	size_t mask;
	size_t used;
};

static struct hsearch_data htab;

int __hcreate_r(size_t, struct hsearch_data *);
void __hdestroy_r(struct hsearch_data *);
int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);

static size_t keyhash(char *k)
{
	unsigned char *p = (void *)k;
	size_t h = 0;

	while (*p)
		h = 31*h + *p++;
	return h;
}

static int resize(size_t nel, struct hsearch_data *htab)
{
	size_t newsize;
	size_t i, j;
	ENTRY *e, *newe;
	ENTRY *oldtab = htab->__tab->entries;
	ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;

	if (nel > MAXSIZE)
		nel = MAXSIZE;
	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
	htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
	if (!htab->__tab->entries) {
		htab->__tab->entries = oldtab;
		return 0;
	}
	htab->__tab->mask = newsize - 1;
	if (!oldtab)
		return 1;
	for (e = oldtab; e < oldend; e++)
		if (e->key) {
			for (i=keyhash(e->key),j=1; ; i+=j++) {
				newe = htab->__tab->entries + (i & htab->__tab->mask);
				if (!newe->key)
					break;
			}
			*newe = *e;
		}
	free(oldtab);
	return 1;
}

int hcreate(size_t nel)
{
	return __hcreate_r(nel, &htab);
}

void hdestroy(void)
{
	__hdestroy_r(&htab);
}

static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
{
	size_t i, j;
	ENTRY *e;

	for (i=hash,j=1; ; i+=j++) {
		e = htab->__tab->entries + (i & htab->__tab->mask);
		if (!e->key || strcmp(e->key, key) == 0)
			break;
	}
	return e;
}

ENTRY *hsearch(ENTRY item, ACTION action)
{
	ENTRY *e;

	__hsearch_r(item, action, &e, &htab);
	return e;
}

int __hcreate_r(size_t nel, struct hsearch_data *htab)
{
	int r;

	htab->__tab = calloc(1, sizeof *htab->__tab);
	if (!htab->__tab)
		return 0;
	r = resize(nel, htab);
	if (r == 0) {
		free(htab->__tab);
		htab->__tab = 0;
	}
	return r;
}
weak_alias(__hcreate_r, hcreate_r);

void __hdestroy_r(struct hsearch_data *htab)
{
	if (htab->__tab) free(htab->__tab->entries);
	free(htab->__tab);
	htab->__tab = 0;
}
weak_alias(__hdestroy_r, hdestroy_r);

int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
{
	size_t hash = keyhash(item.key);
	ENTRY *e = lookup(item.key, hash, htab);

	if (e->key) {
		*retval = e;
		return 1;
	}
	if (action == FIND) {
		*retval = 0;
		return 0;
	}
	*e = item;
	if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
		if (!resize(2*htab->__tab->used, htab)) {
			htab->__tab->used--;
			e->key = 0;
			*retval = 0;
			return 0;
		}
		e = lookup(item.key, hash, htab);
	}
	*retval = e;
	return 1;
}
weak_alias(__hsearch_r, hsearch_r);