• source navigation  • diff markup  • identifier search  • freetext search  • 

Sources/json-c/linkhash.c

  1 /*
  2  * $Id: linkhash.c,v 1.4 2006/01/26 02:16:28 mclark Exp $
  3  *
  4  * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
  5  * Michael Clark <michael@metaparadigm.com>
  6  * Copyright (c) 2009 Hewlett-Packard Development Company, L.P.
  7  *
  8  * This library is free software; you can redistribute it and/or modify
  9  * it under the terms of the MIT license. See COPYING for details.
 10  *
 11  */
 12 
 13 #include <stdio.h>
 14 #include <string.h>
 15 #include <stdlib.h>
 16 #include <stdarg.h>
 17 #include <stddef.h>
 18 #include <limits.h>
 19 
 20 #include "linkhash.h"
 21 
 22 void lh_abort(const char *msg, ...)
 23 {
 24         va_list ap;
 25         va_start(ap, msg);
 26         vprintf(msg, ap);
 27         va_end(ap);
 28         exit(1);
 29 }
 30 
 31 unsigned long lh_ptr_hash(const void *k)
 32 {
 33         /* CAW: refactored to be 64bit nice */
 34         return (unsigned long)((((ptrdiff_t)k * LH_PRIME) >> 4) & ULONG_MAX);
 35 }
 36 
 37 int lh_ptr_equal(const void *k1, const void *k2)
 38 {
 39         return (k1 == k2);
 40 }
 41 
 42 unsigned long lh_char_hash(const void *k)
 43 {
 44         unsigned int h = 0;
 45         const char* data = (const char*)k;
 46  
 47         while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;
 48 
 49         return h;
 50 }
 51 
 52 int lh_char_equal(const void *k1, const void *k2)
 53 {
 54         return (strcmp((const char*)k1, (const char*)k2) == 0);
 55 }
 56 
 57 struct lh_table* lh_table_new(int size, const char *name,
 58                               lh_entry_free_fn *free_fn,
 59                               lh_hash_fn *hash_fn,
 60                               lh_equal_fn *equal_fn)
 61 {
 62         int i;
 63         struct lh_table *t;
 64 
 65         t = (struct lh_table*)calloc(1, sizeof(struct lh_table));
 66         if(!t) lh_abort("lh_table_new: calloc failed\n");
 67         t->count = 0;
 68         t->size = size;
 69         t->name = name;
 70         t->table = (struct lh_entry*)calloc(size, sizeof(struct lh_entry));
 71         if(!t->table) lh_abort("lh_table_new: calloc failed\n");
 72         t->free_fn = free_fn;
 73         t->hash_fn = hash_fn;
 74         t->equal_fn = equal_fn;
 75         for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;
 76         return t;
 77 }
 78 
 79 struct lh_table* lh_kchar_table_new(int size, const char *name,
 80                                     lh_entry_free_fn *free_fn)
 81 {
 82         return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal);
 83 }
 84 
 85 struct lh_table* lh_kptr_table_new(int size, const char *name,
 86                                    lh_entry_free_fn *free_fn)
 87 {
 88         return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal);
 89 }
 90 
 91 void lh_table_resize(struct lh_table *t, int new_size)
 92 {
 93         struct lh_table *new_t;
 94         struct lh_entry *ent;
 95 
 96         new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);
 97         ent = t->head;
 98         while(ent) {
 99                 lh_table_insert(new_t, ent->k, ent->v);
100                 ent = ent->next;
101         }
102         free(t->table);
103         t->table = new_t->table;
104         t->size = new_size;
105         t->head = new_t->head;
106         t->tail = new_t->tail;
107         t->resizes++;
108         free(new_t);
109 }
110 
111 void lh_table_free(struct lh_table *t)
112 {
113         struct lh_entry *c;
114         for(c = t->head; c != NULL; c = c->next) {
115                 if(t->free_fn) {
116                         t->free_fn(c);
117                 }
118         }
119         free(t->table);
120         free(t);
121 }
122 
123 
124 int lh_table_insert(struct lh_table *t, void *k, const void *v)
125 {
126         unsigned long h, n;
127 
128         t->inserts++;
129         if(t->count >= t->size * LH_LOAD_FACTOR) lh_table_resize(t, t->size * 2);
130 
131         h = t->hash_fn(k);
132         n = h % t->size;
133 
134         while( 1 ) {
135                 if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;
136                 t->collisions++;
137                 if ((int)++n == t->size) n = 0;
138         }
139 
140         t->table[n].k = k;
141         t->table[n].v = v;
142         t->count++;
143 
144         if(t->head == NULL) {
145                 t->head = t->tail = &t->table[n];
146                 t->table[n].next = t->table[n].prev = NULL;
147         } else {
148                 t->tail->next = &t->table[n];
149                 t->table[n].prev = t->tail;
150                 t->table[n].next = NULL;
151                 t->tail = &t->table[n];
152         }
153 
154         return 0;
155 }
156 
157 
158 struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k)
159 {
160         unsigned long h = t->hash_fn(k);
161         unsigned long n = h % t->size;
162         int count = 0;
163 
164         t->lookups++;
165         while( count < t->size ) {
166                 if(t->table[n].k == LH_EMPTY) return NULL;
167                 if(t->table[n].k != LH_FREED &&
168                    t->equal_fn(t->table[n].k, k)) return &t->table[n];
169                 if ((int)++n == t->size) n = 0;
170                 count++;
171         }
172         return NULL;
173 }
174 
175 
176 const void* lh_table_lookup(struct lh_table *t, const void *k)
177 {
178         void *result;
179         lh_table_lookup_ex(t, k, &result);
180         return result;
181 }
182 
183 json_bool lh_table_lookup_ex(struct lh_table* t, const void* k, void **v)
184 {
185         struct lh_entry *e = lh_table_lookup_entry(t, k);
186         if (e != NULL) {
187                 if (v != NULL) *v = (void *)e->v;
188                 return TRUE; /* key found */
189         }
190         if (v != NULL) *v = NULL;
191         return FALSE; /* key not found */
192 }
193 
194 int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)
195 {
196         ptrdiff_t n = (ptrdiff_t)(e - t->table); /* CAW: fixed to be 64bit nice, still need the crazy negative case... */
197 
198         /* CAW: this is bad, really bad, maybe stack goes other direction on this machine... */
199         if(n < 0) { return -2; }
200 
201         if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1;
202         t->count--;
203         if(t->free_fn) t->free_fn(e);
204         t->table[n].v = NULL;
205         t->table[n].k = LH_FREED;
206         if(t->tail == &t->table[n] && t->head == &t->table[n]) {
207                 t->head = t->tail = NULL;
208         } else if (t->head == &t->table[n]) {
209                 t->head->next->prev = NULL;
210                 t->head = t->head->next;
211         } else if (t->tail == &t->table[n]) {
212                 t->tail->prev->next = NULL;
213                 t->tail = t->tail->prev;
214         } else {
215                 t->table[n].prev->next = t->table[n].next;
216                 t->table[n].next->prev = t->table[n].prev;
217         }
218         t->table[n].next = t->table[n].prev = NULL;
219         return 0;
220 }
221 
222 
223 int lh_table_delete(struct lh_table *t, const void *k)
224 {
225         struct lh_entry *e = lh_table_lookup_entry(t, k);
226         if(!e) return -1;
227         return lh_table_delete_entry(t, e);
228 }
229 
230 int lh_table_length(struct lh_table *t)
231 {
232         return t->count;
233 }
234 

This page was automatically generated by LXR 0.3.1.  •  OpenWrt