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_objradix.h"
21 #include "comps_set.h"
22 #include <stdio.h>
23 
comps_objrtree_data_destroy(COMPS_ObjRTreeData * rtd)24 void comps_objrtree_data_destroy(COMPS_ObjRTreeData * rtd) {
25     free(rtd->key);
26     comps_object_destroy(rtd->data);
27     comps_hslist_destroy(&rtd->subnodes);
28     free(rtd);
29 }
30 
comps_objrtree_data_destroy_v(void * rtd)31 inline void comps_objrtree_data_destroy_v(void * rtd) {
32     comps_objrtree_data_destroy((COMPS_ObjRTreeData*)rtd);
33 }
34 
__comps_objrtree_data_create(char * key,size_t keylen,COMPS_Object * data)35 inline COMPS_ObjRTreeData * __comps_objrtree_data_create(char *key,
36                                                    size_t keylen,
37                                                    COMPS_Object *data){
38     COMPS_ObjRTreeData * rtd;
39     if ((rtd = malloc(sizeof(*rtd))) == NULL)
40         return NULL;
41     if ((rtd->key = malloc(sizeof(char) * (keylen+1))) == NULL) {
42         free(rtd);
43         return NULL;
44     }
45     memcpy(rtd->key, key, sizeof(char)*keylen);
46     rtd->key[keylen] = 0;
47     rtd->data = data;
48     if (data != NULL) {
49         rtd->is_leaf = 1;
50     }
51     rtd->subnodes = comps_hslist_create();
52     comps_hslist_init(rtd->subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
53     return rtd;
54 }
55 
comps_objrtree_data_create(char * key,COMPS_Object * data)56 COMPS_ObjRTreeData * comps_objrtree_data_create(char *key, COMPS_Object *data) {
57     COMPS_ObjRTreeData * rtd;
58     rtd = __comps_objrtree_data_create(key, strlen(key), data);
59     return rtd;
60 }
61 
comps_objrtree_data_create_n(char * key,size_t keylen,COMPS_Object * data)62 COMPS_ObjRTreeData * comps_objrtree_data_create_n(char *key, size_t keylen,
63                                                   COMPS_Object *data) {
64     COMPS_ObjRTreeData * rtd;
65     rtd = __comps_objrtree_data_create(key, keylen, data);
66     return rtd;
67 }
68 
comps_objrtree_create(COMPS_ObjRTree * rtree,COMPS_Object ** args)69 static void comps_objrtree_create(COMPS_ObjRTree *rtree, COMPS_Object **args) {
70     (void)args;
71     rtree->subnodes = comps_hslist_create();
72     comps_hslist_init(rtree->subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
73     if (rtree->subnodes == NULL) {
74         COMPS_OBJECT_DESTROY(rtree);
75         return;
76     }
77     rtree->len = 0;
78 }
comps_objrtree_create_u(COMPS_Object * obj,COMPS_Object ** args)79 void comps_objrtree_create_u(COMPS_Object * obj, COMPS_Object **args) {
80     (void)args;
81     comps_objrtree_create((COMPS_ObjRTree*)obj, NULL);
82 }
83 
comps_objrtree_destroy(COMPS_ObjRTree * rt)84 static void comps_objrtree_destroy(COMPS_ObjRTree * rt) {
85     comps_hslist_destroy(&(rt->subnodes));
86 }
comps_objrtree_destroy_u(COMPS_Object * obj)87 void comps_objrtree_destroy_u(COMPS_Object *obj) {
88     comps_objrtree_destroy((COMPS_ObjRTree*)obj);
89 }
90 
comps_objrtree_clone(COMPS_ObjRTree * rt)91 COMPS_ObjRTree * comps_objrtree_clone(COMPS_ObjRTree *rt) {
92 
93     COMPS_HSList *to_clone, *tmplist, *new_subnodes;
94     COMPS_ObjRTree *ret;
95     COMPS_HSListItem *it, *it2;
96     COMPS_ObjRTreeData *rtdata;
97     COMPS_Object *new_data;
98 
99     if (!rt) return NULL;
100 
101     to_clone = comps_hslist_create();
102     comps_hslist_init(to_clone, NULL, NULL, NULL);
103     ret = COMPS_OBJECT_CREATE(COMPS_ObjRTree, NULL);
104     ret->len = rt->len;
105 
106     for (it = rt->subnodes->first; it != NULL; it = it->next) {
107         rtdata = comps_objrtree_data_create(
108                                     ((COMPS_ObjRTreeData*)it->data)->key, NULL);
109         if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
110             new_data = comps_object_copy(((COMPS_ObjRTreeData*)it->data)->data);
111         else
112             new_data = NULL;
113         comps_hslist_destroy(&rtdata->subnodes);
114         rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
115         rtdata->data = new_data;
116         comps_hslist_append(ret->subnodes, rtdata, 0);
117         comps_hslist_append(to_clone, rtdata, 0);
118     }
119 
120     while (to_clone->first) {
121         it2 = to_clone->first;
122         tmplist = ((COMPS_ObjRTreeData*)it2->data)->subnodes;
123         comps_hslist_remove(to_clone, to_clone->first);
124 
125         new_subnodes = comps_hslist_create();
126         comps_hslist_init(new_subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
127         for (it = tmplist->first; it != NULL; it = it->next) {
128             rtdata = comps_objrtree_data_create(
129                                       ((COMPS_ObjRTreeData*)it->data)->key, NULL);
130             if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
131                 new_data = comps_object_copy(((COMPS_ObjRTreeData*)it->data)->data);
132             else
133                 new_data = NULL;
134             comps_hslist_destroy(&rtdata->subnodes);
135             rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
136             rtdata->data = new_data;
137             comps_hslist_append(new_subnodes, rtdata, 0);
138             comps_hslist_append(to_clone, rtdata, 0);
139         }
140         ((COMPS_ObjRTreeData*)it2->data)->subnodes = new_subnodes;
141         free(it2);
142     }
143     comps_hslist_destroy(&to_clone);
144     return ret;
145 }
comps_objrtree_copy(COMPS_ObjRTree * rt1,COMPS_ObjRTree * rt2)146 void comps_objrtree_copy(COMPS_ObjRTree *rt1, COMPS_ObjRTree *rt2){
147     COMPS_HSList *to_clone, *tmplist, *new_subnodes;
148     COMPS_HSListItem *it, *it2;
149     COMPS_ObjRTreeData *rtdata;
150     COMPS_Object *new_data;
151 
152     rt1->subnodes = comps_hslist_create();
153     comps_hslist_init(rt1->subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
154     if (rt1->subnodes == NULL) {
155         COMPS_OBJECT_DESTROY(rt1);
156         return;
157     }
158     rt1->len = 0;
159 
160     to_clone = comps_hslist_create();
161     comps_hslist_init(to_clone, NULL, NULL, NULL);
162 
163     for (it = rt2->subnodes->first; it != NULL; it = it->next) {
164         rtdata = comps_objrtree_data_create(
165                                     ((COMPS_ObjRTreeData*)it->data)->key, NULL);
166         if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
167             new_data = comps_object_copy(((COMPS_ObjRTreeData*)it->data)->data);
168         else
169             new_data = NULL;
170         comps_hslist_destroy(&rtdata->subnodes);
171         rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
172         rtdata->data = new_data;
173         comps_hslist_append(rt1->subnodes, rtdata, 0);
174         comps_hslist_append(to_clone, rtdata, 0);
175     }
176 
177     while (to_clone->first) {
178         it2 = to_clone->first;
179         tmplist = ((COMPS_ObjRTreeData*)it2->data)->subnodes;
180         comps_hslist_remove(to_clone, to_clone->first);
181 
182         new_subnodes = comps_hslist_create();
183         comps_hslist_init(new_subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
184         for (it = tmplist->first; it != NULL; it = it->next) {
185             rtdata = comps_objrtree_data_create(
186                                       ((COMPS_ObjRTreeData*)it->data)->key, NULL);
187             if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
188                 new_data = comps_object_copy(((COMPS_ObjRTreeData*)it->data)->data);
189             else
190                 new_data = NULL;
191             comps_hslist_destroy(&rtdata->subnodes);
192             rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
193             rtdata->data = new_data;
194             comps_hslist_append(new_subnodes, rtdata, 0);
195             comps_hslist_append(to_clone, rtdata, 0);
196         }
197         ((COMPS_ObjRTreeData*)it2->data)->subnodes = new_subnodes;
198         free(it2);
199     }
200     comps_hslist_destroy(&to_clone);
201 
202 }
COMPS_COPY_u(objrtree,COMPS_ObjRTree)203 COMPS_COPY_u(objrtree, COMPS_ObjRTree) /*comps_utils.h macro*/
204 
205 void comps_objrtree_copy_shallow(COMPS_ObjRTree *rt1, COMPS_ObjRTree *rt2){
206     COMPS_HSList *to_clone, *tmplist, *new_subnodes;
207     COMPS_HSListItem *it, *it2;
208     COMPS_ObjRTreeData *rtdata;
209     COMPS_Object *new_data;
210 
211     rt1->subnodes = comps_hslist_create();
212     comps_hslist_init(rt1->subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
213     if (rt1->subnodes == NULL) {
214         COMPS_OBJECT_DESTROY(rt1);
215         return;
216     }
217     rt1->len = 0;
218 
219     to_clone = comps_hslist_create();
220     comps_hslist_init(to_clone, NULL, NULL, NULL);
221 
222     for (it = rt2->subnodes->first; it != NULL; it = it->next) {
223         rtdata = comps_objrtree_data_create(
224                                     ((COMPS_ObjRTreeData*)it->data)->key, NULL);
225         if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
226             new_data = COMPS_OBJECT_INCREF(((COMPS_ObjRTreeData*)it->data)->data);
227         else
228             new_data = NULL;
229         comps_hslist_destroy(&rtdata->subnodes);
230         rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
231         rtdata->data = new_data;
232         comps_hslist_append(rt1->subnodes, rtdata, 0);
233         comps_hslist_append(to_clone, rtdata, 0);
234     }
235 
236     while (to_clone->first) {
237         it2 = to_clone->first;
238         tmplist = ((COMPS_ObjRTreeData*)it2->data)->subnodes;
239         comps_hslist_remove(to_clone, to_clone->first);
240 
241         new_subnodes = comps_hslist_create();
242         comps_hslist_init(new_subnodes, NULL, NULL, &comps_objrtree_data_destroy_v);
243         for (it = tmplist->first; it != NULL; it = it->next) {
244             rtdata = comps_objrtree_data_create(
245                                       ((COMPS_ObjRTreeData*)it->data)->key, NULL);
246             if (((COMPS_ObjRTreeData*)it->data)->data != NULL)
247                 new_data = comps_object_incref(((COMPS_ObjRTreeData*)it->data)->data);
248             else
249                 new_data = NULL;
250             comps_hslist_destroy(&rtdata->subnodes);
251             rtdata->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
252             rtdata->data = new_data;
253             comps_hslist_append(new_subnodes, rtdata, 0);
254             comps_hslist_append(to_clone, rtdata, 0);
255         }
256         ((COMPS_ObjRTreeData*)it2->data)->subnodes = new_subnodes;
257         free(it2);
258     }
259     comps_hslist_destroy(&to_clone);
260 }
261 
comps_objrtree_values_walk(COMPS_ObjRTree * rt,void * udata,void (* walk_f)(void *,COMPS_Object *))262 void comps_objrtree_values_walk(COMPS_ObjRTree * rt, void* udata,
263                               void (*walk_f)(void*, COMPS_Object*)) {
264     COMPS_HSList *tmplist, *tmp_subnodes;
265     COMPS_HSListItem *it;
266     tmplist = comps_hslist_create();
267     comps_hslist_init(tmplist, NULL, NULL, NULL);
268     comps_hslist_append(tmplist, rt->subnodes, 0);
269     while (tmplist->first != NULL) {
270         it = tmplist->first;
271         comps_hslist_remove(tmplist, tmplist->first);
272         tmp_subnodes = (COMPS_HSList*)it->data;
273         for (it = tmp_subnodes->first; it != NULL; it=it->next) {
274             if (((COMPS_ObjRTreeData*)it->data)->subnodes->first) {
275                 comps_hslist_append(tmplist,
276                                     ((COMPS_ObjRTreeData*)it->data)->subnodes, 0);
277             }
278             if (((COMPS_ObjRTreeData*)it->data)->data != NULL) {
279                walk_f(udata, ((COMPS_ObjRTreeData*)it->data)->data);
280             }
281         }
282     }
283     comps_hslist_destroy(&tmplist);
284 }
285 
comps_objrtree_paircmp(void * obj1,void * obj2)286 char comps_objrtree_paircmp(void *obj1, void *obj2) {
287     //printf("comparing %s with %s\n", ((COMPS_ObjRTreePair*)obj1)->key,
288     //                               ((COMPS_ObjRTreePair*)obj2)->key);
289     if (strcmp(((COMPS_ObjRTreePair*)obj1)->key,
290                ((COMPS_ObjRTreePair*)obj2)->key) != 0)
291         return 0;
292     return comps_object_cmp(((COMPS_ObjRTreePair*)obj1)->data,
293                             ((COMPS_ObjRTreePair*)obj2)->data);
294 }
295 
296 
comps_objrtree_cmp(COMPS_ObjRTree * ort1,COMPS_ObjRTree * ort2)297 signed char comps_objrtree_cmp(COMPS_ObjRTree *ort1, COMPS_ObjRTree *ort2) {
298     COMPS_HSList *values1, *values2;
299     COMPS_HSListItem *it;
300     COMPS_Set *set1, *set2;
301     signed char ret;
302     values1 = comps_objrtree_pairs(ort1);
303     values2 = comps_objrtree_pairs(ort2);
304     set1 = comps_set_create();
305     comps_set_init(set1, NULL, NULL, NULL, &comps_objrtree_paircmp);
306     set2 = comps_set_create();
307     comps_set_init(set2, NULL, NULL, NULL, &comps_objrtree_paircmp);
308     for (it = values1->first; it != NULL; it = it->next) {
309         comps_set_add(set1, it->data);
310     }
311     for (it = values2->first; it != NULL; it = it->next) {
312         comps_set_add(set2, it->data);
313     }
314 
315     ret = comps_set_cmp(set1, set2);
316     comps_set_destroy(&set1);
317     comps_set_destroy(&set2);
318     //printf("objrtree cmp %d\n", !ret);
319 
320     //char *str;
321     /*for (it = values1->first; it != NULL; it = it->next) {
322         str = comps_object_tostr(((COMPS_ObjRTreePair*)it->data)->data);
323         printf("dict item %s=%s\n", ((COMPS_ObjRTreePair*)it->data)->key, str);
324         free(str);
325     }
326     printf("----------\n");
327     for (it = values2->first; it != NULL; it = it->next) {
328         str = comps_object_tostr(((COMPS_ObjRTreePair*)it->data)->data);
329         printf("dict item %s=%s\n", ((COMPS_ObjRTreePair*)it->data)->key, str);
330         free(str);
331     }
332     printf("cmp objrtree ret:%d\n", ret);*/
333     comps_hslist_destroy(&values1);
334     comps_hslist_destroy(&values2);
335     return ret==0;
336 }
COMPS_CMP_u(objrtree,COMPS_ObjRTree)337 COMPS_CMP_u(objrtree, COMPS_ObjRTree)
338 
339 void __comps_objrtree_set(COMPS_ObjRTree *rt, char *key, size_t len,
340                           COMPS_Object *ndata) {
341 
342     COMPS_HSListItem *it, *lesser;
343     COMPS_HSList *subnodes;
344     COMPS_ObjRTreeData *rtd;
345     static COMPS_ObjRTreeData *rtdata;
346 
347     size_t _len, offset=0;
348     unsigned x, found = 0;
349     char ended;
350 
351     //len = strlen(key);
352 
353     if (rt->subnodes == NULL)
354         return;
355 
356     subnodes = rt->subnodes;
357     while (offset != len)
358     {
359         found = 0;
360         lesser = NULL;
361         for (it = subnodes->first; it != NULL; it=it->next) {
362             if (((COMPS_ObjRTreeData*)it->data)->key[0] == key[offset]) {
363                 found = 1;
364                 break;
365             } else if (((COMPS_ObjRTreeData*)it->data)->key[0] < key[offset]) {
366                 lesser = it;
367             }
368         }
369         if (!found) { // not found in subnodes; create new subnode
370             rtd = comps_objrtree_data_create_n(key+offset, len-offset, ndata);
371             if (!lesser) {
372                 comps_hslist_prepend(subnodes, rtd, 0);
373             } else {
374                 comps_hslist_insert_after(subnodes, lesser, rtd, 0);
375             }
376             rt->len++;
377             return;
378         } else {
379             rtdata = (COMPS_ObjRTreeData*)it->data;
380             ended = 0;
381             for (x=1; ;x++) {
382                 if (rtdata->key[x] == 0) ended += 1;
383                 if (x == len - offset) ended += 2;
384                 if (ended != 0) break;
385                 if (key[offset+x] != rtdata->key[x]) break;
386             }
387             if (ended == 3) { //keys equals; data replacement
388                 comps_object_destroy(rtdata->data);
389                 rtdata->data = ndata;
390                 return;
391             } else if (ended == 2) { //global key ends first; make global leaf
392                 //printf("ended2\n");
393                 comps_hslist_remove(subnodes, it);
394                 it->next = NULL;
395                 rtd = comps_objrtree_data_create_n(key+offset, len-offset, ndata);
396                 comps_hslist_append(subnodes, rtd, 0);
397                 ((COMPS_ObjRTreeData*)subnodes->last->data)->subnodes->last = it;
398                 ((COMPS_ObjRTreeData*)subnodes->last->data)->subnodes->first = it;
399                 _len = len - offset;
400 
401                 memmove(rtdata->key,rtdata->key+_len,
402                         strlen(rtdata->key) - _len);
403                 rtdata->key[strlen(rtdata->key) - _len] = 0;
404                 rtdata->key = realloc(rtdata->key,
405                                       sizeof(char)* (strlen(rtdata->key)+1));
406                 rt->len++;
407                 return;
408             } else if (ended == 1) { //local key ends first; go deeper
409                 subnodes = rtdata->subnodes;
410                 offset += x;
411             } else {
412                 COMPS_Object *tmpdata = rtdata->data;
413                 COMPS_HSList *tmphslist = rtdata->subnodes;
414                 //tmpch = rtdata->key[x];             // split mutual key
415                 rtdata->subnodes = comps_hslist_create();
416                 comps_hslist_init(rtdata->subnodes, NULL, NULL,
417                                   &comps_objrtree_data_destroy_v);
418                 int cmpret = strcmp(key+offset+x, rtdata->key+x);
419                 rtdata->data = NULL;
420 
421                 if (cmpret > 0) {
422                     rtd = comps_objrtree_data_create(rtdata->key+x, tmpdata);
423                     comps_hslist_destroy(&rtd->subnodes);
424                     rtd->subnodes = tmphslist;
425 
426                     comps_hslist_append(rtdata->subnodes,rtd, 0);
427                     rtd = comps_objrtree_data_create(key+offset+x, ndata);
428                     comps_hslist_append(rtdata->subnodes, rtd, 0);
429 
430                 } else {
431                     rtd = comps_objrtree_data_create(key+offset+x, ndata);
432                     comps_hslist_append(rtdata->subnodes, rtd, 0);
433                     rtd = comps_objrtree_data_create(rtdata->key+x, tmpdata);
434                     comps_hslist_destroy(&rtd->subnodes);
435                     rtd->subnodes = tmphslist;
436                     comps_hslist_append(rtdata->subnodes, rtd, 0);
437                 }
438                 rtdata->key = realloc(rtdata->key, sizeof(char)*(x+1));
439                 rtdata->key[x] = 0;
440                 rt->len++;
441                 return;
442             }
443         }
444     }
445 }
446 
comps_objrtree_set_x(COMPS_ObjRTree * rt,char * key,COMPS_Object * data)447 void comps_objrtree_set_x(COMPS_ObjRTree *rt, char *key, COMPS_Object *data) {
448     __comps_objrtree_set(rt, key, strlen(key), data);
449 }
comps_objrtree_set(COMPS_ObjRTree * rt,char * key,COMPS_Object * data)450 void comps_objrtree_set(COMPS_ObjRTree *rt, char *key, COMPS_Object *data) {
451     __comps_objrtree_set(rt, key, strlen(key), comps_object_incref(data));
452 }
comps_objrtree_set_n(COMPS_ObjRTree * rt,char * key,size_t len,COMPS_Object * data)453 void comps_objrtree_set_n(COMPS_ObjRTree *rt, char *key, size_t len,
454                           COMPS_Object *data) {
455     __comps_objrtree_set(rt, key, len, data);
456 }
comps_objrtree_set_nx(COMPS_ObjRTree * rt,char * key,size_t len,COMPS_Object * data)457 void comps_objrtree_set_nx(COMPS_ObjRTree *rt, char *key, size_t len,
458                            COMPS_Object *data) {
459     __comps_objrtree_set(rt, key, len, comps_object_incref(data));
460 }
461 
__comps_objrtree_get(COMPS_ObjRTree * rt,const char * key)462 COMPS_Object* __comps_objrtree_get(COMPS_ObjRTree * rt, const char * key) {
463     COMPS_HSList * subnodes;
464     COMPS_HSListItem * it = NULL;
465     COMPS_ObjRTreeData * rtdata;
466     unsigned int offset, len, x;
467     char found, ended;
468 
469     len = strlen(key);
470     offset = 0;
471     subnodes = rt->subnodes;
472 
473     while (offset != len) {
474         found = 0;
475         for (it = subnodes->first; it != NULL; it=it->next) {
476             if (((COMPS_ObjRTreeData*)it->data)->key[0] == key[offset]) {
477                 found = 1;
478                 break;
479             }
480         }
481         if (!found) {
482             return NULL;
483         }
484         rtdata = (COMPS_ObjRTreeData*)it->data;
485 
486         for (x=1; ;x++) {
487             ended=0;
488             if (x == strlen(rtdata->key)) ended += 1;
489             if (x == len-offset) ended += 2;
490             if (ended != 0) break;
491             if (key[offset+x] != rtdata->key[x]) break;
492         }
493         if (ended == 3) {
494             return rtdata->data;
495         }
496         else if (ended == 1) offset+=x;
497         else {
498             return NULL;
499         }
500         subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
501     }
502     if (it != NULL) {
503         return ((COMPS_ObjRTreeData*)it->data)->data;
504     }
505     else {
506         return NULL;
507     }
508 }
comps_objrtree_get(COMPS_ObjRTree * rt,const char * key)509 COMPS_Object* comps_objrtree_get(COMPS_ObjRTree * rt, const char * key) {
510     return comps_object_incref(__comps_objrtree_get(rt, key));
511 }
comps_objrtree_get_x(COMPS_ObjRTree * rt,const char * key)512 COMPS_Object* comps_objrtree_get_x(COMPS_ObjRTree * rt, const char * key) {
513     return __comps_objrtree_get(rt, key);
514 }
515 
comps_objrtree_unset(COMPS_ObjRTree * rt,const char * key)516 void comps_objrtree_unset(COMPS_ObjRTree * rt, const char * key) {
517     COMPS_HSList * subnodes;
518     COMPS_HSListItem * it;
519     COMPS_ObjRTreeData * rtdata;
520     unsigned int offset, len, x;
521     char found, ended;
522     COMPS_HSList * path;
523 
524     struct Relation {
525         COMPS_HSList * parent_nodes;
526         COMPS_HSListItem * child_it;
527     } *relation;
528 
529     path = comps_hslist_create();
530     comps_hslist_init(path, NULL, NULL, &free);
531 
532     len = strlen(key);
533     offset = 0;
534     subnodes = rt->subnodes;
535     while (offset != len) {
536         found = 0;
537         for (it = subnodes->first; it != NULL; it=it->next) {
538             if (((COMPS_ObjRTreeData*)it->data)->key[0] == key[offset]) {
539                 found = 1;
540                 break;
541             }
542         }
543         if (!found) {
544             comps_hslist_destroy(&path);
545             return;
546         }
547         rtdata = (COMPS_ObjRTreeData*)it->data;
548 
549         for (x=1; ;x++) {
550             ended=0;
551             if (rtdata->key[x] == 0) ended += 1;
552             if (x == len - offset) ended += 2;
553             if (ended != 0) break;
554             if (key[offset+x] != rtdata->key[x]) break;
555         }
556         if (ended == 3) {
557             /* remove node from tree only if there's no descendant*/
558             if (rtdata->subnodes->last == NULL) {
559                 //printf("removing all\n");
560                 comps_hslist_remove(subnodes, it);
561                 comps_objrtree_data_destroy(rtdata);
562                 free(it);
563             }
564             else {
565                 //printf("removing data only\n");
566                 comps_object_destroy(rtdata->data);
567                 rtdata->is_leaf = 0;
568                 rtdata->data = NULL;
569             }
570 
571             if (path->last == NULL) {
572                 comps_hslist_destroy(&path);
573                 return;
574             }
575             rtdata = (COMPS_ObjRTreeData*)
576                      ((struct Relation*)path->last->data)->child_it->data;
577 
578             /*remove all predecessor of deleted node (recursive) with no childs*/
579             while (rtdata->subnodes->last == NULL) {
580                 //printf("removing '%s'\n", rtdata->key);
581                 comps_objrtree_data_destroy(rtdata);
582                 comps_hslist_remove(
583                             ((struct Relation*)path->last->data)->parent_nodes,
584                             ((struct Relation*)path->last->data)->child_it);
585                 free(((struct Relation*)path->last->data)->child_it);
586                 it = path->last;
587                 comps_hslist_remove(path, path->last);
588                 free(it);
589                 rtdata = (COMPS_ObjRTreeData*)
590                          ((struct Relation*)path->last->data)->child_it->data;
591             }
592             comps_hslist_destroy(&path);
593             return;
594         }
595         else if (ended == 1) offset+=x;
596         else {
597             comps_hslist_destroy(&path);
598             return;
599         }
600         if ((relation = malloc(sizeof(struct Relation))) == NULL) {
601             comps_hslist_destroy(&path);
602             return;
603         }
604         subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
605         relation->parent_nodes = subnodes;
606         relation->child_it = it;
607         comps_hslist_append(path, (void*)relation, 0);
608     }
609     comps_hslist_destroy(&path);
610     return;
611 }
612 
comps_objrtree_clear(COMPS_ObjRTree * rt)613 void comps_objrtree_clear(COMPS_ObjRTree * rt) {
614     if (rt==NULL) return;
615     comps_hslist_clear(rt->subnodes);
616     rt->len = 0;
617 }
618 
__comps_objrtree_all(COMPS_ObjRTree * rt,char keyvalpair)619 inline COMPS_HSList* __comps_objrtree_all(COMPS_ObjRTree * rt, char keyvalpair) {
620     COMPS_HSList *to_process, *ret;
621     COMPS_HSListItem *hsit, *oldit;
622     size_t x;
623     struct Pair {
624         char *key;
625         void *data;
626         COMPS_HSList *subnodes;
627     } *pair, *current_pair=NULL;//, *oldpair=NULL;
628     COMPS_ObjRTreePair *rtpair;
629 
630     to_process = comps_hslist_create();
631     comps_hslist_init(to_process, NULL, NULL, &free);
632 
633     ret = comps_hslist_create();
634     if (keyvalpair == 0)
635         comps_hslist_init(ret, NULL, NULL, &free);
636     else if (keyvalpair == 1)
637         comps_hslist_init(ret, NULL, NULL, NULL);
638     else
639         comps_hslist_init(ret, NULL, NULL, &comps_objrtree_pair_destroy_v);
640 
641     for (hsit = rt->subnodes->first; hsit != NULL; hsit = hsit->next) {
642         pair = malloc(sizeof(struct Pair));
643         pair->key = __comps_strcpy(((COMPS_ObjRTreeData*)hsit->data)->key);
644         pair->data = ((COMPS_ObjRTreeData*)hsit->data)->data;
645         pair->subnodes = ((COMPS_ObjRTreeData*)hsit->data)->subnodes;
646         comps_hslist_append(to_process, pair, 0);
647     }
648     while (to_process->first) {
649         //oldpair = current_pair;
650         current_pair = to_process->first->data;
651         oldit = to_process->first;
652         comps_hslist_remove(to_process, to_process->first);
653         if (current_pair->data) {
654             if (keyvalpair == 0) {
655                 comps_hslist_append(ret, __comps_strcpy(current_pair->key), 0);
656             } else if (keyvalpair == 1) {
657                 comps_hslist_append(ret, current_pair->data, 0);
658             } else {
659                 rtpair = malloc(sizeof(COMPS_ObjRTreePair));
660                 rtpair->key = __comps_strcpy(current_pair->key);
661                 rtpair->data = current_pair->data;
662                 comps_hslist_append(ret, rtpair, 0);
663             }
664         }
665         for (hsit = current_pair->subnodes->first, x = 0;
666              hsit != NULL; hsit = hsit->next, x++) {
667             pair = malloc(sizeof(struct Pair));
668             pair->key = __comps_strcat(current_pair->key,
669                                        ((COMPS_ObjRTreeData*)hsit->data)->key);
670             pair->data = ((COMPS_ObjRTreeData*)hsit->data)->data;
671             pair->subnodes = ((COMPS_ObjRTreeData*)hsit->data)->subnodes;
672             comps_hslist_insert_at(to_process, x, pair, 0);
673         }
674         free(current_pair->key);
675         free(current_pair);
676         free(oldit);
677     }
678 
679     comps_hslist_destroy(&to_process);
680     return ret;
681 }
682 
comps_objrtree_unite(COMPS_ObjRTree * rt1,COMPS_ObjRTree * rt2)683 void comps_objrtree_unite(COMPS_ObjRTree *rt1, COMPS_ObjRTree *rt2) {
684     COMPS_HSList *tmplist, *tmp_subnodes;
685     COMPS_HSListItem *it;
686     struct Pair {
687         COMPS_HSList * subnodes;
688         char * key;
689     } *pair, *parent_pair;
690 
691     pair = malloc(sizeof(struct Pair));
692     pair->subnodes = rt2->subnodes;
693     pair->key = NULL;
694 
695     tmplist = comps_hslist_create();
696     comps_hslist_init(tmplist, NULL, NULL, &free);
697     comps_hslist_append(tmplist, pair, 0);
698 
699     while (tmplist->first != NULL) {
700         it = tmplist->first;
701         comps_hslist_remove(tmplist, tmplist->first);
702         tmp_subnodes = ((struct Pair*)it->data)->subnodes;
703         parent_pair = (struct Pair*) it->data;
704         //printf("key-part:%s\n", parent_pair->key);
705         free(it);
706 
707         for (it = tmp_subnodes->first; it != NULL; it=it->next) {
708             pair = malloc(sizeof(struct Pair));
709             pair->subnodes = ((COMPS_ObjRTreeData*)it->data)->subnodes;
710 
711             if (parent_pair->key != NULL) {
712                 pair->key = malloc(sizeof(char)
713                                * (strlen(((COMPS_ObjRTreeData*)it->data)->key)
714                                + strlen(parent_pair->key) + 1));
715                 memcpy(pair->key, parent_pair->key,
716                        sizeof(char) * strlen(parent_pair->key));
717                 memcpy(pair->key + strlen(parent_pair->key),
718                        ((COMPS_ObjRTreeData*)it->data)->key,
719                        sizeof(char)*(strlen(((COMPS_ObjRTreeData*)it->data)->key)+1));
720             } else {
721                 pair->key = malloc(sizeof(char)*
722                                 (strlen(((COMPS_ObjRTreeData*)it->data)->key) +1));
723                 memcpy(pair->key, ((COMPS_ObjRTreeData*)it->data)->key,
724                        sizeof(char)*(strlen(((COMPS_ObjRTreeData*)it->data)->key)+1));
725             }
726             /* current node has data */
727             if (((COMPS_ObjRTreeData*)it->data)->data != NULL) {
728                     comps_objrtree_set(rt1, pair->key,
729                                       (((COMPS_ObjRTreeData*)it->data)->data));
730             }
731             if (((COMPS_ObjRTreeData*)it->data)->subnodes->first) {
732                 comps_hslist_append(tmplist, pair, 0);
733             } else {
734                 free(pair->key);
735                 free(pair);
736             }
737         }
738         free(parent_pair->key);
739         free(parent_pair);
740     }
741     comps_hslist_destroy(&tmplist);
742 }
743 
comps_objrtree_union(COMPS_ObjRTree * rt1,COMPS_ObjRTree * rt2)744 COMPS_ObjRTree* comps_objrtree_union(COMPS_ObjRTree *rt1, COMPS_ObjRTree *rt2){
745     COMPS_ObjRTree *ret;
746     ret = comps_objrtree_clone(rt1);
747     comps_objrtree_unite(ret, rt2);
748     return ret;
749 }
750 
751 
comps_objrtree_keys(COMPS_ObjRTree * rt)752 COMPS_HSList* comps_objrtree_keys(COMPS_ObjRTree * rt) {
753     return __comps_objrtree_all(rt, 0);
754 }
755 
comps_objrtree_values(COMPS_ObjRTree * rt)756 COMPS_HSList* comps_objrtree_values(COMPS_ObjRTree * rt) {
757     return __comps_objrtree_all(rt, 1);
758 }
759 
comps_objrtree_pairs(COMPS_ObjRTree * rt)760 COMPS_HSList* comps_objrtree_pairs(COMPS_ObjRTree * rt) {
761     return __comps_objrtree_all(rt, 2);
762 }
763 
764 
comps_objrtree_pair_destroy(COMPS_ObjRTreePair * pair)765 inline void comps_objrtree_pair_destroy(COMPS_ObjRTreePair * pair) {
766     free(pair->key);
767     free(pair);
768 }
769 
comps_objrtree_pair_destroy_v(void * pair)770 inline void comps_objrtree_pair_destroy_v(void * pair) {
771     free(((COMPS_ObjRTreePair *)pair)->key);
772     free(pair);
773 }
774 
775 COMPS_ObjectInfo COMPS_ObjRTree_ObjInfo = {
776     .obj_size = sizeof(COMPS_ObjRTree),
777     .constructor = &comps_objrtree_create_u,
778     .destructor = &comps_objrtree_destroy_u,
779     .copy = &comps_objrtree_copy_u,
780     .obj_cmp = &comps_objrtree_cmp_u
781 };
782