list.c 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
  1. /* vim: tabstop=4 shiftwidth=4 noexpandtab
  2. * This file is part of ToaruOS and is released under the terms
  3. * of the NCSA / University of Illinois License - see LICENSE.md
  4. * Copyright (C) 2011-2014 Kevin Lange
  5. *
  6. * General-purpose list implementations.
  7. */
  8. #ifdef _KERNEL_
  9. # include <kernel/list.h>
  10. # include <kernel/system.h>
  11. #else
  12. # include <stddef.h>
  13. # include <stdlib.h>
  14. # include <toaru/list.h>
  15. #endif
  16. void list_destroy(list_t * list) {
  17. /* Free all of the contents of a list */
  18. node_t * n = list->head;
  19. while (n) {
  20. free(n->value);
  21. n = n->next;
  22. }
  23. }
  24. void list_free(list_t * list) {
  25. /* Free the actual structure of a list */
  26. node_t * n = list->head;
  27. while (n) {
  28. node_t * s = n->next;
  29. free(n);
  30. n = s;
  31. }
  32. }
  33. void list_append(list_t * list, node_t * node) {
  34. assert(!(node->next || node->prev) && "Node is already in a list.");
  35. node->next = NULL;
  36. /* Insert a node onto the end of a list */
  37. node->owner = list;
  38. if (!list->length) {
  39. list->head = node;
  40. list->tail = node;
  41. node->prev = NULL;
  42. node->next = NULL;
  43. list->length++;
  44. return;
  45. }
  46. list->tail->next = node;
  47. node->prev = list->tail;
  48. list->tail = node;
  49. list->length++;
  50. }
  51. node_t * list_insert(list_t * list, void * item) {
  52. /* Insert an item into a list */
  53. node_t * node = malloc(sizeof(node_t));
  54. node->value = item;
  55. node->next = NULL;
  56. node->prev = NULL;
  57. node->owner = NULL;
  58. list_append(list, node);
  59. return node;
  60. }
  61. void list_append_after(list_t * list, node_t * before, node_t * node) {
  62. assert(!(node->next || node->prev) && "Node is already in a list.");
  63. node->owner = list;
  64. if (!list->length) {
  65. list_append(list, node);
  66. return;
  67. }
  68. if (before == NULL) {
  69. node->next = list->head;
  70. node->prev = NULL;
  71. list->head->prev = node;
  72. list->head = node;
  73. list->length++;
  74. return;
  75. }
  76. if (before == list->tail) {
  77. list->tail = node;
  78. } else {
  79. before->next->prev = node;
  80. node->next = before->next;
  81. }
  82. node->prev = before;
  83. before->next = node;
  84. list->length++;
  85. }
  86. node_t * list_insert_after(list_t * list, node_t * before, void * item) {
  87. node_t * node = malloc(sizeof(node_t));
  88. node->value = item;
  89. node->next = NULL;
  90. node->prev = NULL;
  91. node->owner = NULL;
  92. list_append_after(list, before, node);
  93. return node;
  94. }
  95. void list_append_before(list_t * list, node_t * after, node_t * node) {
  96. assert(!(node->next || node->prev) && "Node is already in a list.");
  97. node->owner = list;
  98. if (!list->length) {
  99. list_append(list, node);
  100. return;
  101. }
  102. if (after == NULL) {
  103. node->next = NULL;
  104. node->prev = list->tail;
  105. list->tail->next = node;
  106. list->tail = node;
  107. list->length++;
  108. return;
  109. }
  110. if (after == list->head) {
  111. list->head = node;
  112. } else {
  113. after->prev->next = node;
  114. node->prev = after->prev;
  115. }
  116. node->next = after;
  117. after->prev = node;
  118. list->length++;
  119. }
  120. node_t * list_insert_before(list_t * list, node_t * after, void * item) {
  121. node_t * node = malloc(sizeof(node_t));
  122. node->value = item;
  123. node->next = NULL;
  124. node->prev = NULL;
  125. node->owner = NULL;
  126. list_append_before(list, after, node);
  127. return node;
  128. }
  129. list_t * list_create(void) {
  130. /* Create a fresh list */
  131. list_t * out = malloc(sizeof(list_t));
  132. out->head = NULL;
  133. out->tail = NULL;
  134. out->length = 0;
  135. return out;
  136. }
  137. node_t * list_find(list_t * list, void * value) {
  138. foreach(item, list) {
  139. if (item->value == value) {
  140. return item;
  141. }
  142. }
  143. return NULL;
  144. }
  145. int list_index_of(list_t * list, void * value) {
  146. int i = 0;
  147. foreach(item, list) {
  148. if (item->value == value) {
  149. return i;
  150. }
  151. i++;
  152. }
  153. return -1; /* not find */
  154. }
  155. void list_remove(list_t * list, size_t index) {
  156. /* remove index from the list */
  157. if (index > list->length) return;
  158. size_t i = 0;
  159. node_t * n = list->head;
  160. while (i < index) {
  161. n = n->next;
  162. i++;
  163. }
  164. list_delete(list, n);
  165. }
  166. void list_delete(list_t * list, node_t * node) {
  167. /* remove node from the list */
  168. assert(node->owner == list && "Tried to remove a list node from a list it does not belong to.");
  169. if (node == list->head) {
  170. list->head = node->next;
  171. }
  172. if (node == list->tail) {
  173. list->tail = node->prev;
  174. }
  175. if (node->prev) {
  176. node->prev->next = node->next;
  177. }
  178. if (node->next) {
  179. node->next->prev = node->prev;
  180. }
  181. node->prev = NULL;
  182. node->next = NULL;
  183. node->owner = NULL;
  184. list->length--;
  185. }
  186. node_t * list_pop(list_t * list) {
  187. /* Remove and return the last value in the list
  188. * If you don't need it, you still probably want to free it!
  189. * Try free(list_pop(list)); !
  190. * */
  191. if (!list->tail) return NULL;
  192. node_t * out = list->tail;
  193. list_delete(list, out);
  194. return out;
  195. }
  196. node_t * list_dequeue(list_t * list) {
  197. if (!list->head) return NULL;
  198. node_t * out = list->head;
  199. list_delete(list, out);
  200. return out;
  201. }
  202. list_t * list_copy(list_t * original) {
  203. /* Create a new copy of original */
  204. list_t * out = list_create();
  205. node_t * node = original->head;
  206. while (node) {
  207. list_insert(out, node->value);
  208. }
  209. return out;
  210. }
  211. void list_merge(list_t * target, list_t * source) {
  212. /* Destructively merges source into target */
  213. foreach(node, source) {
  214. node->owner = target;
  215. }
  216. if (source->head) {
  217. source->head->prev = target->tail;
  218. }
  219. if (target->tail) {
  220. target->tail->next = source->head;
  221. } else {
  222. target->head = source->head;
  223. }
  224. if (source->tail) {
  225. target->tail = source->tail;
  226. }
  227. target->length += source->length;
  228. free(source);
  229. }