← Back to branch summary

~serge-hallyn/ubuntu/raring/libvirt/libvirt-hugepages

« back to all changes in this revision

Viewing changes to src/util/hash.c

  • Committer: Package Import Robot
  • Author(s): Chuck Short
  • Date: 2012-05-13 15:44:12 UTC
  • mfrom: (1.2.13)
  • Revision ID: package-import@ubuntu.com-20120513154412-fgmn5sxqdzgnzlx3
Tags: 0.9.12-0ubuntu1
* New upstream version:
  * Synchronize with debian packaging:
    - debian/control: Update build depends.
    - debian/libvirt-bin.postrm: Cleanup /var/log/libvirt
      on purge.
    - Bump standards verson (no changes).
    - debian/patches/Don-t-fail-if-we-can-t-setup-avahi.patch: Added
  * Dropped patches:
    - debian/patches/Debianize-libvirt-guests.patch
    - debian/patches/rewrite-lxc-controller-eof-handling-yet-again
    - debian/patches/ubuntu/libnl13.patch
    - debian/patches/ubuntu/fix-lxc-startup-error.patch
    - debian/patches/ubuntu/fix-bridge-fd.patch
    - debian/patches/ubuntu/skip-labelling-network-disks.patch
    - debian/patches/ubuntu/xen-xend-shutdown-detection.patch
    - debian/patches/ubuntu/xen-config-no-vfb-for-hvm.patch
    - debian/patches/debian/Disable-daemon-start-test.patch
    - debian/patches/debian/Disable-gnulib-s-test-nonplocking-pipe.sh.patch
    - debian/patches/ubuntu/9006-default-config-test-case.patch
    - debian/patches/fix-block-migration.patch
    - debian/patches/ubuntu/9022-qemu-unescape-HMP-commands-before-converting-them-to.patch
    - debian/patches/ubuntu/9023-qemu-change-rbd-auth_supported-separation-character-.patch
    - debian/patches/ubuntu/9024-qemu-allow-snapshotting-of-sheepdog-and-rbd-disks.patch
    - debian/patches/9025-qemu-change-rbd-auth_supported-separation-character-.patch
    - debian/patches/ubuntu/arm-gcc-workaround.patch
  * Rediffed:
    - debian/patches/Allow-libvirt-group-to-access-the-socket.patch
    - debian/patches/Disable-failing-virnetsockettest.patch
    - debian/patches/dnsmasq-as-priv-user
    - debian/patches/9002-better_default_uri_virsh.patch
  * debian/control: Add libnl-route-3-dev ass a build depends.
  * debian/patches/libnl3-build-fix.patch: Fix build with libnl3.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/hash.c
1
 
/*
2
 
 * hash.c: chained hash tables for domain and domain/connection deallocations
3
 
 *
4
 
 * Reference: Your favorite introductory book on algorithms
5
 
 *
6
 
 * Copyright (C) 2011 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
 
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
16
 
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
17
 
 *
18
 
 * Author: breese@users.sourceforge.net
19
 
 *         Daniel Veillard <veillard@redhat.com>
20
 
 */
21
 
 
22
 
#include <config.h>
23
 
 
24
 
#include <string.h>
25
 
#include <stdlib.h>
26
 
 
27
 
#include "virterror_internal.h"
28
 
#include "hash.h"
29
 
#include "memory.h"
30
 
#include "logging.h"
31
 
 
32
 
#define VIR_FROM_THIS VIR_FROM_NONE
33
 
 
34
 
#define MAX_HASH_LEN 8
35
 
 
36
 
/* #define DEBUG_GROW */
37
 
 
38
 
#define virHashIterationError(ret)                                      \
39
 
    do {                                                                \
40
 
        VIR_ERROR(_("Hash operation not allowed during iteration"));   \
41
 
        return ret;                                                     \
42
 
    } while (0)
43
 
 
44
 
/*
45
 
 * A single entry in the hash table
46
 
 */
47
 
typedef struct _virHashEntry virHashEntry;
48
 
typedef virHashEntry *virHashEntryPtr;
49
 
struct _virHashEntry {
50
 
    struct _virHashEntry *next;
51
 
    void *name;
52
 
    void *payload;
53
 
};
54
 
 
55
 
/*
56
 
 * The entire hash table
57
 
 */
