hsearch.c raw

   1  #define _GNU_SOURCE
   2  #include <stdlib.h>
   3  #include <string.h>
   4  #include <search.h>
   5  
   6  /*
   7  open addressing hash table with 2^n table size
   8  quadratic probing is used in case of hash collision
   9  tab indices and hash are size_t
  10  after resize fails with ENOMEM the state of tab is still usable
  11  
  12  with the posix api items cannot be iterated and length cannot be queried
  13  */
  14  
  15  #define MINSIZE 8
  16  #define MAXSIZE ((size_t)-1/2 + 1)
  17  
  18  struct __tab {
  19  	ENTRY *entries;
  20  	size_t mask;
  21  	size_t used;
  22  };
  23  
  24  static struct hsearch_data htab;
  25  
  26  static int __hcreate_r(size_t, struct hsearch_data *);
  27  static void __hdestroy_r(struct hsearch_data *);
  28  static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
  29  
  30  static size_t keyhash(char *k)
  31  {
  32  	unsigned char *p = (void *)k;
  33  	size_t h = 0;
  34  
  35  	while (*p)
  36  		h = 31*h + *p++;
  37  	return h;
  38  }
  39  
  40  static int resize(size_t nel, struct hsearch_data *htab)
  41  {
  42  	size_t newsize;
  43  	size_t i, j;
  44  	ENTRY *e, *newe;
  45  	ENTRY *oldtab = htab->__tab->entries;
  46  	ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
  47  
  48  	if (nel > MAXSIZE)
  49  		nel = MAXSIZE;
  50  	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
  51  	htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
  52  	if (!htab->__tab->entries) {
  53  		htab->__tab->entries = oldtab;
  54  		return 0;
  55  	}
  56  	htab->__tab->mask = newsize - 1;
  57  	if (!oldtab)
  58  		return 1;
  59  	for (e = oldtab; e < oldend; e++)
  60  		if (e->key) {
  61  			for (i=keyhash(e->key),j=1; ; i+=j++) {
  62  				newe = htab->__tab->entries + (i & htab->__tab->mask);
  63  				if (!newe->key)
  64  					break;
  65  			}
  66  			*newe = *e;
  67  		}
  68  	free(oldtab);
  69  	return 1;
  70  }
  71  
  72  int hcreate(size_t nel)
  73  {
  74  	return __hcreate_r(nel, &htab);
  75  }
  76  
  77  void hdestroy(void)
  78  {
  79  	__hdestroy_r(&htab);
  80  }
  81  
  82  static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
  83  {
  84  	size_t i, j;
  85  	ENTRY *e;
  86  
  87  	for (i=hash,j=1; ; i+=j++) {
  88  		e = htab->__tab->entries + (i & htab->__tab->mask);
  89  		if (!e->key || strcmp(e->key, key) == 0)
  90  			break;
  91  	}
  92  	return e;
  93  }
  94  
  95  ENTRY *hsearch(ENTRY item, ACTION action)
  96  {
  97  	ENTRY *e;
  98  
  99  	__hsearch_r(item, action, &e, &htab);
 100  	return e;
 101  }
 102  
 103  static int __hcreate_r(size_t nel, struct hsearch_data *htab)
 104  {
 105  	int r;
 106  
 107  	htab->__tab = calloc(1, sizeof *htab->__tab);
 108  	if (!htab->__tab)
 109  		return 0;
 110  	r = resize(nel, htab);
 111  	if (r == 0) {
 112  		free(htab->__tab);
 113  		htab->__tab = 0;
 114  	}
 115  	return r;
 116  }
 117  weak_alias(__hcreate_r, hcreate_r);
 118  
 119  static void __hdestroy_r(struct hsearch_data *htab)
 120  {
 121  	if (htab->__tab) free(htab->__tab->entries);
 122  	free(htab->__tab);
 123  	htab->__tab = 0;
 124  }
 125  weak_alias(__hdestroy_r, hdestroy_r);
 126  
 127  static int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
 128  {
 129  	size_t hash = keyhash(item.key);
 130  	ENTRY *e = lookup(item.key, hash, htab);
 131  
 132  	if (e->key) {
 133  		*retval = e;
 134  		return 1;
 135  	}
 136  	if (action == FIND) {
 137  		*retval = 0;
 138  		return 0;
 139  	}
 140  	*e = item;
 141  	if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
 142  		if (!resize(2*htab->__tab->used, htab)) {
 143  			htab->__tab->used--;
 144  			e->key = 0;
 145  			*retval = 0;
 146  			return 0;
 147  		}
 148  		e = lookup(item.key, hash, htab);
 149  	}
 150  	*retval = e;
 151  	return 1;
 152  }
 153  weak_alias(__hsearch_r, hsearch_r);
 154