1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
4 #include "hashtable_private.h"
5 #include "hashtable_itr.h"
6 #include <stdlib.h> /* defines NULL */
8 /*****************************************************************************/
9 /* hashtable_iterator - iterator constructor */
11 struct hashtable_itr *
12 hashtable_iterator(struct hashtable *h)
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;
21 tablelength = h->tablelength;
22 itr->index = tablelength;
23 if (0 == h->entrycount) return itr;
25 for (i = 0; i < tablelength; i++)
27 if (NULL != h->table[i])
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 */
42 hashtable_iterator_key(struct hashtable_itr *i)
46 hashtable_iterator_value(struct hashtable_itr *i)
49 /*****************************************************************************/
50 /* advance - advance the iterator to the next element
51 * returns zero if advanced to end of table */
54 hashtable_iterator_advance(struct hashtable_itr *itr)
56 unsigned int j,tablelength;
59 if (NULL == itr->e) return 0; /* stupidity check */
68 tablelength = itr->h->tablelength;
70 if (tablelength <= (j = ++(itr->index)))
75 table = itr->h->table;
76 while (NULL == (next = table[j]))
78 if (++j >= tablelength)
80 itr->index = tablelength;
90 /*****************************************************************************/
91 /* remove - remove the entry at the current iterator position
92 * and advance the iterator, if there is a successive
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. */
99 hashtable_iterator_remove(struct hashtable_itr *itr)
101 struct entry *remember_e, *remember_parent;
105 if (NULL == (itr->parent))
107 /* element is head of a chain */
108 itr->h->table[itr->index] = itr->e->next;
110 /* element is mid-chain */
111 itr->parent->next = itr->e->next;
113 /* itr->e is now outside the hashtable */
115 itr->h->entrycount--;
116 freekey(remember_e->k);
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; }
126 /*****************************************************************************/
127 int /* returns zero if not found */
128 hashtable_iterator_search(struct hashtable_itr *itr,
129 struct hashtable *h, void *k)
131 struct entry *e, *parent;
132 unsigned int hashvalue, index;
134 hashvalue = hash(h,k);
135 index = indexFor(h->tablelength,hashvalue);
141 /* Check hash value to short circuit heavier comparison */
142 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
146 itr->parent = parent;
158 * Copyright (c) 2002, 2004, Christopher Clark
159 * All rights reserved.
161 * Redistribution and use in source and binary forms, with or without
162 * modification, are permitted provided that the following conditions
165 * * Redistributions of source code must retain the above copyright
166 * notice, this list of conditions and the following disclaimer.
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.
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.
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.