58
 
struct _virHashTable {
59
 
    virHashEntryPtr *table;
60
 
    int size;
61
 
    int nbElems;
62
 
    /* True iff we are iterating over hash entries. */
63
 
    bool iterating;
64
 
    /* Pointer to the current entry during iteration. */
65
 
    virHashEntryPtr current;
66
 
    virHashDataFree dataFree;
67
 
    virHashKeyCode keyCode;
68
 
    virHashKeyEqual keyEqual;
69
 
    virHashKeyCopy keyCopy;
70
 
    virHashKeyFree keyFree;
71
 
};
72
 
 
73
 
static unsigned long virHashStrCode(const void *name)
74
 
{
75
 
    const char *str = name;
76
 
    unsigned long value = 0L;
77
 
    char ch;
78
 
 
79
 
    if (str != NULL) {
80
 
        value += 30 * (*str);
81
 
        while ((ch = *str++) != 0) {
82
 
            value =
83
 
                value ^ ((value << 5) + (value >> 3) + (unsigned long) ch);
84
 
        }
85
 
    }
86
 
    return value;
87
 
}
88
 
 
89
 
static bool virHashStrEqual(const void *namea, const void *nameb)
90
 
{
91
 
    return STREQ(namea, nameb);
92
 
}
93
 
 
94
 
static void *virHashStrCopy(const void *name)
95
 
{
96
 
    return strdup(name);
97
 
}
98
 
 
99
 
static void virHashStrFree(void *name)
100
 
{
101
 
    VIR_FREE(name);
102
 
}
103
 
 
104
 
 
105
 
static unsigned long
106
 
virHashComputeKey(virHashTablePtr table, const void *name)
107
 
{
108
 
    unsigned long value = table->keyCode(name);
109
 
    return (value % table->size);
110
 
}
111
 
 
112
 
/**
113
 
 * virHashCreateFull:
114
 
 * @size: the size of the hash table
115
 
 * @dataFree: callback to free data
116
 
 * @keyCode: callback to compute hash code
117
 
 * @keyEqual: callback to compare hash keys
118
 
 * @keyCopy: callback to copy hash keys
119
 
 * @keyFree: callback to free keys
120
 
 *
121
 
 * Create a new virHashTablePtr.
122
 
 *
123
 
 * Returns the newly created object, or NULL if an error occurred.
124
 
 */
125
 
virHashTablePtr virHashCreateFull(int size,
126
 
                                  virHashDataFree dataFree,
127
 
                                  virHashKeyCode keyCode,
128
 
                                  virHashKeyEqual keyEqual,
129
 
                                  virHashKeyCopy keyCopy,
130
 
                                  virHashKeyFree keyFree)
131
 
{
132
 
    virHashTablePtr table = NULL;
133
 
 
134
 
    if (size <= 0)
135
 
        size = 256;
136
 
 
137
 
    if (VIR_ALLOC(table) < 0) {
138
 
        virReportOOMError();
139
 
        return NULL;
140
 
    }
141
 
 
142
 
    table->size = size;
143
 
    table->nbElems = 0;
144
 
    table->dataFree = dataFree;
145
 
    table->keyCode = keyCode;
146
 
    table->keyEqual = keyEqual;
147
 
    table->keyCopy = keyCopy;
148
 
    table->keyFree = keyFree;
149
 
 
150
 
    if (VIR_ALLOC_N(table->table, size) < 0) {
151
 
        virReportOOMError();
152
 
        VIR_FREE(table);
153
 
        return NULL;
154
 
    }
155
 
 
156
 
    return table;
157
 
}
158
 
 
159
 
 
160
 
/**
161
 
 * virHashCreate:
162
 
 * @size: the size of the hash table
163
 
 * @dataFree: callback to free data
164
 
 *
165
 
 * Create a new virHashTablePtr.
166
 
 *
167
 
 * Returns the newly created object, or NULL if an error occurred.
168
 
 */
169
 
virHashTablePtr virHashCreate(int size, virHashDataFree dataFree)
170
 
{
171
 
    return virHashCreateFull(size,
172
 
                             dataFree,
173
 
                             virHashStrCode,
174
 
                             virHashStrEqual,
175
 
                             virHashStrCopy,
176
 
                             virHashStrFree);
177
 
}
178
 
 
179
 
