tree.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408
  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. unsigned short *sub = (unsigned short *)clientkey + 2;
  25. char *line = ((char *)clientkey + (3 * sizeof(unsigned short)));
  26. /* Priority check */
  27. if (this->priority != *pri)
  28. return (this->priority - *pri);
  29. /* Sequence check */
  30. if (this->seq_num != *seq)
  31. return (this->seq_num - *seq);
  32. /* Sub-sequence check */
  33. if (this->sub_num != *sub)
  34. return (this->sub_num - *sub);
  35. /* Line check */
  36. return lub_string_nocasecmp(this->line, line);
  37. }
  38. /*-------------------------------------------------------- */
  39. static void konf_tree_key(lub_bintree_key_t * key,
  40. unsigned short priority, unsigned short sequence,
  41. unsigned short subseq, const char *text)
  42. {
  43. unsigned short *pri = (unsigned short *)key;
  44. unsigned short *seq = (unsigned short *)key + 1;
  45. unsigned short *sub = (unsigned short *)key + 2;
  46. char *line = ((char *)key + (3 * sizeof(unsigned short)));
  47. /* fill out the opaque key */
  48. *pri = priority;
  49. *seq = sequence;
  50. *sub = subseq;
  51. strcpy(line, text);
  52. }
  53. /*-------------------------------------------------------- */
  54. void konf_tree_bt_getkey(const void *clientnode, lub_bintree_key_t * key)
  55. {
  56. const konf_tree_t *this = clientnode;
  57. konf_tree_key(key, this->priority, this->seq_num,
  58. this->sub_num, this->line);
  59. }
  60. /*---------------------------------------------------------
  61. * PRIVATE METHODS
  62. *--------------------------------------------------------- */
  63. static void
  64. konf_tree_init(konf_tree_t * this, const char *line, unsigned short priority)
  65. {
  66. /* set up defaults */
  67. this->line = lub_string_dup(line);
  68. this->priority = priority;
  69. this->seq_num = 0;
  70. this->sub_num = KONF_ENTRY_OK;
  71. this->splitter = BOOL_TRUE;
  72. this->depth = -1;
  73. /* Be a good binary tree citizen */
  74. lub_bintree_node_init(&this->bt_node);
  75. /* initialise the tree of commands for this conf */
  76. lub_bintree_init(&this->tree,
  77. konf_tree_bt_offset(),
  78. konf_tree_bt_compare, konf_tree_bt_getkey);
  79. }
  80. /*--------------------------------------------------------- */
  81. static void konf_tree_fini(konf_tree_t * this)
  82. {
  83. konf_tree_t *conf;
  84. /* delete each conf held by this conf */
  85. while ((conf = lub_bintree_findfirst(&this->tree))) {
  86. /* remove the conf from the tree */
  87. lub_bintree_remove(&this->tree, conf);
  88. /* release the instance */
  89. konf_tree_delete(conf);
  90. }
  91. /* free our memory */
  92. lub_string_free(this->line);
  93. this->line = NULL;
  94. }
  95. /*---------------------------------------------------------
  96. * PUBLIC META FUNCTIONS
  97. *--------------------------------------------------------- */
  98. size_t konf_tree_bt_offset(void)
  99. {
  100. return offsetof(konf_tree_t, bt_node);
  101. }
  102. /*--------------------------------------------------------- */
  103. konf_tree_t *konf_tree_new(const char *line, unsigned short priority)
  104. {
  105. konf_tree_t *this = malloc(sizeof(konf_tree_t));
  106. if (this) {
  107. konf_tree_init(this, line, priority);
  108. }
  109. return this;
  110. }
  111. /*---------------------------------------------------------
  112. * PUBLIC METHODS
  113. *--------------------------------------------------------- */
  114. void konf_tree_delete(konf_tree_t * this)
  115. {
  116. konf_tree_fini(this);
  117. free(this);
  118. }
  119. /*--------------------------------------------------------- */
  120. void konf_tree_fprintf(konf_tree_t * this, FILE * stream,
  121. const char *pattern, int top_depth,
  122. bool_t seq, unsigned char prev_pri_hi)
  123. {
  124. konf_tree_t *conf;
  125. lub_bintree_iterator_t iter;
  126. unsigned char pri = 0;
  127. regex_t regexp;
  128. if (this->line && (*(this->line) != '\0') &&
  129. (this->depth > top_depth)) {
  130. char *space = NULL;
  131. unsigned space_num = this->depth - top_depth - 1;
  132. if (space_num > 0) {
  133. space = malloc(space_num + 1);
  134. memset(space, ' ', space_num);
  135. space[space_num] = '\0';
  136. }
  137. if ((0 == this->depth) &&
  138. (this->splitter ||
  139. (konf_tree__get_priority_hi(this) != prev_pri_hi)))
  140. fprintf(stream, "!\n");
  141. fprintf(stream, "%s", space ? space : "");
  142. if (seq && (konf_tree__get_seq_num(this) != 0))
  143. fprintf(stream, "%u ", konf_tree__get_seq_num(this));
  144. fprintf(stream, "%s\n", this->line);
  145. free(space);
  146. }
  147. /* regexp compilation */
  148. if (pattern)
  149. regcomp(&regexp, pattern, REG_EXTENDED | REG_ICASE);
  150. /* iterate child elements */
  151. if (!(conf = lub_bintree_findfirst(&this->tree)))
  152. return;
  153. for(lub_bintree_iterator_init(&iter, &this->tree, conf);
  154. conf; conf = lub_bintree_iterator_next(&iter)) {
  155. if (pattern && (0 != regexec(&regexp, conf->line, 0, NULL, 0)))
  156. continue;
  157. konf_tree_fprintf(conf, stream, NULL, top_depth, seq, pri);
  158. pri = konf_tree__get_priority_hi(conf);
  159. }
  160. if (pattern)
  161. regfree(&regexp);
  162. }
  163. /*-------------------------------------------------------- */
  164. static int normalize_seq(konf_tree_t * this, unsigned short priority)
  165. {
  166. unsigned short cnt = 1;
  167. konf_tree_t *conf = NULL;
  168. lub_bintree_iterator_t iter;
  169. /* If tree is empty */
  170. if (!(conf = lub_bintree_findfirst(&this->tree)))
  171. return 0;
  172. /* Iterate and set dirty */
  173. lub_bintree_iterator_init(&iter, &this->tree, conf);
  174. do {
  175. unsigned short cur_pri = konf_tree__get_priority(conf);
  176. if (cur_pri < priority)
  177. continue;
  178. if (konf_tree__get_seq_num(conf) == 0)
  179. continue;
  180. if (cur_pri > priority)
  181. break;
  182. if (konf_tree__get_sub_num(conf) == KONF_ENTRY_OK)
  183. konf_tree__set_sub_num(conf, KONF_ENTRY_DIRTY);
  184. } while ((conf = lub_bintree_iterator_next(&iter)));
  185. /* Iterate and renum */
  186. conf = lub_bintree_findfirst(&this->tree);
  187. lub_bintree_iterator_init(&iter, &this->tree, conf);
  188. do {
  189. unsigned short cur_pri = konf_tree__get_priority(conf);
  190. if (cur_pri < priority)
  191. continue;
  192. if (konf_tree__get_seq_num(conf) == 0)
  193. continue;
  194. if (cur_pri > priority)
  195. break;
  196. if (konf_tree__get_sub_num(conf) == KONF_ENTRY_OK)
  197. continue;
  198. lub_bintree_remove(&this->tree, conf);
  199. konf_tree__set_sub_num(conf, KONF_ENTRY_OK);
  200. konf_tree__set_seq_num(conf, cnt++);
  201. lub_bintree_insert(&this->tree, conf);
  202. } while ((conf = lub_bintree_iterator_next(&iter)));
  203. return 0;
  204. }
  205. /*--------------------------------------------------------- */
  206. konf_tree_t *konf_tree_new_conf(konf_tree_t * this,
  207. const char *line, unsigned short priority,
  208. bool_t seq, unsigned short seq_num)
  209. {
  210. /* Allocate the memory for a new child element */
  211. konf_tree_t *newconf = konf_tree_new(line, priority);
  212. assert(newconf);
  213. /* Sequence */
  214. if (seq) {
  215. konf_tree__set_seq_num(newconf,
  216. seq_num ? seq_num : 0xffff);
  217. konf_tree__set_sub_num(newconf, KONF_ENTRY_NEW);
  218. }
  219. /* Insert it into the binary tree for this conf */
  220. if (-1 == lub_bintree_insert(&this->tree, newconf)) {
  221. /* inserting a duplicate command is bad */
  222. konf_tree_delete(newconf);
  223. newconf = NULL;
  224. }
  225. if (seq)
  226. normalize_seq(this, priority);
  227. return newconf;
  228. }
  229. /*--------------------------------------------------------- */
  230. konf_tree_t *konf_tree_find_conf(konf_tree_t * this,
  231. const char *line, unsigned short priority, unsigned short seq_num)
  232. {
  233. konf_tree_t *conf;
  234. lub_bintree_key_t key;
  235. lub_bintree_iterator_t iter;
  236. if ((0 != priority) && (0 != seq_num)) {
  237. konf_tree_key(&key, priority, seq_num,
  238. KONF_ENTRY_OK, line);
  239. return lub_bintree_find(&this->tree, &key);
  240. }
  241. /* If tree is empty */
  242. if (!(conf = lub_bintree_findfirst(&this->tree)))
  243. return NULL;
  244. /* Iterate non-empty tree */
  245. lub_bintree_iterator_init(&iter, &this->tree, conf);
  246. do {
  247. if (0 == lub_string_nocasecmp(conf->line, line))
  248. return conf;
  249. } while ((conf = lub_bintree_iterator_next(&iter)));
  250. return NULL;
  251. }
  252. /*--------------------------------------------------------- */
  253. int konf_tree_del_pattern(konf_tree_t *this,
  254. const char *pattern, unsigned short priority,
  255. bool_t seq, unsigned short seq_num)
  256. {
  257. konf_tree_t *conf;
  258. lub_bintree_iterator_t iter;
  259. regex_t regexp;
  260. int del_cnt = 0; /* how many strings were deleted */
  261. if (seq && (0 == priority))
  262. return -1;
  263. /* Is tree empty? */
  264. if (!(conf = lub_bintree_findfirst(&this->tree)))
  265. return 0;
  266. /* Compile regular expression */
  267. regcomp(&regexp, pattern, REG_EXTENDED | REG_ICASE);
  268. /* Iterate configuration tree */
  269. lub_bintree_iterator_init(&iter, &this->tree, conf);
  270. do {
  271. if (0 != regexec(&regexp, conf->line, 0, NULL, 0))
  272. continue;
  273. if ((0 != priority) &&
  274. (priority != conf->priority))
  275. continue;
  276. if (seq && (seq_num != 0) &&
  277. (seq_num != conf->seq_num))
  278. continue;
  279. if (seq && (0 == seq_num) && (0 == conf->seq_num))
  280. continue;
  281. lub_bintree_remove(&this->tree, conf);
  282. konf_tree_delete(conf);
  283. del_cnt++;
  284. } while ((conf = lub_bintree_iterator_next(&iter)));
  285. regfree(&regexp);
  286. if (seq && (del_cnt != 0))
  287. normalize_seq(this, priority);
  288. return 0;
  289. }
  290. /*--------------------------------------------------------- */
  291. unsigned short konf_tree__get_priority(const konf_tree_t * this)
  292. {
  293. return this->priority;
  294. }
  295. /*--------------------------------------------------------- */
  296. unsigned char konf_tree__get_priority_hi(const konf_tree_t * this)
  297. {
  298. return (unsigned char)(this->priority >> 8);
  299. }
  300. /*--------------------------------------------------------- */
  301. unsigned char konf_tree__get_priority_lo(const konf_tree_t * this)
  302. {
  303. return (unsigned char)(this->priority & 0xff);
  304. }
  305. /*--------------------------------------------------------- */
  306. bool_t konf_tree__get_splitter(const konf_tree_t * this)
  307. {
  308. return this->splitter;
  309. }
  310. /*--------------------------------------------------------- */
  311. void konf_tree__set_splitter(konf_tree_t *this, bool_t splitter)
  312. {
  313. this->splitter = splitter;
  314. }
  315. /*--------------------------------------------------------- */
  316. unsigned short konf_tree__get_seq_num(const konf_tree_t * this)
  317. {
  318. return this->seq_num;
  319. }
  320. /*--------------------------------------------------------- */
  321. void konf_tree__set_seq_num(konf_tree_t * this, unsigned short seq_num)
  322. {
  323. this->seq_num = seq_num;
  324. }
  325. /*--------------------------------------------------------- */
  326. unsigned short konf_tree__get_sub_num(const konf_tree_t * this)
  327. {
  328. return this->sub_num;
  329. }
  330. /*--------------------------------------------------------- */
  331. void konf_tree__set_sub_num(konf_tree_t * this, unsigned short sub_num)
  332. {
  333. this->sub_num = sub_num;
  334. }
  335. /*--------------------------------------------------------- */
  336. const char * konf_tree__get_line(const konf_tree_t * this)
  337. {
  338. return this->line;
  339. }
  340. /*--------------------------------------------------------- */
  341. void konf_tree__set_depth(konf_tree_t * this, int depth)
  342. {
  343. this->depth = depth;
  344. }
  345. /*--------------------------------------------------------- */
  346. int konf_tree__get_depth(const konf_tree_t * this)
  347. {
  348. return this->depth;
  349. }