local/libqueue: new aport

12 files changed, 832 insertions, 0 deletions

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*/