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_radix.h"
21 #include "comps_utils.h"
22 
23 #include <stdio.h>
24 
comps_rtree_data_destroy(COMPS_RTreeData * rtd)25 void comps_rtree_data_destroy(COMPS_RTreeData * rtd) {
26     free(rtd->key);
27     if ((rtd->data) && (*rtd->data_destructor))
28         (*rtd->data_destructor)(rtd->data);
29     comps_hslist_destroy(&rtd->subnodes);
30     free(rtd);
31 }
32 
comps_rtree_data_destroy_v(void * rtd)33 inline void comps_rtree_data_destroy_v(void * rtd) {
34     comps_rtree_data_destroy((COMPS_RTreeData*)rtd);
35 }
36 
__comps_rtree_data_create(COMPS_RTree * rt,char * key,unsigned int keylen,void * data)37 inline COMPS_RTreeData * __comps_rtree_data_create(COMPS_RTree *rt, char *key,
38                                                    unsigned int keylen,
39                                                    void *data){
40     COMPS_RTreeData * rtd;
41     if ((rtd = malloc(sizeof(*rtd))) == NULL)
42         return NULL;
43     if ((rtd->key = malloc(sizeof(char) * (keylen+1))) == NULL) {
44         free(rtd);
45         return NULL;
46     }
47     memcpy(rtd->key, key, sizeof(char)*keylen);
48     rtd->key[keylen] = 0;
49     rtd->data = data;
50     if (data != NULL) {
51         rtd->is_leaf = 1;
52     }
53     rtd->data_destructor = &rt->data_destructor;
54     rtd->subnodes = comps_hslist_create();
55     comps_hslist_init(rtd->subnodes, NULL, NULL, &comps_rtree_data_destroy_v);
56     return rtd;
57 }
58 
comps_rtree_data_create(COMPS_RTree * rt,char * key,void * data)59 COMPS_RTreeData * comps_rtree_data_create(COMPS_RTree *rt,char * key,
60                                           void * data) {
61     COMPS_RTreeData * rtd;
62     rtd = __comps_rtree_data_create(rt, key, strlen(key), data);
63     return rtd;
64 }
65 
comps_rtree_data_create_n(COMPS_RTree * rt,char * key,size_t keylen,void * data)66 COMPS_RTreeData * comps_rtree_data_create_n(COMPS_RTree *rt, char * key,
67                                             size_t keylen, void * data) {
68     COMPS_RTreeData * rtd;
69     rtd = __comps_rtree_data_create(rt, key, keylen, data);
70     return rtd;
71 }
72 
comps_rtree_create(void * (* data_constructor)(void *),void * (* data_cloner)(void *),void (* data_destructor)(void *))73 COMPS_RTree * comps_rtree_create(void* (*data_constructor)(void*),
74                                  void* (*data_cloner)(void*),
75                                  void (*data_destructor)(void*)) {
76     COMPS_RTree *ret;
77     if ((ret = malloc(sizeof(COMPS_RTree))) == NULL)
78         return NULL;
79     ret->subnodes = comps_hslist_create();
80     comps_hslist_init(ret->subnodes, NULL, NULL, &comps_rtree_data_destroy_v);
81     if (ret->subnodes == NULL) {
82         free(ret);
83         return NULL;
84     }
85     ret->data_constructor = data_constructor;
86     ret->data_cloner = data_cloner;
87     ret->data_destructor = data_destructor;
88     return ret;
89 }
90 
comps_rtree_destroy(COMPS_RTree * rt)91 void comps_rtree_destroy(COMPS_RTree * rt) {
92     if (!rt) return;
93     comps_hslist_destroy(&(rt->subnodes));
94     free(rt);
95 }
96 
comps_rtree_print(COMPS_HSList * hl,unsigned deep)97 void comps_rtree_print(COMPS_HSList * hl, unsigned  deep) {
98     COMPS_HSListItem * it;
99     for (it = hl->first; it != NULL; it=it->next) {
100         printf("%d %s\n",deep, (((COMPS_RTreeData*)it->data)->key));
101         comps_rtree_print(((COMPS_RTreeData*)it->data)->subnodes, deep+1);
102     }
103 }
104 
comps_rtree_clone(COMPS_RTree * rt)105 COMPS_RTree * comps_rtree_clone(COMPS_RTree *rt) {
106 
107     COMPS_HSList *to_clone, *tmplist, *new_subnodes;
108     COMPS_RTree *ret;
109     COMPS_HSListItem *it, *it2;
110     COMPS_RTreeData *rtdata;
111     void *new_data;
112 
113     if (!rt) return NULL;
114 
115     to_clone = comps_hslist_create();
116     comps_hslist_init(to_clone, NULL, NULL, NULL);
117     ret = comps_rtree_create(rt->data_constructor, rt->data_cloner,
118                              rt->data_destructor);
119 
120 
121     for (it = rt->subnodes->first; it != NULL; it = it->next) {
122         rtdata = comps_rtree_data_create(ret,
123                                       ((COMPS_RTreeData*)it->data)->key, NULL);
124         if (((COMPS_RTreeData*)it->data)->data != NULL)
125             new_data = rt->data_cloner(((COMPS_RTreeData*)it->data)->data);
126         else
127             new_data = NULL;
128         comps_hslist_destroy(&rtdata->subnodes);
129         rtdata->subnodes = ((COMPS_RTreeData*)it->data)->subnodes;
130         rtdata->data = new_data;
131         comps_hslist_append(ret->subnodes, rtdata, 0);
132 
133         comps_hslist_append(to_clone, rtdata, 0);
134     }
135 
136 
137     while (to_clone->first) {
138         it2 = to_clone->first;
139         tmplist = ((COMPS_RTreeData*)it2->data)->subnodes;
140         comps_hslist_remove(to_clone, to_clone->first);
141 
142         new_subnodes = comps_hslist_create();
143         comps_hslist_init(new_subnodes, NULL, NULL, &comps_rtree_data_destroy_v);
144         for (it = tmplist->first; it != NULL; it = it->next) {
145             rtdata = comps_rtree_data_create(ret,
146                                       ((COMPS_RTreeData*)it->data)->key, NULL);
147             if (((COMPS_RTreeData*)it->data)->data != NULL)
148                 new_data = rt->data_cloner(((COMPS_RTreeData*)it->data)->data);
149             else
150                 new_data = NULL;
151             comps_hslist_destroy(&rtdata->subnodes);
152             rtdata->subnodes = ((COMPS_RTreeData*)it->data)->subnodes;
153             rtdata->data = new_data;
154             comps_hslist_append(new_subnodes, rtdata, 0);
155 
156             comps_hslist_append(to_clone, rtdata, 0);
157         }
158         ((COMPS_RTreeData*)it2->data)->subnodes = new_subnodes;
159         free(it2);
160     }
161     comps_hslist_destroy(&to_clone);
162     return ret;
163 }
164 
comps_rtree_values_walk(COMPS_RTree * rt,void * udata,void (* walk_f)(void *,void *))165 void comps_rtree_values_walk(COMPS_RTree * rt, void* udata,
166                               void (*walk_f)(void*, void*)) {
167     COMPS_HSList *tmplist, *tmp_subnodes;
168     COMPS_HSListItem *it;
169     tmplist = comps_hslist_create();
170     comps_hslist_init(tmplist, NULL, NULL, NULL);
171     comps_hslist_append(tmplist, rt->subnodes, 0);
172     while (tmplist->first != NULL) {
173         it = tmplist->first;
174         comps_hslist_remove(tmplist, tmplist->first);
175         tmp_subnodes = (COMPS_HSList*)it->data;
176         for (it = tmp_subnodes->first; it != NULL; it=it->next) {
177             if (((COMPS_RTreeData*)it->data)->subnodes->first) {
178                 comps_hslist_append(tmplist,
179                                     ((COMPS_RTreeData*)it->data)->subnodes, 0);
180             }
181             if (((COMPS_RTreeData*)it->data)->data != NULL) {
182                walk_f(udata, ((COMPS_RTreeData*)it->data)->data);
183             }
184         }
185     }
186     comps_hslist_destroy(&tmplist);
187 }
188 
__comps_rtree_set(COMPS_RTree * rt,char * key,size_t len,void * data)189 void __comps_rtree_set(COMPS_RTree * rt, char * key, size_t len, void * data)
190 {
191     COMPS_HSListItem *it, *lesser;
192     COMPS_HSList *subnodes;
193     COMPS_RTreeData *rtd;
194     static COMPS_RTreeData *rtdata;
195 
196     size_t offset=0, _len;
197     unsigned x, found = 0;
198     void *ndata;
199     char ended;//, tmpch;
200 
201     if (rt->subnodes == NULL)
202         return;
203     if (rt->data_constructor) {
204         ndata = rt->data_constructor(data);
205     } else {
206         ndata = data;
207     }
208 
209     subnodes = rt->subnodes;
210     while (offset != len)
211     {
212         found = 0;
213         lesser = NULL;
214         for (it = subnodes->first; it != NULL; it=it->next) {
215             if (((COMPS_RTreeData*)it->data)->key[0] == key[offset]) {
216                 found = 1;
217                 break;
218             } else if (((COMPS_RTreeData*)it->data)->key[0] < key[offset]) {
219                 lesser = it;
220             }
221         }
222         if (!found) { // not found in subnodes; create new subnode
223             rtd = comps_rtree_data_create(rt, key+offset, ndata);
224             if (!lesser) {
225                 comps_hslist_prepend(subnodes, rtd, 0);
226             } else {
227                 comps_hslist_insert_after(subnodes, lesser, rtd, 0);
228             }
229             return;
230         } else {
231             rtdata = (COMPS_RTreeData*)it->data;
232             ended = 0;
233             for (x=1; ;x++) {
234                 if (rtdata->key[x] == 0) ended += 1;
235                 if (x == len - offset) ended += 2;
236                 if (ended != 0) break;
237                 if (key[offset+x] != rtdata->key[x]) break;
238             }
239             if (ended == 3) { //keys equals; data replacement
240                 rt->data_destructor(rtdata->data);
241                 rtdata->data = ndata;
242                 return;
243             } else if (ended == 2) { //global key ends first; make global leaf
244                 comps_hslist_remove(subnodes, it);
245                 it->next = NULL;
246                 rtd = comps_rtree_data_create_n(rt, key+offset,
247                                                 len-offset, ndata);
248                 comps_hslist_append(subnodes, rtd, 0);
249                 ((COMPS_RTreeData*)subnodes->last->data)->subnodes->last = it;
250                 ((COMPS_RTreeData*)subnodes->last->data)->subnodes->first = it;
251                 _len = len - offset;
252 
253                 memmove(rtdata->key,rtdata->key + _len,
254                                     strlen(rtdata->key) - _len);
255                 rtdata->key[strlen(rtdata->key) - _len] = 0;
256                 rtdata->key = realloc(rtdata->key,
257                                       sizeof(char)* (strlen(rtdata->key)+1));
258                 return;
259             } else if (ended == 1) { //local key ends first; go deeper
260                 subnodes = rtdata->subnodes;
261                 offset += x;
262             } else {
263                 void *tmpdata = rtdata->data;
264                 COMPS_HSList *tmpnodes = rtdata->subnodes;
265 
266                 int cmpret = strcmp(key+offset+x, rtdata->key+x);
267                 rtdata->subnodes = comps_hslist_create();
268                 comps_hslist_init(rtdata->subnodes, NULL, NULL,
269                                   &comps_rtree_data_destroy_v);
270                 rtdata->data = NULL;
271 
272                 if (cmpret > 0) {
273                     rtd = comps_rtree_data_create(rt, rtdata->key+x, tmpdata);
274                     comps_hslist_destroy(&rtd->subnodes);
275                     rtd->subnodes = tmpnodes;
276                     comps_hslist_append(rtdata->subnodes, rtd, 0);
277                     rtd = comps_rtree_data_create(rt, key+offset+x, ndata);
278                     comps_hslist_append(rtdata->subnodes, rtd, 0);
279                 } else {
280                     rtd = comps_rtree_data_create(rt, key+offset+x, ndata);
281                     comps_hslist_append(rtdata->subnodes, rtd, 0);
282                     rtd = comps_rtree_data_create(rt, rtdata->key+x, tmpdata);
283                     comps_hslist_destroy(&rtd->subnodes);
284                     rtd->subnodes = tmpnodes;
285                     comps_hslist_append(rtdata->subnodes, rtd, 0);
286                 }
287                 rtdata->key = realloc(rtdata->key, sizeof(char)*(x+1));
288                 rtdata->key[x] = 0;
289                 return;
290             }
291         }
292     }
293 }
294 
comps_rtree_set(COMPS_RTree * rt,char * key,void * data)295 void comps_rtree_set(COMPS_RTree * rt, char * key, void * data)
296 {
297     __comps_rtree_set(rt, key, strlen(key), data);
298 }
comps_rtree_set_n(COMPS_RTree * rt,char * key,size_t keylen,void * data)299 void comps_rtree_set_n(COMPS_RTree * rt, char * key, size_t keylen, void * data)
300 {
301     __comps_rtree_set(rt, key, keylen, data);
302 }
303 
comps_rtree_get(COMPS_RTree * rt,const char * key)304 void* comps_rtree_get(COMPS_RTree * rt, const char * key) {
305     COMPS_HSList * subnodes;
306     COMPS_HSListItem * it = NULL;
307     COMPS_RTreeData * rtdata;
308     unsigned int offset, len, x;
309     char found, ended;
310 
311     len = strlen(key);
312     offset = 0;
313     subnodes = rt->subnodes;
314     while (offset != len) {
315         found = 0;
316         for (it = subnodes->first; it != NULL; it=it->next) {
317             if (((COMPS_RTreeData*)it->data)->key[0] == key[offset]) {
318                 found = 1;
319                 break;
320             }
321         }
322         if (!found) {
323             //printf("not found\n");
324             return NULL;
325         }
326         rtdata = (COMPS_RTreeData*)it->data;
327 
328         for (x=1; ;x++) {
329             ended=0;
330             if (x == strlen(rtdata->key)) ended += 1;
331             if (x == len-offset) ended += 2;
332             if (ended != 0) break;
333             if (key[offset+x] != rtdata->key[x]) break;
334         }
335         //printf("ended :%d key :%s|\n", ended, rtdata->key);
336         if (ended == 3) return rtdata->data;
337         else if (ended == 1) offset+=x;
338         else return NULL;
339         subnodes = ((COMPS_RTreeData*)it->data)->subnodes;
340     }
341     if (it != NULL)
342         return ((COMPS_RTreeData*)it->data)->data;
343     else return NULL;
344 }
345 
comps_rtree_unset(COMPS_RTree * rt,const char * key)346 void comps_rtree_unset(COMPS_RTree * rt, const char * key) {
347     COMPS_HSList * subnodes;
348     COMPS_HSListItem * it;
349     COMPS_RTreeData * rtdata;
350     unsigned int offset, len, x;
351     char found, ended;
352     COMPS_HSList * path;
353 
354     struct Relation {
355         COMPS_HSList * parent_nodes;
356         COMPS_HSListItem * child_it;
357     } *relation;
358 
359     path = comps_hslist_create();
360     comps_hslist_init(path, NULL, NULL, &free);
361 
362     len = strlen(key);
363     offset = 0;
364     subnodes = rt->subnodes;
365     while (offset != len) {
366         found = 0;
367         for (it = subnodes->first; it != NULL; it=it->next) {
368             if (((COMPS_RTreeData*)it->data)->key[0] == key[offset]) {
369                 found = 1;
370                 break;
371             }
372         }
373         if (!found) {
374             comps_hslist_destroy(&path);
375             return;
376         }
377         rtdata = (COMPS_RTreeData*)it->data;
378 
379         for (x=1; ;x++) {
380             ended=0;
381             if (rtdata->key[x] == 0) ended += 1;
382             if (x == len - offset) ended += 2;
383             if (ended != 0) break;
384             if (key[offset+x] != rtdata->key[x]) break;
385         }
386         if (ended == 3) {
387             /* remove node from tree only if there's no descendant*/
388             if (rtdata->subnodes->last == NULL) {
389                 //printf("removing all\n");
390                 comps_hslist_remove(subnodes, it);
391                 comps_rtree_data_destroy(rtdata);
392                 free(it);
393             }
394             else if (rtdata->data_destructor != NULL) {
395                 //printf("removing data only\n");
396                 (*rtdata->data_destructor)(rtdata->data);
397                 rtdata->is_leaf = 0;
398                 rtdata->data = NULL;
399             }
400 
401             if (path->last == NULL) {
402                 comps_hslist_destroy(&path);
403                 return;
404             }
405             rtdata = (COMPS_RTreeData*)
406                      ((struct Relation*)path->last->data)->child_it->data;
407 
408             /*remove all predecessor of deleted node (recursive) with no childs*/
409             while (rtdata->subnodes->last == NULL) {
410                 //printf("removing '%s'\n", rtdata->key);
411                 comps_rtree_data_destroy(rtdata);
412                 comps_hslist_remove(
413                             ((struct Relation*)path->last->data)->parent_nodes,
414                             ((struct Relation*)path->last->data)->child_it);
415                 free(((struct Relation*)path->last->data)->child_it);
416                 it = path->last;
417                 comps_hslist_remove(path, path->last);
418                 free(it);
419                 rtdata = (COMPS_RTreeData*)
420                          ((struct Relation*)path->last->data)->child_it->data;
421             }
422             comps_hslist_destroy(&path);
423             return;
424         }
425         else if (ended == 1) offset+=x;
426         else {
427             comps_hslist_destroy(&path);
428             return;
429         }
430         if ((relation = malloc(sizeof(struct Relation))) == NULL) {
431             comps_hslist_destroy(&path);
432             return;
433         }
434         subnodes = ((COMPS_RTreeData*)it->data)->subnodes;
435         relation->parent_nodes = subnodes;
436         relation->child_it = it;
437         comps_hslist_append(path, (void*)relation, 0);
438     }
439     comps_hslist_destroy(&path);
440     return;
441 }
442 
comps_rtree_clear(COMPS_RTree * rt)443 void comps_rtree_clear(COMPS_RTree * rt) {
444     COMPS_HSListItem *it, *oldit;
445     if (rt==NULL) return;
446     if (rt->subnodes == NULL) return;
447     oldit = rt->subnodes->first;
448     it = (oldit)?oldit->next:NULL;
449     for (;it != NULL; it=it->next) {
450         if (rt->subnodes->data_destructor != NULL)
451             rt->subnodes->data_destructor(oldit->data);
452         free(oldit);
453         oldit = it;
454     }
455     if (oldit) {
456         if (rt->subnodes->data_destructor != NULL)
457             rt->subnodes->data_destructor(oldit->data);
458         free(oldit);
459     }
460 }
461 
__comps_rtree_all(COMPS_RTree * rt,char keyvalpair)462 inline COMPS_HSList* __comps_rtree_all(COMPS_RTree * rt, char keyvalpair) {
463     COMPS_HSList *to_process, *ret;
464     COMPS_HSListItem *hsit, *oldit;
465     size_t x;
466     struct Pair {
467         char *key;
468         void *data;
469         COMPS_HSList *subnodes;
470     } *pair, *current_pair=NULL;//, *oldpair=NULL;
471     COMPS_RTreePair *rtpair;
472 
473     to_process = comps_hslist_create();
474     comps_hslist_init(to_process, NULL, NULL, &free);
475 
476     ret = comps_hslist_create();
477     if (keyvalpair == 0)
478         comps_hslist_init(ret, NULL, NULL, &free);
479     else if (keyvalpair == 1)
480         comps_hslist_init(ret, NULL, NULL, NULL);
481     else
482         comps_hslist_init(ret, NULL, NULL, &comps_rtree_pair_destroy_v);
483 
484     for (hsit = rt->subnodes->first; hsit != NULL; hsit = hsit->next) {
485         pair = malloc(sizeof(struct Pair));
486         pair->key = __comps_strcpy(((COMPS_RTreeData*)hsit->data)->key);
487         pair->data = ((COMPS_RTreeData*)hsit->data)->data;
488         pair->subnodes = ((COMPS_RTreeData*)hsit->data)->subnodes;
489         comps_hslist_append(to_process, pair, 0);
490     }
491     while (to_process->first) {
492         //oldpair = current_pair;
493         current_pair = to_process->first->data;
494         oldit = to_process->first;
495         comps_hslist_remove(to_process, to_process->first);
496         if (current_pair->data) {
497             if (keyvalpair == 0) {
498                 comps_hslist_append(ret, __comps_strcpy(current_pair->key), 0);
499             } else if (keyvalpair == 1) {
500                 comps_hslist_append(ret, current_pair->data, 0);
501             } else {
502                 rtpair = malloc(sizeof(COMPS_RTreePair));
503                 rtpair->key = __comps_strcpy(current_pair->key);
504                 rtpair->data = current_pair->data;
505                 comps_hslist_append(ret, rtpair, 0);
506             }
507         }
508         for (hsit = current_pair->subnodes->first, x = 0;
509              hsit != NULL; hsit = hsit->next, x++) {
510             pair = malloc(sizeof(struct Pair));
511             pair->key = __comps_strcat(current_pair->key,
512                                        ((COMPS_RTreeData*)hsit->data)->key);
513             pair->data = ((COMPS_RTreeData*)hsit->data)->data;
514             pair->subnodes = ((COMPS_RTreeData*)hsit->data)->subnodes;
515             comps_hslist_insert_at(to_process, x, pair, 0);
516         }
517         free(current_pair->key);
518         free(current_pair);
519         free(oldit);
520     }
521 
522     comps_hslist_destroy(&to_process);
523     return ret;
524 }
525 
comps_rtree_unite(COMPS_RTree * rt1,COMPS_RTree * rt2)526 void comps_rtree_unite(COMPS_RTree *rt1, COMPS_RTree *rt2) {
527     COMPS_HSList *tmplist, *tmp_subnodes;
528     COMPS_HSListItem *it;
529     struct Pair {
530         COMPS_HSList * subnodes;
531         char * key;
532     } *pair, *parent_pair;
533 
534     pair = malloc(sizeof(struct Pair));
535     pair->subnodes = rt2->subnodes;
536     pair->key = NULL;
537 
538     tmplist = comps_hslist_create();
539     comps_hslist_init(tmplist, NULL, NULL, &free);
540     comps_hslist_append(tmplist, pair, 0);
541 
542     while (tmplist->first != NULL) {
543         it = tmplist->first;
544         comps_hslist_remove(tmplist, tmplist->first);
545         tmp_subnodes = ((struct Pair*)it->data)->subnodes;
546         parent_pair = (struct Pair*) it->data;
547         free(it);
548 
549         for (it = tmp_subnodes->first; it != NULL; it=it->next) {
550             pair = malloc(sizeof(struct Pair));
551             pair->subnodes = ((COMPS_RTreeData*)it->data)->subnodes;
552 
553             if (parent_pair->key != NULL) {
554                 pair->key = malloc(sizeof(char)
555                                * (strlen(((COMPS_RTreeData*)it->data)->key)
556                                + strlen(parent_pair->key) + 1));
557                 memcpy(pair->key, parent_pair->key,
558                        sizeof(char) * strlen(parent_pair->key));
559                 memcpy(pair->key + strlen(parent_pair->key),
560                        ((COMPS_RTreeData*)it->data)->key,
561                        sizeof(char)*(strlen(((COMPS_RTreeData*)it->data)->key)+1));
562             } else {
563                 pair->key = malloc(sizeof(char)*
564                                 (strlen(((COMPS_RTreeData*)it->data)->key) +1));
565                 memcpy(pair->key, ((COMPS_RTreeData*)it->data)->key,
566                        sizeof(char)*(strlen(((COMPS_RTreeData*)it->data)->key)+1));
567             }
568             /* current node has data */
569             if (((COMPS_RTreeData*)it->data)->data != NULL) {
570                     comps_rtree_set(rt1,
571                                     pair->key,
572                         rt2->data_cloner(((COMPS_RTreeData*)it->data)->data));
573             }
574             if (((COMPS_RTreeData*)it->data)->subnodes->first) {
575                 comps_hslist_append(tmplist, pair, 0);
576             } else {
577                 free(pair->key);
578                 free(pair);
579             }
580         }
581         free(parent_pair->key);
582         free(parent_pair);
583     }
584     comps_hslist_destroy(&tmplist);
585 }
586 
comps_rtree_union(COMPS_RTree * rt1,COMPS_RTree * rt2)587 COMPS_RTree* comps_rtree_union(COMPS_RTree *rt1, COMPS_RTree *rt2){
588     COMPS_RTree *ret;
589     ret = comps_rtree_clone(rt2);
590     comps_rtree_unite(ret, rt1);
591     return ret;
592 }
593 
594 
comps_rtree_keys(COMPS_RTree * rt)595 COMPS_HSList* comps_rtree_keys(COMPS_RTree * rt) {
596     return __comps_rtree_all(rt, 0);
597 }
598 
comps_rtree_values(COMPS_RTree * rt)599 COMPS_HSList* comps_rtree_values(COMPS_RTree * rt) {
600     return __comps_rtree_all(rt, 1);
601 }
602 
comps_rtree_pairs(COMPS_RTree * rt)603 COMPS_HSList* comps_rtree_pairs(COMPS_RTree * rt) {
604     return __comps_rtree_all(rt, 2);
605 }
606 
comps_rtree_pair_destroy(COMPS_RTreePair * pair)607 inline void comps_rtree_pair_destroy(COMPS_RTreePair * pair) {
608     free(pair->key);
609     free(pair);
610 }
611 
comps_rtree_pair_destroy_v(void * pair)612 inline void comps_rtree_pair_destroy_v(void * pair) {
613     free(((COMPS_RTreePair *)pair)->key);
614     free(pair);
615 }
616