commit: cf086cd6b3c452729f68fd9ce3411e28976ae94e
Author: Fabian Groffen <grobian <AT> gentoo <DOT> org>
AuthorDate: Sat Sep 21 19:48:29 2019 +0000
Commit: Fabian Groffen <grobian <AT> gentoo <DOT> org>
CommitDate: Sat Sep 21 19:48:29 2019 +0000
URL: https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=cf086cd6
libq/set: add funcs for key/value support
Signed-off-by: Fabian Groffen <grobian <AT> gentoo.org>
libq/set.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++--------
libq/set.h | 10 ++++--
libq/xarray.h | 4 +--
3 files changed, 100 insertions(+), 17 deletions(-)
diff --git a/libq/set.c b/libq/set.c
index f2c9394..a934a0d 100644
--- a/libq/set.c
+++ b/libq/set.c
@@ -18,7 +18,7 @@
#include "set.h"
static unsigned int
-fnv1a32(char *s)
+fnv1a32(const char *s)
{
unsigned int ret = 2166136261UL;
for (; *s != '\0'; s++)
@@ -33,7 +33,7 @@ create_set(void)
return xzalloc(sizeof(set));
}
-/* add elem to a set (unpure: could add duplicates) */
+/* add elem to a set (unpure: could add duplicates, basically hash) */
set *
add_set(const char *name, set *q)
{
@@ -47,6 +47,7 @@ add_set(const char *name, set *q)
ll->next = NULL;
ll->name = xstrdup(name);
ll->hash = fnv1a32(ll->name);
+ ll->val = NULL;
pos = ll->hash % _SET_HASH_SIZE;
if (q->buckets[pos] == NULL) {
@@ -61,11 +62,10 @@ add_set(const char *name, set *q)
return q;
}
-/* add elem to set if it doesn't exist yet (pure definition of set) */
+/* add elem to set if it doesn't exist yet (pure definition of hash) */
set *
add_set_unique(const char *name, set *q, bool *unique)
{
- char *mname = xstrdup(name);
unsigned int hash;
int pos;
elem *ll;
@@ -75,20 +75,20 @@ add_set_unique(const char *name, set *q, bool *unique)
if (q == NULL)
q = create_set();
- hash = fnv1a32(mname);
+ hash = fnv1a32(name);
pos = hash % _SET_HASH_SIZE;
if (q->buckets[pos] == NULL) {
q->buckets[pos] = ll = xmalloc(sizeof(*ll));
ll->next = NULL;
- ll->name = mname;
+ ll->name = xstrdup(name);
ll->hash = hash;
+ ll->val = NULL;
uniq = true;
} else {
ll = NULL;
for (w = q->buckets[pos]; w != NULL; ll = w, w = w->next) {
- if (w->hash == hash && strcmp(w->name, mname) == 0) {
- free(mname);
+ if (w->hash == hash && strcmp(w->name, name) == 0) {
uniq = false;
break;
}
@@ -96,8 +96,9 @@ add_set_unique(const char *name, set *q, bool *unique)
if (w == NULL) {
ll = ll->next = xmalloc(sizeof(*ll));
ll->next = NULL;
- ll->name = mname;
+ ll->name = xstrdup(name);
ll->hash = hash;
+ ll->val = NULL;
uniq = true;
}
}
@@ -109,22 +110,60 @@ add_set_unique(const char *name, set *q, bool *unique)
return q;
}
+/* add ptr to set with name as key, return existing value when key
+ * already exists or NULL otherwise */
+void *
+add_set_value(const char *name, void *ptr, set *q)
+{
+ unsigned int hash;
+ int pos;
+ elem *ll;
+ elem *w;
+
+ hash = fnv1a32(name);
+ pos = hash % _SET_HASH_SIZE;
+
+ if (q->buckets[pos] == NULL) {
+ q->buckets[pos] = ll = xmalloc(sizeof(*ll));
+ ll->next = NULL;
+ ll->name = xstrdup(name);
+ ll->hash = hash;
+ ll->val = ptr;
+ } else {
+ ll = NULL;
+ for (w = q->buckets[pos]; w != NULL; ll = w, w = w->next) {
+ if (w->hash == hash && strcmp(w->name, name) == 0)
+ return w->val;
+ }
+ if (w == NULL) {
+ ll = ll->next = xmalloc(sizeof(*ll));
+ ll->next = NULL;
+ ll->name = xstrdup(name);
+ ll->hash = hash;
+ ll->val = ptr;
+ }
+ }
+
+ q->len++;
+ return NULL;
+}
+
/* returns whether s is in set */
bool
-contains_set(char *s, set *q)
+contains_set(const char *name, set *q)
{
unsigned int hash;
int pos;
elem *w;
bool found;
- hash = fnv1a32(s);
+ hash = fnv1a32(name);
pos = hash % _SET_HASH_SIZE;
found = false;
if (q->buckets[pos] != NULL) {
for (w = q->buckets[pos]; w != NULL; w = w->next) {
- if (w->hash == hash && strcmp(w->name, s) == 0) {
+ if (w->hash == hash && strcmp(w->name, name) == 0) {
found = true;
break;
}
@@ -134,9 +173,31 @@ contains_set(char *s, set *q)
return found;
}
+/* returns the value for name, or NULL if not found (cannot
+ * differentiate between value NULL and unset) */
+void *
+get_set(const char *name, set *q)
+{
+ unsigned int hash;
+ int pos;
+ elem *w;
+
+ hash = fnv1a32(name);
+ pos = hash % _SET_HASH_SIZE;
+
+ if (q->buckets[pos] != NULL) {
+ for (w = q->buckets[pos]; w != NULL; w = w->next) {
+ if (w->hash == hash && strcmp(w->name, name) == 0)
+ return w->val;
+ }
+ }
+
+ return NULL;
+}
+
/* remove elem from a set. matches ->name and frees name,item */
set *
-del_set(char *s, set *q, bool *removed)
+del_set(const char *s, set *q, bool *removed)
{
unsigned int hash;
int pos;
@@ -191,6 +252,22 @@ list_set(set *q, char ***l)
return q->len;
}
+size_t
+values_set(set *q, array_t *ret)
+{
+ int i;
+ elem *w;
+ array_t blank = array_init_decl;
+
+ *ret = blank;
+ for (i = 0; i < _SET_HASH_SIZE; i++) {
+ for (w = q->buckets[i]; w != NULL; w = w->next)
+ xarraypush_ptr(ret, w->val);
+ }
+
+ return q->len;
+}
+
/* clear out a set */
void
clear_set(set *q)
diff --git a/libq/set.h b/libq/set.h
index 7ca5f65..00ef909 100644
--- a/libq/set.h
+++ b/libq/set.h
@@ -10,12 +10,15 @@
#include <stdbool.h>
#include <unistd.h>
+#include "xarray.h"
+
typedef struct elem_t elem;
typedef struct set_t set;
struct elem_t {
char *name;
unsigned int hash; /* FNV1a32 */
+ void *val;
elem *next;
};
@@ -28,9 +31,12 @@ struct set_t {
set *create_set(void);
set *add_set(const char *name, set *q);
set *add_set_unique(const char *name, set *q, bool *unique);
-bool contains_set(char *s, set *q);
-set *del_set(char *s, set *q, bool *removed);
+void *add_set_value(const char *name, void *ptr, set *q);
+bool contains_set(const char *name, set *q);
+void *get_set(const char *name, set *q);
+set *del_set(const char *s, set *q, bool *removed);
size_t list_set(set *q, char ***l);
+size_t values_set(set *q, array_t *ret);
void free_set(set *q);
void clear_set(set *q);
diff --git a/libq/xarray.h b/libq/xarray.h
index 22ee47a..71dfecb 100644
--- a/libq/xarray.h
+++ b/libq/xarray.h
@@ -26,9 +26,9 @@ typedef struct {
*/
/* TODO: remove ele = NULL after checking all consumers don't rely on this */
#define array_for_each(arr, n, ele) \
- for (n = 0, ele = NULL; n < array_cnt(arr) && (ele = arr->eles[n]); n++)
+ for (n = 0, ele = NULL; n < array_cnt(arr) && (ele = (arr)->eles[n]);
n++)
#define array_for_each_rev(arr, n, ele) \
- for (n = array_cnt(arr); n-- > 0 && (ele = arr->eles[n]); /*nothing*/)
+ for (n = array_cnt(arr); n-- > 0 && (ele = (arr)->eles[n]); /*nothing*/)
#define array_get_elem(arr, n) (arr->eles[n])
#define array_init_decl { .eles = NULL, .num = 0, }
#define array_cnt(arr) (arr)->num
