dungeon_crawler
view prototype/kdtree/kdtree.c @ 61:4472ef41a209
forgot an extra mrt uniform in deferred_omni.p.glsl
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Tue, 25 Sep 2012 06:37:56 +0300 |
| parents | |
| children |
line source
1 /*
2 This file is part of ``kdtree'', a library for working with kd-trees.
3 Copyright (C) 2007-2011 John Tsiombikas <nuclear@member.fsf.org>
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 1. Redistributions of source code must retain the above copyright notice, this
9 list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright notice,
11 this list of conditions and the following disclaimer in the documentation
12 and/or other materials provided with the distribution.
13 3. The name of the author may not be used to endorse or promote products
14 derived from this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19 EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
21 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
24 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
25 OF SUCH DAMAGE.
26 */
27 /* single nearest neighbor search written by Tamas Nepusz <tamas@cs.rhul.ac.uk> */
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <math.h>
32 #include "kdtree.h"
34 #define USE_LIST_NODE_ALLOCATOR
35 #define NO_PTHREADS
36 #define I_WANT_THREAD_BUGS
38 #if defined(WIN32) || defined(__WIN32__)
39 #include <malloc.h>
40 #endif
42 #ifdef USE_LIST_NODE_ALLOCATOR
44 #ifndef NO_PTHREADS
45 #include <pthread.h>
46 #else
48 #ifndef I_WANT_THREAD_BUGS
49 #error "You are compiling with the fast list node allocator, with pthreads disabled! This WILL break if used from multiple threads."
50 #endif /* I want thread bugs */
52 #endif /* pthread support */
53 #endif /* use list node allocator */
55 struct kdhyperrect {
56 int dim;
57 double *min, *max; /* minimum/maximum coords */
58 };
60 struct kdnode {
61 double *pos;
62 int dir;
63 void *data;
65 struct kdnode *left, *right; /* negative/positive side */
66 };
68 struct res_node {
69 struct kdnode *item;
70 double dist_sq;
71 struct res_node *next;
72 };
74 struct kdtree {
75 int dim;
76 struct kdnode *root;
77 struct kdhyperrect *rect;
78 void (*destr)(void*);
79 };
81 struct kdres {
82 struct kdtree *tree;
83 struct res_node *rlist, *riter;
84 int size;
85 };
87 #define SQ(x) ((x) * (x))
90 static void clear_rec(struct kdnode *node, void (*destr)(void*));
91 static int insert_rec(struct kdnode **node, const double *pos, void *data, int dir, int dim);
92 static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq);
93 static void clear_results(struct kdres *set);
95 static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max);
96 static void hyperrect_free(struct kdhyperrect *rect);
97 static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect);
98 static void hyperrect_extend(struct kdhyperrect *rect, const double *pos);
99 static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos);
101 #ifdef USE_LIST_NODE_ALLOCATOR
102 static struct res_node *alloc_resnode(void);
103 static void free_resnode(struct res_node*);
104 #else
105 #define alloc_resnode() malloc(sizeof(struct res_node))
106 #define free_resnode(n) free(n)
107 #endif
111 struct kdtree *kd_create(int k)
112 {
113 struct kdtree *tree;
115 if(!(tree = malloc(sizeof *tree))) {
116 return 0;
117 }
119 tree->dim = k;
120 tree->root = 0;
121 tree->destr = 0;
122 tree->rect = 0;
124 return tree;
125 }
127 void kd_free(struct kdtree *tree)
128 {
129 if(tree) {
130 kd_clear(tree);
131 free(tree);
132 }
133 }
135 static void clear_rec(struct kdnode *node, void (*destr)(void*))
136 {
137 if(!node) return;
139 clear_rec(node->left, destr);
140 clear_rec(node->right, destr);
142 if(destr) {
143 destr(node->data);
144 }
145 free(node->pos);
146 free(node);
147 }
149 void kd_clear(struct kdtree *tree)
150 {
151 clear_rec(tree->root, tree->destr);
152 tree->root = 0;
154 if (tree->rect) {
155 hyperrect_free(tree->rect);
156 tree->rect = 0;
157 }
158 }
160 void kd_data_destructor(struct kdtree *tree, void (*destr)(void*))
161 {
162 tree->destr = destr;
163 }
166 static int insert_rec(struct kdnode **nptr, const double *pos, void *data, int dir, int dim)
167 {
168 int new_dir;
169 struct kdnode *node;
171 if(!*nptr) {
172 if(!(node = malloc(sizeof *node))) {
173 return -1;
174 }
175 if(!(node->pos = malloc(dim * sizeof *node->pos))) {
176 free(node);
177 return -1;
178 }
179 memcpy(node->pos, pos, dim * sizeof *node->pos);
180 node->data = data;
181 node->dir = dir;
182 node->left = node->right = 0;
183 *nptr = node;
184 return 0;
185 }
187 node = *nptr;
188 new_dir = (node->dir + 1) % dim;
189 if(pos[node->dir] < node->pos[node->dir]) {
190 return insert_rec(&(*nptr)->left, pos, data, new_dir, dim);
191 }
192 return insert_rec(&(*nptr)->right, pos, data, new_dir, dim);
193 }
195 int kd_insert(struct kdtree *tree, const double *pos, void *data)
196 {
197 if (insert_rec(&tree->root, pos, data, 0, tree->dim)) {
198 return -1;
199 }
201 if (tree->rect == 0) {
202 tree->rect = hyperrect_create(tree->dim, pos, pos);
203 } else {
204 hyperrect_extend(tree->rect, pos);
205 }
207 return 0;
208 }
210 int kd_insertf(struct kdtree *tree, const float *pos, void *data)
211 {
212 static double sbuf[16];
213 double *bptr, *buf = 0;
214 int res, dim = tree->dim;
216 if(dim > 16) {
217 #ifndef NO_ALLOCA
218 if(dim <= 256)
219 bptr = buf = alloca(dim * sizeof *bptr);
220 else
221 #endif
222 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
223 return -1;
224 }
225 } else {
226 bptr = buf = sbuf;
227 }
229 while(dim-- > 0) {
230 *bptr++ = *pos++;
231 }
233 res = kd_insert(tree, buf, data);
234 #ifndef NO_ALLOCA
235 if(tree->dim > 256)
236 #else
237 if(tree->dim > 16)
238 #endif
239 free(buf);
240 return res;
241 }
243 int kd_insert3(struct kdtree *tree, double x, double y, double z, void *data)
244 {
245 double buf[3];
246 buf[0] = x;
247 buf[1] = y;
248 buf[2] = z;
249 return kd_insert(tree, buf, data);
250 }
252 int kd_insert3f(struct kdtree *tree, float x, float y, float z, void *data)
253 {
254 double buf[3];
255 buf[0] = x;
256 buf[1] = y;
257 buf[2] = z;
258 return kd_insert(tree, buf, data);
259 }
261 static int find_nearest(struct kdnode *node, const double *pos, double range, struct res_node *list, int ordered, int dim)
262 {
263 double dist_sq, dx;
264 int i, ret, added_res = 0;
266 if(!node) return 0;
268 dist_sq = 0;
269 for(i=0; i<dim; i++) {
270 dist_sq += SQ(node->pos[i] - pos[i]);
271 }
272 if(dist_sq <= SQ(range)) {
273 if(rlist_insert(list, node, ordered ? dist_sq : -1.0) == -1) {
274 return -1;
275 }
276 added_res = 1;
277 }
279 dx = pos[node->dir] - node->pos[node->dir];
281 ret = find_nearest(dx <= 0.0 ? node->left : node->right, pos, range, list, ordered, dim);
282 if(ret >= 0 && fabs(dx) < range) {
283 added_res += ret;
284 ret = find_nearest(dx <= 0.0 ? node->right : node->left, pos, range, list, ordered, dim);
285 }
286 if(ret == -1) {
287 return -1;
288 }
289 added_res += ret;
291 return added_res;
292 }
294 #if 0
295 static int find_nearest_n(struct kdnode *node, const double *pos, double range, int num, struct rheap *heap, int dim)
296 {
297 double dist_sq, dx;
298 int i, ret, added_res = 0;
300 if(!node) return 0;
302 /* if the photon is close enough, add it to the result heap */
303 dist_sq = 0;
304 for(i=0; i<dim; i++) {
305 dist_sq += SQ(node->pos[i] - pos[i]);
306 }
307 if(dist_sq <= range_sq) {
308 if(heap->size >= num) {
309 /* get furthest element */
310 struct res_node *maxelem = rheap_get_max(heap);
312 /* and check if the new one is closer than that */
313 if(maxelem->dist_sq > dist_sq) {
314 rheap_remove_max(heap);
316 if(rheap_insert(heap, node, dist_sq) == -1) {
317 return -1;
318 }
319 added_res = 1;
321 range_sq = dist_sq;
322 }
323 } else {
324 if(rheap_insert(heap, node, dist_sq) == -1) {
325 return =1;
326 }
327 added_res = 1;
328 }
329 }
332 /* find signed distance from the splitting plane */
333 dx = pos[node->dir] - node->pos[node->dir];
335 ret = find_nearest_n(dx <= 0.0 ? node->left : node->right, pos, range, num, heap, dim);
336 if(ret >= 0 && fabs(dx) < range) {
337 added_res += ret;
338 ret = find_nearest_n(dx <= 0.0 ? node->right : node->left, pos, range, num, heap, dim);
339 }
341 }
342 #endif
344 static void kd_nearest_i(struct kdnode *node, const double *pos, struct kdnode **result, double *result_dist_sq, struct kdhyperrect* rect)
345 {
346 int dir = node->dir;
347 int i;
348 double dummy, dist_sq;
349 struct kdnode *nearer_subtree, *farther_subtree;
350 double *nearer_hyperrect_coord, *farther_hyperrect_coord;
352 /* Decide whether to go left or right in the tree */
353 dummy = pos[dir] - node->pos[dir];
354 if (dummy <= 0) {
355 nearer_subtree = node->left;
356 farther_subtree = node->right;
357 nearer_hyperrect_coord = rect->max + dir;
358 farther_hyperrect_coord = rect->min + dir;
359 } else {
360 nearer_subtree = node->right;
361 farther_subtree = node->left;
362 nearer_hyperrect_coord = rect->min + dir;
363 farther_hyperrect_coord = rect->max + dir;
364 }
366 if (nearer_subtree) {
367 /* Slice the hyperrect to get the hyperrect of the nearer subtree */
368 dummy = *nearer_hyperrect_coord;
369 *nearer_hyperrect_coord = node->pos[dir];
370 /* Recurse down into nearer subtree */
371 kd_nearest_i(nearer_subtree, pos, result, result_dist_sq, rect);
372 /* Undo the slice */
373 *nearer_hyperrect_coord = dummy;
374 }
376 /* Check the distance of the point at the current node, compare it
377 * with our best so far */
378 dist_sq = 0;
379 for(i=0; i < rect->dim; i++) {
380 dist_sq += SQ(node->pos[i] - pos[i]);
381 }
382 if (dist_sq < *result_dist_sq) {
383 *result = node;
384 *result_dist_sq = dist_sq;
385 }
387 if (farther_subtree) {
388 /* Get the hyperrect of the farther subtree */
389 dummy = *farther_hyperrect_coord;
390 *farther_hyperrect_coord = node->pos[dir];
391 /* Check if we have to recurse down by calculating the closest
392 * point of the hyperrect and see if it's closer than our
393 * minimum distance in result_dist_sq. */
394 if (hyperrect_dist_sq(rect, pos) < *result_dist_sq) {
395 /* Recurse down into farther subtree */
396 kd_nearest_i(farther_subtree, pos, result, result_dist_sq, rect);
397 }
398 /* Undo the slice on the hyperrect */
399 *farther_hyperrect_coord = dummy;
400 }
401 }
403 struct kdres *kd_nearest(struct kdtree *kd, const double *pos)
404 {
405 struct kdhyperrect *rect;
406 struct kdnode *result;
407 struct kdres *rset;
408 double dist_sq;
409 int i;
411 if (!kd) return 0;
412 if (!kd->rect) return 0;
414 /* Allocate result set */
415 if(!(rset = malloc(sizeof *rset))) {
416 return 0;
417 }
418 if(!(rset->rlist = alloc_resnode())) {
419 free(rset);
420 return 0;
421 }
422 rset->rlist->next = 0;
423 rset->tree = kd;
425 /* Duplicate the bounding hyperrectangle, we will work on the copy */
426 if (!(rect = hyperrect_duplicate(kd->rect))) {
427 kd_res_free(rset);
428 return 0;
429 }
431 /* Our first guesstimate is the root node */
432 result = kd->root;
433 dist_sq = 0;
434 for (i = 0; i < kd->dim; i++)
435 dist_sq += SQ(result->pos[i] - pos[i]);
437 /* Search for the nearest neighbour recursively */
438 kd_nearest_i(kd->root, pos, &result, &dist_sq, rect);
440 /* Free the copy of the hyperrect */
441 hyperrect_free(rect);
443 /* Store the result */
444 if (result) {
445 if (rlist_insert(rset->rlist, result, -1.0) == -1) {
446 kd_res_free(rset);
447 return 0;
448 }
449 rset->size = 1;
450 kd_res_rewind(rset);
451 return rset;
452 } else {
453 kd_res_free(rset);
454 return 0;
455 }
456 }
458 struct kdres *kd_nearestf(struct kdtree *tree, const float *pos)
459 {
460 static double sbuf[16];
461 double *bptr, *buf = 0;
462 int dim = tree->dim;
463 struct kdres *res;
465 if(dim > 16) {
466 #ifndef NO_ALLOCA
467 if(dim <= 256)
468 bptr = buf = alloca(dim * sizeof *bptr);
469 else
470 #endif
471 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
472 return 0;
473 }
474 } else {
475 bptr = buf = sbuf;
476 }
478 while(dim-- > 0) {
479 *bptr++ = *pos++;
480 }
482 res = kd_nearest(tree, buf);
483 #ifndef NO_ALLOCA
484 if(tree->dim > 256)
485 #else
486 if(tree->dim > 16)
487 #endif
488 free(buf);
489 return res;
490 }
492 struct kdres *kd_nearest3(struct kdtree *tree, double x, double y, double z)
493 {
494 double pos[3];
495 pos[0] = x;
496 pos[1] = y;
497 pos[2] = z;
498 return kd_nearest(tree, pos);
499 }
501 struct kdres *kd_nearest3f(struct kdtree *tree, float x, float y, float z)
502 {
503 double pos[3];
504 pos[0] = x;
505 pos[1] = y;
506 pos[2] = z;
507 return kd_nearest(tree, pos);
508 }
510 /* ---- nearest N search ---- */
511 /*
512 static kdres *kd_nearest_n(struct kdtree *kd, const double *pos, int num)
513 {
514 int ret;
515 struct kdres *rset;
517 if(!(rset = malloc(sizeof *rset))) {
518 return 0;
519 }
520 if(!(rset->rlist = alloc_resnode())) {
521 free(rset);
522 return 0;
523 }
524 rset->rlist->next = 0;
525 rset->tree = kd;
527 if((ret = find_nearest_n(kd->root, pos, range, num, rset->rlist, kd->dim)) == -1) {
528 kd_res_free(rset);
529 return 0;
530 }
531 rset->size = ret;
532 kd_res_rewind(rset);
533 return rset;
534 }*/
536 struct kdres *kd_nearest_range(struct kdtree *kd, const double *pos, double range)
537 {
538 int ret;
539 struct kdres *rset;
541 if(!(rset = malloc(sizeof *rset))) {
542 return 0;
543 }
544 if(!(rset->rlist = alloc_resnode())) {
545 free(rset);
546 return 0;
547 }
548 rset->rlist->next = 0;
549 rset->tree = kd;
551 if((ret = find_nearest(kd->root, pos, range, rset->rlist, 0, kd->dim)) == -1) {
552 kd_res_free(rset);
553 return 0;
554 }
555 rset->size = ret;
556 kd_res_rewind(rset);
557 return rset;
558 }
560 struct kdres *kd_nearest_rangef(struct kdtree *kd, const float *pos, float range)
561 {
562 static double sbuf[16];
563 double *bptr, *buf = 0;
564 int dim = kd->dim;
565 struct kdres *res;
567 if(dim > 16) {
568 #ifndef NO_ALLOCA
569 if(dim <= 256)
570 bptr = buf = alloca(dim * sizeof *bptr);
571 else
572 #endif
573 if(!(bptr = buf = malloc(dim * sizeof *bptr))) {
574 return 0;
575 }
576 } else {
577 bptr = buf = sbuf;
578 }
580 while(dim-- > 0) {
581 *bptr++ = *pos++;
582 }
584 res = kd_nearest_range(kd, buf, range);
585 #ifndef NO_ALLOCA
586 if(kd->dim > 256)
587 #else
588 if(kd->dim > 16)
589 #endif
590 free(buf);
591 return res;
592 }
594 struct kdres *kd_nearest_range3(struct kdtree *tree, double x, double y, double z, double range)
595 {
596 double buf[3];
597 buf[0] = x;
598 buf[1] = y;
599 buf[2] = z;
600 return kd_nearest_range(tree, buf, range);
601 }
603 struct kdres *kd_nearest_range3f(struct kdtree *tree, float x, float y, float z, float range)
604 {
605 double buf[3];
606 buf[0] = x;
607 buf[1] = y;
608 buf[2] = z;
609 return kd_nearest_range(tree, buf, range);
610 }
612 void kd_res_free(struct kdres *rset)
613 {
614 clear_results(rset);
615 free_resnode(rset->rlist);
616 free(rset);
617 }
619 int kd_res_size(struct kdres *set)
620 {
621 return (set->size);
622 }
624 void kd_res_rewind(struct kdres *rset)
625 {
626 rset->riter = rset->rlist->next;
627 }
629 int kd_res_end(struct kdres *rset)
630 {
631 return rset->riter == 0;
632 }
634 int kd_res_next(struct kdres *rset)
635 {
636 rset->riter = rset->riter->next;
637 return rset->riter != 0;
638 }
640 void *kd_res_item(struct kdres *rset, double *pos)
641 {
642 if(rset->riter) {
643 if(pos) {
644 memcpy(pos, rset->riter->item->pos, rset->tree->dim * sizeof *pos);
645 }
646 return rset->riter->item->data;
647 }
648 return 0;
649 }
651 void *kd_res_itemf(struct kdres *rset, float *pos)
652 {
653 if(rset->riter) {
654 if(pos) {
655 int i;
656 for(i=0; i<rset->tree->dim; i++) {
657 pos[i] = rset->riter->item->pos[i];
658 }
659 }
660 return rset->riter->item->data;
661 }
662 return 0;
663 }
665 void *kd_res_item3(struct kdres *rset, double *x, double *y, double *z)
666 {
667 if(rset->riter) {
668 if(*x) *x = rset->riter->item->pos[0];
669 if(*y) *y = rset->riter->item->pos[1];
670 if(*z) *z = rset->riter->item->pos[2];
671 }
672 return 0;
673 }
675 void *kd_res_item3f(struct kdres *rset, float *x, float *y, float *z)
676 {
677 if(rset->riter) {
678 if(*x) *x = rset->riter->item->pos[0];
679 if(*y) *y = rset->riter->item->pos[1];
680 if(*z) *z = rset->riter->item->pos[2];
681 }
682 return 0;
683 }
685 void *kd_res_item_data(struct kdres *set)
686 {
687 return kd_res_item(set, 0);
688 }
690 /* ---- hyperrectangle helpers ---- */
691 static struct kdhyperrect* hyperrect_create(int dim, const double *min, const double *max)
692 {
693 size_t size = dim * sizeof(double);
694 struct kdhyperrect* rect = 0;
696 if (!(rect = malloc(sizeof(struct kdhyperrect)))) {
697 return 0;
698 }
700 rect->dim = dim;
701 if (!(rect->min = malloc(size))) {
702 free(rect);
703 return 0;
704 }
705 if (!(rect->max = malloc(size))) {
706 free(rect->min);
707 free(rect);
708 return 0;
709 }
710 memcpy(rect->min, min, size);
711 memcpy(rect->max, max, size);
713 return rect;
714 }
716 static void hyperrect_free(struct kdhyperrect *rect)
717 {
718 free(rect->min);
719 free(rect->max);
720 free(rect);
721 }
723 static struct kdhyperrect* hyperrect_duplicate(const struct kdhyperrect *rect)
724 {
725 return hyperrect_create(rect->dim, rect->min, rect->max);
726 }
728 static void hyperrect_extend(struct kdhyperrect *rect, const double *pos)
729 {
730 int i;
732 for (i=0; i < rect->dim; i++) {
733 if (pos[i] < rect->min[i]) {
734 rect->min[i] = pos[i];
735 }
736 if (pos[i] > rect->max[i]) {
737 rect->max[i] = pos[i];
738 }
739 }
740 }
742 static double hyperrect_dist_sq(struct kdhyperrect *rect, const double *pos)
743 {
744 int i;
745 double result = 0;
747 for (i=0; i < rect->dim; i++) {
748 if (pos[i] < rect->min[i]) {
749 result += SQ(rect->min[i] - pos[i]);
750 } else if (pos[i] > rect->max[i]) {
751 result += SQ(rect->max[i] - pos[i]);
752 }
753 }
755 return result;
756 }
758 /* ---- static helpers ---- */
760 #ifdef USE_LIST_NODE_ALLOCATOR
761 /* special list node allocators. */
762 static struct res_node *free_nodes;
764 #ifndef NO_PTHREADS
765 static pthread_mutex_t alloc_mutex = PTHREAD_MUTEX_INITIALIZER;
766 #endif
768 static struct res_node *alloc_resnode(void)
769 {
770 struct res_node *node;
772 #ifndef NO_PTHREADS
773 pthread_mutex_lock(&alloc_mutex);
774 #endif
776 if(!free_nodes) {
777 node = malloc(sizeof *node);
778 } else {
779 node = free_nodes;
780 free_nodes = free_nodes->next;
781 node->next = 0;
782 }
784 #ifndef NO_PTHREADS
785 pthread_mutex_unlock(&alloc_mutex);
786 #endif
788 return node;
789 }
791 static void free_resnode(struct res_node *node)
792 {
793 #ifndef NO_PTHREADS
794 pthread_mutex_lock(&alloc_mutex);
795 #endif
797 node->next = free_nodes;
798 free_nodes = node;
800 #ifndef NO_PTHREADS
801 pthread_mutex_unlock(&alloc_mutex);
802 #endif
803 }
804 #endif /* list node allocator or not */
807 /* inserts the item. if dist_sq is >= 0, then do an ordered insert */
808 /* TODO make the ordering code use heapsort */
809 static int rlist_insert(struct res_node *list, struct kdnode *item, double dist_sq)
810 {
811 struct res_node *rnode;
813 if(!(rnode = alloc_resnode())) {
814 return -1;
815 }
816 rnode->item = item;
817 rnode->dist_sq = dist_sq;
819 if(dist_sq >= 0.0) {
820 while(list->next && list->next->dist_sq < dist_sq) {
821 list = list->next;
822 }
823 }
824 rnode->next = list->next;
825 list->next = rnode;
826 return 0;
827 }
829 static void clear_results(struct kdres *rset)
830 {
831 struct res_node *tmp, *node = rset->rlist->next;
833 while(node) {
834 tmp = node;
835 node = node->next;
836 free_resnode(tmp);
837 }
839 rset->rlist->next = 0;
840 }