ia64/xen-unstable

view tools/vtpm_manager/util/hashtable_itr.c @ 6946:e703abaf6e3d

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