/**
180
 
 * virHashGrow:
181
 
 * @table: the hash table
182
 
 * @size: the new size of the hash table
183
 
 *
184
 
 * resize the hash table
185
 
 *
186
 
 * Returns 0 in case of success, -1 in case of failure
187
 
 */
188
 
static int
189
 
virHashGrow(virHashTablePtr table, int size)
190
 
{
191
 
    int oldsize, i;
192
 
    virHashEntryPtr *oldtable;
193
 
 
194
 
#ifdef DEBUG_GROW
195
 
    unsigned long nbElem = 0;
196
 
#endif
197
 
 
198
 
    if (table == NULL)
199
 
        return (-1);
200
 
    if (size < 8)
201
 
        return (-1);
202
 
    if (size > 8 * 2048)
203
 
        return (-1);
204
 
 
205
 
    oldsize = table->size;
206
 
    oldtable = table->table;
207
 
    if (oldtable == NULL)
208
 
        return (-1);
209
 
 
210
 
    if (VIR_ALLOC_N(table->table, size) < 0) {
211
 
        virReportOOMError();
212
 
        table->table = oldtable;
213
 
        return (-1);
214
 
    }
215
 
    table->size = size;
216
 
 
217
 
    for (i = 0; i < oldsize; i++) {
218
 
        virHashEntryPtr iter = oldtable[i];
219
 
        while (iter) {
220
 
            virHashEntryPtr next = iter->next;
221
 
            unsigned long key = virHashComputeKey(table, iter->name);
222
 
 
223
 
            iter->next = table->table[key];
224
 
            table->table[key] = iter;
225
 
 
226
 
#ifdef DEBUG_GROW
227
 
            nbElem++;
228
 
#endif
229
 
            iter = next;
230
 
        }
231
 
    }
232
 
 
233
 
    VIR_FREE(oldtable);
234
 
 
235
 
#ifdef DEBUG_GROW
236
 
    VIR_DEBUG("virHashGrow : from %d to %d, %ld elems\n", oldsize,
237
 
              size, nbElem);
238
 
#endif
239
 
 
240
 
    return (0);
241
 
}
242
 
 
243
 
/**
244
 
 * virHashFree:
245
 
 * @table: the hash table
246
 
 *
247
 
 * Free the hash @table and its contents. The userdata is
248
 
 * deallocated with function provided at creation time.
249
 
 */
250
 
void
251
 
virHashFree(virHashTablePtr table)
252
 
{
253
 
    int i;
254
 
 
255
 
    if (table == NULL)
256
 
        return;
257
 
 
258
 
    for (i = 0; i < table->size; i++) {
259
 
        virHashEntryPtr iter = table->table[i];
260
 
        while (iter) {
261
 
            virHashEntryPtr next = iter->next;
262
 
 
263
 
            if (table->dataFree)
264
 
                table->dataFree(iter->payload, iter->name);
265
 
            if (table->keyFree)
266
 
                table->keyFree(iter->name);
267
 
            VIR_FREE(iter);
268
 
            iter = next;
269
 
        }
270
 
    }
271
 
 
272
 
    VIR_FREE(table->table);
273
 
    VIR_FREE(table);
274
 
}
275
 
 
276
 
static int
277
 
virHashAddOrUpdateEntry(virHashTablePtr table, const void *name,
278
 
                        void *userdata,
279
 
                        bool is_update)
280
 
{
281
 
    unsigned long key, len = 0;
282
 
    virHashEntryPtr entry;
283
 
    char *new_name;
284
 
 
285
 
    if ((table == NULL) || (name == NULL))
286
 
        return (-1);
287
 
 
288
 
    if (table->iterating)
289
 
        virHashIterationError(-1);
290
 
 
291
 
    key = virHashComputeKey(table, name);
292
 
 
293
 
    /* Check for duplicate entry */
294
 
    for (entry = table->table[key]; entry; entry = entry->next) {
295
 
        if (table->keyEqual(entry->name, name)) {
296
 
            if (is_update) {
297
 
                if (table->dataFree)
298
 
                    table->dataFree(entry->payload, entry->name);
299
 
                entry->payload = userdata;
300
 
                return 0;
301
 
            } else {
302
 
                return -1;
303
 
            }
304
 
        }
305
 
        len++;
306
 
    }
307
 
 
308
 
    if (VIR_ALLOC(entry) < 0 || !(new_name = table->keyCopy(name))) {
309
 
        virReportOOMError();
310
 
        VIR_FREE(entry);
311
 
        return -1;
312
 
    }
313
 
 
314
 
    entry->name = new_name;
315
 
    entry->payload = userdata;
316
 
    entry->next = table->table[key];
317
 
    table->table[key] = entry;
318
 
 
319
 
    table->nbElems++;
320
 
 
321
 
    if (len > MAX_HASH_LEN)
322
 
        virHashGrow(table, MAX_HASH_LEN * table->size);
323
 
 
324
 
    return 0;
325
 
}
326
 
 
327
 
