ia64/xen-unstable

view tools/vtpm_manager/util/hashtable.h @ 8977:f84d5cdd9895

Clean up segment selector fixup and validation.

Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@firebug.cl.cam.ac.uk
date Thu Feb 23 14:43:45 2006 +0100 (2006-02-23)
parents 06d84bf87159
children
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 */
36 #ifndef __HASHTABLE_CWC22_H__
37 #define __HASHTABLE_CWC22_H__
39 struct hashtable;
41 /* Example of use:
42 *
43 * struct hashtable *h;
44 * struct some_key *k;
45 * struct some_value *v;
46 *
47 * static unsigned int hash_from_key_fn( void *k );
48 * static int keys_equal_fn ( void *key1, void *key2 );
49 *
50 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
51 * k = (struct some_key *) malloc(sizeof(struct some_key));
52 * v = (struct some_value *) malloc(sizeof(struct some_value));
53 *
54 * (initialise k and v to suitable values)
55 *
56 * if (! hashtable_insert(h,k,v) )
57 * { exit(-1); }
58 *
59 * if (NULL == (found = hashtable_search(h,k) ))
60 * { printf("not found!"); }
61 *
62 * if (NULL == (found = hashtable_remove(h,k) ))
63 * { printf("Not found\n"); }
64 *
65 */
67 /* Macros may be used to define type-safe(r) hashtable access functions, with
68 * methods specialized to take known key and value types as parameters.
69 *
70 * Example:
71 *
72 * Insert this at the start of your file:
73 *
74 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
75 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
76 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
77 *
78 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
79 * These operate just like hashtable_insert etc., with the same parameters,
80 * but their function signatures have 'struct some_key *' rather than
81 * 'void *', and hence can generate compile time errors if your program is
82 * supplying incorrect data as a key (and similarly for value).
83 *
84 * Note that the hash and key equality functions passed to create_hashtable
85 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
86 * a difficult issue as they're only defined and passed once, and the other
87 * functions will ensure that only valid keys are supplied to them.
88 *
89 * The cost for this checking is increased code size and runtime overhead
90 * - if performance is important, it may be worth switching back to the
91 * unsafe methods once your program has been debugged with the safe methods.
92 * This just requires switching to some simple alternative defines - eg:
93 * #define insert_some hashtable_insert
94 *
95 */
97 /*****************************************************************************
98 * create_hashtable
100 * @name create_hashtable
101 * @param minsize minimum initial size of hashtable
102 * @param hashfunction function for hashing keys
103 * @param key_eq_fn function for determining key equality
104 * @return newly created hashtable or NULL on failure
105 */
107 struct hashtable *
108 create_hashtable(unsigned int minsize,
109 unsigned int (*hashfunction) (void*),
110 int (*key_eq_fn) (void*,void*));
112 /*****************************************************************************
113 * hashtable_insert
115 * @name hashtable_insert
116 * @param h the hashtable to insert into
117 * @param k the key - hashtable claims ownership and will free on removal
118 * @param v the value - does not claim ownership
119 * @return non-zero for successful insertion
120 *
121 * This function will cause the table to expand if the insertion would take
122 * the ratio of entries to table size over the maximum load factor.
123 *
124 * This function does not check for repeated insertions with a duplicate key.
125 * The value returned when using a duplicate key is undefined -- when
126 * the hashtable changes size, the order of retrieval of duplicate key
127 * entries is reversed.
128 * If in doubt, remove before insert.
129 */
131 int
132 hashtable_insert(struct hashtable *h, void *k, void *v);
134 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
135 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
136 { \
137 return hashtable_insert(h,k,v); \
138 }
140 /*****************************************************************************
141 * hashtable_search
143 * @name hashtable_search
144 * @param h the hashtable to search
145 * @param k the key to search for - does not claim ownership
146 * @return the value associated with the key, or NULL if none found
147 */
149 void *
150 hashtable_search(struct hashtable *h, void *k);
152 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
153 valuetype * fnname (struct hashtable *h, keytype *k) \
154 { \
155 return (valuetype *) (hashtable_search(h,k)); \
156 }
158 /*****************************************************************************
159 * hashtable_remove
161 * @name hashtable_remove
162 * @param h the hashtable to remove the item from
163 * @param k the key to search for - does not claim ownership
164 * @return the value associated with the key, or NULL if none found
165 */
167 void * /* returns value */
168 hashtable_remove(struct hashtable *h, void *k);
170 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
171 valuetype * fnname (struct hashtable *h, keytype *k) \
172 { \
173 return (valuetype *) (hashtable_remove(h,k)); \
174 }
177 /*****************************************************************************
178 * hashtable_count
180 * @name hashtable_count
181 * @param h the hashtable
182 * @return the number of items stored in the hashtable
183 */
184 unsigned int
185 hashtable_count(struct hashtable *h);
188 /*****************************************************************************
189 * hashtable_destroy
191 * @name hashtable_destroy
192 * @param h the hashtable
193 * @param free_values whether to call 'free' on the remaining values
194 */
196 void
197 hashtable_destroy(struct hashtable *h, int free_values);
199 #endif /* __HASHTABLE_CWC22_H__ */