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