Branch data Line data Source code
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 : 0 : hashtable_iterator(struct hashtable *h)
13 : : {
14 : : unsigned int i, tablelength;
15 : 0 : struct hashtable_itr *itr = (struct hashtable_itr *)
16 : 0 : malloc(sizeof(struct hashtable_itr));
17 [ # # ]: 0 : if (NULL == itr) return NULL;
18 : 0 : itr->h = h;
19 : 0 : itr->e = NULL;
20 : 0 : itr->parent = NULL;
21 : 0 : tablelength = h->tablelength;
22 : 0 : itr->index = tablelength;
23 [ # # ]: 0 : if (0 == h->entrycount) return itr;
24 : :
25 [ # # ]: 0 : for (i = 0; i < tablelength; i++)
26 : : {
27 [ # # ]: 0 : if (NULL != h->table[i])
28 : : {
29 : 0 : itr->e = h->table[i];
30 : 0 : itr->index = i;
31 : 0 : break;
32 : : }
33 : : }
34 : 0 : 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 : 0 : hashtable_iterator_key(struct hashtable_itr *i)
43 : 0 : { return i->e->k; }
44 : :
45 : : void *
46 : 0 : hashtable_iterator_value(struct hashtable_itr *i)
47 : 0 : { 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 : 0 : hashtable_iterator_advance(struct hashtable_itr *itr)
55 : : {
56 : : unsigned int j,tablelength;
57 : : struct entry **table;
58 : : struct entry *next;
59 [ # # ]: 0 : if (NULL == itr->e) return 0; /* stupidity check */
60 : :
61 : 0 : next = itr->e->next;
62 [ # # ]: 0 : if (NULL != next)
63 : : {
64 : 0 : itr->parent = itr->e;
65 : 0 : itr->e = next;
66 : 0 : return -1;
67 : : }
68 : 0 : tablelength = itr->h->tablelength;
69 : 0 : itr->parent = NULL;
70 [ # # ]: 0 : if (tablelength <= (j = ++(itr->index)))
71 : : {
72 : 0 : itr->e = NULL;
73 : 0 : return 0;
74 : : }
75 : 0 : table = itr->h->table;
76 [ # # ]: 0 : while (NULL == (next = table[j]))
77 : : {
78 [ # # ]: 0 : if (++j >= tablelength)
79 : : {
80 : 0 : itr->index = tablelength;
81 : 0 : itr->e = NULL;
82 : 0 : return 0;
83 : : }
84 : : }
85 : 0 : itr->index = j;
86 : 0 : itr->e = next;
87 : 0 : 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 : 0 : hashtable_iterator_remove(struct hashtable_itr *itr)
100 : : {
101 : : struct entry *remember_e, *remember_parent;
102 : : int ret;
103 : :
104 : : /* Do the removal */
105 [ # # ]: 0 : if (NULL == (itr->parent))
106 : : {
107 : : /* element is head of a chain */
108 : 0 : itr->h->table[itr->index] = itr->e->next;
109 : : } else {
110 : : /* element is mid-chain */
111 : 0 : itr->parent->next = itr->e->next;
112 : : }
113 : : /* itr->e is now outside the hashtable */
114 : 0 : remember_e = itr->e;
115 : 0 : itr->h->entrycount--;
116 : 0 : freekey(remember_e->k);
117 : :
118 : : /* Advance the iterator, correcting the parent */
119 : 0 : remember_parent = itr->parent;
120 : 0 : ret = hashtable_iterator_advance(itr);
121 [ # # ]: 0 : if (itr->parent == remember_e) { itr->parent = remember_parent; }
122 : 0 : free(remember_e);
123 : 0 : return ret;
124 : : }
125 : :
126 : : /*****************************************************************************/
127 : : int /* returns zero if not found */
128 : 0 : 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 : 0 : hashvalue = hash(h,k);
135 : 0 : index = indexFor(h->tablelength,hashvalue);
136 : :
137 : 0 : e = h->table[index];
138 : 0 : parent = NULL;
139 [ # # ]: 0 : while (NULL != e)
140 : : {
141 : : /* Check hash value to short circuit heavier comparison */
142 [ # # ][ # # ]: 0 : if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
143 : : {
144 : 0 : itr->index = index;
145 : 0 : itr->e = e;
146 : 0 : itr->parent = parent;
147 : 0 : itr->h = h;
148 : 0 : return -1;
149 : : }
150 : 0 : parent = e;
151 : 0 : e = e->next;
152 : : }
153 : 0 : 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 : : */
|
