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