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