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