libq: introduce set to replace virtuals (queue)

The virtuals file contained some queue functions which actually were
list functions.  Replaced this with a proper set, which hash backend to
speed up many search operations.  Changed throughout the code to use
more efficient path.

While at it, merge xstrdup wrappers in xmalloc, and use wrappers more
consistently.

Signed-off-by: Fabian Groffen <grobian@gentoo.org>

15 files changed, 438 insertions, 316 deletions

diff --git a/.depend b/.depend
index f823923..d5d2228 100644
--- a/.depend
+++ b/.depend
@@ -1,10 +1,10 @@
 main.o: main.c porting.h main.h libq/libq.c libq/busybox.h libq/i18n.h \
- libq/libq.h libq/colors.c libq/xmalloc.c libq/xstrdup.c libq/xasprintf.c \
- libq/hash_fd.c libq/md5_sha1_sum.c libq/human_readable.c libq/rmspace.c \
- libq/compat.c libq/copy_file.c libq/safe_io.c libq/xchdir.c \
- libq/xmkdir.c libq/xregex.c libq/xsystem.c libq/xarray.c \
- libq/atom_explode.c libq/atom_compare.c libq/basename.c libq/scandirat.c \
- libq/prelink.c libq/profile.c libq/vdb.c libq/vdb_get_next_dir.c \
- libq/virtuals.c applets.h include_applets.h q.c qcheck.c qdepends.c \
- qfile.c qlist.c qlop.c qsearch.c qsize.c qtbz2.c quse.c qxpak.c qpkg.c \
- qgrep.c qatom.c qmerge.c qcache.c qtegrity.c
+ libq/libq.h libq/colors.c libq/xmalloc.c libq/xasprintf.c libq/hash_fd.c \
+ libq/md5_sha1_sum.c libq/human_readable.c libq/rmspace.c libq/compat.c \
+ libq/copy_file.c libq/safe_io.c libq/xchdir.c libq/xmkdir.c \
+ libq/xregex.c libq/xsystem.c libq/xarray.c libq/atom_explode.c \
+ libq/atom_compare.c libq/basename.c libq/scandirat.c libq/prelink.c \
+ libq/profile.c libq/vdb.c libq/vdb_get_next_dir.c libq/set.c applets.h \
+ include_applets.h q.c qcheck.c qdepends.c qfile.c qlist.c qlop.c \
+ qsearch.c qsize.c qtbz2.c quse.c qxpak.c qpkg.c qgrep.c qatom.c qmerge.c \
+ qcache.c qtegrity.c
diff --git a/Makefile.am b/Makefile.am
index db20879..2e6f985 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -119,16 +119,15 @@ EXTRA_DIST += \
 	libq/rmspace.c \
 	libq/safe_io.c \
 	libq/scandirat.c \
+	libq/set.c \
 	libq/vdb.c \
 	libq/vdb_get_next_dir.c \
-	libq/virtuals.c \
 	libq/xarray.c \
 	libq/xasprintf.c \
 	libq/xchdir.c \
 	libq/xmalloc.c \
 	libq/xmkdir.c \
 	libq/xregex.c \
-	libq/xstrdup.c \
 	libq/xsystem.c \
 	main.c \
 	main.h \
diff --git a/TODO.md b/TODO.md
index 24e5eca..31d916d 100644
--- a/TODO.md
+++ b/TODO.md
@@ -11,7 +11,8 @@
 
 - standardize/unify/clean up misc handling of colors
 
-- speed up queue structure ... append walks the whole list
+- remove odd rmspace for each string in libq/set.c (allows a lot less
+  malloc/frees)
 
 - equiv of `equery m` (metadata)
 
diff --git a/libq/basename.c b/libq/basename.c
index dcf3cce..2a3b2e6 100644
--- a/libq/basename.c
+++ b/libq/basename.c
@@ -1,8 +1,9 @@
 /*
- * Copyright 2014 Gentoo Foundation
+ * Copyright 2014-2019 Gentoo Foundation
  * Distributed under the terms of the GNU General Public License v2
  */
 
