zc_hashtable.c 6.17 KB
Newer Older
Hardy Simpson's avatar
Hardy Simpson committed
1
/*
Hardy Simpson's avatar
Hardy Simpson committed
2
 * This file is part of the zlog Library.
Hardy Simpson's avatar
Hardy Simpson committed
3
 *
Hardy Simpson's avatar
Hardy Simpson committed
4
 * Copyright (C) 2011 by Hardy Simpson <HardySimpson1984@gmail.com>
Hardy Simpson's avatar
Hardy Simpson committed
5
 *
6
 * Licensed under the LGPL v2.1, see the file COPYING in base directory.
Hardy Simpson's avatar
Hardy Simpson committed
7 8
 */

Hardy Simpson's avatar
Hardy Simpson committed
9 10 11 12 13 14 15
#include <stdlib.h>
#include <errno.h>
#include <pthread.h>

#include "zc_defs.h"
#include "zc_hashtable.h"

Hardy Simpson's avatar
Hardy Simpson committed
16 17 18 19 20 21 22 23 24 25 26 27
struct zc_hashtable_s {
	size_t nelem;

	zc_hashtable_entry_t **tab;
	size_t tab_size;

	zc_hashtable_hash_fn hash;
	zc_hashtable_equal_fn equal;
	zc_hashtable_del_fn key_del;
	zc_hashtable_del_fn value_del;
};

Hardy Simpson's avatar
Hardy Simpson committed
28
zc_hashtable_t *zc_hashtable_new(size_t a_size,
Hardy Simpson's avatar
Hardy Simpson committed
29 30 31 32
				 zc_hashtable_hash_fn hash,
				 zc_hashtable_equal_fn equal,
				 zc_hashtable_del_fn key_del,
				 zc_hashtable_del_fn value_del)
Hardy Simpson's avatar
Hardy Simpson committed
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
{
	zc_hashtable_t *a_table;

	a_table = calloc(1, sizeof(*a_table));
	if (!a_table) {
		zc_error("calloc fail, errno[%d]", errno);
		return NULL;
	}

	a_table->tab = calloc(a_size, sizeof(*(a_table->tab)));
	if (!a_table->tab) {
		zc_error("calloc fail, errno[%d]", errno);
		free(a_table);
		return NULL;
	}
	a_table->tab_size = a_size;

	a_table->nelem = 0;
Hardy Simpson's avatar
Hardy Simpson committed
51 52
	a_table->hash = hash;
	a_table->equal = equal;
Hardy Simpson's avatar
Hardy Simpson committed
53 54

	/* these two could be NULL */
Hardy Simpson's avatar
Hardy Simpson committed
55 56
	a_table->key_del = key_del;
	a_table->value_del = value_del;
Hardy Simpson's avatar
Hardy Simpson committed
57 58 59 60 61 62 63 64 65 66

	return a_table;
}

void zc_hashtable_del(zc_hashtable_t * a_table)
{
	size_t i;
	zc_hashtable_entry_t *p;
	zc_hashtable_entry_t *q;

67 68 69 70 71
	if (!a_table) {
		zc_error("a_table[%p] is NULL, just do nothing", a_table);
		return;
	}

Hardy Simpson's avatar
Hardy Simpson committed
72 73 74
	for (i = 0; i < a_table->tab_size; i++) {
		for (p = (a_table->tab)[i]; p; p = q) {
			q = p->next;
Hardy Simpson's avatar
Hardy Simpson committed
75 76
			if (a_table->key_del) {
				a_table->key_del(p->key);
Hardy Simpson's avatar
Hardy Simpson committed
77
			}
Hardy Simpson's avatar
Hardy Simpson committed
78 79
			if (a_table->value_del) {
				a_table->value_del(p->value);
Hardy Simpson's avatar
Hardy Simpson committed
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
			}
			free(p);
		}
	}
	if (a_table->tab)
		free(a_table->tab);
	free(a_table);

	return;
}

