root/src/json-lib/linkhash.c

Revision efa9375336eec306ede14a9a1032985a71482810, 4.8 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 4 years ago)

refs #294 resmon no support arbitrary json objects

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