/**
328
 
 * virHashAddEntry:
329
 
 * @table: the hash table
330
 
 * @name: the name of the userdata
331
 
 * @userdata: a pointer to the userdata
332
 
 *
333
 
 * Add the @userdata to the hash @table. This can later be retrieved
334
 
 * by using @name. Duplicate entries generate errors.
335
 
 *
336
 
 * Returns 0 the addition succeeded and -1 in case of error.
337
 
 */
338
 
int
339
 
virHashAddEntry(virHashTablePtr table, const void *name, void *userdata)
340
 
{
341
 
    return virHashAddOrUpdateEntry(table, name, userdata, false);
342
 
}
343
 
 
344
 
/**
345
 
 * virHashUpdateEntry:
346
 
 * @table: the hash table
347
 
 * @name: the name of the userdata
348
 
 * @userdata: a pointer to the userdata
349
 
 *
350
 
 * Add the @userdata to the hash @table. This can later be retrieved
351
 
 * by using @name. Existing entry for this tuple
352
 
 * will be removed and freed with @f if found.
353
 
 *
354
 
 * Returns 0 the addition succeeded and -1 in case of error.
355
 
 */
356
 
int
357
 
virHashUpdateEntry(virHashTablePtr table, const void *name,
358
 
                   void *userdata)
359
 
{
360
 
    return virHashAddOrUpdateEntry(table, name, userdata, true);
361
 
}
362
 
 
363
 
/**
364
 
 * virHashLookup:
365
 
 * @table: the hash table
366
 
 * @name: the name of the userdata
367
 
 *
368
 
 * Find the userdata specified by @name
369
 
 *
370
 
 * Returns the a pointer to the userdata
371
 
 */
372
 
void *
373
 
virHashLookup(virHashTablePtr table, const void *name)
374
 
{
375
 
    unsigned long key;
376
 
    virHashEntryPtr entry;
377
 
 
378
 
    if (!table || !name)
379
 
        return NULL;
380
 
 
381
 
    key = virHashComputeKey(table, name);
382
 
    for (entry = table->table[key]; entry; entry = entry->next) {
383
 
        if (table->keyEqual(entry->name, name))
384
 
            return entry->payload;
385
 
    }
386
 
    return NULL;
387
 
}
388
 
 
389
 
 
390
 
/**
391
 
 * virHashSteal:
392
 
 * @table: the hash table
393
 
 * @name: the name of the userdata
394
 
 *
395
 
 * Find the userdata specified by @name
396
 
 * and remove it from the hash without freeing it.
397
 
 *
398
 
 * Returns the a pointer to the userdata
399
 
 */
400
 
void *virHashSteal(virHashTablePtr table, const void *name)
401
 
{
402
 
    void *data = virHashLookup(table, name);
403
 
    if (data) {
404
 
        virHashDataFree dataFree = table->dataFree;
405
 
        table->dataFree = NULL;
406
 
        virHashRemoveEntry(table, name);
407
 
        table->dataFree = dataFree;
408
 
    }
409
 
    return data;
410
 
}
411
 
 
412
 
 
413
 
/**
414
 
 * virHashSize:
415
 
 * @table: the hash table
416
 
 *
417
 
 * Query the number of elements installed in the hash @table.
418
 
 *
419
 
 * Returns the number of elements in the hash table or
420
 
 * -1 in case of error
421
 
 */
422
 
int
423
 
virHashSize(virHashTablePtr table)
424
 
{
425
 
    if (table == NULL)
426
 
        return (-1);
427
 
    return (table->nbElems);
428
 
}
429
 
 
430
 
