list.c 5.3 KB

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