root/trunk/fl_hash.c

Revision 18, 3.7 kB (checked in by george, 8 years ago)

friendster changes. numerous stability fixes.

Line 
1 /*
2   +----------------------------------------------------------------------+
3   | PHP Version 4                                                        |
4   +----------------------------------------------------------------------+
5   | Copyright (c) 1997-2003 The PHP Group                                |
6   +----------------------------------------------------------------------+
7   | This source file is subject to version 2.02 of the PHP license,      |
8   | that is bundled with this package in the file LICENSE, and is        |
9   | available at through the world-wide-web at                           |
10   | http://www.php.net/license/2_02.txt.                                 |
11   | If you did not receive a copy of the PHP license and are unable to   |
12   | obtain it through the world-wide-web, please send a note to          |
13   | license@php.net so we can mail you a copy immediately.               |
14   +----------------------------------------------------------------------+
15   | Author: Thies C. Arntzen <thies@php.net>                             |
16   |         Sterling Hughes <sterling@php.net>                           |
17   +----------------------------------------------------------------------+
18
19   $Id: fl_hash.c,v 1.1.1.1 2004/02/17 23:31:44 sterling Exp $
20 */
21
22 #include <stdlib.h>
23 #include <string.h>
24 #include "php_fastxsl.h"
25 #include "fl_hash.h"
26
27 FL_Hash *fl_hash_new(FL_Allocator *mems, FL_HashDtor dtor)
28 {
29         FL_Hash *table;
30
31         table = mems->calloc_func(1, sizeof(FL_Hash));
32         table->dtor = dtor;
33         table->mems = mems;
34
35         return table;
36 }
37
38 void fl_hash_free(FL_Hash *table)
39 {
40         FL_Bucket *cur;
41         FL_Bucket *next;
42         FL_Allocator *mems;
43         int     i;
44
45         mems = table->mems;
46        
47         for (i = 0; i < FL_HASH_SIZE; i++) {
48                 cur = table->buckets[i];
49                 while (cur) {
50                         next = cur->next;
51
52                         if (table->dtor) table->dtor(cur->data);
53                         mems->free_func(cur->key);
54                         mems->free_func(cur);
55
56                         cur = next;
57                 }
58         }
59         mems->free_func(table);
60 }
61
62 static unsigned int hash_hash(const char *key, int length)
63 {
64         unsigned int hash = 0;
65
66         while (--length)
67                 hash = hash * 65599 + *key++;
68
69         return hash;
70 }
71
72 void *fl_hash_find(FL_Hash *table, const void *key, int length)
73 {
74         FL_Bucket       *b;
75         unsigned int  hash = hash_hash(key, length) % FL_HASH_SIZE;
76         for (b = table->buckets[ hash ]; b; b = b->next) {
77                 if (hash != b->hash) continue;
78                 if (length != b->length) continue;
79                 if (memcmp(key, b->key, length)) continue;
80                 return b->data;
81         }
82
83         return NULL;
84 }
85
86 int fl_hash_add(FL_Hash *table, char *key, int length, void *data)
87 {
88         FL_Bucket       *b, *ptr;
89         unsigned int  hash;
90        
91         hash = hash_hash(key, length) % FL_HASH_SIZE;
92         /* check hash for dupes */
93         ptr = table->buckets[ hash ];
94         while(ptr) {
95                 if(!strcmp(ptr->key, key)) {
96                         return 0;
97                 }
98                 ptr = ptr->next;
99         }
100
101         b = table->mems->malloc_func(sizeof(FL_Bucket));
102         b->key = table->mems->malloc_func(length + 1);
103         memcpy(b->key, key, length);
104         b->key[length] = 0;
105         b->length = length;
106         b->hash = hash;
107         b->data = data;
108         b->next = table->buckets[ hash ];
109
110         table->buckets[ hash ] = b;
111         table->nElements++;
112         return 1;
113 }
114
115 void fl_hash_delete(FL_Hash *table, char *key, int length)
116 {
117         FL_Bucket       *b;
118         FL_Bucket       *prev = NULL;
119         unsigned int  hash;
120
121         hash = hash_hash(key, length) % FL_HASH_SIZE;
122         for (b = table->buckets[ hash ]; b; b = b->next) {
123                 if (hash != b->hash || length != b->length || memcmp(key, b->key, length)) {
124                         prev = b;
125                         continue;
126                 }
127
128                 /* unlink */
129                 if (prev) {
130                         prev->next = b->next;
131                 } else {
132                         table->buckets[hash] = b->next;
133                 }
134                
135                 if (table->dtor) table->dtor(b->data);
136                 table->mems->free_func(b->key);
137                 table->mems->free_func(b);
138
139                 break;
140         }
141 }
142
143 /*
144 Local variables:
145 tab-width: 4
146 c-basic-offset: 4
147 End:
148 vim600: noet sw=4 ts=4 fdm=marker
149 vim<600: noet sw=4 ts=4
150 */
Note: See TracBrowser for help on using the browser.