+/* our own basename which does not modify its input */
 static const char *_basename(const char *filename)
 {
 	const char *p = strrchr(filename, '/');
diff --git a/libq/libq.c b/libq/libq.c
index 28fe5d1..a9e5b6a 100644
--- a/libq/libq.c
+++ b/libq/libq.c
@@ -1,3 +1,12 @@
+/*
+ * Copyright 2005-2018 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ *
+ * Copyright 2005-2008 Ned Ludd        - <solar@gentoo.org>
+ * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
+ * Copyright 2018-     Fabian Groffen  - <grobian@gentoo.org>
+ */
+
 #if defined(__linux__)
 # include <endian.h>
 # include <byteswap.h>
@@ -11,7 +20,6 @@
 #include "libq.h"
 #include "colors.c"
 #include "xmalloc.c"
-#include "xstrdup.c"
 #include "xasprintf.c"
 #include "hash_fd.c"
 #include "md5_sha1_sum.c"
@@ -38,5 +46,5 @@
 # include "profile.c"
 # include "vdb.c"
 # include "vdb_get_next_dir.c"
-# include "virtuals.c"
+# include "set.c"
 #endif
diff --git a/libq/rmspace.c b/libq/rmspace.c
index 40c3808..3159b08 100644
--- a/libq/rmspace.c
+++ b/libq/rmspace.c
@@ -7,7 +7,6 @@
  * Copyright 2019-     Fabian Groffen  - <grobian@gentoo.org>
  */
 
-
 /* remove leading/trailing extraneous white space */
 static char *rmspace_len(char *s, size_t len)
 {
diff --git a/libq/set.c b/libq/set.c
new file mode 100644
index 0000000..68799fe
--- /dev/null
+++ b/libq/set.c
@@ -0,0 +1,239 @@
+/*
+ * Copyright 2005-2019 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ *
+ * Copyright 2005-2010 Ned Ludd        - <solar@gentoo.org>
+ * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
+ * Copyright 2019-     Fabian Groffen  - <grobian@gentoo.org>
+ */
+
+#include <stdio.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct elem_t elem;
+typedef struct set_t set;
+
+struct elem_t {
+	char *name;
+	unsigned int hash;  /* FNV1a32 */
+	elem *next;
+};
+
+#define _SET_HASH_SIZE 128
+struct set_t {
+	elem *buckets[_SET_HASH_SIZE];
+	size_t len;
+};
+
+static unsigned int
+fnv1a32(char *s)
+{
+	unsigned int ret = 2166136261UL;
+	for (; *s != '\0'; s++)
+		ret = (ret ^ (unsigned int)*s) * 16777619;
+	return ret;
+}
+
+/* create a set */
+static set *
+create_set(void)
+{
+	return xzalloc(sizeof(set));
+}
+
+/* add elem to a set (unpure: could add duplicates) */
+static set *
+add_set(const char *name, set *q)
+{
+	int pos;
+	elem *ll = xmalloc(sizeof(*ll));
+	elem *w;
+
+	if (q == NULL)
+		q = create_set();
+
+	ll->next = NULL;
+	ll->name = xstrdup(name);
+	rmspace(ll->name);
+	ll->hash = fnv1a32(ll->name);
+
+	pos = ll->hash % _SET_HASH_SIZE;
+	if (q->buckets[pos] == NULL) {
+		q->buckets[pos] = ll;
+	} else {
+		for (w = q->buckets[pos]; w->next != NULL; w = w->next)
+			;
+		w->next = ll;
+	}
+
+	q->len++;
+	return q;
+}
+
+/* add elem to set if it doesn't exist yet (pure definition of set) */
+static set *
+add_set_unique(const char *name, set *q, bool *unique)
+{
+	char *mname = xstrdup(name);
+	int hash;
+	int pos;
+	elem *ll;
+	elem *w;
+
+	if (q == NULL)
+		q = create_set();
+
+	rmspace(mname);
+	hash = fnv1a32(mname);
+	pos = hash % _SET_HASH_SIZE;
+
+	if (q->buckets[pos] == NULL) {
+		q->buckets[pos] = ll = xmalloc(sizeof(*ll));
+		ll->next = NULL;
+		ll->name = mname;
+		ll->hash = hash;
+		*unique = 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);
+				*unique = false;
+				break;
+			}
+		}
+		if (w == NULL) {
+			ll = ll->next = xmalloc(sizeof(*ll));
+			ll->next = NULL;
+			ll->name = mname;
+			ll->hash = hash;
+			*unique = true;
+		}
+	}
+
+	if (*unique)
+		q->len++;
+	return q;
+}
+
+/* returns whether s is in set */
+static bool
+contains_set(char *s, set *q)
+{
+	char *mname = xstrdup(s);
+	int hash;
+	int pos;
+	elem *w;
+	bool found;
+
+	rmspace(mname);
+	hash = fnv1a32(mname);
+	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, mname) == 0) {
+				found = true;
+				break;
+			}
+		}
+	}
+
+	free(mname);
+	return found;
+}
+
+/* remove elem from a set. matches ->name and frees name,item */
+static set *
+del_set(char *s, set *q, bool *removed)
+{
+	char *mname = xstrdup(s);
+	unsigned int hash;
+	int pos;
+	elem *ll;
+	elem *w;
+
+	rmspace(mname);
+	hash = fnv1a32(mname);
+	pos = hash % _SET_HASH_SIZE;
+
+	*removed = false;
+	if (q->buckets[pos] != NULL) {
+		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 (ll == NULL) {
+					q->buckets[pos] = w->next;
+				} else {
+					ll->next = w->next;
+				}
+				free(w->name);
+				free(w);
+				*removed = true;
+				break;
+			}
+		}
+	}
+
+	if (*removed)
+		q->len--;
+	return q;
+}
+
+/* return the contents of a set as an array of strings
+ * the length of the list is returned, and the array is terminated with
+ * a NULL (not included in returned length)
+ * the caller should free l, but not the strings within */
+static size_t
+list_set(set *q, char ***l)
+{
+	int i;
+	elem *w;
+	char **ret;
+
+	ret = *l = xmalloc(sizeof(char **) * (q->len + 1));
+	for (i = 0; i < _SET_HASH_SIZE; i++) {
+		for (w = q->buckets[i]; w != NULL; w = w->next) {
+			*ret = w->name;
+			ret++;
+		}
+	}
+	*ret = NULL;
+	return q->len;
+}
+
+/* clear out a set */
+static void
+free_set(set *q)
+{
+	int i;
+	elem *w;
+	elem *e;
+
+	for (i = 0; i < _SET_HASH_SIZE; i++) {
+		for (w = q->buckets[i]; w != NULL; w = e) {
+			e = w->next;
+			free(w->name);
+			free(w);
+		}
+	}
+	free(q);
+}
+
+#ifdef EBUG
+static void
+print_set(const set *q)
+{
+	elem *w;
+	int i;
+
+	for (i = 0; i < _SET_HASH_SIZE; i++) {
+		for (w = q->buckets[i]; w != NULL; w = w->next)
+			puts(w->name);
+	}
+}
+#endif
diff --git a/libq/virtuals.c b/libq/virtuals.c
deleted file mode 100644
index f96b207..0000000
--- a/libq/virtuals.c
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
- * Copyright 2005-2018 Gentoo Foundation
- * Distributed under the terms of the GNU General Public License v2
- *
- * Copyright 2005-2010 Ned Ludd        - <solar@gentoo.org>
- * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
- */
-
-#include <stdio.h>
-#include <unistd.h>
-#include <stdlib.h>
-#include <string.h>
-
-/* used to queue a lot of things */
-struct queue_t {
-	char *name;
-	struct queue_t *next;
-};
-
-typedef struct queue_t queue;
-
-static queue *
-append_set(queue *q, queue *ll)
-{
-	queue *z;
-
-	if (!q)
-		return ll;
-
-	z = q;
-	while (z->next)
-		z = z->next;
-	z->next = ll;
-
-	return q;
-}
-
-/* add a set to a cache */
-static queue *
-add_set(const char *name, queue *q)
-{
-	queue *ll = xmalloc(sizeof(*ll));
-	ll->next = NULL;
-	ll->name = xstrdup(name);
-	rmspace(ll->name);
-	return append_set(q, ll);
-}
-
-/* Performance here is terrible.  Should use a hash at some point. */
-static queue *
-add_set_unique(const char *name, queue *q, bool *ok)
-{
-	queue *ll = q;
-	while (ll) {
-		if (!strcmp(ll->name, name)) {
-			*ok = false;
-			return q;
-		}
-		ll = ll->next;
-	}
-	*ok = true;
-	return add_set(name, q);
-}
-
-/* remove a set from a cache. matches ->name and frees name,item */
-static queue *
-del_set(char *s, queue *q, int *ok)
-{
-	queue *ll, *list, *old;
-	ll = q;
-	list = q;
-	old = q;
-	*ok = 0;
-
-	while (ll != NULL) {
-		if (strcmp(ll->name, s) == 0) {
-			if (ll == list) {
-				list = (ll->next);
-				free(ll->name);
-				free(ll);
-				ll = list;
-
-			} else {
-				old->next = ll->next;
-				free(ll->name);
-				free(ll);
-				ll = old->next;
-			}
-			*ok = 1;
-		} else {
-			old = ll;
-			ll = ll->next;
-		}
-	}
-	return list;
-}
-
-/* clear out a list */
-static void
-free_sets(queue *list)
-{
-	queue *ll, *q;
-	ll = list;
-	while (ll != NULL) {
-		q = ll->next;
-		free(ll->name);
-		free(ll);
-		ll = q;
-	}
-}
-
-#ifdef EBUG
-static void
-print_sets(const queue *list)
-{
-	const queue *ll;
-	for (ll = list; ll != NULL; ll = ll->next)
-		puts(ll->name);
-}
-#endif
diff --git a/libq/xmalloc.c b/libq/xmalloc.c
index 9a9173d..3d4537d 100644
--- a/libq/xmalloc.c
+++ b/libq/xmalloc.c
@@ -3,6 +3,7 @@
  * Utility routines.
  *
  * Copyright (C) 1999-2004 by Erik Andersen <andersen@codepoet.org>
