summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--README.pod4
-rw-r--r--list.h140
-rw-r--r--test/Makefile6
-rw-r--r--test/list.c86
4 files changed, 235 insertions, 1 deletions
diff --git a/README.pod b/README.pod
index 00dfac4..feb15d1 100644
--- a/README.pod
+++ b/README.pod
@@ -18,6 +18,10 @@ An automatically expanding type-safe generic circular buffer.
A convenient thread pool for libev.
+=item B<list> (L<list.h|http://g.blicky.net/ylib.git/plain/list.h>)
+
+Simple macros for working with (intrusive) linked lists.
+
=item B<sqlasync> (L<sqlasync.h|http://g.blicky.net/ylib.git/plain/sqlasync.h> and L<sqlasync.c|http://g.blicky.net/ylib.git/plain/sqlasync.c>)
Asynchronous wrappers for working with SQLite3 databases.
diff --git a/list.h b/list.h
new file mode 100644
index 0000000..fa3537a
--- /dev/null
+++ b/list.h
@@ -0,0 +1,140 @@
+/* Copyright (c) 2012-2015 Yoran Heling
+
+ 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.
+*/
+
+#ifndef YLIB_LIST_H
+#define YLIB_LIST_H
+
+/* All macros assume that the next/prev pointers are embedded in the structure
+ * of each node, and that they are named 'next' and 'prev'. All macros take a
+ * `list' argument, which is a struct that contains a `head' and `tail'
+ * pointer.
+ *
+ * (Not implemented yet) All macros starting with 's' (e.g. slist_ instead of
+ * list_) operate on singly-linked lists. The nodes only need to have a 'next'
+ * pointer.
+ *
+ * All macros containing the 'h' (hlist_, shlist_) flag take only a single
+ * pointer variable as list argument rather than a struct. This pointer is
+ * treated as the `head' of a list.
+ *
+ * All macros containing the 'p' flag (plist_, splist_) accept an additional
+ * prefix argument. This argument is prefixed to the names of the 'next' and
+ * 'prev' pointers.
+ *
+ * All pointers point directly to the outer-most structure of the node and not
+ * to some specially-embedded structure. The latter is the approach taken, for
+ * example, in the Linux kernel. (https://lwn.net/Articles/336255/)
+ *
+ * Circular lists are not supported. List pointers should be zero-initialized
+ * (i.e. NULL,NULL) before use. These macros do not keep a count of the number
+ * of items in the list.
+ */
+
+
+/* Insert an element in the list before _next. */
+#define plist_insert_before(_p, _l, _n, _next) do {\
+ (_n)->_p##next = (_next);\
+ (_n)->_p##prev = (_next) ? (_next)->_p##prev : NULL;\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n);\
+ else (_l).tail = (_n);\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n);\
+ else (_l).head = (_n);\
+ } while(0)
+
+#define list_insert_before(_l, _n, _next) plist_insert_before(, _l, _n, _next)
+
+
+#define hplist_insert_before(_p, _l, _n, _next) do {\
+ (_n)->_p##next = (_next);\
+ (_n)->_p##prev = (_next) ? (_next)->_p##prev : NULL;\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n);\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n);\
+ else (_l) = (_n);\
+ } while(0)
+
+#define hlist_insert_before(_l, _n, _next) hplist_insert_before(, _l, _n, _next)
+
+
+/* Insert an item at the head of the list */
+#define plist_prepend(_p, _l, _n) plist_insert_before(_p, _l, _n, (_l).head)
+#define list_prepend(_l, _n) list_insert_before(_l, _n, (_l).head)
+#define hplist_prepend(_p, _l, _n) hplist_insert_before(_p, _l, _n, _l)
+#define hlist_prepend(_l, _n) hlist_insert_before(_l, _n, _l)
+
+
+/* Insert an element in the list after _prev. */
+#define plist_insert_after(_p, _l, _n, _prev) do {\
+ (_n)->_p##prev = (_prev);\
+ (_n)->_p##next = (_prev) ? (_prev)->_p##next : NULL;\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n);\
+ else (_l).tail = (_n);\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n);\
+ else (_l).head = (_n);\
+ } while(0)
+
+#define list_insert_after(_l, _n, _prev) plist_insert_after(, _l, _n, _prev)
+
+
+#define hplist_insert_after(_p, _l, _n, _prev) do {\
+ (_n)->_p##prev = (_prev);\
+ (_n)->_p##next = (_prev) ? (_prev)->_p##next : NULL;\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n);\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n);\
+ else (_l) = (_n);\
+ } while(0)
+
+#define hlist_insert_after(_l, _n, _prev) hplist_insert_after(, _l, _n, _prev)
+
+
+/* Insert an item at the end of the list */
+#define plist_append(_p, _l, _n) plist_insert_after(_p, _l, _n, (_l).tail)
+#define list_append(_l, _n) list_insert_after(_l, _n, (_l).tail)
+
+
+/* Remove an element from the list.
+ * To remove the first element:
+ * list_remove(l, l.head);
+ * hlist_remove(l, l);
+ * To remove the last element:
+ * list_remove(l, l.tail);
+ */
+#define plist_remove(_p, _l, _n) do {\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n)->_p##prev;\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n)->_p##next;\
+ if((_n) == (_l)._p##head) (_l)._p##head = (_n)->_p##next;\
+ if((_n) == (_l)._p##tail) (_l)._p##tail = (_n)->_p##prev;\
+ } while(0)
+
+#define list_remove(_l, _n) plist_remove(, _l, _n)
+
+
+#define hplist_remove(_p, _l, _n) do {\
+ if((_n)->_p##next) (_n)->_p##next->_p##prev = (_n)->_p##prev;\
+ if((_n)->_p##prev) (_n)->_p##prev->_p##next = (_n)->_p##next;\
+ if((_n) == (_l)) (_l) = (_n)->_p##next;\
+ } while(0)
+
+#define hlist_remove(_l, _n) hplist_remove(, _l, _n)
+
+
+#endif
+/* vim: set noet sw=4 ts=4: */
diff --git a/test/Makefile b/test/Makefile
index 24aeac1..bcb865a 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -14,6 +14,9 @@ ecbuf: ../ecbuf.h ecbuf.c
vec: ../vec.h vec.c
$(CC) $(CFLAGS) -I.. vec.c -o vec
+list: ../list.h list.c
+ $(CC) $(CFLAGS) -I.. list.c -o list
+
evtp: ../evtp.c ../evtp.h evtp.c
$(CC) $(CFLAGS) -I.. ../evtp.c evtp.c -lpthread -lev -o evtp
@@ -23,10 +26,11 @@ sqlasync: ../sqlasync.c ../sqlasync.h sqlasync.c
ylog: ../ylog.c ../ylog.h ylog.c
$(CC) $(CFLAGS) -I.. ylog.c -o ylog
-test: yuri ecbuf vec evtp sqlasync ylog
+test: yuri ecbuf vec list evtp sqlasync ylog
./yuri
./ecbuf
./vec
+ ./list
./evtp
./sqlasync
./ylog
diff --git a/test/list.c b/test/list.c
new file mode 100644
index 0000000..2081c98
--- /dev/null
+++ b/test/list.c
@@ -0,0 +1,86 @@
+/* Copyright (c) 2015 Yoran Heling
+
+ 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.
+*/
+
+#include "list.h"
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct node node_t;
+struct node { node_t *next, *prev; };
+
+#define T(l, ...) do {\
+ node_t *a[] = {__VA_ARGS__};\
+ assert(l.head == a[0]);\
+ assert(l.tail == a[sizeof(a)/sizeof(*a)-1]);\
+ size_t i, n = sizeof(a)/sizeof(*a);\
+ node_t *c = a[0];\
+ for(i=0; i<n; i++) {\
+ assert(c->prev == (i > 0 ? a[i-1] : NULL));\
+ assert(c->next == (i < n-1 ? a[i+1] : NULL));\
+ c = c->next;\
+ }\
+ } while(0)
+
+#define hT(l, ...) do {\
+ node_t *a[] = {__VA_ARGS__};\
+ assert(l == a[0]);\
+ size_t i, n = sizeof(a)/sizeof(*a);\
+ node_t *c = a[0];\
+ for(i=0; i<n; i++) {\
+ assert(c->prev == (i > 0 ? a[i-1] : NULL));\
+ assert(c->next == (i < n-1 ? a[i+1] : NULL));\
+ c = c->next;\
+ }\
+ } while(0)
+
+static void t_doubly() {
+ struct { node_t *head, *tail; } l = {NULL,NULL};
+ node_t m[5], *n[] = {m, m+1, m+2, m+3, m+4};
+
+ list_prepend(l, n[0]); T(l, n[0]);
+ list_insert_before(l, n[1], n[0]); T(l, n[1], n[0]);
+ list_insert_before(l, n[2], l.tail); T(l, n[1], n[2], n[0]);
+ list_remove(l, n[1]); T(l, n[2], n[0]);
+ list_remove(l, n[0]); T(l, n[2]);
+ list_append(l, n[3]); T(l, n[2], n[3]);
+ list_insert_after(l, n[4], n[2]); T(l, n[2], n[4], n[3]);
+ list_remove(l, n[4]); T(l, n[2], n[3]);
+
+ node_t *hl = NULL;
+ hlist_prepend(hl, n[0]); hT(hl, n[0]);
+ hlist_insert_before(hl, n[1], n[0]); hT(hl, n[1], n[0]);
+ hlist_insert_before(hl, n[2], n[0]); hT(hl, n[1], n[2], n[0]);
+ hlist_remove(hl, n[1]); hT(hl, n[2], n[0]);
+ hlist_remove(hl, n[0]); hT(hl, n[2]);
+ hlist_insert_after(hl, n[3], n[2]); hT(hl, n[2], n[3]);
+ hlist_insert_after(hl, n[4], n[2]); hT(hl, n[2], n[4], n[3]);
+ hlist_remove(hl, n[4]); hT(hl, n[2], n[3]);
+}
+
+
+int main(int argc, char **argv) {
+ t_doubly();
+ return 0;
+}
+
+/* vim: set noet sw=4 ts=4: */