diff options
-rw-r--r-- | README.pod | 4 | ||||
-rw-r--r-- | list.h | 140 | ||||
-rw-r--r-- | test/Makefile | 6 | ||||
-rw-r--r-- | test/list.c | 86 |
4 files changed, 235 insertions, 1 deletions
@@ -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. @@ -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: */ |