+ * Copyright (C) 2019-        Fabian Groffen <grobian@gentoo.org>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -19,13 +20,9 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  */
 
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <unistd.h>
-#include <fcntl.h>
 
 static void *xmalloc(size_t size)
 {
@@ -46,8 +43,6 @@ static void *xcalloc(size_t nmemb, size_t size)
 static void *xzalloc(size_t size)
 {
 	void *ptr = xmalloc(size);
-	if (unlikely(ptr == NULL))
-		err("Out of memory");
 	memset(ptr, 0x00, size);
 	return ptr;
 }
@@ -66,3 +61,20 @@ static void *xmemdup(const void *src, size_t n)
 	memcpy(ret, src, n);
 	return ret;
 }
+
+static char *xstrdup_len(const char *s, size_t *len)
+{
+
+	if (s == NULL)
+		return NULL;
+
+	*len = strlen(s);
+	return xmemdup(s, *len + 1);
+}
+
+static char *xstrdup(const char *s)
+{
+	size_t len;
+
+	return xstrdup_len(s, &len);
+}
diff --git a/libq/xstrdup.c b/libq/xstrdup.c
deleted file mode 100644
index e069c9d..0000000
--- a/libq/xstrdup.c
+++ /dev/null
@@ -1,53 +0,0 @@
-/* vi: set sw=4 ts=4: */
-/*
- * Utility routines.
- *
- * Copyright (C) 1999-2004 by Erik Andersen <andersen@codepoet.org>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- */
-
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <fcntl.h>
-
-static char *xstrdup(const char *s)
-{
-	void *t;
-
-	if (s == NULL)
-		return NULL;
-
-	t = (void *)strdup(s);
-	if (unlikely(t == NULL))
-		err("Out of memory");
-
-	return (char *)t;
-}
-
-static char *xstrdup_len(const char *s, size_t *len)
-{
-	char *ret;
-
-	*len = strlen(s);
-	ret = xmalloc(*len + 1);
-	memcpy(ret, s, *len + 1);
-
-	return ret;
-}
diff --git a/main.c b/main.c
index 2eeb21b..044777c 100644
--- a/main.c
+++ b/main.c
@@ -1423,7 +1423,7 @@ atom_to_pvr(depend_atom *atom) {
 }
 
 /* TODO: Merge this into libq/vdb.c somehow. */
