diff options
Diffstat (limited to 'source4/lib/json/linkhash.c')
-rw-r--r-- | source4/lib/json/linkhash.c | 217 |
1 files changed, 0 insertions, 217 deletions
diff --git a/source4/lib/json/linkhash.c b/source4/lib/json/linkhash.c deleted file mode 100644 index b04254b597..0000000000 --- a/source4/lib/json/linkhash.c +++ /dev/null @@ -1,217 +0,0 @@ -/* - * $Id: linkhash.c,v 1.4 2006/01/26 02:16:28 mclark Exp $ - * - * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd. - * Michael Clark <michael@metaparadigm.com> - * - * This library is free software; you can redistribute it and/or modify - * it under the terms of the MIT license. See COPYING for details. - * - */ - -#include "config.h" - -#include <stdio.h> -#include <string.h> -#include <stdlib.h> -#include <stdarg.h> -#include <stddef.h> -#include <limits.h> - -#include "linkhash.h" - -_NORETURN_ void lh_abort(const char *msg, ...) -{ - va_list ap; - va_start(ap, msg); - vprintf(msg, ap); - exit(1); -} - -unsigned long lh_ptr_hash(void *k) -{ - /* CAW: refactored to be 64bit nice */ - return (unsigned long)((((ptrdiff_t)k * LH_PRIME) >> 4) & ULONG_MAX); -} - -int lh_ptr_equal(void *k1, void *k2) -{ - return (k1 == k2); -} - -unsigned long lh_char_hash(void *k) -{ - unsigned int h = 0; - const char* data = k; - - while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME; - - return h; -} - -int lh_char_equal(void *k1, void *k2) -{ - return (strcmp((char*)k1, (char*)k2) == 0); -} - -struct lh_table* lh_table_new(int size, char *name, - lh_entry_free_fn *free_fn, - lh_hash_fn *hash_fn, - lh_equal_fn *equal_fn) -{ - int i; - struct lh_table *t; - - t = calloc(1, sizeof(struct lh_table)); - if(!t) lh_abort("lh_table_new: calloc failed\n"); - t->count = 0; - t->size = size; - t->name = name; - t->table = calloc(size, sizeof(struct lh_entry)); - if(!t->table) lh_abort("lh_table_new: calloc failed\n"); - t->free_fn = free_fn; - t->hash_fn = hash_fn; - t->equal_fn = equal_fn; - for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY; - return t; -} - -struct lh_table* lh_kchar_table_new(int size, char *name, - lh_entry_free_fn *free_fn) -{ - return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal); -} - -struct lh_table* lh_kptr_table_new(int size, char *name, - lh_entry_free_fn *free_fn) -{ - return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal); -} - -void lh_table_resize(struct lh_table *t, int new_size) -{ - struct lh_table *new_t; - struct lh_entry *ent; - - new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn); - ent = t->head; - while(ent) { - lh_table_insert(new_t, ent->k, ent->v); - ent = ent->next; - } - free(t->table); - t->table = new_t->table; - t->size = new_size; - t->head = new_t->head; - t->tail = new_t->tail; - t->resizes++; - free(new_t); -} - -void lh_table_free(struct lh_table *t) -{ - struct lh_entry *c; - for(c = t->head; c != NULL; c = c->next) { - if(t->free_fn) { - t->free_fn(c); - } - } - free(t->table); - free(t); -} - - -int lh_table_insert(struct lh_table *t, void *k, void *v) -{ - unsigned long h, n; - - t->inserts++; - if(t->count > t->size * 0.66) lh_table_resize(t, t->size * 2); - - h = t->hash_fn(k); - n = h % t->size; - - while( 1 ) { - if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break; - t->collisions++; - if(++n == t->size) n = 0; - } - - t->table[n].k = k; - t->table[n].v = v; - t->count++; - - if(t->head == NULL) { - t->head = t->tail = &t->table[n]; - t->table[n].next = t->table[n].prev = NULL; - } else { - t->tail->next = &t->table[n]; - t->table[n].prev = t->tail; - t->table[n].next = NULL; - t->tail = &t->table[n]; - } - - return 0; -} - - -struct lh_entry* lh_table_lookup_entry(struct lh_table *t, void *k) -{ - unsigned long h = t->hash_fn(k); - unsigned long n = h % t->size; - - t->lookups++; - while( 1 ) { - if(t->table[n].k == LH_EMPTY) return NULL; - if(t->table[n].k != LH_FREED && - t->equal_fn(t->table[n].k, k)) return &t->table[n]; - if(++n == t->size) n = 0; - } - return NULL; -} - - -void* lh_table_lookup(struct lh_table *t, void *k) -{ - struct lh_entry *e = lh_table_lookup_entry(t, k); - if(e) return e->v; - return NULL; -} - - -int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e) -{ - ptrdiff_t n = (ptrdiff_t)(e - t->table); /* CAW: fixed to be 64bit nice, still need the crazy negative case... */ - - /* CAW: this is bad, really bad, maybe stack goes other direction on this machine... */ - if(n < 0) { return -2; } - - if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1; - t->count--; - if(t->free_fn) t->free_fn(e); - t->table[n].v = NULL; - t->table[n].k = LH_FREED; - if(t->tail == &t->table[n] && t->head == &t->table[n]) { - t->head = t->tail = NULL; - } else if (t->head == &t->table[n]) { - t->head->next->prev = NULL; - t->head = t->head->next; - } else if (t->tail == &t->table[n]) { - t->tail->prev->next = NULL; - t->tail = t->tail->prev; - } else { - t->table[n].prev->next = t->table[n].next; - t->table[n].next->prev = t->table[n].prev; - } - t->table[n].next = t->table[n].prev = NULL; - return 0; -} - - -int lh_table_delete(struct lh_table *t, void *k) -{ - struct lh_entry *e = lh_table_lookup_entry(t, k); - if(!e) return -1; - return lh_table_delete_entry(t, e); -} - |