1
0

tree.c 9.9 KB

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