-static queue *
+static set *
 get_vdb_atoms(int fullcpv)
 {
 	q_vdb_ctx *ctx;
@@ -1440,18 +1440,21 @@ get_vdb_atoms(int fullcpv)
 	struct dirent **pf;
 
 	depend_atom *atom = NULL;
-	queue *cpf = NULL;
+	set *cpf = NULL;
 
 	ctx = q_vdb_open();
 	if (!ctx)
 		return NULL;
 
 	/* scan the cat first */
-	if ((cfd = scandirat(ctx->vdb_fd, ".", &cat, q_vdb_filter_cat, alphasort)) < 0)
+	cfd = scandirat(ctx->vdb_fd, ".", &cat, q_vdb_filter_cat, alphasort);
+	if (cfd < 0)
 		goto fuckit;
 
 	for (j = 0; j < cfd; j++) {
-		if ((dfd = scandirat(ctx->vdb_fd, cat[j]->d_name, &pf, q_vdb_filter_pkg, alphasort)) < 0)
+		dfd = scandirat(ctx->vdb_fd, cat[j]->d_name,
+				&pf, q_vdb_filter_pkg, alphasort);
+		if (dfd < 0)
 			continue;
 		for (i = 0; i < dfd; i++) {
 			int blen = snprintf(buf, sizeof(buf), "%s/%s/SLOT",
@@ -1475,9 +1478,11 @@ get_vdb_atoms(int fullcpv)
 
 			if (fullcpv) {
 				if (atom->PR_int)
-					snprintf(buf, sizeof(buf), "%s/%s-%s-r%i", atom->CATEGORY, atom->PN, atom->PV, atom->PR_int);
+					snprintf(buf, sizeof(buf), "%s/%s-%s-r%i",
+							atom->CATEGORY, atom->PN, atom->PV, atom->PR_int);
 				else
-					snprintf(buf, sizeof(buf), "%s/%s-%s", atom->CATEGORY, atom->PN, atom->PV);
+					snprintf(buf, sizeof(buf), "%s/%s-%s",
+							atom->CATEGORY, atom->PN, atom->PV);
 			} else {
 				snprintf(buf, sizeof(buf), "%s/%s", atom->CATEGORY, atom->PN);
 			}
diff --git a/qcache.c b/qcache.c
index 831af2e..e4b6a7e 100644
--- a/qcache.c
+++ b/qcache.c
@@ -54,7 +54,8 @@ typedef struct {
 /* Global Variables                                                 */
 /********************************************************************/
 
-static queue *arches;
+static set *archs;
+static char **archlist;
 static int archlist_count;
 static size_t arch_longest_len;
 const char status[3] = {'-', '~', '+'};
@@ -99,12 +100,12 @@ decode_status(char c)
  * IN:
  *  const char *arch - name of an arch (alpha, amd64, ...)
  * OUT:
- *  int pos - location of arch in archlist[]
+ *  int - position in keywords, or -1 if not found
  */
 static int
 decode_arch(const char *arch)
 {
-	queue *q = arches;
+	char **q;
 	int a;
 	const char *p;
 
@@ -112,12 +113,9 @@ decode_arch(const char *arch)
 	if (*p == '~' || *p == '-')
 		p++;
 
-	a = 0;
-	while (q) {
-		if (strcmp(q->name, p) == 0)
+	for (q = archlist, a = 0; *q != NULL; q++, a++) {
+		if (strcmp(*q, p) == 0)
 			return a;
-		++a;
-		q = q->next;
 	}
 
 	return -1;
@@ -135,7 +133,7 @@ decode_arch(const char *arch)
 static void
 print_keywords(const char *category, const char *ebuild, int *keywords)
 {
-	queue *arch = arches;
+	char **arch = archlist;
 	int a;
 	char *package;
 
@@ -143,16 +141,15 @@ print_keywords(const char *category, const char *ebuild, int *keywords)
 	package[strlen(ebuild)-7] = '\0';
 
 	printf("%s%s/%s%s%s ", BOLD, category, BLUE, package, NORM);
-	for (a = 0; a < archlist_count; ++a) {
+	for (a = 0; a < archlist_count; a++) {
 		switch (keywords[a]) {
 			case stable:
-				printf("%s%c%s%s ", GREEN, status[keywords[a]], arch->name, NORM);
+				printf("%s%c%s%s ", GREEN, status[keywords[a]], arch[a], NORM);
 				break;
 			case testing:
-				printf("%s%c%s%s ", YELLOW, status[keywords[a]], arch->name, NORM);
+				printf("%s%c%s%s ", YELLOW, status[keywords[a]], arch[0], NORM);
 				break;
 		}
-		arch = arch->next;
 	}
 
 	printf("\n");
@@ -182,6 +179,7 @@ read_keywords(char *s, int *keywords)
 
 	memset(keywords, 0, sizeof(*keywords) * archlist_count);
 
+	/* handle -* */
 	slen = strlen(s);
 	if (slen >= 2 && s[0] == '-' && s[1] == '*')
 		for (a = 0; a < archlist_count; ++a)
@@ -696,7 +694,7 @@ static void
 qcache_stats(qcache_data *data)
 {
 	static time_t runtime;
-	static queue *allcats;
+	static set *allcats;
 	static const char *last_overlay;
 	static int numpkg  = 0;
 	static int numebld = 0;
@@ -709,15 +707,20 @@ qcache_stats(qcache_data *data)
 
 	/* Is this the last time we'll be called? */
 	if (!data) {
+		char **arch;
 		const char border[] = "------------------------------------------------------------------";
 
 		printf("+%.*s+\n", 25, border);
 		printf("|   general statistics    |\n");
 		printf("+%.*s+\n", 25, border);
-		printf("| %s%13s%s | %s%7d%s |\n", GREEN, "architectures", NORM, BLUE, archlist_count, NORM);
-		printf("| %s%13s%s | %s%7d%s |\n", GREEN, "categories", NORM, BLUE, numcat, NORM);
-		printf("| %s%13s%s | %s%7d%s |\n", GREEN, "packages", NORM, BLUE, numpkg, NORM);
-		printf("| %s%13s%s | %s%7d%s |\n", GREEN, "ebuilds", NORM, BLUE, numebld, NORM);
+		printf("| %s%13s%s | %s%7d%s |\n",
+				GREEN, "architectures", NORM, BLUE, archlist_count, NORM);
+		printf("| %s%13s%s | %s%7d%s |\n",
+				GREEN, "categories", NORM, BLUE, numcat, NORM);
+		printf("| %s%13s%s | %s%7d%s |\n",
+				GREEN, "packages", NORM, BLUE, numpkg, NORM);
+		printf("| %s%13s%s | %s%7d%s |\n",
+				GREEN, "ebuilds", NORM, BLUE, numebld, NORM);
 		printf("+%.*s+\n\n", 25, border);
 
 		printf("+%.*s+\n", (int)(arch_longest_len + 46), border);
@@ -725,20 +728,23 @@ qcache_stats(qcache_data *data)
 			(int)arch_longest_len, "");
 		printf("+%.*s+\n", (int)(arch_longest_len + 46), border);
 		printf("| %s%*s%s |%s%8s%s |%s%8s%s |%s%8s%s | %s%8s%s |\n",
-			RED, (int)arch_longest_len, "architecture", NORM, RED, "stable", NORM,
+			RED, (int)arch_longest_len, "architecture", NORM,
+			RED, "stable", NORM,
 			RED, "~arch", NORM, RED, "total", NORM, RED, "total/#pkgs", NORM);
 		printf("| %*s |         |%s%8s%s |         |             |\n",
 			(int)arch_longest_len, "", RED, "only", NORM);
 		printf("+%.*s+\n", (int)(arch_longest_len + 46), border);
 
-		queue *arch = arches;
-		for (a = 0; a < archlist_count; ++a) {
-			printf("| %s%*s%s |", GREEN, (int)arch_longest_len, arch->name, NORM);
+		arch = archlist;
+		for (a = 0; a < archlist_count; a++) {
+			printf("| %s%*s%s |", GREEN, (int)arch_longest_len, arch[a], NORM);
 			printf("%s%8d%s |", BLUE, packages_stable[a], NORM);
 			printf("%s%8d%s |", BLUE, packages_testing[a], NORM);
-			printf("%s%8d%s |", BLUE, packages_testing[a]+packages_stable[a], NORM);
-			printf("%s%11.2f%s%% |\n", BLUE, (100.0*(packages_testing[a]+packages_stable[a]))/numpkg, NORM);
-			arch = arch->next;
+			printf("%s%8d%s |",
+					BLUE, packages_testing[a] + packages_stable[a], NORM);
+			printf("%s%11.2f%s%% |\n", BLUE,
+					(100.0*(packages_testing[a]+packages_stable[a]))/numpkg,
+					NORM);
 		}
 
 		printf("+%.*s+\n\n", (int)(arch_longest_len + 46), border);
@@ -751,7 +757,7 @@ qcache_stats(qcache_data *data)
 		free(packages_testing);
 		free(keywords);
 		free(current_package_keywords);
-		free_sets(allcats);
+		free_set(allcats);
 		return;
 	}
 
@@ -797,15 +803,20 @@ qcache_stats(qcache_data *data)
 	}
 
 	if (!numpkg) {
-		packages_stable          = xcalloc(archlist_count, sizeof(*packages_stable));
-		packages_testing         = xcalloc(archlist_count, sizeof(*packages_testing));
-		keywords                 = xcalloc(archlist_count, sizeof(*keywords));
-		current_package_keywords = xcalloc(archlist_count, sizeof(*current_package_keywords));
+		packages_stable          =
+			xcalloc(archlist_count, sizeof(*packages_stable));
+		packages_testing         =
+			xcalloc(archlist_count, sizeof(*packages_testing));
+		keywords                 =
+			xcalloc(archlist_count, sizeof(*keywords));
+		current_package_keywords =
+			xcalloc(archlist_count, sizeof(*current_package_keywords));
 	}
 
 	if (data->cur == 1) {
 		numpkg++;
-		memset(current_package_keywords, 0, archlist_count * sizeof(*current_package_keywords));
+		memset(current_package_keywords, 0,
+				archlist_count * sizeof(*current_package_keywords));
 	}
 	++numebld;
 
@@ -914,7 +925,7 @@ qcache_load_arches(const char *overlay)
 			continue;
 
 		bool ok;
-		arches = add_set_unique(buf, arches, &ok);
+		archs = add_set_unique(buf, archs, &ok);
 		if (ok) {
 			++archlist_count;
 			arch_longest_len = MAX(arch_longest_len, strlen(buf));
@@ -922,6 +933,9 @@ qcache_load_arches(const char *overlay)
 	}
 	free(buf);
 
+	/* materialise into a list */
+	list_set(archs, &archlist);
+
 	fclose(fp);
  done:
 	free(filename);
@@ -935,7 +949,8 @@ qcache_load_arches(const char *overlay)
 static void
 qcache_free(void)
 {
-	free_sets(arches);
+	free(archlist);
+	free_set(archs);
 }
 
 /********************************************************************/
diff --git a/qlist.c b/qlist.c
index 3ca3f5e..6addc14 100644
--- a/qlist.c
+++ b/qlist.c
@@ -313,7 +313,6 @@ struct qlist_opt_state {
 	bool show_umap;
 	bool show_dbg;
 	bool columns;
-	queue *sets;
 	char *buf;
 	size_t buflen;
 };
@@ -434,7 +433,6 @@ int qlist_main(int argc, char **argv)
 		.show_umap = false,
 		.show_dbg = false,
 		.columns = false,
-		.sets = NULL,
 		.buflen = _Q_PATH_MAX,
 	};
 	int i, ret;
diff --git a/qmerge.c b/qmerge.c
index 195d92b..aec51be 100644
--- a/qmerge.c
+++ b/qmerge.c
@@ -101,7 +101,7 @@ typedef struct llist_char_t llist_char;
 
 static void pkg_fetch(int, const depend_atom *, const struct pkg_t *);
 static void pkg_merge(int, const depend_atom *, const struct pkg_t *);
-static int pkg_unmerge(q_vdb_pkg_ctx *, queue *, int, char **, int, char **);
+static int pkg_unmerge(q_vdb_pkg_ctx *, set *, int, char **, int, char **);
 static struct pkg_t *grab_binpkg_info(const char *);
 static char *find_binpkg(const char *);
 
@@ -684,7 +684,7 @@ pkg_run_func_at(int dirfd, const char *vdb_path, const char *phases, const char
 /* Copy one tree (the single package) to another tree (ROOT) */
 static int
 merge_tree_at(int fd_src, const char *src, int fd_dst, const char *dst,
-              FILE *contents, queue **objs, char **cpathp,
+              FILE *contents, set **objs, char **cpathp,
               int cp_argc, char **cp_argv, int cpm_argc, char **cpm_argv)
 {
 	int i, ret, subfd_src, subfd_dst;
@@ -919,7 +919,7 @@ merge_tree_at(int fd_src, const char *src, int fd_dst, const char *dst,
 static void
 pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 {
-	queue *objs;
+	set *objs;
 	q_vdb_ctx *vdb_ctx;
 	q_vdb_cat_ctx *cat_ctx;
 	FILE *fp, *contents;
@@ -1305,7 +1305,7 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 	freeargv(cpm_argc, cpm_argv);
 
 	/* Clean up the package state */
-	free_sets(objs);
+	free_set(objs);
 	free(D);
 	free(T);
 
@@ -1341,7 +1341,7 @@ pkg_merge(int level, const depend_atom *atom, const struct pkg_t *pkg)
 }
 
 static int
-pkg_unmerge(q_vdb_pkg_ctx *pkg_ctx, queue *keep,
+pkg_unmerge(q_vdb_pkg_ctx *pkg_ctx, set *keep,
 		int cp_argc, char **cp_argv, int cpm_argc, char **cpm_argv)
 {
 	q_vdb_cat_ctx *cat_ctx = pkg_ctx->cat_ctx;
@@ -1385,7 +1385,7 @@ pkg_unmerge(q_vdb_pkg_ctx *pkg_ctx, queue *keep,
 		strstr(features, "config-protect-if-modified") != NULL;
 
 	while (getline(&buf, &buflen, fp) != -1) {
-		queue *q;
+		bool del;
 		contents_entry *e;
 		char zing[20];
 		int protected = 0;
@@ -1455,21 +1455,16 @@ pkg_unmerge(q_vdb_pkg_ctx *pkg_ctx, queue *keep,
 		}
 
 		/* See if this was updated */
-		q = keep;
-		while (q) {
-			if (!strcmp(q->name, e->name)) {
-				/* XXX: could remove this from the queue */
-				strcpy(zing, "---");
-				q = NULL;
-				break;
-			}
-			q = q->next;
-		}
+		del = false;
+		if (keep != NULL)
+			(void)del_set(e->name, keep, &del);
+		if (del)
+			strcpy(zing, "---");
 
 		/* No match, so unmerge it */
 		if (!quiet)
 			printf("%s %s\n", zing, e->name);
-		if (!keep || q) {
+		if (!keep || !del) {
 			char *p;
 
 			if (!pretend && unlinkat(portroot_fd, e->name + 1, 0)) {
@@ -1599,7 +1594,9 @@ pkg_fetch(int level, const depend_atom *atom, const struct pkg_t *pkg)
 
 	/* XXX: should do a size check here for partial downloads */
 
-	if (force_download && (access(buf, R_OK) == 0) && (pkg->SHA1[0] || pkg->MD5[0])) {
+	if (force_download && (access(buf, R_OK) == 0) &&
+			(pkg->SHA1[0] || pkg->MD5[0]))
+	{
 		if (pkg_verify_checksums(buf, pkg, atom, 0, 0) != 0)
 			unlink(buf);
 	}
@@ -1608,7 +1605,9 @@ pkg_fetch(int level, const depend_atom *atom, const struct pkg_t *pkg)
 			warn("No checksum data for %s (try `emaint binhost --fix`)", buf);
 			return;
 		} else {
-			if (pkg_verify_checksums(buf, pkg, atom, qmerge_strict, !quiet) == 0) {
+			if (pkg_verify_checksums(buf, pkg, atom, qmerge_strict, !quiet)
+					== 0)
+			{
 				pkg_merge(0, atom, pkg);
 				return;
 			}
@@ -1700,21 +1699,23 @@ print_Pkg(int full, const depend_atom *atom, const struct pkg_t *pkg)
 static int
 qmerge_unmerge_cb(q_vdb_pkg_ctx *pkg_ctx, void *priv)
 {
-	queue *todo = priv;
 	int cp_argc;
 	int cpm_argc;
 	char **cp_argv;
 	char **cpm_argv;
+	char **todo;
+	char **p;
 
 	makeargv(config_protect, &cp_argc, &cp_argv);
 	makeargv(config_protect_mask, &cpm_argc, &cpm_argv);
 
-	while (todo) {
-		if (qlist_match(pkg_ctx, todo->name, NULL, true))
+	(void)list_set(priv, &todo);
+	for (p = todo; *p != NULL; p++) {
+		if (qlist_match(pkg_ctx, *p, NULL, true))
 			pkg_unmerge(pkg_ctx, NULL, cp_argc, cp_argv, cpm_argc, cpm_argv);
-		todo = todo->next;
 	}
 
+	free(todo);
 	freeargv(cp_argc, cp_argv);
 	freeargv(cpm_argc, cpm_argv);
 
@@ -1722,7 +1723,7 @@ qmerge_unmerge_cb(q_vdb_pkg_ctx *pkg_ctx, void *priv)
 }
 
 static int
-unmerge_packages(queue *todo)
+unmerge_packages(set *todo)
 {
 	return q_vdb_foreach_pkg(qmerge_unmerge_cb, todo, NULL);
 }
@@ -2000,7 +2001,7 @@ find_binpkg(const char *name)
 }
 
 static int
-parse_packages(queue *todo)
+parse_packages(set *todo)
 {
 	FILE *fp;
 	int linelen;
@@ -2009,10 +2010,16 @@ parse_packages(queue *todo)
 	struct pkg_t Pkg;
 	depend_atom *pkg_atom;
 	char repo[sizeof(Pkg.REPO)];
+	depend_atom **todo_atoms;
+	size_t todo_cnt;
+	size_t i;
 
 	fp = open_binpkg_index();
+	if (fp == NULL)
+		return EXIT_FAILURE;
 
 	buf = NULL;
+	buflen = 0;  /* make getline allocate */
 	repo[0] = '\0';
 
 	/* First consume the header with the common data. */
@@ -2040,6 +2047,16 @@ parse_packages(queue *todo)
 	memset(&Pkg, 0, sizeof(Pkg));
 	strcpy(Pkg.SLOT, "0");
 
+	/* build list with exploded atoms for each access below */
+	{
+		char **todo_strs;
+		todo_cnt = list_set(todo, &todo_strs);
+		todo_atoms = xmalloc(sizeof(*todo_atoms) * todo_cnt);
+		for (i = 0; i < todo_cnt; i++)
+			todo_atoms[i] = atom_explode(todo_strs[i]);
+		free(todo_strs);
+	}
+
 	/* Then walk all the package entries. */
 	while (getline(&buf, &buflen, fp) != -1) {
 		if (*buf == '\n') {
@@ -2047,20 +2064,15 @@ parse_packages(queue *todo)
 				if (search_pkgs && !todo) {
 					print_Pkg(verbose, pkg_atom, &Pkg);
 				} else {
-					const queue *ll = todo;
-					depend_atom *todo_atom;
-					while (ll) {
-						todo_atom = atom_explode(ll->name);
-						pkg_atom->REPO = todo_atom->REPO ? Pkg.REPO : NULL;
-						pkg_atom->SLOT = todo_atom->SLOT ? Pkg.SLOT : NULL;
-						if (atom_compare(todo_atom, pkg_atom) == EQUAL) {
+					for (i = 0; i < todo_cnt; i++) {
+						pkg_atom->REPO = todo_atoms[i]->REPO ? Pkg.REPO : NULL;
+						pkg_atom->SLOT = todo_atoms[i]->SLOT ? Pkg.SLOT : NULL;
+						if (atom_compare(todo_atoms[i], pkg_atom) == EQUAL) {
 							if (search_pkgs)
 								print_Pkg(verbose, pkg_atom, &Pkg);
 							else
 								pkg_fetch(0, pkg_atom, &Pkg);
 						}
-						atom_implode(todo_atom);
-						ll = ll->next;
 					}
 				}
 
@@ -2155,11 +2167,15 @@ parse_packages(queue *todo)
 	if (pkg_atom)
 		atom_implode(pkg_atom);
 
+	for (i = 0; i < todo_cnt; i++)
+		atom_implode(todo_atoms[i]);
+	free(todo_atoms);
+
 	return EXIT_SUCCESS;
 }
 
-static queue *
-qmerge_add_set_file(const char *dir, const char *file, queue *set)
+static set *
+qmerge_add_set_file(const char *dir, const char *file, set *q)
 {
 	FILE *fp;
 	int linelen;
@@ -2180,19 +2196,19 @@ qmerge_add_set_file(const char *dir, const char *file, queue *set)
 	buf = NULL;
 	while ((linelen = getline(&buf, &buflen, fp)) >= 0) {
 		rmspace_len(buf, (size_t)linelen);
-		set = add_set(buf, set);
+		q = add_set(buf, q);
 	}
 	free(buf);
 
 	fclose(fp);
 
-	return set;
+	return q;
 }
 
 static void *
 qmerge_add_set_system(void *data, char *buf)
 {
-	queue *set = data;
+	set *q = data;
 	char *s;
 
 	s = strchr(buf, '#');
@@ -2202,35 +2218,35 @@ qmerge_add_set_system(void *data, char *buf)
 
 	s = buf;
 	if (*s == '*')
-		set = add_set(s + 1, set);
+		q = add_set(s + 1, q);
 	else if (s[0] == '-' && s[1] == '*') {
-		int ok;
-		set = del_set(s + 2, set, &ok);
+		bool ok;
+		q = del_set(s + 2, q, &ok);
 	}
 
-	return set;
+	return q;
 }
 
 /* XXX: note, this doesn't handle more complicated set files like
  *      the portage .ini files in /usr/share/portage/sets/ */
 /* XXX: this code does not combine duplicate dependencies */
-static queue *
-qmerge_add_set(char *buf, queue *set)
+static set *
+qmerge_add_set(char *buf, set *q)
 {
 	if (strcmp(buf, "world") == 0)
-		return qmerge_add_set_file("/var/lib/portage", "world", set);
+		return qmerge_add_set_file("/var/lib/portage", "world", q);
 	else if (strcmp(buf, "all") == 0)
 		return get_vdb_atoms(0);
 	else if (strcmp(buf, "system") == 0)
-		return q_profile_walk("packages", qmerge_add_set_system, set);
+		return q_profile_walk("packages", qmerge_add_set_system, q);
 	else if (buf[0] == '@')
-		return qmerge_add_set_file("/etc/portage", buf+1, set);
+		return qmerge_add_set_file("/etc/portage", buf+1, q);
 	else
-		return add_set(buf, set);
+		return add_set(buf, q);
 }
 
 static int
-qmerge_run(queue *todo)
+qmerge_run(set *todo)
 {
 	if (uninstall)
 		return unmerge_packages(todo);
@@ -2241,7 +2257,7 @@ qmerge_run(queue *todo)
 int qmerge_main(int argc, char **argv)
 {
 	int i, ret;
-	queue *todo;
+	set *todo;
 
 	if (argc < 2)
 		qmerge_usage(EXIT_FAILURE);
@@ -2310,7 +2326,7 @@ int qmerge_main(int argc, char **argv)
 	}
 
 	ret = qmerge_run(todo);
-	free_sets(todo);
+	free_set(todo);
 	return ret;
 }
 
diff --git a/qpkg.c b/qpkg.c
index dcdc190..05c8505 100644
--- a/qpkg.c
+++ b/qpkg.c
@@ -44,15 +44,17 @@ filter_tbz2(const struct dirent *dentry)
 
 /* process a single dir for cleaning. dir can be a $PKGDIR, $PKGDIR/All/, $PKGDIR/$CAT */
 static uint64_t
-qpkg_clean_dir(char *dirp, queue *vdb)
+qpkg_clean_dir(char *dirp, set *vdb)
 {
-	queue *ll;
+	set *ll = NULL;
 	struct dirent **fnames;
 	int i, count;
 	char buf[_Q_PATH_MAX];
 	struct stat st;
 	uint64_t num_all_bytes = 0;
 	size_t disp_units = 0;
+	char **t;
+	bool ignore;
 
 	if (dirp == NULL)
 		return 0;
@@ -61,18 +63,13 @@ qpkg_clean_dir(char *dirp, queue *vdb)
 	if ((count = scandir(".", &fnames, filter_tbz2, alphasort)) < 0)
 		return 0;
 
+	/* create copy of vdb with only basenames */
+	for ((void)list_set(vdb, &t); *t != NULL; t++)
+		ll = add_set_unique(basename(*t), ll, &ignore);
+
 	for (i = 0; i < count; i++) {
-		int del = 1;
 		fnames[i]->d_name[strlen(fnames[i]->d_name)-5] = 0;
-		for (ll = vdb; ll != NULL; ll = ll->next) {
-			if (1) {
-				if (strcmp(fnames[i]->d_name, basename(ll->name)) == 0) {
-					del = 0;
-					break;
-				}
-			}
-		}
-		if (!del)
+		if (contains_set(fnames[i]->d_name, ll))
 			continue;
 		snprintf(buf, sizeof(buf), "%s.tbz2", fnames[i]->d_name);
 		if (lstat(buf, &st) != -1) {
@@ -81,14 +78,19 @@ qpkg_clean_dir(char *dirp, queue *vdb)
 				if ((st.st_size / KILOBYTE) > 1000)
 					disp_units = MEGABYTE;
 				num_all_bytes += st.st_size;
-				qprintf(" %s[%s%s %3s %s %s%s]%s %s%s/%s%s\n", DKBLUE, NORM, GREEN, make_human_readable_str(st.st_size, 1, disp_units),
-					disp_units == MEGABYTE ? "M" : "K", NORM, DKBLUE, NORM, CYAN, basename(dirp), fnames[i]->d_name, NORM);
+				qprintf(" %s[%s%s %3s %s %s%s]%s %s%s/%s%s\n",
+						DKBLUE, NORM, GREEN,
+						make_human_readable_str(st.st_size, 1, disp_units),
+						disp_units == MEGABYTE ? "M" : "K",
+						NORM, DKBLUE, NORM, CYAN,
+						basename(dirp), fnames[i]->d_name, NORM);
 			}
 			if (!pretend)
 				unlink(buf);
 		}
 	}
 
+	free_set(ll);
 	scandir_free(fnames, count);
 
 	return num_all_bytes;
@@ -103,18 +105,14 @@ qpkg_clean(char *dirp)
 	size_t disp_units = 0;
 	uint64_t num_all_bytes;
 	struct dirent **dnames;
-	queue *vdb;
-
-	vdb = get_vdb_atoms(1);
+	set *vdb;
 
-	if (chdir(dirp) != 0) {
-		free_sets(vdb);
+	if (chdir(dirp) != 0)
 		return 1;
-	}
-	if ((count = scandir(".", &dnames, filter_hidden, alphasort)) < 0) {
-		free_sets(vdb);
+	if ((count = scandir(".", &dnames, filter_hidden, alphasort)) < 0)
 		return 1;
-	}
+
+	vdb = get_vdb_atoms(1);
 
 	if (eclean) {
 		size_t n;
@@ -141,11 +139,13 @@ qpkg_clean(char *dirp)
 				if ((p = strrchr(buf, '/')) == NULL)
 					continue;
 				*p = 0;
-				/* these strcat() are safe. the name is extracted from buf already. */
+				/* these strcat() are safe. the name is extracted from
+				 * buf already. */
 				strcat(buf, "/");
 				strcat(buf, name);
 
-				/* num_all_bytes will be off when pretend and eclean are enabled together */
+				/* num_all_bytes will be off when pretend and eclean are
+				 * enabled together */
 				/* vdb = del_set(buf, vdb, &i); */
 				vdb = add_set(buf, vdb);
 			}
@@ -164,13 +164,15 @@ qpkg_clean(char *dirp)
 	}
 	scandir_free(dnames, count);
 
-	free_sets(vdb);
+	free_set(vdb);
 
 	disp_units = KILOBYTE;
 	if ((num_all_bytes / KILOBYTE) > 1000)
 		disp_units = MEGABYTE;
-	qprintf(" %s*%s Total space that would be freed in packages directory: %s%s %c%s\n", GREEN, NORM, RED,
-		make_human_readable_str(num_all_bytes, 1, disp_units), disp_units == MEGABYTE ? 'M' : 'K', NORM);
+	qprintf(" %s*%s Total space that would be freed in packages "
+			"directory: %s%s %c%s\n", GREEN, NORM, RED,
+			make_human_readable_str(num_all_bytes, 1, disp_units),
+			disp_units == MEGABYTE ? 'M' : 'K', NORM);
 
 	return 0;
 }