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