From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id 61EF8138334 for ; Sat, 21 Sep 2019 19:54:00 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 9C65AE08D0; Sat, 21 Sep 2019 19:53:58 +0000 (UTC) Received: from smtp.gentoo.org (mail.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id 6297FE0897 for ; Sat, 21 Sep 2019 19:53:58 +0000 (UTC) Received: from oystercatcher.gentoo.org (unknown [IPv6:2a01:4f8:202:4333:225:90ff:fed9:fc84]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.gentoo.org (Postfix) with ESMTPS id 04FA834B465 for ; Sat, 21 Sep 2019 19:53:57 +0000 (UTC) Received: from localhost.localdomain (localhost [IPv6:::1]) by oystercatcher.gentoo.org (Postfix) with ESMTP id 9A0F1720 for ; Sat, 21 Sep 2019 19:53:54 +0000 (UTC) From: "Fabian Groffen" To: gentoo-commits@lists.gentoo.org Content-Transfer-Encoding: 8bit Content-type: text/plain; charset=UTF-8 Reply-To: gentoo-dev@lists.gentoo.org, "Fabian Groffen" Message-ID: <1569095309.cf086cd6b3c452729f68fd9ce3411e28976ae94e.grobian@gentoo> Subject: [gentoo-commits] proj/portage-utils:master commit in: libq/ X-VCS-Repository: proj/portage-utils X-VCS-Files: libq/set.c libq/set.h libq/xarray.h X-VCS-Directories: libq/ X-VCS-Committer: grobian X-VCS-Committer-Name: Fabian Groffen X-VCS-Revision: cf086cd6b3c452729f68fd9ce3411e28976ae94e X-VCS-Branch: master Date: Sat, 21 Sep 2019 19:53:54 +0000 (UTC) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-commits@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply X-Archives-Salt: db35db01-c569-4c9a-a871-7d264dbd1f3f X-Archives-Hash: 87ed6e673fd5dddf0bf89789eb2fb3ad commit: cf086cd6b3c452729f68fd9ce3411e28976ae94e Author: Fabian Groffen gentoo org> AuthorDate: Sat Sep 21 19:48:29 2019 +0000 Commit: Fabian Groffen gentoo 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 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 #include +#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