local/libqueue: new aport

13 files changed, 880 insertions, 0 deletions

diff --git a/libqueue/APKBUILD b/libqueue/APKBUILD
new file mode 100644
index 0000000..f5347c6
--- /dev/null
+++ b/libqueue/APKBUILD
@@ -0,0 +1,48 @@
+# Contributor: John Vogel <jvogel4@stny.rr.com>
+# Maintainer: John Vogel <jvogel4@stny.rr.com>
+pkgname=libqueue
+pkgver=0.1
+pkgrel=0
+pkgdesc="NetBSD queue.h derived list/queue library"
+url="http://localhost/home/john/Code/queue"
+arch="all"
+license="MIT"
+subpackages="$pkgname-dev"
+source="queue/LICENSE
+	queue/Makefile
+	queue/dl.c
+	queue/dl.h
+	queue/sl.c
+	queue/sl.h
+	queue/sq.c
+	queue/sq.h
+	queue/stq.c
+	queue/stq.h
+	queue/tq.c
+	queue/tq.h"
+options="!check"
+
+builddir="$srcdir/"
+
+build() {
+	make
+}
+
+package() {
+	make DESTDIR="$pkgdir" PREFIX=/usr install
+}
+
+sha512sums="
+a4e4208b0e3a53559dfa5c65500b0e87fd5129596bfca1540e153996a6799b5499ba7380cba8915c15e66016bd4b249e7d6bedf29af3b143df813ec787d06631  LICENSE
+608a07422bfe102ca5f20e3f6f8b37c42324403746ef16527f54ac72f9de06d8c8db9904d5da72cfd0e2b33aed7d7cdd411acfca35b7e99deba8a7ef564205a7  Makefile
+aa7667c5065b53734b1b88f0628e3e9fd7cbc39fe1ffe5f8713b3f47bc756a18b0d2e436238f311e0e9c0a5e3979afa1fa2f5361a5233b578ca09cca549c71aa  dl.c
+31aa820e140cd672e94314edc607c56e9d4035ba9db09ae333c0974fdcd873d6df476a20a57176a2c81863c15db09efdf0073db82f575a23c9246aa717259899  dl.h
+7318a82bdab546e5f8143c4654625041e9dff2c6f00cbeb7b9ea32254c2d350b937da2580de27b3e26979b52ab83cffce0956f6d0ac3f401e42f4cfa0ea2841d  sl.c
+cd4991bf0d092a6c2913a461218db6f79f6c1da9962b7c421058943b548781b468fb359dea0501a41a61c94250caeed251313b6cde1770e38766f9544a48a92b  sl.h
+2474668ba93d7e264a7e6aafe43e4880b4a74e9ec443e88b6cdf4b9f3659dfa2f74faa3b95424081bdd02ce964672429f0cb743dc1b8a84041ea1b72282a0f47  sq.c
+e31f394aff87fa2a562058ec4f406ecd2add74c7d43f5d023a09717852072d021e4d89cfcafc01eb813d7a17200cb54b0ea5fe7803e2bb30cd95ee1edb3fa34c  sq.h
+c79335486b7bceace3e4dd135dca503987866029ee632e1ca05e9bd184f442373825a5e40b55d9799134008dcd53cea15df32c74d4ce194a6d83ce3171e287e8  stq.c
+9838fb0cdb0acb0a221d35ffffdfbec228cc69ec64a82add401ddcfb06b11063937986365239cceb5e9e1afc76872331a3695d5ef5c8a4510d1f2b2d131ff2f6  stq.h
+6cc5a4e94ba62bc15d383c2f91cec827db027d8911a6a96a8b4607674a800b3bfaf31b419d70b4f19a0d939967206d2834c11fbc7d062ff93e03db25b03a6146  tq.c
+b303ffb71971d5fe026014eafe6f2b6fbf142f19f538452976f097cdbcfa559ca68f498d692dfd82d8d0739fea0ae2e0594f3d1e75f518443af017d1d3d8a6ae  tq.h
+"
diff --git a/libqueue/queue/LICENSE b/libqueue/queue/LICENSE
new file mode 100644
index 0000000..338d5ba
--- /dev/null
+++ b/libqueue/queue/LICENSE
@@ -0,0 +1,9 @@
+MIT License
+
+Copyright (c) 2024 John Vogel <jvogel4@stny.rr.com>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
diff --git a/libqueue/queue/Makefile b/libqueue/queue/Makefile
new file mode 100644
index 0000000..d7d6a40
--- /dev/null
+++ b/libqueue/queue/Makefile
@@ -0,0 +1,46 @@
+# based heavily on mandoc's Makefile
+
+CFLAGS += -fPIC
+INSTALL = install
+INSTALL_LIB = $(INSTALL) -m 0644
+PREFIX = /usr/local
+LIBDIR = $(PREFIX)/lib
+INCLUDEDIR = $(PREFIX)/include/queue
+
+SRCS = dl.c sl.c sq.c stq.c tq.c
+
+OBJS = dl.o sl.o sq.o stq.o tq.o
+
+HDRS = dl.h sl.h sq.h stq.h tq.h
+
+LIBS = libqueue.a
+
+SOLIBS = libqueue.so
+
+all: $(LIBS) $(SOLIBS)
+
+libqueue.a: $(OBJS)
+	$(AR) rs $@ $(OBJS)
+
+libqueue.so: $(OBJS)
+	$(CC) $(LDFLAGS) -shared -o $@ $(OBJS)
+
+clean:
+	rm -f $(LIBS) $(SOLIBS) $(OBJS)
+
+install: $(LIBS) $(SOLIBS)
+	mkdir -p $(DESTDIR)$(LIBDIR)
+	mkdir -p $(DESTDIR)$(INCLUDEDIR)
+	$(INSTALL_LIB) $(LIBS) $(DESTDIR)$(LIBDIR)
+	$(INSTALL_LIB) $(SOLIBS) $(DESTDIR)$(LIBDIR)
+	$(INSTALL_LIB) $(HDRS) $(DESTDIR)$(INCLUDEDIR)
+
+uninstall:
+	rm -f $(DESTDIR)$(LIBDIR)/libqueue.a
+	rm -f $(DESTDIR)$(LIBDIR)/libqueue.so
+	rm -f $(DESTDIR)$(INCLUDEDIR)/dl.h
+	rm -f $(DESTDIR)$(INCLUDEDIR)/sl.h
+	rm -f $(DESTDIR)$(INCLUDEDIR)/sq.h
+	rm -f $(DESTDIR)$(INCLUDEDIR)/stq.h
+	rm -f $(DESTDIR)$(INCLUDEDIR)/tq.h
+	[ ! -e $(DESTDIR)$(INCLUDEDIR) ] || rmdir $(DESTDIR)$(INCLUDEDIR)
diff --git a/libqueue/queue/dl.c b/libqueue/queue/dl.c
new file mode 100644
index 0000000..65e024d
--- /dev/null
+++ b/libqueue/queue/dl.c
@@ -0,0 +1,103 @@
+/* vim: set ts=4 sw=4 ai:
+ * dl.c -- doubly linked list implementation derived from NetBSD's queue.h
+ */
+
+#include <stdlib.h>
+#include "dl.h"
+
+struct dlh *dl_new(void)
+{
+	struct dlh *hd;
+
+	hd = malloc(sizeof(*hd));
+	if (hd != NULL)
+		dl_init(hd);
+
+	return hd;
+}
+
+struct dle *dl_elem_new(void *data)
+{
+	struct dle *e;
+
+	e = malloc(sizeof(*e));
+	if (e != NULL)
+		e->data = data;
+
+	return e;
+}
+
+void dl_insert_after(struct dle *e, struct dle *n)
+{
+	if ((n->next = e->next) != NULL)
+		 e->next->pprev = &n->next;
+	e->next = n;
+	n->pprev = &e->next;
+}
+
+void dl_insert_before(struct dle *e, struct dle *n)
+{
+	n->pprev = e->pprev;
+	n->next = e;
+	*e->pprev = n;
+	e->pprev = &n->next;
+}
+
+void dl_insert_head(struct dlh *hd, struct dle *e)
+{
+ 	if ((e->next = hd->first) != NULL)
+		hd->first->pprev = &e->next;
+	hd->first = e;
+	e->pprev = &hd->first;
+}
+
+void dl_remove(struct dlh *hd, struct dle *e)
+{
+	if (e->next != NULL)
+		e->next->pprev = e->pprev;
+	*e->pprev = e->next;
+}
+
+void dl_replace(struct dle *e1, struct dle *e2)
+{
+ 	if ((e2->next = e1->next) != NULL)
+		e2->next->pprev = &e2->next;
+	e2->pprev = e1->pprev;
+
+	*e2->pprev = e2;
+}
+
+void dlist_move(struct dlh *hd1, struct dlh *hd2)
+{
+ 	hd2->first = NULL;
+	if (!(hd1->first == NULL))
+	{
+		hd2->first = hd1->first;
+		hd2->first->pprev = &hd2->first;
+		hd1->first = NULL;
+	}
+}
+
+void dl_cleanup(struct dlh *hd, void (*func)(void *))
+{
+	struct dle *e, *t;
+
+	dl_foreach_safe(e, hd, t) {
+		dl_remove(hd, e);
+		if (func)
+			func(e->data);
+		free(e);
+	}
+}
+
+struct dle *dl_find_from_data(struct dlh *hd, const void *data, int (*cmp)(const void *, const void *))
+{
+	struct dle *e;
+
+	if (hd && !dl_empty(hd))
+		dl_foreach(e, hd)
+			if (e->data && cmp(e->data, data) == 0)
+				return e;
+
+	return NULL;
+}
diff --git a/libqueue/queue/dl.h b/libqueue/queue/dl.h
new file mode 100644
index 0000000..e53843f
--- /dev/null
+++ b/libqueue/queue/dl.h
@@ -0,0 +1,44 @@
+/* vim: set ts=4 sw=4 ai:
+ * dl.h -- doubly linked list implementation derived from NetBSD's queue.h
+ */
+
+#ifndef DL_H
+#define DL_H
+
+struct dle {
+	void *data;
+	struct dle *next;
+	struct dle **pprev;
+};
+
+struct dlh {
+	struct dle *first;
+};
+
+#define dl_first(hd) ((hd)->first)
+#define dl_next(e) ((e)->next)
+#define dl_empty(hd) (((hd)->first) == NULL)
+#define dl_init(hd) ((hd)->first = NULL)
+
+#define dl_foreach(var,head) \
+	for ((var) = ((head)->first); \
+		(var) != NULL; \
+		(var) = ((var)->next))
+
+#define dl_foreach_safe(var,head,vnext) \
+	for ((var) = ((head)->first); \
+		(var) != NULL && ((vnext) = dl_next((var)), 1); \
+		(var) = (vnext))
+
+struct dlh *dl_new(void);
+struct dle *dl_elem_new(void *);
+void dl_insert_after(struct dle *, struct dle *);
+void dl_insert_before(struct dle *, struct dle *);
+void dl_insert_head(struct dlh *, struct dle *);
+void dl_remove(struct dlh *, struct dle *);
+void dl_replace(struct dle *, struct dle *);
+void dl_move(struct dlh *, struct dlh *);
+void dl_cleanup(struct dlh *, void (*)(void *));
+struct dle *dl_find_from_data(struct dlh *, const void *, int (*)(const void *, const void *));
+
+#endif/*!DL_H*/
diff --git a/libqueue/queue/sl.c b/libqueue/queue/sl.c
new file mode 100644
index 0000000..ccc6476
--- /dev/null
+++ b/libqueue/queue/sl.c
@@ -0,0 +1,93 @@
+/* vim: set ts=4 sw=4 ai:
+ * sl.c -- singly linked list implementation derived from NetBSD's queue.h
+ */
+
+#include <stdlib.h>
+#include "sl.h"
+
+struct slh *sl_new(void)
+{
+	struct slh *hd;
+
+	hd = malloc(sizeof(*hd));
+	if (hd != NULL)
+		sl_init(hd);
+
+	return hd;
+}
+
+struct sle *sl_elem_new(void *data)
+{
+	struct sle *e;
+
+	e = malloc(sizeof(*e));
+	if (e != NULL)
+		e->data = data;
+
+	return e;
+}
+
+void sl_insert_after(struct sle *e, struct sle *n)
+{
+	n->next = e->next;
+	e->next = n;
+}
+
+void sl_insert_head(struct slh *hd, struct sle *e)
+{
+	e->next = hd->first;
+	hd->first = e;
+}
+
+void sl_remove_after(struct sle *e)
+{
+	if (e->next != NULL)
+		e->next = e->next->next;
+}
+
+void sl_remove_head(struct slh *hd)
+{
+	if (hd->first != NULL)
+		hd->first = hd->first->next;
+}
+
+void sl_remove(struct slh *hd, struct sle *e)
+{
+	struct sle *cur;
+
+	if (hd->first == e) {
+		hd->first = hd->first->next;
+	}
+	else {
+		cur = hd->first;
+		while (cur->next != NULL && cur->next != e)
+			cur = cur->next;
+		if (cur->next == NULL)
+			return;
+		cur->next = cur->next->next;
+	}
+}
+
+void sl_cleanup(struct slh *hd, void (*func)(void *))
+{
+	struct sle *e, *t;
+
+	sl_foreach_safe(e, hd, t) {
+		sl_remove(hd, e);
+		if (func)
+			func(e->data);
+		free(e);
+	}
+}
+
+struct sle *sl_find_from_data(struct slh *hd, const void *data, int (*cmp)(const void *, const void *))
+{
+	struct sle *e;
+
+	if (hd && !sl_empty(hd))
+		sl_foreach(e, hd)
+			if (e->data && cmp(e->data, data) == 0)
+				return e;
+
+	return NULL;
+}
diff --git a/libqueue/queue/sl.h b/libqueue/queue/sl.h
new file mode 100644
index 0000000..168107a
--- /dev/null
+++ b/libqueue/queue/sl.h
@@ -0,0 +1,42 @@
+/* vim: set ts=4 sw=4 ai:
+ * sl.h -- singly linked list implementation derived from NetBSD's queue.h
+ */
+
+#ifndef SL_H
+#define SL_H
+
+struct sle {
+	void *data;
+	struct sle *next;
+};
+
+struct slh {
+	struct sle *first;
+};
+
+#define sl_first(hd) ((hd)->first)
+#define sl_next(e) ((e)->next)
+#define sl_empty(hd) (((hd)->first) == NULL)
+#define sl_init(hd) ((hd)->first = NULL)
+
+#define sl_foreach(var,head) \
+	for ((var) = ((head)->first); \
+		(var) != NULL; \
+		(var) = ((var)->next))
+
+#define sl_foreach_safe(var,head,vnext) \
+	for ((var) = ((head)->first); \
+		(var) != NULL && ((vnext) = sl_next((var)), 1); \
+		(var) = (vnext))
+
+struct slh *sl_new(void);
+struct sle *sl_elem_new(void *);
+void sl_insert_after(struct sle *, struct sle *);
+void sl_insert_head(struct slh *, struct sle *);
+void sl_remove_after(struct sle *);
+void sl_remove_head(struct slh *);
+void sl_remove(struct slh *, struct sle *);
+void sl_cleanup(struct slh *, void (*)(void *));
+struct sle *sl_find_from_data(struct slh *, const void *, int (*)(const void *, const void *));
+
+#endif/*!SL_H*/
diff --git a/libqueue/queue/sq.c b/libqueue/queue/sq.c
new file mode 100644
index 0000000..66b396a
--- /dev/null
+++ b/libqueue/queue/sq.c
@@ -0,0 +1,110 @@
+/* vim: set ts=4 sw=4 ai:
+ * sq.c -- simple queue implementation derived from NetBSD's queue.h
+ */
+
+#include <stdlib.h>
+#include "sq.h"
+
+struct sqh *sq_new(void)
+{
+	struct sqh *hd;
+
+	hd = malloc(sizeof(*hd));
+	if (hd != NULL)
+		sq_init(hd);
+
+	return hd;
+}
+
+struct sqe *sq_elem_new(void *data)
+{
+	struct sqe *e;
+
+	e = malloc(sizeof(*e));
+	if (e != NULL)
+		e->data = data;
+
+	return e;
+}
+
+void sq_insert_head(struct sqh *hd, struct sqe *e)
+{
+	if ((e->next = hd->first) == NULL)
+		hd->last = &e->next;
+		
+	hd->first = e;
+}
+
+void sq_insert_tail(struct sqh *hd, struct sqe *e)
+{
+	e->next = NULL;
+	*hd->last = e;
+	hd->last = &e->next;
+}
+
+void sq_insert_after(struct sqh *hd, struct sqe *e, struct sqe *n)
+{
+	if ((n->next = e->next) == NULL)
+		hd->last = &n->next;
+	e->next = n;
+}
+
+void sq_remove_head(struct sqh *hd)
+{
+	if ((hd->first = hd->first->next) == NULL)
+		hd->last = &hd->first;
+}
+
+void sq_remove_after(struct sqh *hd, struct sqe *e)
+{
+	if ((e->next = e->next->next) == NULL)
+		hd->last = &e->next;
+}
+
+void sq_remove(struct sqh *hd, struct sqe *e)
+{
+	if (hd->first == e) {
+		if ((hd->first = hd->first->next) == NULL)
+			hd->last = &hd->first;
+	}
+	else {
+		struct sqe *cur = hd->first;
+		while (cur->next != e)
+			cur = cur->next;
+		if ((cur->next = cur->next->next) == NULL)
+			hd->last = &cur->next;
+	}
+}
+
+void sq_concat(struct sqh *hd1, struct sqh *hd2)
+{
+	if (!(hd2->first == NULL)) {
+		*hd1->last = hd2->first;
+		hd1->last = hd2->last;
+		hd2->first = NULL;
+		hd2->last = &hd2->first;
+	}
+}
+
+void sq_cleanup(struct sqh *hd, void (*func)(void *))
+{
+	struct sqe *e, *t;
+
+	sq_foreach_safe(e, hd, t) {
+		sq_remove(hd, e);
+		if (func)
+			func(e->data);
+		free(e);
+	}
+}
+struct sqe *sq_find_from_data(struct sqh *hd, const void *data, int (*cmp)(const void *, const void *))
+{
+	struct sqe *e;
+
+	if (hd && !sq_empty(hd))
+		sq_foreach(e, hd)
+			if (e->data && cmp(e->data, data) == 0)
+				return e;
+
+	return NULL;
+}
diff --git a/libqueue/queue/sq.h b/libqueue/queue/sq.h
new file mode 100644
index 0000000..e0a22cf
--- /dev/null
+++ b/libqueue/queue/sq.h
@@ -0,0 +1,49 @@
+/* vim: set ts=4 sw=4 ai:
+ * sq.h -- singly linked queue implementation derived from NetBSD's queue.h
+ */
+
+#ifndef SQ_H
+#define SQ_H
+
+struct sqe {
+	void *data;
+	struct sqe *next;
+};
+
+struct sqh {
+	struct sqe *first;
+	struct sqe **last;
+};
+
+#define sq_first(hd) ((hd)->first)
+#define sq_last(hd) (*(((struct sqh *)(void *)((hd)->last))->last))
+#define sq_next(e) ((e)->next)
+#define sq_empty(hd) (((hd)->first) == NULL)
+#define sq_init(hd) do { \
+	(hd)->first = NULL; \
+	(hd)->last = &(hd)->first; \
+} while (0)
+
+#define sq_foreach(var,head) \
+	for ((var) = ((head)->first); \
+		(var) != NULL; \
+		(var) = ((var)->next))
+
+#define sq_foreach_safe(var,head,vnext) \
+	for ((var) = ((head)->first); \
+		(var) != NULL && ((vnext) = sq_next((var)), 1); \
+		(var) = (vnext))
+
+struct sqh *sq_new(void);
+struct sqe *sq_elem_new(void *);
+void sq_insert_head(struct sqh *, struct sqe *);
+void sq_insert_tail(struct sqh *, struct sqe *);
+void sq_insert_after(struct sqh *, struct sqe *, struct sqe *);
+void sq_remove_head(struct sqh *);
+void sq_remove_after(struct sqh *, struct sqe *);
+void sq_remove(struct sqh *, struct sqe *);
+void sq_concat(struct sqh *, struct sqh *);
+void sq_cleanup(struct sqh *, void (*)(void *));
+struct sqe *sq_find_from_data(struct sqh *, const void *, int (*)(const void *, const void *));
+
+#endif/*!SQ_H*/
diff --git a/libqueue/queue/stq.c b/libqueue/queue/stq.c
new file mode 100644
index 0000000..a39a608
--- /dev/null
+++ b/libqueue/queue/stq.c
@@ -0,0 +1,105 @@
+/* vim: set ts=4 sw=4 ai:
+ * stq.c -- singly linked tail queue implementation derived from NetBSD's queue.h
+ */
+
+#include <stdlib.h>
+#include "stq.h"
+
+struct stqh *stq_new(void)
+{
+	struct stqh *hd;
+
+	hd = malloc(sizeof(*hd));
+	if (hd != NULL)
+		stq_init(hd);
+
+	return hd;
+}
+
+struct stqe *stq_elem_new(void *data)
+{
+	struct stqe *e;
+
+	e = malloc(sizeof(*e));
+	if (e != NULL)
+		e->data = data;
+
+	return e;
+}
+
+void stq_insert_head(struct stqh *hd, struct stqe *e)
+{
+	if ((e->next = hd->first) == NULL)
+		hd->last = &e->next;
+	hd->first = e;
+}
+
+void stq_insert_tail(struct stqh *hd, struct stqe *e)
+{
+	e->next = NULL;
+	*hd->last = e;
+	hd->last = &e->next;
+}
+
+void stq_insert_after(struct stqh *hd, struct stqe *e, struct stqe *n)
+{
+	if ((n->next = e->next) == NULL)
+		hd->last = &n->next;
+	e->next = n;
+}
+
+void stq_remove_head(struct stqh *hd)
+{
+	if ((hd->first = hd->first->next) == NULL)
+		hd->last = &hd->first;
+}
+
+void stq_remove(struct stqh *hd, struct stqe *e)
+{
+	if (hd->first == (e)) {
+		if ((hd->first = hd->first->next) == NULL)
+			hd->last = &hd->first;
+	}
+	else {
+		struct stqe *cur = hd->first;
+		while (cur->next != (e))
+			cur = cur->next;
+		if ((cur->next = cur->next->next) == NULL)
+			hd->last = &cur->next;
+	}
+}
+
+void stq_concat(struct stqh *hd1, struct stqh *hd2)
+{
+	if (!(hd2->first == NULL)) {
+		*hd1->last = hd2->first;
+		hd1->last = hd2->last;
+		hd2->first = NULL;
+		hd2->last = &hd2->first;
+	}
+}
+
+void stq_cleanup(struct stqh *hd, void (*func)(void *))
+{
+	struct stqe *e, *t;
+
+	stq_foreach_safe(e, hd, t) {
+		stq_remove(hd, e);
+		if (func)
+			func(e->data);
+		free(e);
+	}
+}
+
+struct stqe *stq_find_from_data(struct stqh *hd, const void *data, int (*cmp)(const void *, const void *))
+{
+	struct stqe *e;
+
+	if (hd && stq_empty(hd))
+		stq_foreach(e, hd)
+			if (e->data && cmp(e->data, data) == 0)
+				return e;
+
+	return NULL;
+}
+
diff --git a/libqueue/queue/stq.h b/libqueue/queue/stq.h
new file mode 100644
index 0000000..dcf5c85
--- /dev/null
+++ b/libqueue/queue/stq.h
@@ -0,0 +1,49 @@
+/* vim: set ts=4 sw=4 ai:
+ * stq.h -- singly linked tail queue implementation derived from NetBSD's queue.h
+ */
+
+#ifndef STQ_H
+#define STQ_H
+
+struct stqe {
+	void *data;
+	struct stqe *next;
+};
+
+struct stqh {
+	struct stqe *first;
+	struct stqe **last;
+};
+
+#define stq_first(hd) ((hd)->first)
+#define stq_last(hd) (*(((struct stqh *)(void *)((hd)->last))->last))
+#define stq_next(e) ((e)->next)
+#define stq_empty(hd) (((hd)->first) == NULL)
+#define stq_init(hd) do { \
+	(hd)->first = NULL; \
+	(hd)->last = &(hd)->first; \
+} while (0)
+
+
+#define stq_foreach(var,head) \
+	for ((var) = stq_first((head)); \
+		(var); \
+		(var) = stq_next((var)))
+
+#define stq_foreach_safe(var,head,vnext) \
+	for ((var) = stq_first((head)); \
+		(var) && ((vnext) = stq_next((var)),1); \
+		(var) = (vnext))
+
+struct stqh *stq_new(void);
+struct stqe *stq_elem_new(void *);
+void stq_insert_head(struct stqh *, struct stqe *);
+void stq_insert_tail(struct stqh *, struct stqe *);
+void stq_insert_after(struct stqh *, struct stqe *, struct stqe *);
+void stq_remove_head(struct stqh *);
+void stq_remove(struct stqh *, struct stqe *);
+void stq_concat(struct stqh *, struct stqh *);
+void stq_cleanup(struct stqh *, void (*)(void *));
+struct stqe *stq_find_from_data(struct stqh *, const void *, int (*)(const void *, const void *));
+
+#endif/*!STQ_H*/
diff --git a/libqueue/queue/tq.c b/libqueue/queue/tq.c
new file mode 100644
index 0000000..d55b63a
--- /dev/null
+++ b/libqueue/queue/tq.c
@@ -0,0 +1,120 @@
+/* vim: set ts=4 sw=4 ai:
+ * tq.c -- tail queue implementation derived from NetBSD's queue.h
+ */
+
+#include <stdlib.h>
+#include "tq.h"
+
+struct tqh *tq_new(void)
+{
+	struct tqh *hd;
+
+	hd = malloc(sizeof(*hd));
+	if (hd != NULL)
+		tq_init(hd);
+
+	return hd;
+}
+
+struct tqe *tq_elem_new(void *data)
+{
+	struct tqe *e;
+
+	e = malloc(sizeof(*e));
+	if (e != NULL)
+		e->data = data;
+
+	return e;
+}
+
+void tq_insert_head(struct tqh *hd, struct tqe *e)
+{
+	if ((e->next = hd->first) != NULL)
+		hd->first->pprev = &e->next;
+	else
+		hd->last = &e->next;
+	hd->first = e;
+	e->pprev = &hd->first;
+}
+
+void tq_insert_tail(struct tqh *hd, struct tqe *e)
+{
+	e->next = NULL;
+	e->pprev = hd->last;
+	*hd->last = e;
+	hd->last = &e->next;
+}
+
+void tq_insert_after(struct tqh *hd, struct tqe *e, struct tqe *n)
+{
+	if ((n->next = e->next) != NULL)
+		n->next->pprev = &n->next;
+	else
+		hd->last = &n->next;
+	e->next = n;
+	n->pprev = &e->next;
+}
+
+void tq_insert_before(struct tqh *hd, struct tqe *e, struct tqe *n)
+{
+	n->pprev = e->pprev;
+	n->next = e;
+	*e->pprev = n;
+	e->pprev = &n->next;
+	if (hd->first == e)
+		hd->first = n;
+}
+
+void tq_remove(struct tqh *hd, struct tqe *e)
+{
+	if ((e->next) != NULL)
+		e->next->pprev = e->pprev;
+	else
+		hd->last = e->pprev;
+	*e->pprev = e->next;
+}
+
+void tq_replace(struct tqh *hd, struct tqe *e, struct tqe *n)
+{
+	if ((n->next = e->next) != NULL)
+		n->next->pprev = &n->next;
+	else
+		hd->last = &n->next;
+	n->pprev = e->pprev;
+	*n->pprev = n;
+}
+
+void tq_concat(struct tqh *hd1, struct tqh *hd2)
+{
+	if (hd2->first != NULL) {
+		*hd1->last = hd2->first;
+		hd2->first->pprev = hd1->last;
+		hd1->last = hd2->last;
+		hd2->first = NULL;
+		hd2->last = &hd2->first;
+	}
+}
+
+void tq_cleanup(struct tqh *hd, void (*func)(void *))
+{
+	struct tqe *e, *t;
+
+	tq_foreach_safe(e, hd, t) {
+		tq_remove(hd, e);
+		if (func)
+			func(e->data);
+		free(e);
+	}
+}
+
+struct tqe *tq_find_from_data(struct tqh *hd, const void *data, int (*cmp)(const void *, const void *))
+{
+	struct tqe *e;
+
+	if (hd && !tq_empty(hd))
+		tq_foreach(e, hd)
+			if (e->data && cmp(e->data, data) == 0)
+				return e;
+
+	return NULL;
+}
diff --git a/libqueue/queue/tq.h b/libqueue/queue/tq.h
new file mode 100644
index 0000000..cf3ff46
--- /dev/null
+++ b/libqueue/queue/tq.h
@@ -0,0 +1,62 @@
+/* vim: set ts=4 sw=4 ai:
+ * tq.h -- tailq implementation derived from NetBSD's queue.h
+ */
+
+#ifndef TQ_H
+#define TQ_H
+
+struct tqe {
+	void *data;
+	struct tqe *next;
+	struct tqe **pprev;
+};
+
+struct tqh {
+	struct tqe *first;
+	struct tqe **last;
+};
+
+#define tq_first(hd) ((hd)->first)
+#define tq_last(hd) (*(((struct tqh *)(void *)((hd)->last))->last))
+#define tq_next(e) ((e)->next)
+#define tq_prev(e) (*(((struct tqh *)(void *)((e)->pprev))->last))
+#define tq_empty(hd) (((hd)->first) == NULL)
+#define tq_init(hd) do { \
+	(hd)->first = NULL; \
+	(hd)->last = &(hd)->first; \
+} while (0)
+
+
+#define tq_foreach(var,head) \
+	for ((var) = ((head)->first); \
+		(var) != NULL; \
+		(var) = ((var)->next))
+
+#define tq_foreach_safe(var,head,vnext) \
+	for ((var) = ((head)->first); \
+		(var) != NULL && ((vnext) = tq_next((var)), 1); \
+		(var) = (vnext))
+
+#define tq_foreach_reverse(var,head) \
+	for ((var) = tq_last((head)); \
+		(var) != NULL; \
+		(var) = tq_prev((var)))
+
+#define tq_foreach_reverse_safe(var,head,vprev) \
+	for ((var) = tq_last((head)); \
+		(var) != NULL && ((vprev) = tq_prev((var)),1); \
+		(var) = (vprev))
+
+struct tqh *tq_new(void);
+struct tqe *tq_elem_new(void *);
+void tq_insert_head(struct tqh *, struct tqe *);
+void tq_insert_tail(struct tqh *, struct tqe *);
+void tq_insert_after(struct tqh *, struct tqe *, struct tqe *);
+void tq_insert_before(struct tqh *, struct tqe *, struct tqe *);
+void tq_remove(struct tqh *, struct tqe *);
+void tq_replace(struct tqh *, struct tqe *, struct tqe *);
+void tq_concat(struct tqh *, struct tqh *);
+void tq_cleanup(struct tqh *, void (*)(void *));
+struct tqe *tq_find_from_data(struct tqh *, const void *, int (*)(const void *, const void *));
+
+#endif/*!TQ_H*/