diff options
| -rw-r--r-- | dll.h | 136 | ||||
| -rw-r--r-- | test.c | 79 |
2 files changed, 215 insertions, 0 deletions
@@ -0,0 +1,136 @@ +/* + * Copyright (C) 2019 - Vito Caputo - <vcaputo@pengaru.com> + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 3 as published + * by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +/* (circular) Doubly-Linked List header */ + +/* I've been using the Linux kernel's list.h for ages, so it definitely + * takes some inspiration from that API. + */ + +#ifndef _DLL_H +#define _DLL_H + + +#include <stddef.h> /* offsetof() */ + + +typedef struct dll_t dll_t; + +struct dll_t { + dll_t *next, *previous; +}; + + +/* This is analagous to container_of */ +#define DLL_ENTRY(_ptr, _type, _member) \ + (_type *)((char *)(_ptr) - offsetof(_type, _member)) + + +/* Declare and initialize an empty list named _name */ +#define DLL_INIT(_name) \ + dll_t _name = { .next = &_name, .previous = &_name } + + +/* Iterate list */ +#define DLL_FOR_EACH(_head, _node) \ + for ( (_node) = (_head)->next; \ + (_node) != (_head); \ + (_node) = (_node)->next \ + ) + + +/* Iterate list in a removal-safe fashion */ +#define DLL_FOR_EACH_SAFE(_head, _node, _next) \ + for ( (_node) = (_head)->next, (_next) = (_node)->next; \ + (_node) != (_head); \ + (_node) = (_next), (_next) = (_next->next) \ + ) + + +/* Iterate list as containers */ +#define DLL_FOR_EACH_ENTRY(_head, _entry, _type, _member) \ + for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member); \ + &(_entry)->_member != (_head); \ + (_entry) = DLL_ENTRY((_entry)->_member.next, _type, _member) \ + ) + + +/* Iterate list as containers in a removal-safe fashion */ +#define DLL_FOR_EACH_ENTRY_SAFE(_head, _entry, _next, _type, _member) \ + for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member), \ + (_next) = DLL_ENTRY((_entry)->_member.next, _type, _member); \ + &(_entry)->_member != (_head); \ + (_entry) = (_next), \ + (_next) = DLL_ENTRY((_next)->_member.next, _type, _member) \ + ) + + +/* Initialize node to an empty list state, + * node is returned for convenience. + */ +static inline dll_t * dll_init(dll_t *node) +{ + return node->next = node->previous = node; +} + + +/* Delete node from the list it belongs to, + * node is returned for convenience. + */ +static inline dll_t * dll_del(dll_t *node) +{ + node->next->previous = node->previous; + node->previous->next = node->next; + + return dll_init(node); +} + + +/* Insert node immediately before where, + * node is returned for convenience. + */ +static inline dll_t * dll_pre(dll_t *where, dll_t *node) +{ + node->next = where; + node->previous = where->previous; + where->previous->next = node; + where->previous = node; + + return node; +} + + +/* Append node immediately after where, + * node is returned for convenience. + */ +static inline dll_t * dll_post(dll_t *where, dll_t *node) +{ + node->next = where->next; + node->previous = where; + where->next->previous = node; + where->next = node; + + return node; +} + + +static inline int dll_empty(dll_t *dll) +{ + return (dll->next == dll && dll->next == dll->previous); +} + + +#endif @@ -0,0 +1,79 @@ +#include <assert.h> +#include <stdio.h> + +#include "dll.h" + +#define NUM_NODES 100 + +DLL_INIT(foo); + +typedef struct entry_t { + dll_t node; + int id; +} entry_t; + + +int main(int argc, char *argv[]) +{ + entry_t entries[NUM_NODES], *entry, *_entry; + dll_t nodes[NUM_NODES]; + dll_t *tmp, *_tmp; + + for (int i = 0; i < NUM_NODES; i++) { + dll_pre(&foo, &nodes[i]); + printf("appended %i:%p to tail\n", i, &nodes[i]); + } + + DLL_FOR_EACH(&foo, tmp) + printf("node=%p\n", tmp); + + for (int i = 0; i < NUM_NODES; i++) { + if (!(i % 2)) + continue; + + printf("deleted %i:%p\n", i, dll_del(&nodes[i])); + } + + DLL_FOR_EACH(&foo, tmp) + printf("node=%p\n", tmp); + + assert(!dll_empty(&foo)); + + DLL_FOR_EACH_SAFE(&foo, tmp, _tmp) + printf("deleted %p\n", dll_del(tmp)); + + DLL_FOR_EACH(&foo, tmp) + printf("!!!notempty!!! node=%p\n", tmp); + + assert(dll_empty(&foo)); + + for (int i = 0; i < NUM_NODES; i++) { + dll_pre(&foo, &entries[i].node); + entries[i].id = i; + } + + DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node) { + printf("id=%i entry=%p node=%p\n", + entry->id, entry, &entry->node); + } + + for (int i = 0; i < NUM_NODES; i++) { + if (!(i % 2)) + continue; + + printf("deleted %i:%p\n", i, dll_del(&entries[i].node)); + } + + DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node) { + printf("id=%i entry=%p node=%p\n", + entry->id, entry, &entry->node); + } + + DLL_FOR_EACH_ENTRY_SAFE(&foo, entry, _entry, entry_t, node) + printf("deleted %p\n", dll_del(&entry->node)); + + DLL_FOR_EACH_ENTRY(&foo, entry, entry_t, node) + printf("!!!notempty!!! entry=%p\n", entry); + + assert(dll_empty(&foo)); +} |