summaryrefslogtreecommitdiff
path: root/src/deque.c
diff options
context:
space:
mode:
authorJörg Frings-Fürst <debian@jff-webhosting.net>2015-02-04 14:09:54 +0100
committerJörg Frings-Fürst <debian@jff-webhosting.net>2015-02-04 14:09:54 +0100
commitbd82d030011cd8b9655e5ded6b6df9343b42a6bd (patch)
treede82d886dfea0cb7dbb6e80436218a25cb211bc3 /src/deque.c
Imported Upstream version 3.22upstream/3.22
Diffstat (limited to 'src/deque.c')
-rw-r--r--src/deque.c181
1 files changed, 181 insertions, 0 deletions
diff --git a/src/deque.c b/src/deque.c
new file mode 100644
index 0000000..3ff7dc9
--- /dev/null
+++ b/src/deque.c
@@ -0,0 +1,181 @@
+/*
+ * Double-ended queues
+ * Copyright Jan Engelhardt, 2002-2008
+ *
+ * This file is part of libHX. libHX is free software; you can
+ * redistribute it and/or modify it under the terms of the GNU Lesser
+ * General Public License as published by the Free Software Foundation;
+ * either version 2.1 or (at your option) any later version.
+ */
+#include <errno.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+#include <libHX/deque.h>
+#include <libHX/string.h>
+#include "internal.h"
+
+static __inline__ void
+HXdeque_add(struct HXdeque_node *af, struct HXdeque_node *nd)
+{
+ struct HXdeque *parent = af->parent;
+ nd->next = af->next;
+ nd->prev = af;
+ af->next = nd;
+ nd->parent = parent;
+ if (parent->last == af)
+ parent->last = nd;
+}
+
+static __inline__ void
+HXdeque_drop(struct HXdeque *parent, struct HXdeque_node *node)
+{
+ struct HXdeque_node *left = node->prev, *right = node->next;
+
+ if (left == NULL) parent->first = right;
+ else left->next = right;
+
+ if (right == NULL) parent->last = left;
+ else right->prev = left;
+}
+
+EXPORT_SYMBOL struct HXdeque *HXdeque_init(void)
+{
+ struct HXdeque *dq;
+ if ((dq = calloc(1, sizeof(struct HXdeque))) == NULL)
+ return NULL;
+ return dq;
+}
+
+EXPORT_SYMBOL struct HXdeque_node *HXdeque_push(struct HXdeque *dq,
+ const void *ptr)
+{
+ struct HXdeque_node *nd;
+ if ((nd = malloc(sizeof(struct HXdeque_node))) == NULL)
+ return NULL;
+ nd->prev = dq->last;
+ nd->next = NULL;
+ nd->parent = dq;
+ nd->ptr = const_cast1(void *, ptr);
+
+ if (dq->first == NULL) {
+ dq->first = dq->last = nd;
+ } else {
+ dq->last->next = nd;
+ dq->last = nd;
+ }
+
+ ++dq->items;
+ return nd;
+}
+
+EXPORT_SYMBOL void *HXdeque_pop(struct HXdeque *dq)
+{
+ if (dq->last == NULL)
+ return NULL;
+ return HXdeque_del(dq->last);
+}
+
+EXPORT_SYMBOL struct HXdeque_node *HXdeque_unshift(struct HXdeque *dq,
+ const void *ptr)
+{
+ struct HXdeque_node *nd;
+
+ if (dq->first == NULL)
+ return HXdeque_push(dq, ptr);
+ if ((nd = malloc(sizeof(struct HXdeque_node))) == NULL)
+ return NULL;
+
+ nd->prev = NULL;
+ nd->next = dq->first;
+ nd->parent = dq;
+ nd->ptr = const_cast1(void *, ptr);
+
+ dq->first->prev = nd;
+ dq->first = nd;
+ ++dq->items;
+ return nd;
+}
+
+EXPORT_SYMBOL void *HXdeque_shift(struct HXdeque *dq)
+{
+ if (dq->first == NULL)
+ return NULL;
+ return HXdeque_del(dq->first);
+}
+
+EXPORT_SYMBOL void HXdeque_move(struct HXdeque_node *nd,
+ struct HXdeque_node *af)
+{
+ HXdeque_drop(nd->parent, nd);
+ HXdeque_add(af, nd);
+}
+
+EXPORT_SYMBOL void *HXdeque_del(struct HXdeque_node *node)
+{
+ void *ret = node->ptr;
+ HXdeque_drop(node->parent, node);
+ --node->parent->items;
+ free(node);
+ return ret;
+}
+
+EXPORT_SYMBOL void HXdeque_free(struct HXdeque *dq)
+{
+ struct HXdeque_node *node, *next;
+ for (node = dq->first; node != NULL; node = next) {
+ next = node->next;
+ free(node);
+ }
+ free(dq);
+}
+
+EXPORT_SYMBOL struct HXdeque_node *HXdeque_find(struct HXdeque *dq,
+ const void *ptr)
+{
+ struct HXdeque_node *travp;
+ for (travp = dq->first; travp != NULL; travp = travp->next)
+ if (travp->ptr == ptr)
+ return travp;
+ return NULL;
+}
+
+EXPORT_SYMBOL void *HXdeque_get(struct HXdeque *dq, const void *ptr)
+{
+ struct HXdeque_node *trav;
+ for (trav = dq->first; trav != NULL; trav = trav->next)
+ if (trav->ptr == ptr)
+ return trav->ptr;
+ return NULL;
+}
+
+EXPORT_SYMBOL void HXdeque_genocide2(struct HXdeque *dq, void (*xfree)(void *))
+{
+ struct HXdeque_node *trav, *next;
+ for (trav = dq->first; trav != NULL; trav = next) {
+ next = trav->next;
+ xfree(trav->ptr);
+ free(trav);
+ }
+ free(dq);
+}
+
+EXPORT_SYMBOL void **
+HXdeque_to_vec(const struct HXdeque *dq, unsigned int *num)
+{
+ const struct HXdeque_node *trav;
+ void **ret, **p;
+
+ ret = malloc((dq->items + 1) * sizeof(void *));
+ if (ret == NULL)
+ return NULL;
+
+ p = ret;
+ for (trav = dq->first; trav != NULL; trav = trav->next)
+ *p++ = trav->ptr;
+ *p = NULL;
+
+ if (num != NULL)
+ *num = dq->items;
+ return ret;
+}