123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248 |
- /* vim: tabstop=4 shiftwidth=4 noexpandtab
- * This file is part of ToaruOS and is released under the terms
- * of the NCSA / University of Illinois License - see LICENSE.md
- * Copyright (C) 2011-2018 K. Lange
- *
- * General-purpose list implementations.
- */
- #ifdef _KERNEL_
- # include <kernel/system.h>
- #else
- # include <stddef.h>
- # include <stdlib.h>
- #endif
- #include <toaru/list.h>
- void list_destroy(list_t * list) {
- /* Free all of the contents of a list */
- node_t * n = list->head;
- while (n) {
- free(n->value);
- n = n->next;
- }
- }
- void list_free(list_t * list) {
- /* Free the actual structure of a list */
- node_t * n = list->head;
- while (n) {
- node_t * s = n->next;
- free(n);
- n = s;
- }
- }
- void list_append(list_t * list, node_t * node) {
- assert(!(node->next || node->prev) && "Node is already in a list.");
- node->next = NULL;
- /* Insert a node onto the end of a list */
- node->owner = list;
- if (!list->length) {
- list->head = node;
- list->tail = node;
- node->prev = NULL;
- node->next = NULL;
- list->length++;
- return;
- }
- list->tail->next = node;
- node->prev = list->tail;
- list->tail = node;
- list->length++;
- }
- node_t * list_insert(list_t * list, void * item) {
- /* Insert an item into a list */
- node_t * node = malloc(sizeof(node_t));
- node->value = item;
- node->next = NULL;
- node->prev = NULL;
- node->owner = NULL;
- list_append(list, node);
- return node;
- }
- void list_append_after(list_t * list, node_t * before, node_t * node) {
- assert(!(node->next || node->prev) && "Node is already in a list.");
- node->owner = list;
- if (!list->length) {
- list_append(list, node);
- return;
- }
- if (before == NULL) {
- node->next = list->head;
- node->prev = NULL;
- list->head->prev = node;
- list->head = node;
- list->length++;
- return;
- }
- if (before == list->tail) {
- list->tail = node;
- } else {
- before->next->prev = node;
- node->next = before->next;
- }
- node->prev = before;
- before->next = node;
- list->length++;
- }
- node_t * list_insert_after(list_t * list, node_t * before, void * item) {
- node_t * node = malloc(sizeof(node_t));
- node->value = item;
- node->next = NULL;
- node->prev = NULL;
- node->owner = NULL;
- list_append_after(list, before, node);
- return node;
- }
- void list_append_before(list_t * list, node_t * after, node_t * node) {
- assert(!(node->next || node->prev) && "Node is already in a list.");
- node->owner = list;
- if (!list->length) {
- list_append(list, node);
- return;
- }
- if (after == NULL) {
- node->next = NULL;
- node->prev = list->tail;
- list->tail->next = node;
- list->tail = node;
- list->length++;
- return;
- }
- if (after == list->head) {
- list->head = node;
- } else {
- after->prev->next = node;
- node->prev = after->prev;
- }
- node->next = after;
- after->prev = node;
- list->length++;
- }
- node_t * list_insert_before(list_t * list, node_t * after, void * item) {
- node_t * node = malloc(sizeof(node_t));
- node->value = item;
- node->next = NULL;
- node->prev = NULL;
- node->owner = NULL;
- list_append_before(list, after, node);
- return node;
- }
- list_t * list_create(void) {
- /* Create a fresh list */
- list_t * out = malloc(sizeof(list_t));
- out->head = NULL;
- out->tail = NULL;
- out->length = 0;
- return out;
- }
- node_t * list_find(list_t * list, void * value) {
- foreach(item, list) {
- if (item->value == value) {
- return item;
- }
- }
- return NULL;
- }
- int list_index_of(list_t * list, void * value) {
- int i = 0;
- foreach(item, list) {
- if (item->value == value) {
- return i;
- }
- i++;
- }
- return -1; /* not find */
- }
- void list_remove(list_t * list, size_t index) {
- /* remove index from the list */
- if (index > list->length) return;
- size_t i = 0;
- node_t * n = list->head;
- while (i < index) {
- n = n->next;
- i++;
- }
- list_delete(list, n);
- }
- void list_delete(list_t * list, node_t * node) {
- /* remove node from the list */
- assert(node->owner == list && "Tried to remove a list node from a list it does not belong to.");
- if (node == list->head) {
- list->head = node->next;
- }
- if (node == list->tail) {
- list->tail = node->prev;
- }
- if (node->prev) {
- node->prev->next = node->next;
- }
- if (node->next) {
- node->next->prev = node->prev;
- }
- node->prev = NULL;
- node->next = NULL;
- node->owner = NULL;
- list->length--;
- }
- node_t * list_pop(list_t * list) {
- /* Remove and return the last value in the list
- * If you don't need it, you still probably want to free it!
- * Try free(list_pop(list)); !
- * */
- if (!list->tail) return NULL;
- node_t * out = list->tail;
- list_delete(list, out);
- return out;
- }
- node_t * list_dequeue(list_t * list) {
- if (!list->head) return NULL;
- node_t * out = list->head;
- list_delete(list, out);
- return out;
- }
- list_t * list_copy(list_t * original) {
- /* Create a new copy of original */
- list_t * out = list_create();
- node_t * node = original->head;
- while (node) {
- list_insert(out, node->value);
- }
- return out;
- }
- void list_merge(list_t * target, list_t * source) {
- /* Destructively merges source into target */
- foreach(node, source) {
- node->owner = target;
- }
- if (source->head) {
- source->head->prev = target->tail;
- }
- if (target->tail) {
- target->tail->next = source->head;
- } else {
- target->head = source->head;
- }
- if (source->tail) {
- target->tail = source->tail;
- }
- target->length += source->length;
- free(source);
- }
|