void zc_hashtable_clean(zc_hashtable_t * a_table)
{
	size_t i;
	zc_hashtable_entry_t *p;
	zc_hashtable_entry_t *q;

	for (i = 0; i < a_table->tab_size; i++) {
		for (p = (a_table->tab)[i]; p; p = q) {
			q = p->next;
Hardy Simpson's avatar
Hardy Simpson committed
100 101
			if (a_table->key_del) {
				a_table->key_del(p->key);
Hardy Simpson's avatar
Hardy Simpson committed
102
			}
Hardy Simpson's avatar
Hardy Simpson committed
103 104
			if (a_table->value_del) {
				a_table->value_del(p->value);
Hardy Simpson's avatar
Hardy Simpson committed
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
			}
			free(p);
		}
		(a_table->tab)[i] = NULL;
	}
	a_table->nelem = 0;
	return;
}

static int zc_hashtable_rehash(zc_hashtable_t * a_table)
{
	size_t i;
	size_t j;
	size_t tab_size;
	zc_hashtable_entry_t **tab;
	zc_hashtable_entry_t *p;
	zc_hashtable_entry_t *q;

	tab_size = 2 * a_table->tab_size;
	tab = calloc(tab_size, sizeof(*tab));
	if (!tab) {
		zc_error("calloc fail, errno[%d]", errno);
		return -1;
	}

	for (i = 0; i < a_table->tab_size; i++) {
		for (p = (a_table->tab)[i]; p; p = q) {
			q = p->next;

			p->next = NULL;
			p->prev = NULL;
			j = p->hash_key % tab_size;
			if (tab[j]) {
				tab[j]->prev = p;
				p->next = tab[j];
			}
			tab[j] = p;
		}
	}
	free(a_table->tab);
	a_table->tab = tab;
	a_table->tab_size = tab_size;

	return 0;
}

151
zc_hashtable_entry_t *zc_hashtable_get_entry(zc_hashtable_t * a_table, const void *a_key)
Hardy Simpson's avatar
Hardy Simpson committed
152 153 154 155
{
	unsigned int i;
	zc_hashtable_entry_t *p;

Hardy Simpson's avatar
Hardy Simpson committed
156
	i = a_table->hash(a_key) % a_table->tab_size;
Hardy Simpson's avatar
Hardy Simpson committed
157
	for (p = (a_table->tab)[i]; p; p = p->next) {
Hardy Simpson's avatar
Hardy Simpson committed
158
		if (a_table->equal(a_key, p->key))
Hardy Simpson's avatar
Hardy Simpson committed
159 160 161 162 163 164
			return p;
	}

	return NULL;
}

165
void *zc_hashtable_get(zc_hashtable_t * a_table, const void *a_key)
Hardy Simpson's avatar
Hardy Simpson committed
166
{
Hardy Simpson's avatar
Hardy Simpson committed
167
	unsigned int i;
Hardy Simpson's avatar
Hardy Simpson committed
168 169
	zc_hashtable_entry_t *p;

Hardy Simpson's avatar
Hardy Simpson committed
170 171 172 173 174 175 176
	i = a_table->hash(a_key) % a_table->tab_size;
	for (p = (a_table->tab)[i]; p; p = p->next) {
		if (a_table->equal(a_key, p->key))
			return p->value;
	}

	return NULL;
Hardy Simpson's avatar
Hardy Simpson committed
177 178 179 180 181 182 183 184
}

int zc_hashtable_put(zc_hashtable_t * a_table, void *a_key, void *a_value)
{
	int rc = 0;
	unsigned int i;
	zc_hashtable_entry_t *p = NULL;

Hardy Simpson's avatar
Hardy Simpson committed
185
	i = a_table->hash(a_key) % a_table->tab_size;
Hardy Simpson's avatar
Hardy Simpson committed
186
	for (p = (a_table->tab)[i]; p; p = p->next) {
Hardy Simpson's avatar
Hardy Simpson committed
187
		if (a_table->equal(a_key, p->key))
Hardy Simpson's avatar
Hardy Simpson committed
188 189 190 191
			break;
	}

	if (p) {
Hardy Simpson's avatar
Hardy Simpson committed
192 193
		if (a_table->key_del) {
			a_table->key_del(p->key);
Hardy Simpson's avatar
Hardy Simpson committed
194
		}
Hardy Simpson's avatar
Hardy Simpson committed
195 196
		if (a_table->value_del) {
			a_table->value_del(p->value);
Hardy Simpson's avatar
Hardy Simpson committed
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
		}
		p->key = a_key;
		p->value = a_value;
		return 0;
	} else {
		if (a_table->nelem > a_table->tab_size * 1.3) {
			rc = zc_hashtable_rehash(a_table);
			if (rc) {
				zc_error("rehash fail");
				return -1;
			}
		}

		p = calloc(1, sizeof(*p));
		if (!p) {
			zc_error("calloc fail, errno[%d]", errno);
			return -1;
		}

Hardy Simpson's avatar
Hardy Simpson committed
216
		p->hash_key = a_table->hash(a_key);
Hardy Simpson's avatar
Hardy Simpson committed
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
		p->key = a_key;
		p->value = a_value;
		p->next = NULL;
		p->prev = NULL;

		i = p->hash_key % a_table->tab_size;
		if ((a_table->tab)[i]) {
			(a_table->tab)[i]->prev = p;
			p->next = (a_table->tab)[i];
		}
		(a_table->tab)[i] = p;
		a_table->nelem++;
	}

	return 0;
}

