ia64/xen-unstable

view tools/vnet/libxutil/hash_table.h @ 19848:5839491bbf20

[IA64] replace MAX_VCPUS with d->max_vcpus where necessary.

don't use MAX_VCPUS, and use vcpu::max_vcpus.
The changeset of 2f9e1348aa98 introduced max_vcpus to allow more vcpus
per guest. This patch is ia64 counter part.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
author Isaku Yamahata <yamahata@valinux.co.jp>
date Mon Jun 29 11:26:05 2009 +0900 (2009-06-29)
parents 6d7bba6443ef
children
line source
1 /*
2 * Copyright (C) 2001 - 2005 Mike Wray <mike.wray@hp.com>
3 *
4 * This library is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation; either version 2.1 of the License, or
7 * (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
19 #ifndef _XUTIL_HASH_TABLE_H_
20 #define _XUTIL_HASH_TABLE_H_
22 #include "iostream.h"
23 #include "sys_string.h"
25 typedef unsigned long Hashcode;
27 /** Type used to pass parameters to table functions. */
28 typedef union TableArg {
29 unsigned long ul;
30 void *ptr;
31 } TableArg;
33 /** An entry in a bucket list. */
34 typedef struct HTEntry {
35 /** Hashcode of the entry's key. */
36 Hashcode hashcode;
37 /** The key for this entry. */
38 void *key;
39 /** The value in this entry. */
40 void *value;
41 /** The next entry in the list. */
42 struct HTEntry *next;
43 } HTEntry;
45 /** A bucket in a rule table. */
46 typedef struct HTBucket {
47 /** Number of entries in the bucket. */
48 int count;
49 /** First entry in the bucket (may be null). */
50 HTEntry *head;
51 } HTBucket;
53 /** Default number of buckets in a hash table.
54 * You want enough buckets so the lists in the buckets will typically be short.
55 * If the hash function is good it doesn't matter whether the number of
56 * buckets is prime or not.
57 */
58 //#define HT_BUCKETS_N 1
59 //#define HT_BUCKETS_N 3
60 //#define HT_BUCKETS_N 7
61 //#define HT_BUCKETS_N 17
62 //#define HT_BUCKETS_N 97
63 //#define HT_BUCKETS_N 211
64 //#define HT_BUCKETS_N 401
65 #define HT_BUCKETS_N 1021
67 typedef struct HashTable HashTable;
69 /** Type for a function used to select table entries. */
70 typedef int TableTestFn(TableArg arg, HashTable *table, HTEntry *entry);
72 /** Type for a function to map over table entries. */
73 typedef int TableMapFn(TableArg arg, HashTable *table, HTEntry *entry);
75 /** Type for a function to free table entries. */
76 typedef void TableFreeFn(HashTable *table, HTEntry *entry);
78 /** Type for a function to hash table keys. */
79 typedef Hashcode TableHashFn(void *key);
81 /** Type for a function to test table keys for equality. */
82 typedef int TableEqualFn(void *key1, void *key2);
84 /** Type for a function to order table entries. */
85 typedef int TableOrderFn(HTEntry *e1, HTEntry *e2);
87 /** General hash table.
88 * A hash table with a list in each bucket.
89 * Functions can be supplied for freeing entries, hashing keys, and comparing keys.
90 * These all default to 0, when default behaviour treating keys as integers is used.
91 */
92 struct HashTable {
93 /** Array of buckets, each with its own list. */
94 HTBucket *buckets;
95 /** Number of buckets in the bucket array. */
96 int buckets_n;
97 /** Number of entries in the table. */
98 int entry_count;
99 unsigned long key_size;
100 /** Function to free keys and values in entries. */
101 TableFreeFn *entry_free_fn;
102 /** Function to hash keys. */
103 TableHashFn *key_hash_fn;
104 /** Function to compare keys for equality. */
105 TableEqualFn *key_equal_fn;
106 /** Place for the user of the table to hang extra data. */
107 void *user_data;
108 };
110 extern HashTable *HashTable_new(int bucket_n);
111 extern void HashTable_free(HashTable *table);
112 extern HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value);
113 extern void HTEntry_free(HTEntry *entry);
114 extern int HashTable_set_bucket_n(HashTable *table, int bucket_n);
115 extern void HashTable_clear(HashTable *table);
116 extern HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value);
117 extern HTEntry * HashTable_get_entry(HashTable *table, void *key);
118 extern HTEntry * HashTable_add(HashTable *table, void *key, void *value);
119 extern void * HashTable_get(HashTable *table, void *key);
120 extern int HashTable_remove(HashTable *table, void *key);
121 extern HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
122 TableTestFn *test_fn, TableArg arg);
123 extern int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
124 TableTestFn *test_fn, TableArg arg);
125 extern void HashTable_print(HashTable *table, IOStream *out);
126 extern int HashTable_set_buckets_n(HashTable *table, int buckets_n);
127 extern int HashTable_adjust(HashTable *table, int buckets_min);
129 extern int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order);
131 typedef unsigned long ub4;
132 typedef unsigned char ub1;
134 extern ub4 hash(const ub1 *k, ub4 length, ub4 initval);
136 /** Hash some bytes starting with a given hashcode.
137 *
138 * @param h initial hashcode - use 0, a previous hash, or an arbitrary value
139 * @param b bytes to hash
140 * @param b_n number of bytes to hash
141 * @return hashcode
142 */
143 static inline Hashcode hash_hvoid(Hashcode h, const void *b, unsigned b_n){
144 return hash(b, b_n, h);
145 }
147 /** Hash a string (null-terminated).
148 *
149 * @param s input to hash
150 * @return hashcode
151 */
152 static inline Hashcode hash_string(char *s){
153 return (s ? hash_hvoid(0, s, strlen(s)) : 0);
154 }
156 /** Macro to declare variables for HashTable_for_each() to use.
157 *
158 * @param entry variable that is set to entries in the table
159 */
160 #define HashTable_for_decl(entry) \
161 HashTable *_var_table; \
162 HTBucket *_var_bucket; \
163 HTBucket *_var_end; \
164 HTEntry *_var_next; \
165 HTEntry *entry
167 /** Macro to iterate over the entries in a hashtable.
168 * Must be in a scope where HashTable_for_decl() has been used to declare
169 * variables for it to use.
170 * The variable 'entry' is iterated over entries in the table.
171 * The code produced is syntactically a loop, so it must be followed by
172 * a loop body, typically some statements in braces:
173 * HashTable_for_each(entry, table){ ...loop body... }
174 *
175 * HashTable_for_each() and HashTable_for_decl() cannot be used for nested
176 * loops as variables will clash.
177 *
178 * @note The simplest way to code a direct loop over the entries in a hashtable
179 * is to use a loop over the buckets, with a nested loop over the entries
180 * in a bucket. Using this approach in a macro means the macro contains
181 * an opening brace, and calls to it must be followed by 2 braces!
182 * To avoid this the code has been restructured so that it is a for loop.
183 * So that statements could be used in the test expression of the for loop,
184 * we have used the gcc statement expression extension ({ ... }).
185 *
186 * @param entry variable to iterate over the entries
187 * @param table to iterate over (non-null)
188 */
189 #define HashTable_for_each(entry, table) \
190 _var_table = table; \
191 _var_bucket = _var_table->buckets; \
192 _var_end = _var_bucket + _var_table->buckets_n; \
193 for(entry=0, _var_next=0; \
194 ({ if(_var_next){ \
195 entry = _var_next; \
196 _var_next = entry->next; \
197 } else { \
198 while(_var_bucket < _var_end){ \
199 entry = _var_bucket->head; \
200 _var_bucket++; \
201 if(entry){ \
202 _var_next = entry->next; \
203 break; \
204 } \
205 } \
206 }; \
207 entry; }); \
208 entry = _var_next )
210 /** Map a function over the entries in a table.
211 * Mapping stops when the function returns a non-zero value.
212 * Uses the gcc statement expression extension ({ ... }).
213 *
214 * @param table to map over
215 * @param fn function to apply to entries
216 * @param arg first argument to call the function with
217 * @return 0 if fn always returned 0, first non-zero value otherwise
218 */
219 #define HashTable_map(table, fn, arg) \
220 ({ HashTable_for_decl(_var_entry); \
221 TableArg _var_arg = arg; \
222 int _var_value = 0; \
223 HashTable_for_each(_var_entry, table){ \
224 if((_var_value = fn(_var_arg, _var_table, _var_entry))) break; \
225 } \
226 _var_value; })
228 /** Cast x to the type for a key or value in a hash table.
229 * This avoids compiler warnings when using short integers
230 * as keys or values (especially on 64-bit platforms).
231 */
232 #define HKEY(x) ((void*)(unsigned long)(x))
234 /** Cast x from the type for a key or value in a hash table.
235 * to an unsigned long. This avoids compiler warnings when using
236 * short integers as keys or values (especially on 64-bit platforms).
237 */
238 #define HVAL(x) ((unsigned long)(x))
240 #endif /* !_XUTIL_HASH_TABLE_H_ */