[gentoo-commits] proj/portage-utils:master commit in: libq/

["Fabian Groffen" <grobian@gentoo.org>]

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