234
void zc_hashtable_remove(zc_hashtable_t * a_table, const void *a_key)
Hardy Simpson's avatar
Hardy Simpson committed
235 236 237 238
{
	zc_hashtable_entry_t *p;
	unsigned int i;

239
        if (!a_table || !a_key) {
240 241
		zc_error("a_table[%p] or a_key[%p] is NULL, just do nothing", a_table, a_key);
		return;
242 243
        }

Hardy Simpson's avatar
Hardy Simpson committed
244
	i = a_table->hash(a_key) % a_table->tab_size;
Hardy Simpson's avatar
Hardy Simpson committed
245
	for (p = (a_table->tab)[i]; p; p = p->next) {
Hardy Simpson's avatar
Hardy Simpson committed
246
		if (a_table->equal(a_key, p->key))
Hardy Simpson's avatar
Hardy Simpson committed
247 248 249 250
			break;
	}

	if (!p) {
251
		zc_error("p[%p] not found in hashtable", p);
Hardy Simpson's avatar
Hardy Simpson committed
252 253 254
		return;
	}

Hardy Simpson's avatar
Hardy Simpson committed
255 256
	if (a_table->key_del) {
		a_table->key_del(p->key);
Hardy Simpson's avatar
Hardy Simpson committed
257
	}
Hardy Simpson's avatar
Hardy Simpson committed
258 259
	if (a_table->value_del) {
		a_table->value_del(p->value);
Hardy Simpson's avatar
Hardy Simpson committed
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
	}

	if (p->next) {
		p->next->prev = p->prev;
	}
	if (p->prev) {
		p->prev->next = p->next;
	} else {
		unsigned int i;

		i = p->hash_key % a_table->tab_size;
		a_table->tab[i] = p->next;
	}

	free(p);
	a_table->nelem--;

	return;
}

zc_hashtable_entry_t *zc_hashtable_begin(zc_hashtable_t * a_table)
{
	size_t i;
	zc_hashtable_entry_t *p;

	for (i = 0; i < a_table->tab_size; i++) {
		for (p = (a_table->tab)[i]; p; p = p->next) {
			if (p)
				return p;
		}
	}

	return NULL;
}

295
zc_hashtable_entry_t *zc_hashtable_next(zc_hashtable_t * a_table, zc_hashtable_entry_t * a_entry)
Hardy Simpson's avatar
Hardy Simpson committed
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
{
	size_t i;
	size_t j;

	if (a_entry->next)
		return a_entry->next;

	i = a_entry->hash_key % a_table->tab_size;

	for (j = i + 1; j < a_table->tab_size; j++) {
		if ((a_table->tab)[j]) {
			return (a_table->tab)[j];
		}
	}

	return NULL;
}

/*******************************************************************************/

316
unsigned int zc_hashtable_str_hash(const void *str)
Hardy Simpson's avatar
Hardy Simpson committed
317
{
318
	unsigned int h = 5381;
Hardy Simpson's avatar
Hardy Simpson committed
319 320 321
	const char *p = (const char *)str;

	while (*p != '\0')
322
		h = ((h << 5) + h) + (*p++); /* hash * 33 + c */
Hardy Simpson's avatar
Hardy Simpson committed
323 324 325 326

	return h;
}

327
int zc_hashtable_str_equal(const void *key1, const void *key2)
Hardy Simpson's avatar
Hardy Simpson committed
328 329 330
{
	return (STRCMP((const char *)key1, ==, (const char *)key2));
}