1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
2
3 #include "hashtable.h"
4 #include "hashtable_private.h"
5 #include "hashtable_itr.h"
6 #include <stdlib.h> /* defines NULL */
7
8 struct hashtable_itr {
9 struct hashtable *h;
10 struct entry *e;
11 struct entry *parent;
12 unsigned int index;
13 };
14
15 /*****************************************************************************/
16 /* hashtable_iterator - iterator constructor */
17
18 struct hashtable_itr *
hashtable_iterator(struct hashtable * h)19 hashtable_iterator(struct hashtable *h)
20 {
21 unsigned int i, tablelength;
22 struct hashtable_itr *itr = (struct hashtable_itr *)
23 malloc(sizeof(struct hashtable_itr));
24 if (NULL == itr) return NULL;
25 itr->h = h;
26 itr->e = NULL;
27 itr->parent = NULL;
28 tablelength = h->tablelength;
29 itr->index = tablelength;
30 if (0 == h->entrycount) return itr;
31
32 for (i = 0; i < tablelength; i++)
33 {
34 if (NULL != h->table[i])
35 {
36 itr->e = h->table[i];
37 itr->index = i;
38 break;
39 }
40 }
41 return itr;
42 }
43
44 /*****************************************************************************/
45 /* key - return the key of the (key,value) pair at the current position */
46 /* value - return the value of the (key,value) pair at the current position */
47
48 void *
hashtable_iterator_key(struct hashtable_itr * i)49 hashtable_iterator_key(struct hashtable_itr *i)
50 { return i->e->k; }
51
52 void *
hashtable_iterator_value(struct hashtable_itr * i)53 hashtable_iterator_value(struct hashtable_itr *i)
54 { return i->e->v; }
55
56 /*****************************************************************************/
57 /* advance - advance the iterator to the next element
58 * returns zero if advanced to end of table */
59
60 int
hashtable_iterator_advance(struct hashtable_itr * itr)61 hashtable_iterator_advance(struct hashtable_itr *itr)
62 {
63 unsigned int j,tablelength;
64 struct entry **table;
65 struct entry *next;
66 if (NULL == itr->e) return 0; /* stupidity check */
67
68 next = itr->e->next;
69 if (NULL != next)
70 {
71 itr->parent = itr->e;
72 itr->e = next;
73 return -1;
74 }
75 tablelength = itr->h->tablelength;
76 itr->parent = NULL;
77 if (tablelength <= (j = ++(itr->index)))
78 {
79 itr->e = NULL;
80 return 0;
81 }
82 table = itr->h->table;
83 while (NULL == (next = table[j]))
84 {
85 if (++j >= tablelength)
86 {
87 itr->index = tablelength;
88 itr->e = NULL;
89 return 0;
90 }
91 }
92 itr->index = j;
93 itr->e = next;
94 return -1;
95 }
96
97 /*****************************************************************************/
98 /* remove - remove the entry at the current iterator position
99 * and advance the iterator, if there is a successive
100 * element.
101 * If you want the value, read it before you remove:
102 * beware memory leaks if you don't.
103 * Returns zero if end of iteration. */
104
105 int
hashtable_iterator_remove(struct hashtable_itr * itr)106 hashtable_iterator_remove(struct hashtable_itr *itr)
107 {
108 struct entry *remember_e, *remember_parent;
109 int ret;
110
111 /* Do the removal */
112 if (NULL == (itr->parent))
113 {
114 /* element is head of a chain */
115 itr->h->table[itr->index] = itr->e->next;
116 } else {
117 /* element is mid-chain */
118 itr->parent->next = itr->e->next;
119 }
120 /* itr->e is now outside the hashtable */
121 remember_e = itr->e;
122 itr->h->entrycount--;
123 freekey(remember_e->k);
124
125 /* Advance the iterator, correcting the parent */
126 remember_parent = itr->parent;
127 ret = hashtable_iterator_advance(itr);
128 if (itr->parent == remember_e) { itr->parent = remember_parent; }
129 free(remember_e);
130 return ret;
131 }
132
133 /*****************************************************************************/
134 int /* returns zero if not found */
hashtable_iterator_search(struct hashtable_itr * itr,struct hashtable * h,void * k)135 hashtable_iterator_search(struct hashtable_itr *itr,
136 struct hashtable *h, void *k)
137 {
138 struct entry *e, *parent;
139 unsigned int hashvalue, index;
140
141 hashvalue = hash(h,k);
142 index = indexFor(h->tablelength,hashvalue);
143
144 e = h->table[index];
145 parent = NULL;
146 while (NULL != e)
147 {
148 /* Check hash value to short circuit heavier comparison */
149 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
150 {
151 itr->index = index;
152 itr->e = e;
153 itr->parent = parent;
154 itr->h = h;
155 return -1;
156 }
157 parent = e;
158 e = e->next;
159 }
160 return 0;
161 }
162
163
164 /*
165 * Copyright (c) 2002, 2004, Christopher Clark
166 * All rights reserved.
167 *
168 * Redistribution and use in source and binary forms, with or without
169 * modification, are permitted provided that the following conditions
170 * are met:
171 *
172 * * Redistributions of source code must retain the above copyright
173 * notice, this list of conditions and the following disclaimer.
174 *
175 * * Redistributions in binary form must reproduce the above copyright
176 * notice, this list of conditions and the following disclaimer in the
177 * documentation and/or other materials provided with the distribution.
178 *
179 * * Neither the name of the original author; nor the names of any contributors
180 * may be used to endorse or promote products derived from this software
181 * without specific prior written permission.
182 *
183 *
184 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
185 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
186 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
187 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
188 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
189 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
190 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
191 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
192 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
193 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
194 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
195 */
196