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 */ 189