aboutsummaryrefslogtreecommitdiff
path: root/subprojects
diff options
context:
space:
mode:
Diffstat (limited to 'subprojects')
-rw-r--r--subprojects/tllist/LICENSE21
-rw-r--r--subprojects/tllist/README.md301
-rw-r--r--subprojects/tllist/meson.build5
-rw-r--r--subprojects/tllist/test.c96
-rw-r--r--subprojects/tllist/tllist.h180
5 files changed, 603 insertions, 0 deletions
diff --git a/subprojects/tllist/LICENSE b/subprojects/tllist/LICENSE
new file mode 100644
index 00000000..6d93abca
--- /dev/null
+++ b/subprojects/tllist/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2018 Daniel Eklöf
+
+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/subprojects/tllist/README.md b/subprojects/tllist/README.md
new file mode 100644
index 00000000..0fc3fa48
--- /dev/null
+++ b/subprojects/tllist/README.md
@@ -0,0 +1,301 @@
+# tllist
+
+**tllist** is a *T*yped *L*inked *L*ist C header file only
+library implemented using pre-processor macros.
+
+
+1. [Description](#description)
+1. [Usage](#usage)
+ 1. [Declaring a variable](#declaring-a-variable)
+ 1. [Adding items - basic](#adding-items-basic)
+ 1. [List length](#list-length)
+ 1. [Accessing items](#accessing-items)
+ 1. [Iterating](#iterating)
+ 1. [Removing items - basic](#removing-items-basic)
+ 1. [Adding items - advanced](#adding-items-advanced)
+ 1. [Removing items - advanced](#removing-items-advanced)
+ 1. [Freeing](#freeing)
+1. [Integrating](#integrating)
+ 1. [Meson](#meson)
+1. [API](#api)
+ 1. [Cheat sheet](#cheat-sheet)
+
+
+## Description
+
+Most C implementations of linked list are untyped. That is, their data
+carriers are typically `void *`. This is error prone since your
+compiler will not be able to help you correct your mistakes (_oh, was
+it pointer-to-a-pointer... I though it was just a pointer..._).
+
+**tllist** addresses this by using pre-processor macros to implement
+dynamic types, where the data carrier is typed to whatever you want;
+both **primitive** data types are supported as well as aggregated ones
+such as **structs**, **enums** and **unions**.
+
+Being a double-linked list, most operations are constant in time
+(including pushing and popping both to/from front and back).
+
+The memory overhead is fairly small; each item carries, besides its
+data, a _prev_ and _next_ pointer (i.e. a constant 16 byte overhead
+per item on 64-bit architectures).
+
+The list itself has two _head_ and _tail_ pointers, plus a _length_
+variable (typically 8 bytes on 64-bit architectures) to make list
+length lookup constant in time.
+
+Thus, assuming 64-bit pointers (and a 64-bit `size_t` type), the total
+overhead is `3*8 + n*2*8` bytes.
+
+
+## Usage
+
+### Declaring a variable
+
+1. **Declare a variable**
+
+ ```c
+ /* Declare a variable using an anonymous type */
+ tll(int) an_integer_list = tll_init();
+ ```
+
+
+2. **Typedef**
+
+ ```c
+ /* First typedef the list type */
+ typedef tll(int) an_integer_list_t;
+
+ /* Then declare a variable using that typedef */
+ an_integer_list_t an_integer_list = tll_init();
+ ```
+
+3. **Named struct**
+
+ ```c
+ /* First declare named struct */
+ tll(int, an_integer_list);
+
+ /* Then declare a variable using that named struct */
+ struct an_integer_list an_integer_list = tll_init();
+ ```
+
+### Adding items - basic
+
+Use `tll_push_back()` or `tll_push_front()` to add elements to the
+back or front of the list.
+
+```c
+tll_push_back(an_integer_list, 4711);
+tll_push_front(an_integer_list, 1234);
+```
+
+
+### List length
+
+`tll_length()` returns the length (number of items) in a list.
+
+```c
+tll_push_back(an_integer_list, 1234);
+tll_push_back(an_integer_list, 5678);
+printf("length: %zu\n", tll_length(an_integer_list));
+```
+
+Outputs:
+
+ length: 2
+
+
+### Accessing items
+
+For the front and back items, you can use `tll_front()` and
+`tll_back()` respectively. For any other item in the list, you need to
+iterate the list and find the item yourself.
+
+```c
+tll_push_back(an_integer_list, 1234);
+tll_push_back(an_integer_list, 5555);
+tll_push_back(an_integer_list, 6789);
+
+printf("front: %d\n", tll_front(an_integer_list));
+printf("back: %d\n", tll_back(an_integer_list));
+```
+
+Outputs:
+
+ front: 1234
+ back: 6789
+
+
+### Iterating
+
+You can iterate the list either forward or backwards, using
+`tll_foreach()` and `tll_rforeach()` respectively.
+
+The `it` variable should be treated as an opaque iterator type, where
+`it->item` is the item.
+
+In reality, it is simply a pointer to the linked list entry, and since
+tllist is a header-only implementation, you do have access to e.g. the
+next/prev pointers. There should not be any need to access anything
+except `item` however.
+
+Note that `it` can be named anything.
+
+```c
+tll_push_back(an_integer_list, 1);
+tll_push_back(an_integer_list, 2);
+
+tll_foreach(an_integer_list, it) {
+ printf("forward: %d\n", it->item);
+}
+
+tll_rforeach(an_integer_list, it) {
+ printf("reverse: %d\n", it->item);
+}
+```
+
+Outputs:
+
+ forward: 1
+ forward: 2
+ reverse: 2
+ reverse: 1
+
+
+### Removing items - basic
+
+`tll_pop_front()` and `tll_pop_back()` removes the front/back item and
+returns it.
+
+```c
+tll_push_back(an_integer_list, 1234);
+tll_push_back(an_integer_list, 5678);
+
+printf("front: %d\n", tll_pop_front(an_integer_list));
+printf("back: %d\n", tll_pop_back(an_integer_list));
+printf("length: %zu\n", tll_length(an_integer_list));
+```
+
+Outputs:
+
+ front: 1234
+ back: 5678
+ length: 0
+
+
+### Adding items - advanced
+
+Given an iterator, you can insert new items before or after that
+iterator, using `tll_insert_before()` and `tll_insert_after()`.
+
+```c
+tll_foreach(an_integer_list, it) {
+ if (it->item == 1234) {
+ tll_insert_before(an_integer_list, it, 7777);
+ break;
+ }
+}
+```
+
+Q: Why do I have to pass **both** the _list_ and the _iterator_ to
+ `tll_insert_before()`?
+
+A: If not, **each** element in the list would have to contain a
+ pointer to the owning list, which would significantly increase the
+ overhead.
+
+
+### Removing items - advanced
+
+Similar to how you can add items while iterating a list, you can also
+remove them.
+
+Note that the `*foreach()` functions are **safe** in this regard - it
+is perfectly OK to remove the "current" item.
+
+```c
+tll_foreach(an_integer_list, it) {
+ if (it->item.delete_me)
+ tll_remove(an_integer_list, it);
+}
+```
+
+To make it slightly easier to handle cases where the item _itself_
+must be free:d as well, there is also `tll_remove_and_free()`. It
+works just like `tll_remove()`, but takes an additional argument; a
+callback that will be called for each item.
+
+```c
+tll(int *) int_p_list = tll_init();
+
+int *a = malloc(sizeof(*a));
+int *b = malloc(sizeof(*b));
+
+*a = 1234;
+*b = 5678;
+
+tll_push_back(int_p_list, a);
+tll_push_back(int_p_list, b);
+
+tll_foreach(int_p_list, it) {
+ tll_remove_and_free(int_p_list, it, free);
+}
+```
+
+
+### Freeing
+
+To remove **all** items, use `tll_free()`, or
+`tll_free_and_free()`. These are just convenience functions and
+calling these are equivalent to:
+
+```c
+tll_foreach(an_integer_list, it) {
+ tll_remove(an_integer_list, it);
+}
+```
+
+Note that there is no need to call `tll_free()` on an empty
+(`tll_length(list) == 0`) list.
+
+
+## Integrating
+
+The easiest way may be to simply copy `tllist.h` into your
+project. But see sections below for other ways.
+
+
+### Meson
+
+You can use tllist as a subproject. In your main project's
+`meson.build`, to something like:
+
+```meson
+tllist = subproject('tllist').get_variable('tllist')
+executable('you-executable', ..., dependencies: [tllist])
+```
+
+
+## API
+
+### Cheat sheet
+
+| Function | Description | Context | Complexity |
+|-------------------------------------|-------------------------------------------------------|--------------------|-----------:|
+| `list = tll_init()` | initialize a new tllist variable to an empty list | Variable init | O(1) |
+| `tll_length(list)` | returns the length (number of items) of a list | | O(1) |
+| `tll_push_front(list, item)` | inserts _item_ at the beginning of the list | | O(1) |
+| `tll_push_back(list, item)` | inserts _item_ at the end of the list | | O(1) |
+| `tll_front(list)` | returns the first item in the list | | O(1) |
+| `tll_back(list)` | returns the last item in the list | | O(1) |
+| `tll_pop_front(list)` | removes and returns the first item in the list | | O(1) |
+| `tll_pop_back(list)` | removes and returns the last item in the list | | O(1) |
+| `tll_foreach(list, it)` | iterates the list from the beginning to the end | | O(n) |
+| `tll_rforeach(list, it)` | iterates the list from the end to the beginning | | O(n) |
+| `tll_insert_before(list, it, item)` | inserts _item_ before _it_. | `tll_(r)foreach()` | O(1) |
+| `tll_insert_after(list, it, item)` | inserts _item_ after _it_. | `tll_(r)foreach()` | O(1) |
+| `tll_remove(list, it)` | removes _it_ from the list. | `tll_(r)foreach()` | O(1) |
+| `tll_remove_and_free(list, it, cb)` | removes _it_ from the list, and calls `cb(it->item)`. | `tll_(r)foreach()` | O(1) |
+| `tll_free(list)` | removes **all** items from the list | | O(n) |
+| `tll_free_and_free(list, cb)` | removes **all** items from the list, and calls `cb(it->item)` for each item. | | O(n) |
diff --git a/subprojects/tllist/meson.build b/subprojects/tllist/meson.build
new file mode 100644
index 00000000..2f6123f5
--- /dev/null
+++ b/subprojects/tllist/meson.build
@@ -0,0 +1,5 @@
+project('tllist', 'c', version: '1.0.0', license: 'MIT', meson_version: '>=0.50.0')
+tllist = declare_dependency(include_directories: '.')
+
+unittest = executable('unittest', 'test.c', dependencies: [tllist])
+test('unittest', unittest)
diff --git a/subprojects/tllist/test.c b/subprojects/tllist/test.c
new file mode 100644
index 00000000..515b5ad2
--- /dev/null
+++ b/subprojects/tllist/test.c
@@ -0,0 +1,96 @@
+#undef NDEBUG
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include <tllist.h>
+
+int
+main(int argc, const char *const *argv)
+{
+ tll(int) l = tll_init();
+ assert(tll_length(l) == 0);
+
+ /* push back */
+ tll_push_back(l, 123); assert(tll_length(l) == 1);
+ tll_push_back(l, 456); assert(tll_length(l) == 2);
+ tll_push_back(l, 789); assert(tll_length(l) == 3);
+
+ assert(tll_front(l) == 123);
+ assert(tll_back(l) == 789);
+
+ /* push front */
+ tll_push_front(l, 0xabc); assert(tll_length(l) == 4);
+
+ assert(tll_front(l) == 0xabc);
+ assert(tll_back(l) == 789);
+
+ /* Pop back */
+ assert(tll_pop_back(l) == 789);
+ assert(tll_back(l) == 456);
+
+ /* Pop front */
+ assert(tll_pop_front(l) == 0xabc);
+ assert(tll_front(l) == 123);
+
+ /* foreach */
+ assert(tll_length(l) == 2);
+
+ int seen[tll_length(l)];
+ memset(seen, 0, tll_length(l) * sizeof(seen[0]));
+
+ size_t count = 0;
+ tll_foreach(l, it)
+ seen[count++] = it->item;
+
+ assert(count == tll_length(l));
+ assert(seen[0] == 123);
+ assert(seen[1] == 456);
+
+ /* rforeach */
+ memset(seen, 0, tll_length(l) * sizeof(seen[0]));
+ count = 0;
+ tll_rforeach(l, it)
+ seen[count++] = it->item;
+
+ assert(count == tll_length(l));
+ assert(seen[0] == 456);
+ assert(seen[1] == 123);
+
+ /* remove */
+ tll_push_back(l, 789);
+ tll_foreach(l, it) {
+ if (it->item > 123 && it->item < 789)
+ tll_remove(l, it);
+ }
+ assert(tll_length(l) == 2);
+ assert(tll_front(l) == 123);
+ assert(tll_back(l) == 789);
+
+ /* insert before */
+ tll_foreach(l, it) {
+ if (it->item == 123)
+ tll_insert_before(l, it, 0xabc);
+ }
+ assert(tll_length(l) == 3);
+ assert(tll_front(l) == 0xabc);
+ assert(tll_back(l) == 789);
+
+ /* insert after */
+ tll_foreach(l, it) {
+ if (it->item == 789)
+ tll_insert_after(l, it, 999);
+ }
+ assert(tll_length(l) == 4);
+ assert(tll_front(l) == 0xabc);
+ assert(tll_back(l) == 999);
+
+ /* free */
+ tll_free(l);
+ assert(tll_length(l) == 0);
+ assert(l.head == NULL);
+ assert(l.tail == NULL);
+
+ return EXIT_SUCCESS;
+}
diff --git a/subprojects/tllist/tllist.h b/subprojects/tllist/tllist.h
new file mode 100644
index 00000000..ec2fd41c
--- /dev/null
+++ b/subprojects/tllist/tllist.h
@@ -0,0 +1,180 @@
+#pragma once
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <assert.h>
+
+#define TLL_PASTE2( a, b) a##b
+#define TLL_PASTE( a, b) TLL_PASTE2( a, b)
+
+/* Utility macro to generate a list element struct with a unique struct tag */
+#define TLL_UNIQUE_INNER_STRUCT(TYPE, ID) \
+ struct TLL_PASTE(__tllist_ , ID) { \
+ TYPE item; \
+ struct TLL_PASTE(__tllist_, ID) *prev; \
+ struct TLL_PASTE(__tllist_, ID) *next; \
+ } *head, *tail;
+
+/*
+ * Defines a new typed-list type, or directly instantiate a typed-list variable
+ *
+ * Example a, declare a variable (list of integers):
+ * tll(int) my_list;
+ *
+ * Example b, declare a type, and then use the type:
+ * tll(int, my_list_type);
+ * struct my_list_type my_list;
+ */
+#define tll(TYPE, ...) \
+ struct __VA_ARGS__ { \
+ TLL_UNIQUE_INNER_STRUCT(TYPE, __COUNTER__) \
+ size_t length; \
+ }
+
+/* Initializer: tll(int) my_list = tll_init(); */
+#define tll_init() {.head = NULL, .tail = NULL, .length = 0}
+
+/* Length/size of list: printf("size: %zu\n", tll_length(my_list)); */
+#define tll_length(list) (list).length
+
+/* Adds a new item to the back of the list */
+#define tll_push_back(list, new_item) \
+ do { \
+ tll_insert_after(list, (list).tail, new_item); \
+ if ((list).head == NULL) \
+ (list).head = (list).tail; \
+ } while (0)
+
+/* Adds a new item to the front of the list */
+#define tll_push_front(list, new_item) \
+ do { \
+ tll_insert_before(list, (list).head, new_item); \
+ if ((list).tail == NULL) \
+ (list).tail = (list).head; \
+ } while (0)
+
+/*
+ * Iterates the list. <it> is an iterator pointer. You can access the
+ * list item with ->item:
+ *
+ * tll(int) my_list = vinit();
+ * tll_push_back(my_list, 5);
+ *
+ * tll_foreach(my_list i) {
+ * printf("%d\n", i->item);
+ * }
+*/
+#define tll_foreach(list, it) \
+ for (__typeof__(*(list).head) *it = (list).head, \
+ *it_next = it != NULL ? it->next : NULL; \
+ it != NULL; \
+ it = it_next, \
+ it_next = it_next != NULL ? it_next->next : NULL)
+
+/* Same as tll_foreach(), but iterates backwards */
+#define tll_rforeach(list, it) \
+ for (__typeof__(*(list).tail) *it = (list).tail, \
+ *it_prev = it != NULL ? it->prev : NULL; \
+ it != NULL; \
+ it = it_prev, \
+ it_prev = it_prev != NULL ? it_prev->prev : NULL)
+
+/*
+ * Inserts a new item after <it>, which is an iterator. I.e. you can
+ * only call this from inside a tll_foreach() or tll_rforeach() loop.
+ */
+#define tll_insert_after(list, it, new_item) \
+ do { \
+ __typeof__((list).head) __e = malloc(sizeof(*__e)); \
+ __e->item = (new_item); \
+ __e->prev = (it); \
+ __e->next = (it) != NULL ? (it)->next : NULL; \
+ if ((it) != NULL) { \
+ if ((it)->next != NULL) \
+ (it)->next->prev = __e; \
+ (it)->next = __e; \
+ } \
+ if ((it) == (list).tail) \
+ (list).tail = __e; \
+ (list).length++; \
+ } while (0)
+
+/*
+ * Inserts a new item before <it>, which is an iterator. I.e. you can
+ * only call this from inside a tll_foreach() or tll_rforeach() loop.
+ */
+#define tll_insert_before(list, it, new_item) \
+ do { \
+ __typeof__((list).head) __e = malloc(sizeof(*__e)); \
+ __e->item = (new_item); \
+ __e->prev = (it) != NULL ? (it)->prev : NULL; \
+ __e->next = (it); \
+ if ((it) != NULL) { \
+ if ((it)->prev != NULL) \
+ (it)->prev->next = __e; \
+ (it)->prev = __e; \
+ } \
+ if ((it) == (list).head) \
+ (list).head = __e; \
+ (list).length++; \
+ } while (0)
+
+/*
+ * Removes an entry from the list. <it> is an iterator. I.e. you can
+ * only call this from inside a tll_foreach() or tll_rforeach() loop.
+ */
+#define tll_remove(list, it) \
+ do { \
+ assert((list).length > 0); \
+ __typeof__((list).head) __prev = it->prev; \
+ __typeof__((list).head) __next = it->next; \
+ if (__prev != NULL) \
+ __prev->next = __next; \
+ else \
+ (list).head = __next; \
+ if (__next != NULL) \
+ __next->prev = __prev; \
+ else \
+ (list).tail = __prev; \
+ free(it); \
+ (list).length--; \
+ } while (0)
+
+/* Same as tll_remove(), but calls free_callback(it->item) */
+#define tll_remove_and_free(list, it, free_callback) \
+ do { \
+ free_callback((it)->item); \
+ tll_remove((list), (it)); \
+ } while (0)
+
+#define tll_front(list) (list).head->item
+#define tll_back(list) (list).tail->item
+
+/*
+ * Removes the first element from the list, and returns it (note:
+ * returns the *actual* item, not an iterator.
+ */
+#define tll_pop_front(list) \
+ ({__typeof__((list).head) it = (list).head; \
+ __typeof__((list).head->item) __ret = it->item; \
+ tll_remove((list), it); \
+ __ret; \
+ })
+
+/* Same as tll_pop_front(), but returns/removes the *last* element */
+#define tll_pop_back(list) \
+ ({__typeof__((list).tail) it = (list).tail; \
+ __typeof__((list).tail->item) __ret = it->item; \
+ tll_remove((list), it); \
+ __ret; \
+ })
+
+/* Frees the list. This call is *not* needed if the list is already empty. */
+#define tll_free(list) \
+ tll_foreach(list, __it) \
+ tll_remove(list, __it)
+
+/* Same as tll_free(), but also calls free_callback(item) for every item */
+#define tll_free_and_free(list, free_callback) \
+ tll_foreach(list, __it) \
+ tll_remove_and_free(list, __it, free_callback)