1 /* libcomps - C alternative to yum.comps library
2 * Copyright (C) 2013 Jindrich Luza
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
17 * USA
18 */
19
20 #include "comps_objmradix.h"
21 #include "comps_set.h"
22 #include <stdio.h>
23
comps_objmrtree_data_destroy(COMPS_ObjMRTreeData * rtd)24 void comps_objmrtree_data_destroy(COMPS_ObjMRTreeData * rtd) {
25 free(rtd->key);
26 COMPS_OBJECT_DESTROY(rtd->data);
27 comps_hslist_destroy(&rtd->subnodes);
28 free(rtd);
29 }
30
comps_objmrtree_data_destroy_v(void * rtd)31 inline void comps_objmrtree_data_destroy_v(void * rtd) {
32 comps_objmrtree_data_destroy((COMPS_ObjMRTreeData*)rtd);
33 }
34
__comps_objmrtree_data_create(char * key,size_t keylen,COMPS_Object * data)35 static COMPS_ObjMRTreeData * __comps_objmrtree_data_create(char * key,
36 size_t keylen,
37 COMPS_Object *data) {
38
39 COMPS_ObjMRTreeData * rtd;
40 if ((rtd = malloc(sizeof(*rtd))) == NULL)
41 return NULL;
42 if ((rtd->key = malloc(sizeof(char) * (keylen+1))) == NULL) {
43 free(rtd);
44 return NULL;
45 }
46 memcpy(rtd->key, key, sizeof(char)*keylen);
47 rtd->key[keylen] = '\0';
48 rtd->is_leaf = 1;
49 rtd->data = COMPS_OBJECT_CREATE(COMPS_ObjList, NULL);
50 if (data)
51 comps_objlist_append_x(rtd->data, data);
52 rtd->subnodes = comps_hslist_create();
53 comps_hslist_init(rtd->subnodes, NULL,
54 NULL,
55 &comps_objmrtree_data_destroy_v);
56 return rtd;
57 }
58
comps_objmrtree_data_create(char * key,COMPS_Object * data)59 COMPS_ObjMRTreeData * comps_objmrtree_data_create(char *key, COMPS_Object *data){
60 COMPS_ObjMRTreeData * rtd;
61 rtd = __comps_objmrtree_data_create(key, strlen(key), data);
62 return rtd;
63 }
64
comps_objmrtree_data_create_n(char * key,unsigned keylen,void * data)65 COMPS_ObjMRTreeData * comps_objmrtree_data_create_n(char * key, unsigned keylen,
66 void * data) {
67 COMPS_ObjMRTreeData * rtd;
68 rtd = __comps_objmrtree_data_create(key, keylen, data);
69 return rtd;
70 }
comps_objmrtree_create(COMPS_ObjMRTree * rtree,COMPS_Object ** args)71 static void comps_objmrtree_create(COMPS_ObjMRTree *rtree, COMPS_Object **args){
72 (void)args;
73 rtree->subnodes = comps_hslist_create();
74 comps_hslist_init(rtree->subnodes, NULL, NULL, &comps_objmrtree_data_destroy_v);
75 if (rtree->subnodes == NULL) {
76 COMPS_OBJECT_DESTROY(rtree);
77 return;
78 }
79 rtree->len = 0;
80 }
comps_objmrtree_create_u(COMPS_Object * obj,COMPS_Object ** args)81 void comps_objmrtree_create_u(COMPS_Object * obj, COMPS_Object **args) {
82 (void)args;
83 comps_objmrtree_create((COMPS_ObjMRTree*)obj, NULL);
84 }
85
comps_objmrtree_destroy(COMPS_ObjMRTree * rt)86 static void comps_objmrtree_destroy(COMPS_ObjMRTree * rt) {
87 comps_hslist_destroy(&(rt->subnodes));
88 }
comps_objmrtree_destroy_u(COMPS_Object * obj)89 void comps_objmrtree_destroy_u(COMPS_Object *obj) {
90 comps_objmrtree_destroy((COMPS_ObjMRTree*)obj);
91 }
92
comps_objmrtree_values_walk(COMPS_ObjMRTree * rt,void * udata,void (* walk_f)(void *,void *))93 void comps_objmrtree_values_walk(COMPS_ObjMRTree * rt, void* udata,
94 void (*walk_f)(void*, void*)) {
95 COMPS_HSList *tmplist, *tmp_subnodes;
96 COMPS_HSListItem *it, *it2;
97 tmplist = comps_hslist_create();
98 comps_hslist_init(tmplist, NULL, NULL, NULL);
99 comps_hslist_append(tmplist, rt->subnodes, 0);
100 while (tmplist->first != NULL) {
101 it = tmplist->first;
102 comps_hslist_remove(tmplist, tmplist->first);
103 tmp_subnodes = (COMPS_HSList*)it->data;
104 free(it);
105 for (it = tmp_subnodes->first; it != NULL; it=it->next) {
106 if (((COMPS_ObjMRTreeData*)it->data)->subnodes->first) {
107 comps_hslist_append(tmplist,
108 ((COMPS_ObjMRTreeData*)it->data)->subnodes, 0);
109 }
110 for (it2 = (COMPS_HSListItem*)((COMPS_ObjMRTreeData*)it->data)->data->first;
111 it2 != NULL; it2 = it2->next) {
112 walk_f(udata, it2->data);
113 }
114 }
115 }
116 comps_hslist_destroy(&tmplist);
117 }
118
comps_objmrtree_copy(COMPS_ObjMRTree * ret,COMPS_ObjMRTree * rt)119 void comps_objmrtree_copy(COMPS_ObjMRTree *ret, COMPS_ObjMRTree *rt){
120 COMPS_HSList * to_clone, *tmplist, *new_subnodes;
121 COMPS_HSListItem *it, *it2;
122 COMPS_ObjMRTreeData *rtdata;
123 COMPS_ObjList *new_data_list;
124
125 to_clone = comps_hslist_create();
126 comps_hslist_init(to_clone, NULL, NULL, NULL);
127
128 for (it = rt->subnodes->first; it != NULL; it = it->next) {
129 rtdata = comps_objmrtree_data_create(
130 ((COMPS_ObjMRTreeData*)it->data)->key,
131 NULL);
132 new_data_list = (COMPS_ObjList*)
133 COMPS_OBJECT_COPY(((COMPS_ObjMRTreeData*)it->data)->data);
134 COMPS_OBJECT_DESTROY(&rtdata->data);
135 comps_hslist_destroy(&rtdata->subnodes);
136 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
137 rtdata->data = new_data_list;
138 comps_hslist_append(ret->subnodes, rtdata, 0);
139
140 comps_hslist_append(to_clone, rtdata, 0);
141 }
142
143 while (to_clone->first) {
144 it2 = to_clone->first;
145 tmplist = ((COMPS_ObjMRTreeData*)it2->data)->subnodes;
146 comps_hslist_remove(to_clone, to_clone->first);
147
148 new_subnodes = comps_hslist_create();
149 comps_hslist_init(new_subnodes, NULL, NULL, &comps_objmrtree_data_destroy_v);
150 for (it = tmplist->first; it != NULL; it = it->next) {
151 rtdata = comps_objmrtree_data_create(
152 ((COMPS_ObjMRTreeData*)it->data)->key,
153 NULL);
154 new_data_list = (COMPS_ObjList*)
155 COMPS_OBJECT_COPY(((COMPS_ObjMRTreeData*)it->data)->data);
156
157 comps_hslist_destroy(&rtdata->subnodes);
158 COMPS_OBJECT_DESTROY(rtdata->data);
159 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
160 rtdata->data = new_data_list;
161 comps_hslist_append(new_subnodes, rtdata, 0);
162
163 comps_hslist_append(to_clone, rtdata, 0);
164 }
165 ((COMPS_ObjMRTreeData*)it2->data)->subnodes = new_subnodes;
166 free(it2);
167 }
168 ret->len = rt->len;
169 comps_hslist_destroy(&to_clone);
170 }
COMPS_COPY_u(objmrtree,COMPS_ObjMRTree)171 COMPS_COPY_u(objmrtree, COMPS_ObjMRTree) /*comps_utils.h macro*/
172
173 void comps_objmrtree_copy_shallow(COMPS_ObjMRTree *ret, COMPS_ObjMRTree *rt){
174 COMPS_HSList * to_clone, *tmplist, *new_subnodes;
175 COMPS_HSListItem *it, *it2;
176 COMPS_ObjMRTreeData *rtdata;
177 COMPS_ObjList *new_data_list;
178
179 to_clone = comps_hslist_create();
180 comps_hslist_init(to_clone, NULL, NULL, NULL);
181
182 for (it = rt->subnodes->first; it != NULL; it = it->next) {
183 rtdata = comps_objmrtree_data_create(
184 ((COMPS_ObjMRTreeData*)it->data)->key,
185 NULL);
186 new_data_list = (COMPS_ObjList*)
187 COMPS_OBJECT_COPY(((COMPS_ObjMRTreeData*)it->data)->data);
188 COMPS_OBJECT_DESTROY(&rtdata->data);
189 comps_hslist_destroy(&rtdata->subnodes);
190 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
191 rtdata->data = new_data_list;
192 comps_hslist_append(ret->subnodes, rtdata, 0);
193
194 comps_hslist_append(to_clone, rtdata, 0);
195 }
196
197 while (to_clone->first) {
198 it2 = to_clone->first;
199 tmplist = ((COMPS_ObjMRTreeData*)it2->data)->subnodes;
200 comps_hslist_remove(to_clone, to_clone->first);
201
202 new_subnodes = comps_hslist_create();
203 comps_hslist_init(new_subnodes, NULL, NULL, &comps_objmrtree_data_destroy_v);
204 for (it = tmplist->first; it != NULL; it = it->next) {
205 rtdata = comps_objmrtree_data_create(
206 ((COMPS_ObjMRTreeData*)it->data)->key,
207 NULL);
208 new_data_list = ((COMPS_ObjMRTreeData*)it->data)->data;
209
210 comps_hslist_destroy(&rtdata->subnodes);
211 COMPS_OBJECT_DESTROY(rtdata->data);
212 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
213 rtdata->data = new_data_list;
214 comps_hslist_append(new_subnodes, rtdata, 0);
215
216 comps_hslist_append(to_clone, rtdata, 0);
217 }
218 ((COMPS_ObjMRTreeData*)it2->data)->subnodes = new_subnodes;
219 free(it2);
220 }
221 ret->len = rt->len;
222 comps_hslist_destroy(&to_clone);
223 }
224
comps_objmrtree_clone(COMPS_ObjMRTree * rt)225 COMPS_ObjMRTree * comps_objmrtree_clone(COMPS_ObjMRTree * rt) {
226 COMPS_HSList * to_clone, *tmplist, *new_subnodes;
227 COMPS_ObjMRTree * ret;
228 COMPS_HSListItem *it, *it2;
229 COMPS_ObjMRTreeData *rtdata;
230 COMPS_ObjList *new_data_list;
231
232 to_clone = comps_hslist_create();
233 comps_hslist_init(to_clone, NULL, NULL, NULL);
234 ret = COMPS_OBJECT_CREATE(COMPS_ObjMRTree, NULL);
235
236 for (it = rt->subnodes->first; it != NULL; it = it->next) {
237 rtdata = comps_objmrtree_data_create(
238 ((COMPS_ObjMRTreeData*)it->data)->key,
239 NULL);
240 new_data_list = (COMPS_ObjList*)
241 COMPS_OBJECT_COPY(((COMPS_ObjMRTreeData*)it->data)->data);
242 COMPS_OBJECT_DESTROY(&rtdata->data);
243 comps_hslist_destroy(&rtdata->subnodes);
244 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
245 rtdata->data = new_data_list;
246 comps_hslist_append(ret->subnodes, rtdata, 0);
247
248 comps_hslist_append(to_clone, rtdata, 0);
249 }
250
251 while (to_clone->first) {
252 it2 = to_clone->first;
253 tmplist = ((COMPS_ObjMRTreeData*)it2->data)->subnodes;
254 comps_hslist_remove(to_clone, to_clone->first);
255
256 new_subnodes = comps_hslist_create();
257 comps_hslist_init(new_subnodes, NULL, NULL, &comps_objmrtree_data_destroy_v);
258 for (it = tmplist->first; it != NULL; it = it->next) {
259 rtdata = comps_objmrtree_data_create(
260 ((COMPS_ObjMRTreeData*)it->data)->key,
261 NULL);
262 new_data_list = (COMPS_ObjList*)
263 COMPS_OBJECT_COPY(((COMPS_ObjMRTreeData*)it->data)->data);
264
265 comps_hslist_destroy(&rtdata->subnodes);
266 COMPS_OBJECT_DESTROY(rtdata->data);
267 rtdata->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
268 rtdata->data = new_data_list;
269 comps_hslist_append(new_subnodes, rtdata, 0);
270
271 comps_hslist_append(to_clone, rtdata, 0);
272 }
273 ((COMPS_ObjMRTreeData*)it2->data)->subnodes = new_subnodes;
274 free(it2);
275 }
276 ret->len = rt->len;
277 comps_hslist_destroy(&to_clone);
278 return ret;
279 }
280
comps_objmrtree_unite(COMPS_ObjMRTree * rt1,COMPS_ObjMRTree * rt2)281 void comps_objmrtree_unite(COMPS_ObjMRTree *rt1, COMPS_ObjMRTree *rt2) {
282 COMPS_HSList *tmplist, *tmp_subnodes;
283 COMPS_HSListItem *it;
284 COMPS_ObjListIt *it2;
285 struct Pair {
286 COMPS_HSList * subnodes;
287 char * key;
288 } *pair, *parent_pair;
289
290 pair = malloc(sizeof(struct Pair));
291 pair->subnodes = rt2->subnodes;
292 pair->key = NULL;
293
294 tmplist = comps_hslist_create();
295 comps_hslist_init(tmplist, NULL, NULL, &free);
296 comps_hslist_append(tmplist, pair, 0);
297
298 while (tmplist->first != NULL) {
299 it = tmplist->first;
300 comps_hslist_remove(tmplist, tmplist->first);
301 tmp_subnodes = ((struct Pair*)it->data)->subnodes;
302 parent_pair = (struct Pair*) it->data;
303 free(it);
304
305 for (it = tmp_subnodes->first; it != NULL; it=it->next) {
306 pair = malloc(sizeof(struct Pair));
307 pair->subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
308
309 if (parent_pair->key != NULL) {
310 pair->key =
311 malloc(sizeof(char)
312 * (strlen(((COMPS_ObjMRTreeData*)it->data)->key)
313 + strlen(parent_pair->key) + 1));
314 memcpy(pair->key, parent_pair->key,
315 sizeof(char) * strlen(parent_pair->key));
316 memcpy(pair->key+strlen(parent_pair->key),
317 ((COMPS_ObjMRTreeData*)it->data)->key,
318 sizeof(char)*(strlen(((COMPS_ObjMRTreeData*)it->data)->key)+1));
319 } else {
320 pair->key = malloc(sizeof(char)*
321 (strlen(((COMPS_ObjMRTreeData*)it->data)->key) +
322 1));
323 memcpy(pair->key, ((COMPS_ObjMRTreeData*)it->data)->key,
324 sizeof(char)*(strlen(((COMPS_ObjMRTreeData*)it->data)->key)+1));
325 }
326 /* current node has data */
327 if (((COMPS_ObjMRTreeData*)it->data)->data->first != NULL) {
328 for (it2 = ((COMPS_ObjMRTreeData*)it->data)->data->first;
329 it2 != NULL; it2 = it2->next) {
330 comps_objmrtree_set(rt1, pair->key, it2->comps_obj);
331 }
332
333 if (((COMPS_ObjMRTreeData*)it->data)->subnodes->first) {
334 comps_hslist_append(tmplist, pair, 0);
335 } else {
336 free(pair->key);
337 free(pair);
338 }
339 /* current node hasn't data */
340 } else {
341 if (((COMPS_ObjMRTreeData*)it->data)->subnodes->first) {
342 comps_hslist_append(tmplist, pair, 0);
343 } else {
344 free(pair->key);
345 free(pair);
346 }
347 }
348 }
349 free(parent_pair->key);
350 free(parent_pair);
351 }
352 comps_hslist_destroy(&tmplist);
353 }
354
comps_objmrtree_set_x(COMPS_ObjMRTree * rt,char * key,COMPS_Object * data)355 void comps_objmrtree_set_x(COMPS_ObjMRTree *rt, char *key, COMPS_Object *data) {
356 __comps_objmrtree_set(rt, key, strlen(key), data);
357 }
comps_objmrtree_set(COMPS_ObjMRTree * rt,char * key,COMPS_Object * data)358 void comps_objmrtree_set(COMPS_ObjMRTree *rt, char *key, COMPS_Object *data) {
359 __comps_objmrtree_set(rt, key, strlen(key), comps_object_incref(data));
360 }
361
__comps_objmrtree_set(COMPS_ObjMRTree * rt,char * key,size_t len,COMPS_Object * ndata)362 void __comps_objmrtree_set(COMPS_ObjMRTree *rt, char *key,
363 size_t len, COMPS_Object *ndata) {
364 static COMPS_HSListItem *it;
365 COMPS_HSList *subnodes;
366 COMPS_ObjMRTreeData *rtd;
367 static COMPS_ObjMRTreeData *rtdata;
368
369 size_t _len, offset=0;
370 unsigned x, found = 0;
371 char ended;//, tmpch;
372
373 if (rt->subnodes == NULL)
374 return;
375
376 subnodes = rt->subnodes;
377 while (offset != len)
378 {
379 found = 0;
380 for (it = subnodes->first; it != NULL; it = it->next) {
381 if (((COMPS_ObjMRTreeData*)it->data)->key[0] == key[offset]) {
382 found = 1;
383 break;
384 }
385 }
386 if (!found) { // not found in subnodes; create new subnode
387 rtd = comps_objmrtree_data_create(key+offset, ndata);
388 comps_hslist_append(subnodes, rtd, 0);
389 rt->len++;
390 return;
391 } else {
392 rtdata = (COMPS_ObjMRTreeData*)it->data;
393 ended = 0;
394 for (x=1; ;x++) {
395 if (rtdata->key[x] == 0) ended += 1;
396 if (x == len - offset) ended += 2;
397 if (ended != 0) break;
398 if (key[offset+x] != rtdata->key[x]) break;
399 }
400 if (ended == 3) { //keys equals; append new data
401 comps_objlist_append_x(rtdata->data, ndata);
402 rt->len++;
403 return;
404 } else if (ended == 2) { //global key ends first; make global leaf
405 comps_hslist_remove(subnodes, it);
406 it->next = NULL;
407 rtd = comps_objmrtree_data_create(key+offset, ndata);
408 comps_hslist_append(subnodes, rtd, 0);
409 ((COMPS_ObjMRTreeData*)subnodes->last->data)->subnodes->last = it;
410 ((COMPS_ObjMRTreeData*)subnodes->last->data)->subnodes->first = it;
411 _len = strlen(key + offset);
412 memmove(rtdata->key,rtdata->key + _len,
413 strlen(rtdata->key) - _len);
414 rtdata->key[strlen(rtdata->key) - _len] = 0;
415 rtdata->key = realloc(rtdata->key,
416 sizeof(char)* (strlen(rtdata->key)+1));
417 rt->len++;
418 return;
419 } else if (ended == 1) { //local key ends first; go deeper
420 subnodes = rtdata->subnodes;
421 offset += x;
422 } else { /* keys differ */
423 COMPS_ObjList *tmpdata = rtdata->data;
424 COMPS_HSList *tmphslist = rtdata->subnodes;
425
426 rtdata->subnodes = comps_hslist_create();
427 comps_hslist_init(rtdata->subnodes, NULL, NULL,
428 &comps_objmrtree_data_destroy_v);
429 int cmpret = strcmp(key+offset+x, rtdata->key+x);
430 rtdata->data = COMPS_OBJECT_CREATE(COMPS_ObjList, NULL);
431
432 if (cmpret > 0) {
433 rtd = comps_objmrtree_data_create(rtdata->key+x,
434 (COMPS_Object*)tmpdata);
435 comps_hslist_destroy(&rtd->subnodes);
436 rtd->subnodes = tmphslist;
437
438 comps_hslist_append(rtdata->subnodes, rtd, 0);
439 rtd = comps_objmrtree_data_create(key+offset+x,
440 (COMPS_Object*)ndata);
441 comps_hslist_append(rtdata->subnodes, rtd, 0);
442
443 } else {
444 rtd = comps_objmrtree_data_create(key+offset+x,
445 (COMPS_Object*)ndata);
446 comps_hslist_append(rtdata->subnodes, rtd, 0);
447 rtd = comps_objmrtree_data_create(rtdata->key+x,
448 (COMPS_Object*)tmpdata);
449 comps_hslist_destroy(&rtd->subnodes);
450 rtd->subnodes = tmphslist;
451 comps_hslist_append(rtdata->subnodes, rtd, 0);
452 }
453 rtdata->key = realloc(rtdata->key, sizeof(char)*(x+1));
454 rtdata->key[x] = 0;
455 rt->len++;
456 return;
457 }
458 }
459 }
460 }
461
comps_objmrtree_set_n(COMPS_ObjMRTree * rt,char * key,size_t len,void * ndata)462 void comps_objmrtree_set_n(COMPS_ObjMRTree *rt, char *key,
463 size_t len, void *ndata) {
464 __comps_objmrtree_set(rt, key, len, ndata);
465 }
466
comps_objmrtree_get(COMPS_ObjMRTree * rt,const char * key)467 COMPS_ObjList * comps_objmrtree_get(COMPS_ObjMRTree * rt, const char * key) {
468 COMPS_HSList * subnodes;
469 COMPS_HSListItem * it = NULL;
470 COMPS_ObjMRTreeData * rtdata;
471 unsigned int offset, len, x;
472 char found, ended;
473
474 len = strlen(key);
475 offset = 0;
476 subnodes = rt->subnodes;
477 while (offset != len) {
478 found = 0;
479 for (it = subnodes->first; it != NULL; it=it->next) {
480 if (((COMPS_ObjMRTreeData*)it->data)->key[0] == key[offset]) {
481 found = 1;
482 break;
483 }
484 }
485 if (!found)
486 return NULL;
487 rtdata = (COMPS_ObjMRTreeData*)it->data;
488
489 for (x=1; ;x++) {
490 ended=0;
491 if (rtdata->key[x] == 0) ended += 1;
492 if (x == len - offset) ended += 2;
493 if (ended != 0) break;
494 if (key[offset+x] != rtdata->key[x]) break;
495 }
496 if (ended == 3) return (COMPS_ObjList*)
497 comps_object_incref((COMPS_Object*)rtdata->data);
498 else if (ended == 1) offset+=x;
499 else return NULL;
500 subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
501 }
502 if (it)
503 return ((COMPS_ObjMRTreeData*)it->data)->data;
504 else return NULL;
505 }
506
comps_objmrtree_unset(COMPS_ObjMRTree * rt,const char * key)507 void comps_objmrtree_unset(COMPS_ObjMRTree * rt, const char * key) {
508 COMPS_HSList * subnodes;
509 COMPS_HSListItem * it;
510 COMPS_ObjMRTreeData * rtdata;
511 unsigned int offset, len, x;
512 char found, ended;
513 COMPS_HSList * path;
514
515 struct Relation {
516 COMPS_HSList * parent_nodes;
517 COMPS_HSListItem * child_it;
518 } *relation;
519
520 path = comps_hslist_create();
521 comps_hslist_init(path, NULL, NULL, &free);
522
523 len = strlen(key);
524 offset = 0;
525 subnodes = rt->subnodes;
526 while (offset != len) {
527 found = 0;
528 for (it = subnodes->first; it != NULL; it=it->next) {
529 if (((COMPS_ObjMRTreeData*)it->data)->key[0] == key[offset]) {
530 found = 1;
531 break;
532 }
533 }
534 if (!found) {
535 comps_hslist_destroy(&path);
536 return;
537 }
538 rtdata = (COMPS_ObjMRTreeData*)it->data;
539
540 for (x=1; ;x++) {
541 ended=0;
542 if (rtdata->key[x] == 0) ended += 1;
543 if (x == len - offset) ended += 2;
544 if (ended != 0) break;
545 if (key[offset+x] != rtdata->key[x]) break;
546 }
547 if (ended == 3) {
548 /* remove node from tree only if there's no descendant*/
549 if (rtdata->subnodes->last == NULL) {
550 comps_hslist_remove(subnodes, it);
551 rt->len -= rtdata->data->len;
552 comps_objmrtree_data_destroy(rtdata);
553 free(it);
554 }
555 else {
556 rt->len -= rtdata->data->len;
557 comps_objlist_clear(rtdata->data);
558 rtdata->is_leaf = 0;
559 }
560
561 if (path->last == NULL) {
562 comps_hslist_destroy(&path);
563 return;
564 }
565 rtdata = (COMPS_ObjMRTreeData*)
566 ((struct Relation*)path->last->data)->child_it->data;
567
568 /*remove all predecessor of deleted node (recursive) with no childs*/
569 while (rtdata->subnodes->last == NULL) {
570 //printf("removing '%s'\n", rtdata->key);
571 comps_objmrtree_data_destroy(rtdata);
572 comps_hslist_remove(
573 ((struct Relation*)path->last->data)->parent_nodes,
574 ((struct Relation*)path->last->data)->child_it);
575 free(((struct Relation*)path->last->data)->child_it);
576 it = path->last;
577 comps_hslist_remove(path, path->last);
578 free(it);
579 rtdata = (COMPS_ObjMRTreeData*)
580 ((struct Relation*)path->last->data)->child_it->data;
581 }
582 comps_hslist_destroy(&path);
583 return;
584 }
585 else if (ended == 1) offset+=x;
586 else {
587 comps_hslist_destroy(&path);
588 return;
589 }
590 if ((relation = malloc(sizeof(struct Relation))) == NULL) {
591 comps_hslist_destroy(&path);
592 return;
593 }
594 subnodes = ((COMPS_ObjMRTreeData*)it->data)->subnodes;
595 relation->parent_nodes = subnodes;
596 relation->child_it = it;
597 comps_hslist_append(path, (void*)relation, 0);
598 }
599 comps_hslist_destroy(&path);
600 return;
601 }
602
comps_objmrtree_pair_destroy_v(void * pair)603 inline void comps_objmrtree_pair_destroy_v(void * pair) {
604 free(((COMPS_ObjMRTreePair *)pair)->key);
605 free(pair);
606 }
607
__comps_objmrtree_all(COMPS_ObjMRTree * rt,char keyvalpair)608 static inline COMPS_HSList* __comps_objmrtree_all(COMPS_ObjMRTree * rt, char keyvalpair) {
609 COMPS_HSList *to_process, *ret;
610 COMPS_HSListItem *hsit, *oldit;
611 size_t x;
612 struct Pair {
613 char *key;
614 void *data;
615 COMPS_HSList *subnodes;
616 } *pair, *current_pair=NULL;//, *oldpair=NULL;
617 COMPS_ObjMRTreePair *rtpair;
618
619 to_process = comps_hslist_create();
620 comps_hslist_init(to_process, NULL, NULL, &free);
621
622 ret = comps_hslist_create();
623 if (keyvalpair == 0)
624 comps_hslist_init(ret, NULL, NULL, &free);
625 else if (keyvalpair == 1)
626 comps_hslist_init(ret, NULL, NULL, NULL);
627 else
628 comps_hslist_init(ret, NULL, NULL, &comps_objmrtree_pair_destroy_v);
629
630 for (hsit = rt->subnodes->first; hsit != NULL; hsit = hsit->next) {
631 pair = malloc(sizeof(struct Pair));
632 pair->key = __comps_strcpy(((COMPS_ObjMRTreeData*)hsit->data)->key);
633 pair->data = ((COMPS_ObjMRTreeData*)hsit->data)->data;
634 pair->subnodes = ((COMPS_ObjMRTreeData*)hsit->data)->subnodes;
635 comps_hslist_append(to_process, pair, 0);
636 }
637 while (to_process->first) {
638 //oldpair = current_pair;
639 current_pair = to_process->first->data;
640 oldit = to_process->first;
641 comps_hslist_remove(to_process, to_process->first);
642 if (current_pair->data) {
643 if (keyvalpair == 0) {
644 comps_hslist_append(ret, __comps_strcpy(current_pair->key), 0);
645 } else if (keyvalpair == 1) {
646 comps_hslist_append(ret, current_pair->data, 0);
647 } else {
648 rtpair = malloc(sizeof(COMPS_ObjMRTreePair));
649 rtpair->key = __comps_strcpy(current_pair->key);
650 rtpair->data = current_pair->data;
651 comps_hslist_append(ret, rtpair, 0);
652 }
653 }
654 for (hsit = current_pair->subnodes->first, x = 0;
655 hsit != NULL; hsit = hsit->next, x++) {
656 pair = malloc(sizeof(struct Pair));
657 pair->key = __comps_strcat(current_pair->key,
658 ((COMPS_ObjMRTreeData*)hsit->data)->key);
659 pair->data = ((COMPS_ObjMRTreeData*)hsit->data)->data;
660 pair->subnodes = ((COMPS_ObjMRTreeData*)hsit->data)->subnodes;
661 comps_hslist_insert_at(to_process, x, pair, 0);
662 }
663 free(current_pair->key);
664 free(current_pair);
665 free(oldit);
666 }
667
668 comps_hslist_destroy(&to_process);
669 return ret;
670 }
671
comps_objmrtree_keys(COMPS_ObjMRTree * rt)672 COMPS_HSList* comps_objmrtree_keys(COMPS_ObjMRTree * rt) {
673 return __comps_objmrtree_all(rt, 0);
674 }
675
comps_objmrtree_values(COMPS_ObjMRTree * rt)676 COMPS_HSList* comps_objmrtree_values(COMPS_ObjMRTree * rt) {
677 return __comps_objmrtree_all(rt, 1);
678 }
679
comps_objmrtree_pairs(COMPS_ObjMRTree * rt)680 COMPS_HSList* comps_objmrtree_pairs(COMPS_ObjMRTree * rt) {
681 return __comps_objmrtree_all(rt, 2);
682 }
683
comps_objmrtree_clear(COMPS_ObjMRTree * rt)684 void comps_objmrtree_clear(COMPS_ObjMRTree * rt) {
685 COMPS_HSListItem *it, *oldit;
686 if (rt == NULL) return;
687 if (rt->subnodes == NULL) return;
688 oldit = rt->subnodes->first;
689 it = (oldit)?oldit->next:NULL;
690 for (;it != NULL; it=it->next) {
691 if (rt->subnodes->data_destructor != NULL)
692 rt->subnodes->data_destructor(oldit->data);
693 free(oldit);
694 oldit = it;
695 }
696 if (oldit) {
697 if (rt->subnodes->data_destructor != NULL)
698 rt->subnodes->data_destructor(oldit->data);
699 free(oldit);
700 }
701 }
702
comps_objmrtree_paircmp(void * obj1,void * obj2)703 char comps_objmrtree_paircmp(void *obj1, void *obj2) {
704 if (strcmp(((COMPS_ObjMRTreePair*)obj1)->key,
705 ((COMPS_ObjMRTreePair*)obj2)->key) != 0)
706 return 0;
707 return comps_object_cmp((COMPS_Object*)((COMPS_ObjMRTreePair*)obj1)->data,
708 (COMPS_Object*)((COMPS_ObjMRTreePair*)obj1)->data);
709 }
710
comps_objmrtree_cmp(COMPS_ObjMRTree * ort1,COMPS_ObjMRTree * ort2)711 signed char comps_objmrtree_cmp(COMPS_ObjMRTree *ort1, COMPS_ObjMRTree *ort2) {
712 COMPS_HSList *values1, *values2;
713 COMPS_HSListItem *it;
714 COMPS_Set *set1, *set2;
715 signed char ret;
716 values1 = comps_objmrtree_pairs(ort1);
717 values2 = comps_objmrtree_pairs(ort2);
718 set1 = comps_set_create();
719 comps_set_init(set1, NULL, NULL, NULL, &comps_objmrtree_paircmp);
720 set2 = comps_set_create();
721 comps_set_init(set2, NULL, NULL, NULL, &comps_objmrtree_paircmp);
722 for (it = values1->first; it != NULL; it = it->next) {
723 comps_set_add(set1, it->data);
724 }
725 for (it = values2->first; it != NULL; it = it->next) {
726 comps_set_add(set2, it->data);
727 }
728
729 ret = comps_set_cmp(set1, set2);
730 comps_set_destroy(&set1);
731 comps_set_destroy(&set2);
732 //printf("objmrtree cmp %d\n", !ret);
733
734 comps_hslist_destroy(&values1);
735 comps_hslist_destroy(&values2);
736 return !ret;
737 }
738 COMPS_CMP_u(objmrtree, COMPS_ObjMRTree)
739
740 COMPS_ObjectInfo COMPS_ObjMRTree_ObjInfo = {
741 .obj_size = sizeof(COMPS_ObjMRTree),
742 .constructor = &comps_objmrtree_create_u,
743 .destructor = &comps_objmrtree_destroy_u,
744 .copy = &comps_objmrtree_copy_u,
745 .obj_cmp = &comps_objmrtree_cmp_u
746 };
747