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