tree.c 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301
  1. /*
  2. * tree.c
  3. *
  4. * This file provides the implementation of a konf_tree class
  5. */
  6. #include "private.h"
  7. #include "lub/argv.h"
  8. #include "lub/string.h"
  9. #include "lub/ctype.h"
  10. #include <assert.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <stdio.h>
  14. #include <sys/types.h>
  15. #include <regex.h>
  16. /*---------------------------------------------------------
  17. * PRIVATE META FUNCTIONS
  18. *--------------------------------------------------------- */
  19. int konf_tree_bt_compare(const void *clientnode, const void *clientkey)
  20. {
  21. const konf_tree_t *this = clientnode;
  22. unsigned short *pri = (unsigned short *)clientkey;
  23. unsigned short *seq = (unsigned short *)clientkey + 1;
  24. char *line = ((char *)clientkey + (2 * sizeof(unsigned short)));
  25. /* Priority check */
  26. if (this->priority != *pri)
  27. return (this->priority - *pri);
  28. /* Sequence check */
  29. if (this->seq_num != *seq)
  30. return (this->seq_num - *seq);
  31. /* Line check */
  32. return lub_string_nocasecmp(this->line, line);
  33. }
  34. /*-------------------------------------------------------- */
  35. static void konf_tree_key(lub_bintree_key_t * key,
  36. unsigned short priority, unsigned short sequence,
  37. const char *text)
  38. {
  39. unsigned short *pri = (unsigned short *)key;
  40. unsigned short *seq = (unsigned short *)key + 1;
  41. char *line = ((char *)key + (2 * sizeof(unsigned short)));
  42. /* fill out the opaque key */
  43. *pri = priority;
  44. *seq = sequence;
  45. strcpy(line, text);
  46. }
  47. /*-------------------------------------------------------- */
  48. void konf_tree_bt_getkey(const void *clientnode, lub_bintree_key_t * key)
  49. {
  50. const konf_tree_t *this = clientnode;
  51. konf_tree_key(key, this->priority, this->seq_num, this->line);
  52. }
  53. /*---------------------------------------------------------
  54. * PRIVATE METHODS
  55. *--------------------------------------------------------- */
  56. static void
  57. konf_tree_init(konf_tree_t * this, const char *line, unsigned short priority)
  58. {
  59. /* set up defaults */
  60. this->line = lub_string_dup(line);
  61. this->priority = priority;
  62. this->seq_num = 0;
  63. this->splitter = BOOL_TRUE;
  64. /* Be a good binary tree citizen */
  65. lub_bintree_node_init(&this->bt_node);
  66. /* initialise the tree of commands for this conf */
  67. lub_bintree_init(&this->tree,
  68. konf_tree_bt_offset(),
  69. konf_tree_bt_compare, konf_tree_bt_getkey);
  70. }
  71. /*--------------------------------------------------------- */
  72. static void konf_tree_fini(konf_tree_t * this)
  73. {
  74. konf_tree_t *conf;
  75. /* delete each conf held by this conf */
  76. while ((conf = lub_bintree_findfirst(&this->tree))) {
  77. /* remove the conf from the tree */
  78. lub_bintree_remove(&this->tree, conf);
  79. /* release the instance */
  80. konf_tree_delete(conf);
  81. }
  82. /* free our memory */
  83. lub_string_free(this->line);
  84. this->line = NULL;
  85. }
  86. /*---------------------------------------------------------
  87. * PUBLIC META FUNCTIONS
  88. *--------------------------------------------------------- */
  89. size_t konf_tree_bt_offset(void)
  90. {
  91. return offsetof(konf_tree_t, bt_node);
  92. }
  93. /*--------------------------------------------------------- */
  94. konf_tree_t *konf_tree_new(const char *line, unsigned short priority)
  95. {
  96. konf_tree_t *this = malloc(sizeof(konf_tree_t));
  97. if (this) {
  98. konf_tree_init(this, line, priority);
  99. }
  100. return this;
  101. }
  102. /*---------------------------------------------------------
  103. * PUBLIC METHODS
  104. *--------------------------------------------------------- */
  105. void konf_tree_delete(konf_tree_t * this)
  106. {
  107. konf_tree_fini(this);
  108. free(this);
  109. }
  110. /*--------------------------------------------------------- */
  111. void konf_tree_fprintf(konf_tree_t * this, FILE * stream,
  112. const char *pattern, int depth,
  113. unsigned char prev_pri_hi)
  114. {
  115. konf_tree_t *conf;
  116. lub_bintree_iterator_t iter;
  117. unsigned char pri = 0;
  118. if (this->line && *(this->line) != '\0') {
  119. char *space = NULL;
  120. if (depth > 0) {
  121. space = malloc(depth + 1);
  122. memset(space, ' ', depth);
  123. space[depth] = '\0';
  124. }
  125. if ((0 == depth) &&
  126. (this->splitter ||
  127. (konf_tree__get_priority_hi(this) != prev_pri_hi)))
  128. fprintf(stream, "!\n");
  129. fprintf(stream, "%s%s\n", space ? space : "", this->line);
  130. free(space);
  131. }
  132. /* iterate child elements */
  133. if (!(conf = lub_bintree_findfirst(&this->tree)))
  134. return;
  135. for(lub_bintree_iterator_init(&iter, &this->tree, conf);
  136. conf; conf = lub_bintree_iterator_next(&iter)) {
  137. if (pattern &&
  138. (lub_string_nocasestr(conf->line, pattern) != conf->line))
  139. continue;
  140. konf_tree_fprintf(conf, stream, NULL, depth + 1, pri);
  141. pri = konf_tree__get_priority_hi(conf);
  142. }
  143. }
  144. /*--------------------------------------------------------- */
  145. konf_tree_t *konf_tree_new_conf(konf_tree_t * this,
  146. const char *line, unsigned short priority,
  147. bool_t seq, unsigned short seq_num, unsigned short seq_step)
  148. {
  149. konf_tree_t *conf;
  150. /* Allocate the memory for a new child element */
  151. konf_tree_t *newconf = konf_tree_new(line, priority);
  152. assert(newconf);
  153. /* Sequence */
  154. if (seq) {
  155. konf_tree__set_seq_num(newconf, seq_num);
  156. /* If tree is empty */
  157. /* conf = lub_bintree_findfirst(&this->tree);
  158. konf_tree__set_seq_num(newconf, seq_num);
  159. return NULL;
  160. else {
  161. }
  162. */
  163. }
  164. /* Non empty tree */
  165. if (seq && conf) {
  166. }
  167. /* Insert it into the binary tree for this conf */
  168. if (-1 == lub_bintree_insert(&this->tree, newconf)) {
  169. /* inserting a duplicate command is bad */
  170. konf_tree_delete(newconf);
  171. newconf = NULL;
  172. }
  173. return newconf;
  174. }
  175. /*--------------------------------------------------------- */
  176. konf_tree_t *konf_tree_find_conf(konf_tree_t * this,
  177. const char *line, unsigned short priority, unsigned short sequence)
  178. {
  179. konf_tree_t *conf;
  180. lub_bintree_key_t key;
  181. lub_bintree_iterator_t iter;
  182. if ((0 != priority) && (0 != sequence)) {
  183. konf_tree_key(&key, priority, sequence, line);
  184. return lub_bintree_find(&this->tree, &key);
  185. }
  186. /* If tree is empty */
  187. if (!(conf = lub_bintree_findfirst(&this->tree)))
  188. return NULL;
  189. /* Iterate non-empty tree */
  190. lub_bintree_iterator_init(&iter, &this->tree, conf);
  191. do {
  192. if (0 == lub_string_nocasecmp(conf->line, line))
  193. return conf;
  194. } while ((conf = lub_bintree_iterator_next(&iter)));
  195. return NULL;
  196. }
  197. /*--------------------------------------------------------- */
  198. void konf_tree_del_pattern(konf_tree_t *this,
  199. const char *pattern)
  200. {
  201. konf_tree_t *conf;
  202. lub_bintree_iterator_t iter;
  203. regex_t regexp;
  204. /* Is tree empty? */
  205. if (!(conf = lub_bintree_findfirst(&this->tree)))
  206. return;
  207. /* Compile regular expression */
  208. regcomp(&regexp, pattern, REG_EXTENDED | REG_ICASE);
  209. /* Iterate configuration tree */
  210. lub_bintree_iterator_init(&iter, &this->tree, conf);
  211. do {
  212. if (0 == regexec(&regexp, conf->line, 0, NULL, 0)) {
  213. lub_bintree_remove(&this->tree, conf);
  214. konf_tree_delete(conf);
  215. }
  216. } while ((conf = lub_bintree_iterator_next(&iter)));
  217. regfree(&regexp);
  218. }
  219. /*--------------------------------------------------------- */
  220. unsigned short konf_tree__get_priority(const konf_tree_t * this)
  221. {
  222. return this->priority;
  223. }
  224. /*--------------------------------------------------------- */
  225. unsigned char konf_tree__get_priority_hi(const konf_tree_t * this)
  226. {
  227. return (unsigned char)(this->priority >> 8);
  228. }
  229. /*--------------------------------------------------------- */
  230. unsigned char konf_tree__get_priority_lo(const konf_tree_t * this)
  231. {
  232. return (unsigned char)(this->priority & 0xff);
  233. }
  234. /*--------------------------------------------------------- */
  235. bool_t konf_tree__get_splitter(const konf_tree_t * this)
  236. {
  237. return this->splitter;
  238. }
  239. /*--------------------------------------------------------- */
  240. void konf_tree__set_splitter(konf_tree_t *this, bool_t splitter)
  241. {
  242. this->splitter = splitter;
  243. }
  244. /*--------------------------------------------------------- */
  245. unsigned short konf_tree__get_seq_num(const konf_tree_t * this)
  246. {
  247. return this->seq_num;
  248. }
  249. /*--------------------------------------------------------- */
  250. void konf_tree__set_seq_num(konf_tree_t * this, unsigned short seq_num)
  251. {
  252. this->seq_num = seq_num;
  253. }