tree.c 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192
  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 tree implementation
  7. */
  8. #ifdef _KERNEL_
  9. # include <kernel/tree.h>
  10. # include <kernel/system.h>
  11. #else
  12. # include <toaru/tree.h>
  13. # include <stddef.h>
  14. # include <stdlib.h>
  15. #endif
  16. tree_t * tree_create(void) {
  17. /* Create a new tree */
  18. tree_t * out = malloc(sizeof(tree_t));
  19. out->nodes = 0;
  20. out->root = NULL;
  21. return out;
  22. }
  23. void tree_set_root(tree_t * tree, void * value) {
  24. /* Set the root node for a new tree. */
  25. tree_node_t * root = tree_node_create(value);
  26. tree->root = root;
  27. tree->nodes = 1;
  28. }
  29. void tree_node_destroy(tree_node_t * node) {
  30. /* Free the contents of a node and its children, but not the nodes themselves */
  31. foreach(child, node->children) {
  32. tree_node_destroy((tree_node_t *)child->value);
  33. }
  34. free(node->value);
  35. }
  36. void tree_destroy(tree_t * tree) {
  37. /* Free the contents of a tree, but not the nodes */
  38. if (tree->root) {
  39. tree_node_destroy(tree->root);
  40. }
  41. }
  42. void tree_node_free(tree_node_t * node) {
  43. /* Free a node and its children, but not their contents */
  44. if (!node) return;
  45. foreach(child, node->children) {
  46. tree_node_free(child->value);
  47. }
  48. free(node);
  49. }
  50. void tree_free(tree_t * tree) {
  51. /* Free all of the nodes in a tree, but not their contents */
  52. tree_node_free(tree->root);
  53. }
  54. tree_node_t * tree_node_create(void * value) {
  55. /* Create a new tree node pointing to the given value */
  56. tree_node_t * out = malloc(sizeof(tree_node_t));
  57. out->value = value;
  58. out->children = list_create();
  59. out->parent = NULL;
  60. return out;
  61. }
  62. void tree_node_insert_child_node(tree_t * tree, tree_node_t * parent, tree_node_t * node) {
  63. /* Insert a node as a child of parent */
  64. list_insert(parent->children, node);
  65. node->parent = parent;
  66. tree->nodes++;
  67. }
  68. tree_node_t * tree_node_insert_child(tree_t * tree, tree_node_t * parent, void * value) {
  69. /* Insert a (fresh) node as a child of parent */
  70. tree_node_t * out = tree_node_create(value);
  71. tree_node_insert_child_node(tree, parent, out);
  72. return out;
  73. }
  74. tree_node_t * tree_node_find_parent(tree_node_t * haystack, tree_node_t * needle) {
  75. /* Recursive node part of tree_find_parent */
  76. tree_node_t * found = NULL;
  77. foreach(child, haystack->children) {
  78. if (child->value == needle) {
  79. return haystack;
  80. }
  81. found = tree_node_find_parent((tree_node_t *)child->value, needle);
  82. if (found) {
  83. break;
  84. }
  85. }
  86. return found;
  87. }
  88. tree_node_t * tree_find_parent(tree_t * tree, tree_node_t * node) {
  89. /* Return the parent of a node, inefficiently. */
  90. if (!tree->root) return NULL;
  91. return tree_node_find_parent(tree->root, node);
  92. }
  93. size_t tree_count_children(tree_node_t * node) {
  94. /* return the number of children this node has */
  95. if (!node) return 0;
  96. if (!node->children) return 0;
  97. size_t out = node->children->length;
  98. foreach(child, node->children) {
  99. out += tree_count_children((tree_node_t *)child->value);
  100. }
  101. return out;
  102. }
  103. void tree_node_parent_remove(tree_t * tree, tree_node_t * parent, tree_node_t * node) {
  104. /* remove a node when we know its parent; update node counts for the tree */
  105. tree->nodes -= tree_count_children(node) + 1;
  106. list_delete(parent->children, list_find(parent->children, node));
  107. tree_node_free(node);
  108. }
  109. void tree_node_remove(tree_t * tree, tree_node_t * node) {
  110. /* remove an entire branch given its root */
  111. tree_node_t * parent = node->parent;
  112. if (!parent) {
  113. if (node == tree->root) {
  114. tree->nodes = 0;
  115. tree->root = NULL;
  116. tree_node_free(node);
  117. }
  118. }
  119. tree_node_parent_remove(tree, parent, node);
  120. }
  121. void tree_remove(tree_t * tree, tree_node_t * node) {
  122. /* Remove this node and move its children into its parent's list of children */
  123. tree_node_t * parent = node->parent;
  124. /* This is something we just can't do. We don't know how to merge our
  125. * children into our "parent" because then we'd have more than one root node.
  126. * A good way to think about this is actually what this tree struct
  127. * primarily exists for: processes. Trying to remove the root is equivalent
  128. * to trying to kill init! Which is bad. We immediately fault on such
  129. * a case anyway ("Tried to kill init, shutting down!").
  130. */
  131. if (!parent) return;
  132. tree->nodes--;
  133. list_delete(parent->children, list_find(parent->children, node));
  134. foreach(child, node->children) {
  135. /* Reassign the parents */
  136. ((tree_node_t *)child->value)->parent = parent;
  137. }
  138. list_merge(parent->children, node->children);
  139. free(node);
  140. }
  141. void tree_remove_reparent_root(tree_t * tree, tree_node_t * node) {
  142. /* Remove this node and move its children into the root children */
  143. tree_node_t * parent = node->parent;
  144. if (!parent) return;
  145. tree->nodes--;
  146. list_delete(parent->children, list_find(parent->children, node));
  147. foreach(child, node->children) {
  148. /* Reassign the parents */
  149. ((tree_node_t *)child->value)->parent = tree->root;
  150. }
  151. list_merge(tree->root->children, node->children);
  152. free(node);
  153. }
  154. void tree_break_off(tree_t * tree, tree_node_t * node) {
  155. tree_node_t * parent = node->parent;
  156. if (!parent) return;
  157. list_delete(parent->children, list_find(parent->children, node));
  158. }
  159. tree_node_t * tree_node_find(tree_node_t * node, void * search, tree_comparator_t comparator) {
  160. if (comparator(node->value,search)) {
  161. return node;
  162. }
  163. tree_node_t * found;
  164. foreach(child, node->children) {
  165. found = tree_node_find((tree_node_t *)child->value, search, comparator);
  166. if (found) return found;
  167. }
  168. return NULL;
  169. }
  170. tree_node_t * tree_find(tree_t * tree, void * value, tree_comparator_t comparator) {
  171. return tree_node_find(tree->root, value, comparator);
  172. }