/**
431
 
 * virHashTableSize:
432
 
 * @table: the hash table
433
 
 *
434
 
 * Query the size of the hash @table, i.e., number of buckets in the table.
435
 
 *
436
 
 * Returns the number of keys in the hash table or
437
 
 * -1 in case of error
438
 
 */
439
 
int
440
 
virHashTableSize(virHashTablePtr table)
441
 
{
442
 
    if (table == NULL)
443
 
        return -1;
444
 
    return table->size;
445
 
}
446
 
 
447
 
 
448
 
/**
449
 
 * virHashRemoveEntry:
450
 
 * @table: the hash table
451
 
 * @name: the name of the userdata
452
 
 *
453
 
 * Find the userdata specified by the @name and remove
454
 
 * it from the hash @table. Existing userdata for this tuple will be removed
455
 
 * and freed with @f.
456
 
 *
457
 
 * Returns 0 if the removal succeeded and -1 in case of error or not found.
458
 
 */
459
 
int
460
 
virHashRemoveEntry(virHashTablePtr table, const void *name)
461
 
{
462
 
    virHashEntryPtr entry;
463
 
    virHashEntryPtr *nextptr;
464
 
 
465
 
    if (table == NULL || name == NULL)
466
 
        return (-1);
467
 
 
468
 
    nextptr = table->table + virHashComputeKey(table, name);
469
 
    for (entry = *nextptr; entry; entry = entry->next) {
470
 
        if (table->keyEqual(entry->name, name)) {
471
 
            if (table->iterating && table->current != entry)
472
 
                virHashIterationError(-1);
473
 
 
474
 
            if (table->dataFree)
475
 
                table->dataFree(entry->payload, entry->name);
476
 
            if (table->keyFree)
477
 
                table->keyFree(entry->name);
478
 
            *nextptr = entry->next;
479
 
            VIR_FREE(entry);
480
 
            table->nbElems--;
481
 
            return 0;
482
 
        }
483
 
        nextptr = &entry->next;
484
 
    }
485
 
 
486
 
    return -1;
487
 
}
488
 
 
489
 
 
490
 
/**
491
 
 * virHashForEach
492
 
 * @table: the hash table to process
493
 
 * @iter: callback to process each element
494
 
 * @data: opaque data to pass to the iterator
495
 
 *
496
 
 * Iterates over every element in the hash table, invoking the
497
 
 * 'iter' callback. The callback is allowed to remove the current element
498
 
 * using virHashRemoveEntry but calling other virHash* functions is prohibited.
499
 
 *
500
 
 * Returns number of items iterated over upon completion, -1 on failure
501
 
 */
502
 
int virHashForEach(virHashTablePtr table, virHashIterator iter, void *data)
503
 
{
504
 
    int i, count = 0;
505
 
 
506
 
    if (table == NULL || iter == NULL)
507
 
        return (-1);
508
 
 
509
 
    if (table->iterating)
510
 
        virHashIterationError(-1);
511
 
 
512
 
    table->iterating = true;
513
 
    table->current = NULL;
514
 
    for (i = 0 ; i < table->size ; i++) {
515
 
        virHashEntryPtr entry = table->table[i];
516
 
        while (entry) {
517
 
            virHashEntryPtr next = entry->next;
518
 
 
519
 
            table->current = entry;
520
 
            iter(entry->payload, entry->name, data);
521
 
            table->current = NULL;
522
 
 
523
 
            count++;
524
 
            entry = next;
525
 
        }
526
 
    }
527
 
    table->iterating = false;
528
 
 
529
 
    return (count);
530
 
}
531
 
 
532
 
/**
533
 
 * virHashRemoveSet
534
 
 * @table: the hash table to process
535
 
 * @iter: callback to identify elements for removal
536
 
 * @data: opaque data to pass to the iterator
537
 
 *
538
 
 * Iterates over all elements in the hash table, invoking the 'iter'
539
 
 * callback. If the callback returns a non-zero value, the element
540
 
 * will be removed from the hash table & its payload passed to the
541
 
 * data freer callback registered at creation.
542
 
 *
543
 
 * Returns number of items removed on success, -1 on failure
544
 
 */
545
 
int virHashRemoveSet(virHashTablePtr table,
546
 
                     virHashSearcher iter,
547
 
                     const void *data)
