ia64/xen-unstable

view tools/vtpm_manager/util/hashtable_itr.c @ 8740:3d7ea7972b39

Update patches for linux 2.6.15.

Signed-off-by: Christian Limpach <Christian.Limpach@cl.cam.ac.uk>
author cl349@firebug.cl.cam.ac.uk
date Thu Feb 02 17:16:00 2006 +0000 (2006-02-02)
parents 06d84bf87159
children ac814633799b
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 }