[PATCH 02/13] util: hash: Rewrite sorting of elements in virHashGetItems
Peter Krempa
pkrempa at redhat.com
Mon Oct 26 15:45:42 UTC 2020
All but one of the callers either use the list in arbitrary order or
sorted by key. Rewrite the function so that it supports sorting by key
natively and make it return the element count. This in turn allows to
rewrite the only caller to sort by value internally.
This allows to remove multiple sorting functions which were sorting by
key and the function will be also later reused for some hash operations
internally.
Signed-off-by: Peter Krempa <pkrempa at redhat.com>
---
src/conf/nwfilter_params.c | 10 +---
src/hyperv/hyperv_wmi.c | 2 +-
src/locking/lock_daemon.c | 2 +-
src/nwfilter/nwfilter_ebiptables_driver.c | 13 +++--
src/qemu/qemu_interop_config.c | 9 +---
src/rpc/virnetdaemon.c | 11 +---
src/util/virhash.c | 66 ++++++++++++++---------
src/util/virhash.h | 5 +-
src/util/virlockspace.c | 2 +-
tests/virhashtest.c | 11 +---
10 files changed, 59 insertions(+), 72 deletions(-)
diff --git a/src/conf/nwfilter_params.c b/src/conf/nwfilter_params.c
index 73160a38a4..dd2b92c97b 100644
--- a/src/conf/nwfilter_params.c
+++ b/src/conf/nwfilter_params.c
@@ -755,13 +755,6 @@ virNWFilterParseParamAttributes(xmlNodePtr cur)
}
-static int
-virNWFilterFormatParameterNameSorter(const virHashKeyValuePair *a,
- const virHashKeyValuePair *b)
-{
- return strcmp(a->key, b->key);
-}
-
int
virNWFilterFormatParamAttributes(virBufferPtr buf,
virHashTablePtr table,
@@ -779,8 +772,7 @@ virNWFilterFormatParamAttributes(virBufferPtr buf,
return -1;
}
- items = virHashGetItems(table,
- virNWFilterFormatParameterNameSorter);
+ items = virHashGetItems(table, NULL, true);
if (!items)
return -1;
diff --git a/src/hyperv/hyperv_wmi.c b/src/hyperv/hyperv_wmi.c
index 421cbfa31b..3de7f0ed90 100644
--- a/src/hyperv/hyperv_wmi.c
+++ b/src/hyperv/hyperv_wmi.c
@@ -683,7 +683,7 @@ hypervSerializeEmbeddedParam(hypervParamPtr p, const char *resourceUri,
/* retrieve parameters out of hash table */
numKeys = virHashSize(p->embedded.table);
- items = virHashGetItems(p->embedded.table, NULL);
+ items = virHashGetItems(p->embedded.table, NULL, false);
if (!items) {
virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
_("Could not read embedded param hash table"));
diff --git a/src/locking/lock_daemon.c b/src/locking/lock_daemon.c
index 8f16dfd064..021792cc69 100644
--- a/src/locking/lock_daemon.c
+++ b/src/locking/lock_daemon.c
@@ -730,7 +730,7 @@ virLockDaemonPreExecRestart(const char *state_file,
}
- tmp = pairs = virHashGetItems(lockDaemon->lockspaces, NULL);
+ tmp = pairs = virHashGetItems(lockDaemon->lockspaces, NULL, false);
while (tmp && tmp->key) {
virLockSpacePtr lockspace = (virLockSpacePtr)tmp->value;
diff --git a/src/nwfilter/nwfilter_ebiptables_driver.c b/src/nwfilter/nwfilter_ebiptables_driver.c
index da6f88f135..8dfc870ab7 100644
--- a/src/nwfilter/nwfilter_ebiptables_driver.c
+++ b/src/nwfilter/nwfilter_ebiptables_driver.c
@@ -3126,9 +3126,12 @@ virNWFilterRuleInstSortPtr(const void *a, const void *b)
static int
-ebiptablesFilterOrderSort(const virHashKeyValuePair *a,
- const virHashKeyValuePair *b)
+ebiptablesFilterOrderSort(const void *va,
+ const void *vb)
{
+ const virHashKeyValuePair *a = va;
+ const virHashKeyValuePair *b = vb;
+
/* elements' values has been limited to range [-1000, 1000] */
return *(virNWFilterChainPriority *)a->value -
*(virNWFilterChainPriority *)b->value;
@@ -3288,13 +3291,15 @@ ebtablesGetSubChainInsts(virHashTablePtr chains,
size_t *ninsts)
{
g_autofree virHashKeyValuePairPtr filter_names = NULL;
+ size_t nfilter_names;
size_t i;
- filter_names = virHashGetItems(chains,
- ebiptablesFilterOrderSort);
+ filter_names = virHashGetItems(chains, &nfilter_names, false);
if (filter_names == NULL)
return -1;
+ qsort(filter_names, nfilter_names, sizeof(*filter_names), ebiptablesFilterOrderSort);
+
for (i = 0; filter_names[i].key; i++) {
g_autofree ebtablesSubChainInstPtr inst = NULL;
enum l3_proto_idx idx = ebtablesGetProtoIdxByFiltername(
diff --git a/src/qemu/qemu_interop_config.c b/src/qemu/qemu_interop_config.c
index 53b251f056..e806d1e41f 100644
--- a/src/qemu/qemu_interop_config.c
+++ b/src/qemu/qemu_interop_config.c
@@ -83,13 +83,6 @@ qemuBuildFileList(virHashTablePtr files, const char *dir)
return ret;
}
-static int
-qemuConfigFilesSorter(const virHashKeyValuePair *a,
- const virHashKeyValuePair *b)
-{
- return strcmp(a->key, b->key);
-}
-
#define QEMU_SYSTEM_LOCATION PREFIX "/share/qemu"
#define QEMU_ETC_LOCATION SYSCONFDIR "/qemu"
@@ -145,7 +138,7 @@ qemuInteropFetchConfigs(const char *name,
if (virHashSize(files) == 0)
return 0;
- if (!(pairs = virHashGetItems(files, qemuConfigFilesSorter)))
+ if (!(pairs = virHashGetItems(files, NULL, true)))
return -1;
for (tmp = pairs; tmp->key; tmp++) {
diff --git a/src/rpc/virnetdaemon.c b/src/rpc/virnetdaemon.c
index ce13f0d927..525cbb3ce6 100644
--- a/src/rpc/virnetdaemon.c
+++ b/src/rpc/virnetdaemon.c
@@ -378,15 +378,6 @@ virNetDaemonNewPostExecRestart(virJSONValuePtr object,
}
-static int
-daemonServerCompare(const virHashKeyValuePair *a, const virHashKeyValuePair *b)
-{
- const char *as = a->key;
- const char *bs = b->key;
-
- return strcmp(as, bs);
-}
-
virJSONValuePtr
virNetDaemonPreExecRestart(virNetDaemonPtr dmn)
{
@@ -402,7 +393,7 @@ virNetDaemonPreExecRestart(virNetDaemonPtr dmn)
goto error;
}
- if (!(srvArray = virHashGetItems(dmn->servers, daemonServerCompare)))
+ if (!(srvArray = virHashGetItems(dmn->servers, NULL, true)))
goto error;
for (i = 0; srvArray[i].key; i++) {
diff --git a/src/util/virhash.c b/src/util/virhash.c
index 301e485e69..2a27ce8de6 100644
--- a/src/util/virhash.c
+++ b/src/util/virhash.c
@@ -626,49 +626,63 @@ void *virHashSearch(const virHashTable *ctable,
return NULL;
}
-struct getKeysIter
-{
- virHashKeyValuePair *sortArray;
- size_t arrayIdx;
+
+struct virHashGetItemsIteratorData {
+ virHashKeyValuePair *items;
+ size_t i;
};
-static int virHashGetKeysIterator(void *payload,
- const char *key, void *data)
+
+static int
+virHashGetItemsIterator(void *payload,
+ const char *key,
+ void *opaque)
{
- struct getKeysIter *iter = data;
+ struct virHashGetItemsIteratorData *data = opaque;
- iter->sortArray[iter->arrayIdx].key = key;
- iter->sortArray[iter->arrayIdx].value = payload;
+ data->items[data->i].key = key;
+ data->items[data->i].value = payload;
- iter->arrayIdx++;
+ data->i++;
return 0;
}
-typedef int (*qsort_comp)(const void *, const void *);
-virHashKeyValuePairPtr virHashGetItems(virHashTablePtr table,
- virHashKeyComparator compar)
+static int
+virHashGetItemsKeySorter(const void *va,
+ const void *vb)
{
- ssize_t numElems = virHashSize(table);
- struct getKeysIter iter = {
- .arrayIdx = 0,
- .sortArray = NULL,
- };
+ const virHashKeyValuePair *a = va;
+ const virHashKeyValuePair *b = vb;
- if (numElems < 0)
- return NULL;
+ return strcmp(a->key, b->key);
+}
+
+
+virHashKeyValuePairPtr
+virHashGetItems(virHashTablePtr table,
+ size_t *nitems,
+ bool sortKeys)
+{
+ size_t dummy;
+ struct virHashGetItemsIteratorData data = { .items = NULL, .i = 0 };
- iter.sortArray = g_new0(virHashKeyValuePair, numElems + 1);
+ if (!nitems)
+ nitems = &dummy;
- virHashForEach(table, virHashGetKeysIterator, &iter);
+ *nitems = virHashSize(table);
- if (compar)
- qsort(&iter.sortArray[0], numElems, sizeof(iter.sortArray[0]),
- (qsort_comp)compar);
+ data.items = g_new0(virHashKeyValuePair, *nitems + 1);
- return iter.sortArray;
+ virHashForEach(table, virHashGetItemsIterator, &data);
+
+ if (sortKeys)
+ qsort(data.items, *nitems, sizeof(* data.items), virHashGetItemsKeySorter);
+
+ return data.items;
}
+
struct virHashEqualData
{
bool equal;
diff --git a/src/util/virhash.h b/src/util/virhash.h
index 029e6e83b7..d8b31e43a1 100644
--- a/src/util/virhash.h
+++ b/src/util/virhash.h
@@ -116,10 +116,9 @@ struct _virHashKeyValuePair {
const void *key;
const void *value;
};
-typedef int (*virHashKeyComparator)(const virHashKeyValuePair *,
- const virHashKeyValuePair *);
virHashKeyValuePairPtr virHashGetItems(virHashTablePtr table,
- virHashKeyComparator compar);
+ size_t *nitems,
+ bool sortedKeys);
/*
* Compare two tables for equality: the lookup of a key's value in
diff --git a/src/util/virlockspace.c b/src/util/virlockspace.c
index 2731d46dfc..d39f2c026f 100644
--- a/src/util/virlockspace.c
+++ b/src/util/virlockspace.c
@@ -435,7 +435,7 @@ virJSONValuePtr virLockSpacePreExecRestart(virLockSpacePtr lockspace)
goto error;
}
- tmp = pairs = virHashGetItems(lockspace->resources, NULL);
+ tmp = pairs = virHashGetItems(lockspace->resources, NULL, false);
while (tmp && tmp->value) {
virLockSpaceResourcePtr res = (virLockSpaceResourcePtr)tmp->value;
virJSONValuePtr child = virJSONValueNewObject();
diff --git a/tests/virhashtest.c b/tests/virhashtest.c
index 8cc3109929..93949d8b7a 100644
--- a/tests/virhashtest.c
+++ b/tests/virhashtest.c
@@ -361,13 +361,6 @@ testHashSearch(const void *data G_GNUC_UNUSED)
}
-static int
-testHashGetItemsCompKey(const virHashKeyValuePair *a,
- const virHashKeyValuePair *b)
-{
- return strcmp(a->key, b->key);
-}
-
static int
testHashGetItems(const void *data G_GNUC_UNUSED)
{
@@ -389,14 +382,14 @@ testHashGetItems(const void *data G_GNUC_UNUSED)
goto cleanup;
}
- if (!(array = virHashGetItems(hash, NULL)) ||
+ if (!(array = virHashGetItems(hash, NULL, false)) ||
array[3].key || array[3].value) {
VIR_TEST_VERBOSE("\nfailed to get items with NULL sort");
goto cleanup;
}
VIR_FREE(array);
- if (!(array = virHashGetItems(hash, testHashGetItemsCompKey)) ||
+ if (!(array = virHashGetItems(hash, NULL, true)) ||
STRNEQ(array[0].key, "a") ||
STRNEQ(array[0].value, "3") ||
STRNEQ(array[1].key, "b") ||
--
2.26.2
More information about the libvir-list
mailing list