Mercurial > ~mikael > mcabber > hg
comparison mcabber/libjabber/hashtable.c @ 25:bf3d6e241714
[/trunk] Changeset 41 by mikael
* Add libjabber to trunk. Let the game begin! :-)
author | mikael |
---|---|
date | Sun, 27 Mar 2005 20:18:21 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
24:e88b15cbf2de | 25:bf3d6e241714 |
---|---|
1 /* | |
2 The contents of this file are subject to the Mozilla Public License | |
3 Version 1.1 (the "License"); you may not use this file except in | |
4 csompliance with the License. You may obtain a copy of the License at | |
5 http://www.mozilla.org/MPL/ | |
6 | |
7 Software distributed under the License is distributed on an "AS IS" | |
8 basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the | |
9 License for the specific language governing rights and limitations | |
10 under the License. | |
11 | |
12 The Original Code is expat. | |
13 | |
14 The Initial Developer of the Original Code is James Clark. | |
15 Portions created by James Clark are Copyright (C) 1998, 1999 | |
16 James Clark. All Rights Reserved. | |
17 | |
18 Contributor(s): | |
19 | |
20 Alternatively, the contents of this file may be used under the terms | |
21 of the GNU General Public License (the "GPL"), in which case the | |
22 provisions of the GPL are applicable instead of those above. If you | |
23 wish to allow use of your version of this file only under the terms of | |
24 the GPL and not to allow others to use your version of this file under | |
25 the MPL, indicate your decision by deleting the provisions above and | |
26 replace them with the notice and other provisions required by the | |
27 GPL. If you do not delete the provisions above, a recipient may use | |
28 your version of this file under either the MPL or the GPL. | |
29 */ | |
30 | |
31 #include "xmldef.h" | |
32 | |
33 #ifdef XML_UNICODE_WCHAR_T | |
34 #ifndef XML_UNICODE | |
35 #define XML_UNICODE | |
36 #endif | |
37 #endif | |
38 | |
39 #include "hashtable.h" | |
40 | |
41 #define INIT_SIZE 64 | |
42 | |
43 static | |
44 int keyeq(KEY s1, KEY s2) | |
45 { | |
46 for (; *s1 == *s2; s1++, s2++) | |
47 if (*s1 == 0) | |
48 return 1; | |
49 return 0; | |
50 } | |
51 | |
52 static | |
53 unsigned long hash(KEY s) | |
54 { | |
55 unsigned long h = 0; | |
56 while (*s) | |
57 h = (h << 5) + h + (unsigned char)*s++; | |
58 return h; | |
59 } | |
60 | |
61 NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize) | |
62 { | |
63 size_t i; | |
64 if (table->size == 0) { | |
65 if (!createSize) | |
66 return 0; | |
67 table->v = calloc(INIT_SIZE, sizeof(NAMED *)); | |
68 if (!table->v) | |
69 return 0; | |
70 table->size = INIT_SIZE; | |
71 table->usedLim = INIT_SIZE / 2; | |
72 i = hash(name) & (table->size - 1); | |
73 } | |
74 else { | |
75 unsigned long h = hash(name); | |
76 for (i = h & (table->size - 1); | |
77 table->v[i]; | |
78 i == 0 ? i = table->size - 1 : --i) { | |
79 if (keyeq(name, table->v[i]->name)) | |
80 return table->v[i]; | |
81 } | |
82 if (!createSize) | |
83 return 0; | |
84 if (table->used == table->usedLim) { | |
85 /* check for overflow */ | |
86 size_t newSize = table->size * 2; | |
87 NAMED **newV = calloc(newSize, sizeof(NAMED *)); | |
88 if (!newV) | |
89 return 0; | |
90 for (i = 0; i < table->size; i++) | |
91 if (table->v[i]) { | |
92 size_t j; | |
93 for (j = hash(table->v[i]->name) & (newSize - 1); | |
94 newV[j]; | |
95 j == 0 ? j = newSize - 1 : --j) | |
96 ; | |
97 newV[j] = table->v[i]; | |
98 } | |
99 free(table->v); | |
100 table->v = newV; | |
101 table->size = newSize; | |
102 table->usedLim = newSize/2; | |
103 for (i = h & (table->size - 1); | |
104 table->v[i]; | |
105 i == 0 ? i = table->size - 1 : --i) | |
106 ; | |
107 } | |
108 } | |
109 table->v[i] = calloc(1, createSize); | |
110 if (!table->v[i]) | |
111 return 0; | |
112 table->v[i]->name = name; | |
113 (table->used)++; | |
114 return table->v[i]; | |
115 } | |
116 | |
117 void hashTableDestroy(HASH_TABLE *table) | |
118 { | |
119 size_t i; | |
120 for (i = 0; i < table->size; i++) { | |
121 NAMED *p = table->v[i]; | |
122 if (p) | |
123 free(p); | |
124 } | |
125 free(table->v); | |
126 } | |
127 | |
128 void hashTableInit(HASH_TABLE *p) | |
129 { | |
130 p->size = 0; | |
131 p->usedLim = 0; | |
132 p->used = 0; | |
133 p->v = 0; | |
134 } | |
135 | |
136 void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table) | |
137 { | |
138 iter->p = table->v; | |
139 iter->end = iter->p + table->size; | |
140 } | |
141 | |
142 NAMED *hashTableIterNext(HASH_TABLE_ITER *iter) | |
143 { | |
144 while (iter->p != iter->end) { | |
145 NAMED *tem = *(iter->p)++; | |
146 if (tem) | |
147 return tem; | |
148 } | |
149 return 0; | |
150 } | |
151 |