548
 
{
549
 
    int i, count = 0;
550
 
 
551
 
    if (table == NULL || iter == NULL)
552
 
        return (-1);
553
 
 
554
 
    if (table->iterating)
555
 
        virHashIterationError(-1);
556
 
 
557
 
    table->iterating = true;
558
 
    table->current = NULL;
559
 
    for (i = 0 ; i < table->size ; i++) {
560
 
        virHashEntryPtr *nextptr = table->table + i;
561
 
 
562
 
        while (*nextptr) {
563
 
            virHashEntryPtr entry = *nextptr;
564
 
            if (!iter(entry->payload, entry->name, data)) {
565
 
                nextptr = &entry->next;
566
 
            } else {
567
 
                count++;
568
 
                if (table->dataFree)
569
 
                    table->dataFree(entry->payload, entry->name);
570
 
                if (table->keyFree)
571
 
                    table->keyFree(entry->name);
572
 
                *nextptr = entry->next;
573
 
                VIR_FREE(entry);
574
 
                table->nbElems--;
575
 
            }
576
 
        }
577
 
    }
578
 
    table->iterating = false;
579
 
 
580
 
    return count;
581
 
}
582
 
 
583
 
/**
584
 
 * virHashSearch:
585
 
 * @table: the hash table to search
586
 
 * @iter: an iterator to identify the desired element
587
 
 * @data: extra opaque information passed to the iter
588
 
 *
589
 
 * Iterates over the hash table calling the 'iter' callback
590
 
 * for each element. The first element for which the iter
591
 
 * returns non-zero will be returned by this function.
592
 
 * The elements are processed in a undefined order
593
 
 */
594
 
void *virHashSearch(virHashTablePtr table,
595
 
                    virHashSearcher iter,
596
 
                    const void *data)
597
 
{
598
 
    int i;
599
 
 
600
 
    if (table == NULL || iter == NULL)
601
 
        return (NULL);
602
 
 
603
 
    if (table->iterating)
604
 
        virHashIterationError(NULL);
605
 
 
606
 
    table->iterating = true;
607
 
    table->current = NULL;
608
 
    for (i = 0 ; i < table->size ; i++) {
609
 
        virHashEntryPtr entry;
610
 
        for (entry = table->table[i]; entry; entry = entry->next) {
611
 
            if (iter(entry->payload, entry->name, data)) {
612
 
                table->iterating = false;
613
 
                return entry->payload;
614
 
            }
615
 
        }
616
 
    }
617
 
    table->iterating = false;
618
 
 
619
 
    return NULL;
620
 
}
621
 
 
622
 
struct getKeysIter
623
 
{
624
 
    virHashKeyValuePair *sortArray;
625
 
    unsigned arrayIdx;
626
 
};
627
 
 
628
 
static void virHashGetKeysIterator(void *payload,
629
 
                                   const void *key, void *data)
630
 
{
631
 
    struct getKeysIter *iter = data;
632
 
 
633
 
    iter->sortArray[iter->arrayIdx].key = key;
634
 
    iter->sortArray[iter->arrayIdx].value = payload;
635
 
 
636
 
    iter->arrayIdx++;
637
 
}
638
 
 
639
 
typedef int (*qsort_comp)(const void *, const void *);
640
 
 
641
 
virHashKeyValuePairPtr virHashGetItems(virHashTablePtr table,
642
 
                                       virHashKeyComparator compar)
643
 
{
644
 
    int numElems = virHashSize(table);
645
 
    struct getKeysIter iter = {
646
 
        .arrayIdx = 0,
647
 
        .sortArray = NULL,
648
 
    };
649
 
 
650
 
    if (numElems < 0)
651
 
        return NULL;
652
 
 
653
 
    if (VIR_ALLOC_N(iter.sortArray, numElems + 1)) {
654
 
        virReportOOMError();
655
 
        return NULL;
656
 
    }
657
 
 
658
 
    virHashForEach(table, virHashGetKeysIterator, &iter);
659
 
 
660
 
    if (compar)
661
 
        qsort(&iter.sortArray[0], numElems, sizeof(iter.sortArray[0]),
662
 
              (qsort_comp)compar);
663
 
 
664
 
    return iter.sortArray;
665
 
}