1 /*
2 * virhash.c: chained hash tables
3 *
4 * Reference: Your favorite introductory book on algorithms
5 *
6 * Copyright (C) 2005-2014 Red Hat, Inc.
7 * Copyright (C) 2000 Bjorn Reese and Daniel Veillard.
8 *
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
12 *
13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
14 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
16 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
17 */
18
19 #include <config.h>
20
21
22 #include "virerror.h"
23 #include "virhash.h"
24 #include "virlog.h"
25 #include "virhashcode.h"
26 #include "virrandom.h"
27 #include "virobject.h"
28
29 #define VIR_FROM_THIS VIR_FROM_NONE
30
31 VIR_LOG_INIT("util.hash");
32
33
34 struct _virHashAtomic {
35 virObjectLockable parent;
36 GHashTable *hash;
37 };
38
39 static virClass *virHashAtomicClass;
40 static void virHashAtomicDispose(void *obj);
41
virHashAtomicOnceInit(void)42 static int virHashAtomicOnceInit(void)
43 {
44 if (!VIR_CLASS_NEW(virHashAtomic, virClassForObjectLockable()))
45 return -1;
46
47 return 0;
48 }
49
50 VIR_ONCE_GLOBAL_INIT(virHashAtomic);
51
52
53 /**
54 * Our hash function uses a random seed to provide uncertainty from run to run
55 * to prevent pre-crafting of colliding hash keys.
56 */
57 static uint32_t virHashTableSeed;
58
virHashTableSeedOnceInit(void)59 static int virHashTableSeedOnceInit(void)
60 {
61 virHashTableSeed = virRandomBits(32);
62 return 0;
63 }
64
65 VIR_ONCE_GLOBAL_INIT(virHashTableSeed);
66
67
68 static unsigned int
virHashTableStringKey(const void * vkey)69 virHashTableStringKey(const void *vkey)
70 {
71 const char *key = vkey;
72
73 return virHashCodeGen(key, strlen(key), virHashTableSeed);
74 }
75
76
77 /**
78 * virHashNew:
79 * @dataFree: callback to free data
80 *
81 * Create a new GHashTable * for use with string-based keys.
82 *
83 * Returns the newly created object.
84 */
85 GHashTable *
virHashNew(virHashDataFree dataFree)86 virHashNew(virHashDataFree dataFree)
87 {
88 ignore_value(virHashTableSeedInitialize());
89
90 return g_hash_table_new_full(virHashTableStringKey, g_str_equal, g_free, dataFree);
91 }
92
93
94 virHashAtomic *
virHashAtomicNew(virHashDataFree dataFree)95 virHashAtomicNew(virHashDataFree dataFree)
96 {
97 virHashAtomic *hash;
98
99 if (virHashAtomicInitialize() < 0)
100 return NULL;
101
102 if (!(hash = virObjectLockableNew(virHashAtomicClass)))
103 return NULL;
104
105 hash->hash = virHashNew(dataFree);
106 return hash;
107 }
108
109
110 static void
virHashAtomicDispose(void * obj)111 virHashAtomicDispose(void *obj)
112 {
113 virHashAtomic *hash = obj;
114
115 virHashFree(hash->hash);
116 }
117
118
119 /**
120 * virHashFree:
121 * @table: the hash table
122 *
123 * Free the hash @table and its contents. The userdata is
124 * deallocated with function provided at creation time.
125 *
126 * Deprecated: consider using g_hash_table_unref instead
127 */
128 void
virHashFree(GHashTable * table)129 virHashFree(GHashTable *table)
130 {
131 if (table == NULL)
132 return;
133
134 g_hash_table_unref(table);
135 }
136
137
138 /**
139 * virHashAddEntry:
140 * @table: the hash table
141 * @name: the name of the userdata
142 * @userdata: a pointer to the userdata
143 *
144 * Add the @userdata to the hash @table. This can later be retrieved
145 * by using @name. Duplicate entries generate errors.
146 *
147 * Deprecated: Consider using g_hash_table_insert insert. Note that
148 * g_hash_table_instead doesn't fail if entry exists. Also note that
149 * g_hash_table_insert doesn't copy the key.
150 *
151 * Returns 0 the addition succeeded and -1 in case of error.
152 */
153 int
virHashAddEntry(GHashTable * table,const char * name,void * userdata)154 virHashAddEntry(GHashTable *table, const char *name, void *userdata)
155 {
156 if (!table || !name)
157 return -1;
158
159 if (g_hash_table_contains(table, name)) {
160 virReportError(VIR_ERR_INTERNAL_ERROR,
161 _("Duplicate hash table key '%s'"), name);
162 return -1;
163 }
164
165 g_hash_table_insert(table, g_strdup(name), userdata);
166
167 return 0;
168 }
169
170 /**
171 * virHashUpdateEntry:
172 * @table: the hash table
173 * @name: the name of the userdata
174 * @userdata: a pointer to the userdata
175 *
176 * Add the @userdata to the hash @table. This can later be retrieved
177 * by using @name. Existing entry for this tuple
178 * will be removed and freed with @f if found.
179 *
180 * Deprecated: consider using g_hash_table_insert insert. Note that
181 * g_hash_table_insert doesn't copy the key.
182 *
183 * Returns 0 the addition succeeded and -1 in case of error.
184 */
185 int
virHashUpdateEntry(GHashTable * table,const char * name,void * userdata)186 virHashUpdateEntry(GHashTable *table, const char *name,
187 void *userdata)
188 {
189 if (!table || !name)
190 return -1;
191
192 g_hash_table_insert(table, g_strdup(name), userdata);
193
194 return 0;
195 }
196
197 int
virHashAtomicUpdate(virHashAtomic * table,const char * name,void * userdata)198 virHashAtomicUpdate(virHashAtomic *table,
199 const char *name,
200 void *userdata)
201 {
202 int ret;
203
204 virObjectLock(table);
205 ret = virHashUpdateEntry(table->hash, name, userdata);
206 virObjectUnlock(table);
207
208 return ret;
209 }
210
211
212 /**
213 * virHashLookup:
214 * @table: the hash table
215 * @name: the name of the userdata
216 *
217 * Find the userdata specified by @name
218 *
219 * Deprecated: consider using g_hash_table_lookup instead
220 *
221 * Returns a pointer to the userdata
222 */
223 void *
virHashLookup(GHashTable * table,const char * name)224 virHashLookup(GHashTable *table,
225 const char *name)
226 {
227 if (!table || !name)
228 return NULL;
229
230 return g_hash_table_lookup(table, name);
231 }
232
233
234 /**
235 * virHashHasEntry:
236 * @table: the hash table
237 * @name: the name of the userdata
238 *
239 * Find whether entry specified by @name exists.
240 *
241 * Deprecated: consider using g_hash_table_contains instead
242 *
243 * Returns true if the entry exists and false otherwise
244 */
245 bool
virHashHasEntry(GHashTable * table,const char * name)246 virHashHasEntry(GHashTable *table,
247 const char *name)
248 {
249 if (!table || !name)
250 return false;
251
252 return g_hash_table_contains(table, name);
253 }
254
255
256 /**
257 * virHashSteal:
258 * @table: the hash table
259 * @name: the name of the userdata
260 *
261 * Find the userdata specified by @name
262 * and remove it from the hash without freeing it.
263 *
264 * Deprecated: consider using g_hash_table_steal_extended once we upgrade to
265 * glib 2.58
266 *
267 * Returns a pointer to the userdata
268 */
virHashSteal(GHashTable * table,const char * name)269 void *virHashSteal(GHashTable *table, const char *name)
270 {
271 g_autofree void *orig_name = NULL;
272 void *val = NULL;
273
274 if (!table || !name)
275 return NULL;
276
277 /* we can replace this by g_hash_table_steal_extended with glib 2.58 */
278 if (!(g_hash_table_lookup_extended(table, name, &orig_name, &val)))
279 return NULL;
280
281 g_hash_table_steal(table, name);
282
283 return val;
284 }
285
286 void *
virHashAtomicSteal(virHashAtomic * table,const char * name)287 virHashAtomicSteal(virHashAtomic *table,
288 const char *name)
289 {
290 void *data;
291
292 virObjectLock(table);
293 data = virHashSteal(table->hash, name);
294 virObjectUnlock(table);
295
296 return data;
297 }
298
299
300 /**
301 * virHashSize:
302 * @table: the hash table
303 *
304 * Query the number of elements installed in the hash @table.
305 *
306 * Deprecated: consider using g_hash_table_size instead
307 *
308 * Returns the number of elements in the hash table or
309 * -1 in case of error
310 */
311 ssize_t
virHashSize(GHashTable * table)312 virHashSize(GHashTable *table)
313 {
314 if (table == NULL)
315 return -1;
316
317 return g_hash_table_size(table);
318 }
319
320
321 /**
322 * virHashRemoveEntry:
323 * @table: the hash table
324 * @name: the name of the userdata
325 *
326 * Find the userdata specified by the @name and remove
327 * it from the hash @table. Existing userdata for this tuple will be removed
328 * and freed with @f.
329 *
330 * Deprecated: consider using g_hash_table_remove
331 *
332 * Returns 0 if the removal succeeded and -1 in case of error or not found.
333 */
334 int
virHashRemoveEntry(GHashTable * table,const char * name)335 virHashRemoveEntry(GHashTable *table,
336 const char *name)
337 {
338 if (!table || !name)
339 return -1;
340
341 if (g_hash_table_remove(table, name))
342 return 0;
343
344 return -1;
345 }
346
347
348 /**
349 * virHashForEach, virHashForEachSorted, virHashForEachSafe
350 * @table: the hash table to process
351 * @iter: callback to process each element
352 * @opaque: opaque data to pass to the iterator
353 *
354 * Iterates over every element in the hash table, invoking the 'iter' callback.
355 *
356 * The elements are iterated in arbitrary order.
357 *
358 * virHashForEach prohibits @iter from modifying @table
359 *
360 * virHashForEachSafe allows the callback to remove the current
361 * element using virHashRemoveEntry but calling other virHash* functions is
362 * prohibited. Note that removing the entry invalidates @key and @payload in
363 * the callback.
364 *
365 * virHashForEachSorted iterates the elements in order by sorted key.
366 *
367 * virHashForEachSorted and virHashForEachSafe are more computationally
368 * expensive than virHashForEach.
369 *
370 * If @iter fails and returns a negative value, the evaluation is stopped and -1
371 * is returned.
372 *
373 * Deprecated: Consider using g_hash_table_foreach as replacement for
374 * virHashForEach, rewrite your code if it would require virHashForEachSafe.
375 *
376 * Returns 0 on success or -1 on failure.
377 */
378 int
virHashForEach(GHashTable * table,virHashIterator iter,void * opaque)379 virHashForEach(GHashTable *table, virHashIterator iter, void *opaque)
380 {
381 GHashTableIter htitr;
382 void *key;
383 void *value;
384
385 if (!table || !iter)
386 return -1;
387
388 g_hash_table_iter_init(&htitr, table);
389
390 while (g_hash_table_iter_next(&htitr, &key, &value)) {
391 if (iter(value, key, opaque) < 0)
392 return -1;
393 }
394
395 return 0;
396 }
397
398
399 int
virHashForEachSafe(GHashTable * table,virHashIterator iter,void * opaque)400 virHashForEachSafe(GHashTable *table,
401 virHashIterator iter,
402 void *opaque)
403 {
404 g_autofree virHashKeyValuePair *items = virHashGetItems(table, NULL, false);
405 size_t i;
406
407 if (!items)
408 return -1;
409
410 for (i = 0; items[i].key; i++) {
411 if (iter((void *)items[i].value, items[i].key, opaque) < 0)
412 return -1;
413 }
414
415 return 0;
416 }
417
418
419 int
virHashForEachSorted(GHashTable * table,virHashIterator iter,void * opaque)420 virHashForEachSorted(GHashTable *table,
421 virHashIterator iter,
422 void *opaque)
423 {
424 g_autofree virHashKeyValuePair *items = virHashGetItems(table, NULL, true);
425 size_t i;
426
427 if (!items)
428 return -1;
429
430 for (i = 0; items[i].key; i++) {
431 if (iter((void *)items[i].value, items[i].key, opaque) < 0)
432 return -1;
433 }
434
435 return 0;
436 }
437
438
439 struct virHashSearcherWrapFuncData {
440 virHashSearcher iter;
441 const void *opaque;
442 const char *name;
443 };
444
445 static gboolean
virHashSearcherWrapFunc(gpointer key,gpointer value,gpointer opaque)446 virHashSearcherWrapFunc(gpointer key,
447 gpointer value,
448 gpointer opaque)
449 {
450 struct virHashSearcherWrapFuncData *data = opaque;
451
452 data->name = key;
453
454 return !!(data->iter(value, key, data->opaque));
455 }
456
457 /**
458 * virHashRemoveSet
459 * @table: the hash table to process
460 * @iter: callback to identify elements for removal
461 * @opaque: opaque data to pass to the iterator
462 *
463 * Iterates over all elements in the hash table, invoking the 'iter'
464 * callback. If the callback returns a non-zero value, the element
465 * will be removed from the hash table & its payload passed to the
466 * data freer callback registered at creation.
467 *
468 * Deprecated: consider using g_hash_table_foreach_remove instead
469 *
470 * Returns number of items removed on success, -1 on failure
471 */
472 ssize_t
virHashRemoveSet(GHashTable * table,virHashSearcher iter,const void * opaque)473 virHashRemoveSet(GHashTable *table,
474 virHashSearcher iter,
475 const void *opaque)
476 {
477 struct virHashSearcherWrapFuncData data = { iter, opaque, NULL };
478
479 if (table == NULL || iter == NULL)
480 return -1;
481
482 return g_hash_table_foreach_remove(table, virHashSearcherWrapFunc, &data);
483 }
484
485 /**
486 * virHashRemoveAll
487 * @table: the hash table to clear
488 *
489 * Free the hash @table's contents. The userdata is
490 * deallocated with the function provided at creation time.
491 *
492 * Deprecated: consider using g_hash_table_remove_all instead
493 */
494 void
virHashRemoveAll(GHashTable * table)495 virHashRemoveAll(GHashTable *table)
496 {
497 if (!table)
498 return;
499
500 g_hash_table_remove_all(table);
501 }
502
503 /**
504 * virHashSearch:
505 * @table: the hash table to search
506 * @iter: an iterator to identify the desired element
507 * @opaque: extra opaque information passed to the iter
508 * @name: the name of found user data, pass NULL to ignore
509 *
510 * Iterates over the hash table calling the 'iter' callback
511 * for each element. The first element for which the iter
512 * returns non-zero will be returned by this function.
513 * The elements are processed in a undefined order. Caller is
514 * responsible for freeing the @name.
515 *
516 * Deprecated: consider using g_hash_table_find instead
517 */
virHashSearch(GHashTable * table,virHashSearcher iter,const void * opaque,char ** name)518 void *virHashSearch(GHashTable *table,
519 virHashSearcher iter,
520 const void *opaque,
521 char **name)
522 {
523 struct virHashSearcherWrapFuncData data = { iter, opaque, NULL };
524 void *ret;
525
526 if (!table || !iter)
527 return NULL;
528
529 if (!(ret = g_hash_table_find(table, virHashSearcherWrapFunc, &data)))
530 return NULL;
531
532 if (name)
533 *name = g_strdup(data.name);
534
535 return ret;
536 }
537
538
539 static int
virHashGetItemsKeySorter(const void * va,const void * vb)540 virHashGetItemsKeySorter(const void *va,
541 const void *vb)
542 {
543 const virHashKeyValuePair *a = va;
544 const virHashKeyValuePair *b = vb;
545
546 return strcmp(a->key, b->key);
547 }
548
549
550 virHashKeyValuePair *
virHashGetItems(GHashTable * table,size_t * nitems,bool sortKeys)551 virHashGetItems(GHashTable *table,
552 size_t *nitems,
553 bool sortKeys)
554 {
555 virHashKeyValuePair *items;
556 size_t dummy;
557 GHashTableIter htitr;
558 void *key;
559 void *value;
560 size_t i = 0;
561
562 if (!nitems)
563 nitems = &dummy;
564
565 if (!table)
566 return NULL;
567
568 *nitems = g_hash_table_size(table);
569 items = g_new0(virHashKeyValuePair, *nitems + 1);
570
571 g_hash_table_iter_init(&htitr, table);
572
573 while (g_hash_table_iter_next(&htitr, &key, &value)) {
574 items[i].key = key;
575 items[i].value = value;
576 i++;
577 }
578
579 if (sortKeys)
580 qsort(items, *nitems, sizeof(*items), virHashGetItemsKeySorter);
581
582 return items;
583 }
584
585
586 struct virHashEqualData
587 {
588 bool equal;
589 GHashTable *table2;
590 virHashValueComparator compar;
591 };
592
virHashEqualSearcher(const void * payload,const char * name,const void * opaque)593 static int virHashEqualSearcher(const void *payload, const char *name,
594 const void *opaque)
595 {
596 struct virHashEqualData *vhed = (void *)opaque;
597 const void *value;
598
599 value = virHashLookup(vhed->table2, name);
600 if (!value ||
601 vhed->compar(value, payload) != 0) {
602 /* key is missing in 2nd table or values are different */
603 vhed->equal = false;
604 /* stop 'iteration' */
605 return 1;
606 }
607 return 0;
608 }
609
virHashEqual(GHashTable * table1,GHashTable * table2,virHashValueComparator compar)610 bool virHashEqual(GHashTable *table1,
611 GHashTable *table2,
612 virHashValueComparator compar)
613 {
614 struct virHashEqualData data = {
615 .equal = true,
616 .table2 = table2,
617 .compar = compar,
618 };
619
620 if (table1 == table2)
621 return true;
622
623 if (!table1 || !table2 ||
624 virHashSize(table1) != virHashSize(table2))
625 return false;
626
627 virHashSearch(table1, virHashEqualSearcher, &data, NULL);
628
629 return data.equal;
630 }
631