1 /* tree.c
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * File Name: tree.c
27 *
28 * Author: Vladimir Soussov
29 *
30 * File Description: tree manager functions
31 *
32 *
33 * $Log: tree.c,v $
34 * Revision 1.11 2000/08/15 14:34:33 soussov
35 * fixes bug in tree_getAncestor
36 *
37 * Revision 1.10 2000/08/14 16:05:30 soussov
38 * improvements in tree_getAncestor
39 *
40 * Revision 1.9 2000/08/07 14:32:04 soussov
41 * fixes bug in tree_getAncestor function
42 *
43 * Revision 1.8 1999/05/18 21:13:47 soussov
44 * TREE_SHUTDOWN event added
45 *
46 * Revision 1.7 1998/08/24 18:04:15 kans
47 * added continue statements to empty for loops to suppress Mac warnings
48 *
49 * Revision 1.6 1998/08/24 17:42:04 kans
50 * fixed old style function definition warnings
51 *
52 * Revision 1.5 1998/07/02 18:24:29 vakatov
53 * Cleaned the code & made it pass through the C++ compilation
54 *
55 * Revision 1.4 1998/06/23 16:33:49 vakatov
56 * [WIN32,MSVC++] Made the tree API functions DLL-exportable
57 *
58 * Revision 1.3 1998/04/02 22:30:26 soussov
59 * Some prototype added to make Denis happy
60 *
61 * Revision 1.2 1998/04/01 17:48:06 soussov
62 * changed tp include <>
63 *
64 * Revision 1.1 1998/03/31 21:22:25 sirotkin
65 * With Vladimir - moved from distrib/internal/taxonomy/tree
66 *
67 * Revision 6.0 1997/08/25 18:29:47 madden
68 * Revision changed to 6.0
69 *
70 * Revision 1.1 1997/05/30 16:16:16 soussov
71 * Set of files for ncbitree library
72 *
73 * Revision 1.1 1997/05/29 20:44:26 soussov
74 * Initial version of tree library
75 *
76 *
77 */
78
79 #include <treemgr.h>
80
notify(TreePtr tree,TreeEvent tevent,_NodeId id1,_NodeId id2,VoidPtr data,Int2 d_size)81 static void notify(TreePtr tree, TreeEvent tevent, _NodeId id1, _NodeId id2, VoidPtr data, Int2 d_size)
82 {
83 int i;
84
85 for(i= 0; i < TREE_NOF_SPIES; i++) {
86 if(tree->spy[i] != NULL) {
87 (*(tree->spy[i]))(tree, i, tevent, id1, id2, data, d_size);
88 }
89 }
90 }
91
tree_Message(CharPtr str1,CharPtr str2,Int2 msg_type)92 static void tree_Message(CharPtr str1, CharPtr str2, Int2 msg_type)
93 {
94 fprintf(stderr, "Function %s :\t%s\n", str1, str2);
95 }
96
tree_toNode(TreeCursorPtr cursor,_NodeId id)97 NLM_EXTERN Boolean tree_toNode(TreeCursorPtr cursor, _NodeId id)
98 {
99 _BagStore bstore;
100 _NodeBagPtr bag;
101
102 if(id.idi == 0) return FALSE; /* empty id */
103 if(cursor->node_id.idi == id.idi) {
104 return TRUE; /* same node */
105 }
106
107 if((cursor->node_id.idi != 0) &&
108 (cursor->node_id.id4.bag_store == id.id4.bag_store) &&
109 (cursor->node_id.id4.bag == id.id4.bag)) {
110 /* we are looking for node from the same bag */
111
112 bag= cursor->cbag;
113 if(((bag->node[id.id4.node].flags & TREE_FREE_ROOM) != 0) ||
114 (bag->node[id.id4.node].vers != id.id4.vers)) {
115 return FALSE;
116 }
117
118 }
119 else {
120
121 if(((bstore= cursor->tree->bag_store[id.id4.bag_store]) == NULL) ||
122 ((bag= bstore[id.id4.bag]) == NULL) ||
123 ((bag->node[id.id4.node].flags & TREE_FREE_ROOM) != 0) ||
124 (bag->node[id.id4.node].vers != id.id4.vers)) {
125
126 /* node does not exist */
127 return FALSE;
128 }
129 }
130
131 if(bag->node[id.id4.node].flags & TREE_MERGED_NODE) {
132 /* this node has been merged */
133 return tree_toNode(cursor, bag->node[id.id4.node].sibling);
134 }
135
136 cursor->prev_id= cursor->node_id;
137 cursor->node_id= id;
138 cursor->node= bag->node + id.id4.node;
139 cursor->cbag= bag;
140 if(cursor->callBack != NULL) {
141 (*(cursor->callBack))(cursor, TREE_CURSOR_MOVED, id);
142 }
143 return TRUE;
144 }
145
tree_root(TreeCursorPtr cursor)146 NLM_EXTERN Boolean tree_root(TreeCursorPtr cursor)
147 {
148 return tree_toNode(cursor, cursor->tree->rootNodeId);
149 }
150
tree_parent(TreeCursorPtr cursor)151 NLM_EXTERN Boolean tree_parent(TreeCursorPtr cursor)
152 {
153
154 if(cursor->node_id.idi == cursor->tree->rootNodeId.idi) return FALSE;
155
156 return tree_toNode(cursor, cursor->node->parent);
157 }
158
tree_sibling(TreeCursorPtr cursor)159 NLM_EXTERN Boolean tree_sibling(TreeCursorPtr cursor)
160 {
161 return tree_toNode(cursor, cursor->node->sibling);
162 }
163
tree_child(TreeCursorPtr cursor)164 NLM_EXTERN Boolean tree_child(TreeCursorPtr cursor)
165 {
166 return tree_toNode(cursor, cursor->node->child);
167 }
168
169
170 /**********************************************
171 * Open cursor and set it on a root node.
172 * You can provide an optional callback function
173 * Tree manager calls this callBack function in following cases:
174 * - cursor has been moved
175 * - node under cursor is going to be deleted, updated, moved or merged using another cursor
176 *
177 * callBack function should be defined as
178 * void callBackFunc(TreeCursorPtr cursor, TreeEvent event, TreeNodeId id //optional);
179 */
180
tree_openCursor(TreePtr tree,VoidPtr userDataPointer,TreeCursorCBFunc callBack)181 NLM_EXTERN TreeCursorPtr tree_openCursor(TreePtr tree,
182 VoidPtr userDataPointer,
183 TreeCursorCBFunc callBack)
184 {
185 TreeCursorPtr cursor;
186
187 if((cursor= (TreeCursorPtr)MemNew(sizeof(TreeCursor))) == NULL) {
188 tree_Message("tree_openCursor", "Not enaugh memory", NO_MEM_MSG);
189 return NULL;
190 }
191
192 cursor->tree= tree;
193 cursor->next_cursor= tree->cursor;
194 tree->cursor= cursor;
195 cursor->node_id.idi= 0;
196 cursor->callBack= NULL;
197 tree_toNode(cursor, tree->rootNodeId);
198 cursor->prev_id= cursor->node_id;
199 cursor->callBack= callBack;
200 cursor->user_data= userDataPointer;
201 return cursor;
202 }
203
204 /**********************************************
205 * Close cursor
206 */
tree_closeCursor(TreeCursorPtr cursor)207 NLM_EXTERN void tree_closeCursor(TreeCursorPtr cursor)
208 {
209 TreeCursorPtr crs;
210
211 if(cursor == NULL) return;
212
213 if(cursor->tree->cursor == cursor) {
214 cursor->tree->cursor= cursor->next_cursor;
215 MemFree(cursor);
216 }
217 else {
218 for(crs= cursor->tree->cursor; crs != NULL; crs= crs->next_cursor) {
219 if(crs->next_cursor == cursor) {
220 crs->next_cursor= cursor->next_cursor;
221 MemFree(cursor);
222 return;
223 }
224 }
225 }
226 }
227
228 /***********************************************
229 * Get user data associated with a cursor
230 */
tree_getUserData(TreeCursorPtr cursor)231 NLM_EXTERN VoidPtr tree_getUserData(TreeCursorPtr cursor)
232 {
233 return (cursor != NULL)? cursor->user_data : NULL;
234 }
235
236 /***********************************************
237 * Get node id
238 */
tree_getId(TreeCursorPtr cursor)239 NLM_EXTERN TreeNodeId tree_getId(TreeCursorPtr cursor)
240 {
241 if(cursor != NULL) return cursor->node_id;
242 else {
243 _NodeId id;
244
245 id.idi= 0;
246 return id;
247 }
248 }
249
250
tree_getAncestor(TreeCursorPtr cursor1,TreeCursorPtr cursor2)251 NLM_EXTERN _NodeId tree_getAncestor(TreeCursorPtr cursor1,
252 TreeCursorPtr cursor2)
253 {
254 _NodeId aId;
255
256 aId.idi= 0;
257
258 if(cursor1->tree == cursor2->tree) {
259 TreeCursorPtr t_cursor= tree_openCursor(cursor1->tree, NULL, NULL);
260 _NodeId *lin1;
261 _NodeId *lin2;
262 int l1, l2, s1= 64, s2= 64;
263
264 /* build lineage for cursor1 */
265 lin1= (_NodeId *)MemNew(sizeof(_NodeId)*s1);
266 if(lin1 == NULL) {
267 tree_Message("tree_getAncestor", "Not enaugh memory", NO_MEM_MSG);
268 return aId;
269 }
270
271 tree_toNode(t_cursor, cursor1->node_id);
272
273 for(l1= 0; tree_parent(t_cursor); l1++) {
274 if(l1 >= s1) {
275 s1+= s1/2;
276 lin1= (_NodeId *)MemMore(lin1, sizeof(_NodeId)*s1);
277 if(lin1 == NULL) {
278 tree_Message("tree_getAncestor", "Not enaugh memory", NO_MEM_MSG);
279 return aId;
280 }
281 }
282 lin1[l1]= t_cursor->node_id;
283 }
284 s1= l1;
285
286 /* check lin1 against cursor2 */
287 for(l1= 0; l1 < s1; l1++) {
288 if(lin1[l1].idi == cursor2->node_id.idi) {
289 MemFree(lin1);
290 tree_closeCursor(t_cursor);
291 return cursor2->node_id;
292 }
293 }
294
295 /* build lineage for cursor2 */
296 lin2= (_NodeId *)MemNew(sizeof(_NodeId)*s2);
297 if(lin2 == NULL) {
298 tree_Message("tree_getAncestor", "Not enaugh memory", NO_MEM_MSG);
299 return aId;
300 }
301
302 tree_toNode(t_cursor, cursor2->node_id);
303
304 for(l2= 0; tree_parent(t_cursor); l2++) {
305 if(l2 >= s2) {
306 s2+= s2/2;
307 lin2= (_NodeId *)MemMore(lin2, sizeof(_NodeId)*s2);
308 if(lin2 == NULL) {
309 tree_Message("tree_getAncestor", "Not enaugh memory", NO_MEM_MSG);
310 return aId;
311 }
312 }
313 lin2[l2]= t_cursor->node_id;
314 }
315 s2= l2;
316
317 /* check lin2 against cursor1 */
318 for(l2= 0; l2 < s2; l2++) {
319 if(lin2[l2].idi == cursor1->node_id.idi) {
320 MemFree(lin1);
321 MemFree(lin2);
322 tree_closeCursor(t_cursor);
323 return cursor1->node_id;
324 }
325 }
326
327 /* check lineages */
328 for(l1= s1, l2= s2; (--l1 > 0) && (--l2 > 0);) {
329 if(lin1[l1-1].idi != lin2[l2-1].idi) {
330 aId= lin1[l1];
331 break;
332 }
333 }
334 if(aId.idi == 0) aId= lin1[l1];
335 MemFree(lin1);
336 MemFree(lin2);
337 tree_closeCursor(t_cursor);
338 }
339
340 return aId;
341
342 }
343
detach_subtree(TreeCursorPtr cursor)344 static void detach_subtree(TreeCursorPtr cursor)
345 {
346 TreeCursorPtr t_cursor= tree_openCursor(cursor->tree, NULL, NULL);
347
348 tree_toNode(t_cursor, cursor->node->parent);
349 if(t_cursor->node->child.idi == cursor->node_id.idi) {
350 /* this is a first child */
351 t_cursor->node->child= cursor->node->sibling;
352 }
353 else {
354 Boolean cont= TRUE;
355
356 for(tree_child(t_cursor);
357 cont && (t_cursor->node->sibling.idi != cursor->node_id.idi);
358 cont= tree_sibling(t_cursor)) continue;
359
360 if(cont) {
361 t_cursor->node->sibling= cursor->node->sibling;
362 }
363 else {
364 fprintf(stderr, "detach_subtree: Tree structure corrupted\n");
365 }
366 }
367
368 tree_closeCursor(t_cursor);
369 }
370
371
372
tree_moveNode(TreeCursorPtr cursor1,TreeCursorPtr cursor2)373 NLM_EXTERN Boolean tree_moveNode(TreeCursorPtr cursor1, TreeCursorPtr cursor2)
374 {
375 _NodeId aId= tree_getAncestor(cursor1, cursor2);
376 _NodePtr cnode;
377 _NodePtr pnode;
378
379 if(aId.idi == cursor2->node_id.idi) return FALSE; /* to prevent loop */
380
381 if(cursor2->tree->nof_spies > 0) {
382 notify(cursor2->tree, TREE_NODE_MOVE, cursor1->node_id, cursor2->node_id, NULL, 0);
383 }
384
385 detach_subtree(cursor2);
386
387 cnode= cursor2->node;
388 pnode= cursor1->node;
389
390 cnode->sibling= pnode->child;
391 pnode->child= cursor2->node_id;
392 cnode->parent= cursor1->node_id;
393
394 if(cursor2->tree->nof_spies > 0) {
395 notify(cursor2->tree, TREE_NODE_MV_DONE, cursor1->node_id, cursor2->node_id, NULL, 0);
396 }
397
398 return TRUE;
399 }
400
tree_moveChildren(TreeCursorPtr cursor1,TreeCursorPtr cursor2)401 NLM_EXTERN Boolean tree_moveChildren(TreeCursorPtr cursor1,
402 TreeCursorPtr cursor2)
403 {
404 _NodeId aId= tree_getAncestor(cursor1, cursor2);
405 TreeCursorPtr t_cursor;
406 Boolean cnt, flg= FALSE;
407
408
409 if(aId.idi == cursor2->node_id.idi) return FALSE; /* to prevent loop */
410
411 if(cursor2->node->child.idi == 0) return TRUE; /* no children */
412
413 if(cursor2->tree->nof_spies > 0) {
414 notify(cursor2->tree, TREE_CHILDREN_MOVE, cursor1->node_id, cursor2->node_id, NULL, 0);
415 }
416
417 t_cursor= tree_openCursor(cursor2->tree, NULL, NULL);
418
419 for(cnt= tree_toNode(t_cursor, cursor2->node->child); cnt; cnt= tree_sibling(t_cursor)) {
420 t_cursor->node->parent= cursor1->node_id;
421 flg= TRUE;
422 }
423
424 if(flg) {
425 t_cursor->node->sibling= cursor1->node->child;
426 cursor1->node->child= cursor2->node->child;
427 cursor2->node->child.idi= 0;
428 }
429
430 if(cursor2->tree->nof_spies > 0) {
431 notify(cursor2->tree, TREE_CHILDREN_MV_DONE, cursor1->node_id, cursor2->node_id, NULL, 0);
432 }
433
434 return TRUE;
435 }
436
add_node(TreeCursorPtr cursor,_NodeBagPtr bag,_NodeId new_id,VoidPtr node_data,Uint2 data_size)437 static _NodeId add_node(TreeCursorPtr cursor, _NodeBagPtr bag, _NodeId new_id,
438 VoidPtr node_data, Uint2 data_size)
439 {
440 _NodePtr nnode= bag->node + new_id.id4.node;
441
442 nnode->parent= cursor->node_id;
443 nnode->child.idi= 0;
444 nnode->sibling= cursor->node->child;
445 nnode->flags^= TREE_FREE_ROOM;
446 nnode->sys_data= NULL;
447 new_id.id4.vers= ++nnode->vers;
448 cursor->node->child= new_id;
449 bag->nof_nodes++;
450 if(data_size <= sizeof(_NodeData)) {
451 memcpy(&nnode->data, node_data, data_size);
452 }
453 else {
454 nnode->data= MemNew(data_size);
455 memcpy(nnode->data, node_data, data_size);
456 }
457 nnode->size= data_size;
458
459 if(cursor->tree->nof_spies > 0) {
460 notify(cursor->tree, TREE_NODE_ADDED, cursor->node_id, new_id, node_data, data_size);
461 }
462
463 return new_id;
464 }
465
466
tree_addChild(TreeCursorPtr cursor,VoidPtr node_data,Uint2 node_data_size)467 NLM_EXTERN _NodeId tree_addChild(TreeCursorPtr cursor, VoidPtr node_data, Uint2 node_data_size)
468 {
469 int i;
470 _NodeBagPtr bag= cursor->cbag;
471 _NodeId new_id;
472 _BagStore bstore;
473 int j, k;
474
475 if(bag->nof_nodes < NODE_BAG_SIZE) {
476 /* there is a room in current bag */
477 for(i= 0; i != NODE_BAG_SIZE; i++) {
478 if((bag->node[i].flags & TREE_FREE_ROOM) != 0) break; /* free room */
479 }
480 if(i < NODE_BAG_SIZE) {
481 /* free room was found */
482 new_id= cursor->node_id;
483 new_id.id4.node= i;
484 return add_node(cursor, bag, new_id, node_data, node_data_size);
485 }
486 else {
487 bag->nof_nodes= NODE_BAG_SIZE;
488 }
489 }
490
491 /* there is no room in current bag */
492
493 /* try the current store first */
494 bstore= bag->my_bag_store;
495
496 for(i= 0; i != NODE_BAG_SIZE; i++) {
497 if((bstore[i] != NULL) && (bstore[i]->nof_nodes < NODE_BAG_SIZE)) {
498 bag= bstore[i];
499 for(j= 0; j != NODE_BAG_SIZE; j++) {
500 if((bag->node[j].flags & TREE_FREE_ROOM) != 0) break; /* free room */
501 }
502 if(j < NODE_BAG_SIZE) {
503 /* free room was found */
504 new_id= cursor->node_id;
505 new_id.id4.bag= i;
506 new_id.id4.node= j;
507 return add_node(cursor, bag, new_id, node_data, node_data_size);
508 }
509 else {
510 bag->nof_nodes= NODE_BAG_SIZE;
511 }
512 }
513 }
514
515 /* there is no room in current bag store */
516 /* try all non-empty bag stores */
517 for(k= 0; k != NOF_BAGS; k++) {
518 if((bstore= cursor->tree->bag_store[k]) != NULL) {
519 for(i= 0; i != NODE_BAG_SIZE; i++) {
520 if((bstore[i] != NULL) && (bstore[i]->nof_nodes < NODE_BAG_SIZE)) {
521 bag= bstore[i];
522 for(j= 0; j != NODE_BAG_SIZE; j++) {
523 if((bag->node[j].flags & TREE_FREE_ROOM) != 0) break; /* free room */
524 }
525 if(j < NODE_BAG_SIZE) {
526 /* free room was found */
527 new_id.id4.bag_store= k;
528 new_id.id4.bag= i;
529 new_id.id4.node= j;
530 return add_node(cursor, bag, new_id, node_data, node_data_size);
531 }
532 else {
533 bag->nof_nodes= NODE_BAG_SIZE;
534 }
535 }
536 }
537 }
538 }
539
540 /* we need the new bag */
541 k= cursor->tree->id4NewNode.id4.bag_store;
542 j= cursor->tree->id4NewNode.id4.bag;
543
544 if(++j >= NODE_BAG_SIZE) {
545 /* all bags in last bag store are used, we need new bag store */
546 if(++k >= NOF_BAGS) {
547 /* there are no more bag store available */
548 new_id.idi= 0;
549 return new_id;
550 }
551 /* allocate the new bag_store */
552 if((bstore= (_NodeBagPtr*)MemNew(NODE_BAG_SIZE*sizeof(_NodeBagPtr))) == NULL) {
553 /* no memory */
554 new_id.idi= 0;
555 return new_id;
556 }
557 cursor->tree->bag_store[k]= bstore;
558 cursor->tree->id4NewNode.id4.bag_store= k;
559
560 for(i= 0; i != NODE_BAG_SIZE; bstore[i++]= NULL) continue;
561 j= 0;
562 cursor->tree->id4NewNode.id4.bag= 0;
563 }
564 else {
565 bstore= cursor->tree->bag_store[k];
566 }
567
568 if((bag= bstore[j]= (_NodeBagPtr)MemNew(sizeof(_NodeBag))) == NULL) {
569 /* no memory */
570 new_id.idi= 0;
571 return new_id;
572 }
573
574
575 bag->nof_nodes= 0;
576 bag->my_bag_store= bstore;
577
578 for(i= 0; i != NODE_BAG_SIZE; i++) {
579 bag->node[i].flags= TREE_FREE_ROOM;
580 bag->node[i].vers= 0;
581 }
582
583 new_id.idi= cursor->tree->id4NewNode.idi;
584 new_id.id4.node= 0;
585 new_id.id4.bag= cursor->tree->id4NewNode.id4.bag= j;
586 return add_node(cursor, bag, new_id, node_data, node_data_size);
587 }
588
589
tree_delNode(TreeCursorPtr cursor)590 NLM_EXTERN Boolean tree_delNode(TreeCursorPtr cursor)
591 {
592 TreeCursorPtr t_cursor;
593 _NodeId pid;
594
595 if(cursor->node_id.idi == cursor->tree->rootNodeId.idi) return FALSE; /* can not remove root */
596
597 pid= cursor->node->parent;
598
599
600 for(t_cursor= cursor->tree->cursor; t_cursor != NULL; t_cursor= t_cursor->next_cursor) {
601 if((t_cursor != cursor) && (t_cursor->node == cursor->node)) {
602 if(t_cursor->callBack != NULL) {
603 (*(t_cursor->callBack))(t_cursor, TREE_NODE_DELETE, cursor->node_id);
604
605 if(t_cursor->node == cursor->node) {
606 tree_toNode(t_cursor, pid);
607 }
608 }
609 else {
610 tree_toNode(t_cursor, pid);
611 }
612 }
613 }
614
615
616 t_cursor= tree_openCursor(cursor->tree, NULL, NULL);
617 tree_toNode(t_cursor, pid);
618
619 tree_moveChildren(t_cursor, cursor);
620
621 tree_closeCursor(t_cursor);
622
623 if(cursor->tree->nof_spies > 0) {
624 notify(cursor->tree, TREE_NODE_DELETE, cursor->node_id, pid, NULL, 0);
625 }
626
627 detach_subtree(cursor);
628
629 if(cursor->node->size > sizeof(_NodeData)) {
630 /* free node data if allocated separatelly */
631 MemFree(cursor->node->data);
632 }
633
634 if(cursor->node->vers < 255) {
635 /* we can reuse this room in the future */
636 cursor->node->flags|= TREE_FREE_ROOM;
637 cursor->cbag->nof_nodes--;
638 }
639 else { /* we can not reuse this room */
640 int i;
641
642 cursor->node->vers= 0;
643 for(i= 0; i != NODE_BAG_SIZE; i++) {
644 if((cursor->cbag->node[i].vers != 0) ||
645 ((cursor->cbag->node[i].flags & TREE_FREE_ROOM) != 0)) break;
646 }
647
648 if(i == NODE_BAG_SIZE) { /* all rooms in this bag are empty */
649 _BagStore bs= cursor->cbag->my_bag_store;
650
651 i= cursor->node_id.id4.bag;
652 MemFree(bs[i]);
653 bs[i]= NULL;
654 }
655 }
656
657 tree_toNode(cursor, pid);
658
659 if(cursor->tree->nof_spies > 0) {
660 notify(cursor->tree, TREE_NODE_DEL_DONE, cursor->node_id, pid, NULL, 0);
661 }
662
663 return TRUE;
664 }
665
666 /* recursion function to delete nodes from subtree */
del_subtreeNodes(TreeCursorPtr cursor)667 static void del_subtreeNodes(TreeCursorPtr cursor)
668 {
669 _NodeId nid, sid;
670
671 nid= cursor->node_id;
672
673 if(tree_child(cursor)) {
674 do {
675 sid= cursor->node->sibling;
676 del_subtreeNodes(cursor);
677 }
678 while(tree_toNode(cursor, sid));
679 }
680
681 tree_toNode(cursor, nid);
682
683 if(cursor->node->size > sizeof(_NodeData)) {
684 /* free node data if allocated separatelly */
685 MemFree(cursor->node->data);
686 }
687
688 if(cursor->node->vers < 255) {
689 /* we can reuse this room in the future */
690 cursor->node->flags|= TREE_FREE_ROOM;
691 cursor->cbag->nof_nodes--;
692 }
693 else { /* we can not reuse this room */
694 int i;
695
696 cursor->node->vers= 0;
697 for(i= 0; i != NODE_BAG_SIZE; i++) {
698 if((cursor->cbag->node[i].vers != 0) ||
699 ((cursor->cbag->node[i].flags & TREE_FREE_ROOM) != 0)) break;
700 }
701
702 if(i == NODE_BAG_SIZE) { /* all rooms in this bag are empty */
703 _BagStore bs= cursor->cbag->my_bag_store;
704
705 i= cursor->node_id.id4.bag;
706 MemFree(bs[i]);
707 bs[i]= NULL;
708 }
709 }
710 }
711
712
713
714
tree_delSubtree(TreeCursorPtr cursor)715 NLM_EXTERN Boolean tree_delSubtree(TreeCursorPtr cursor)
716 {
717 TreeCursorPtr t_cursor;
718 TreeCursorPtr crs;
719 _NodeId pid;
720 Boolean res;
721
722 if(cursor->node_id.idi == cursor->tree->rootNodeId.idi) return FALSE; /* can not remove root */
723
724 pid= cursor->node->parent;
725
726 if(cursor->tree->nof_spies > 0) {
727 notify(cursor->tree, TREE_SUBTREE_DELETE, cursor->node_id, pid, NULL, 0);
728 }
729
730 crs= tree_openCursor(cursor->tree, NULL, NULL);
731
732 /* shovl cursors from deleting subtree */
733 for(t_cursor= cursor->tree->cursor; t_cursor != NULL; t_cursor= t_cursor->next_cursor) {
734 if((t_cursor != cursor) && (t_cursor != crs)) {
735 for(res= tree_toNode(crs, t_cursor->node_id); res; res= tree_parent(crs)) {
736 if(crs->node_id.idi == cursor->node_id.idi) break;
737 }
738
739 if(res) {
740 if(t_cursor->callBack != NULL) {
741 (*(t_cursor->callBack))(t_cursor, TREE_NODE_DELETE, cursor->node_id);
742
743 for(res= tree_toNode(crs, t_cursor->node_id); res; res= tree_parent(crs)) {
744 if(crs->node_id.idi == cursor->node_id.idi) break;
745 }
746
747 if(res) {
748 tree_toNode(t_cursor, pid);
749 }
750 }
751 else {
752 tree_toNode(t_cursor, pid);
753 }
754 }
755 }
756 }
757
758 /* remove nodes */
759
760 detach_subtree(cursor);
761
762 tree_toNode(crs, cursor->node_id);
763 del_subtreeNodes(crs);
764
765 tree_closeCursor(crs);
766
767
768 if(cursor->tree->nof_spies > 0) {
769 notify(cursor->tree, TREE_SUBTREE_DEL_DONE, cursor->node_id, pid, NULL, 0);
770 }
771
772 return tree_toNode(cursor, cursor->node->parent);
773 }
774
tree_merge(TreeCursorPtr cursor1,TreeCursorPtr cursor2)775 NLM_EXTERN Boolean tree_merge(TreeCursorPtr cursor1, TreeCursorPtr cursor2)
776 {
777 _NodeId aId= tree_getAncestor(cursor1, cursor2);
778 TreeCursorPtr p_crs;
779
780 if(aId.idi == cursor2->node_id.idi) return FALSE; /* to prevent loop */
781
782 if(cursor2->tree->nof_spies > 0) {
783 notify(cursor2->tree, TREE_NODE_MERGE, cursor1->node_id, cursor2->node_id, NULL, 0);
784 }
785
786 /* Notify and move out all cursors which point to cursor2->node_id */
787 for(p_crs= cursor2->tree->cursor; p_crs != NULL; p_crs= p_crs->next_cursor) {
788 if((p_crs->node == cursor2->node) && (p_crs != cursor2)) {
789 if(p_crs->callBack != NULL) {
790 (*(p_crs->callBack))(p_crs, TREE_NODE_MERGE, cursor1->node_id);
791 if(p_crs->node == cursor2->node) {
792 tree_toNode(p_crs, cursor1->node_id);
793 }
794 }
795 else {
796 tree_toNode(p_crs, cursor1->node_id);
797 }
798 }
799 }
800
801 tree_moveChildren(cursor1, cursor2);
802 detach_subtree(cursor2);
803 cursor2->node->flags|= TREE_MERGED_NODE;
804 cursor2->node->sibling= cursor1->node_id;
805
806 if(cursor2->tree->nof_spies > 0) {
807 notify(cursor2->tree, TREE_NODE_MERGE_DONE, cursor1->node_id, cursor2->node->parent, NULL, 0);
808 }
809
810 return tree_toNode(cursor2, cursor1->node_id);
811 }
812
813
814 /**********************************************
815 * Create new tree and add root node to it
816 *
817 */
tree_new(void)818 NLM_EXTERN TreePtr tree_new(void)
819 {
820 TreePtr ntree;
821 _BagStore bs;
822 int i;
823
824 if((ntree= (TreePtr)MemNew(sizeof(Tree))) == NULL) {
825 tree_Message("tree_new", "Not enaugh memory", NO_MEM_MSG);
826 return NULL;
827 }
828
829 ntree->cursor= NULL;
830 ntree->get_func= NULL;
831 ntree->update_func= NULL;
832 ntree->save_func= NULL;
833
834 for(i= 0; i < TREE_NOF_SPIES; ntree->spy[i++]= NULL) continue;
835
836 ntree->nof_spies= 0;
837
838 for(i= 1; i != NOF_BAGS; ntree->bag_store[i++]= NULL) continue;
839
840 if((ntree->bag_store[0]= bs= (_BagStore)MemNew(sizeof(_NodeBagPtr)*NODE_BAG_SIZE)) == NULL) {
841 tree_Message("tree_new", "Not enaugh memory", NO_MEM_MSG);
842 return NULL;
843 }
844
845 for(i= 1; i != NODE_BAG_SIZE; bs[i++]= NULL) continue;
846
847 if((bs[0]= (_NodeBagPtr)MemNew(sizeof(_NodeBag))) == NULL) {
848 tree_Message("tree_new", "Not enaugh memory", NO_MEM_MSG);
849 return NULL;
850 }
851
852 bs[0]->nof_nodes= 1;
853 bs[0]->my_bag_store= bs;
854
855 for(i= 1; i != NODE_BAG_SIZE; i++) {
856 bs[0]->node[i].vers= 0;
857 bs[0]->node[i].flags= TREE_FREE_ROOM;
858 }
859
860 /* setup root node */
861
862 bs[0]->node[0].parent.idi= bs[0]->node[0].child.idi= bs[0]->node[0].sibling.idi= 0;
863 bs[0]->node[0].size= 0;
864 bs[0]->node[0].vers= 1;
865 bs[0]->node[0].flags= 0;
866
867 ntree->rootNodeId.id4.bag_store= 0;
868 ntree->rootNodeId.id4.bag= 0;
869 ntree->rootNodeId.id4.node= 0;
870 ntree->rootNodeId.id4.vers= 1;
871
872 ntree->id4NewNode= ntree->rootNodeId;
873
874 return ntree;
875 }
876
877 /**********************************************
878 * Delete tree
879 */
freeNodeData(TreeCursorPtr cursor)880 static void freeNodeData(TreeCursorPtr cursor)
881 {
882 if(cursor->node->size > sizeof(_NodeData)) MemFree(cursor->node->data);
883 if(tree_child(cursor)) {
884 do {
885 freeNodeData(cursor);
886 }
887 while(tree_sibling(cursor));
888 tree_parent(cursor);
889 }
890 }
891
892
tree_delete(TreePtr tree)893 NLM_EXTERN Boolean tree_delete(TreePtr tree)
894 {
895 TreeCursorPtr cursor;
896 int i, j;
897 _BagStore bs;
898 _NodeId nid;
899
900 nid.idi= 0;
901
902 notify(tree, TREE_SHUTDOWN, nid, nid, NULL, 0);
903 /* close all existing cursors first */
904 while((cursor= tree->cursor) != NULL) {
905 tree_closeCursor(cursor);
906 }
907
908 /* delete all data allocated for nodes */
909 cursor= tree_openCursor(tree, NULL, NULL);
910
911 freeNodeData(cursor);
912
913 tree_closeCursor(cursor);
914
915 for(i= 0; i != NOF_BAGS; i++) {
916 if((bs= tree->bag_store[i]) != NULL) {
917 for(j= 0; j != NODE_BAG_SIZE; j++)
918 if(bs[j] != NULL) MemFree(bs[j]);
919 MemFree(bs);
920 }
921 }
922
923 MemFree(tree);
924 return TRUE;
925 }
926
927
928 /***********************************************
929 * Save tree in a file
930 */
saveNode(TreeCursorPtr cursor)931 static Boolean saveNode(TreeCursorPtr cursor /* cursor->user_data is a file pointer */)
932 {
933 if(cursor->tree->save_func != NULL) cursor->tree->save_func(cursor);
934
935 if(cursor->node->size > sizeof(_NodeData)) {
936 if(FileWrite(cursor->node->data, cursor->node->size, 1, (FILE*)(cursor->user_data)) < 1)
937 return FALSE;
938 }
939
940 if(tree_child(cursor)) {
941 do {
942 if(!saveNode(cursor)) return FALSE;
943 }
944 while(tree_sibling(cursor));
945
946 tree_parent(cursor);
947 }
948
949 return TRUE;
950 }
951
952
tree_save(TreePtr tree,CharPtr filename)953 NLM_EXTERN Boolean tree_save(TreePtr tree, CharPtr filename)
954 {
955 FILE* f;
956 Int2 i, j;
957 _BagStore bs;
958 TreeCursorPtr cursor;
959 Boolean res;
960
961 f= FileOpen(filename, "wb");
962 if(f == NULL) return FALSE;
963
964 /* write ids from tree */
965 if(FileWrite(&tree->id4NewNode, sizeof(_NodeId), 1, f) < 1) return FALSE;
966 if(FileWrite(&tree->rootNodeId, sizeof(_NodeId), 1, f) < 1) return FALSE;
967
968 i= (tree->save_func == NULL)? 1 : 0;
969
970 if(FileWrite(&i, sizeof(Int2), 1, f) < 1) return FALSE;
971
972 /* write tree structure itself */
973 if(FileWrite(tree->bag_store, sizeof(_BagStore), NOF_BAGS, f) < NOF_BAGS) return FALSE;
974
975 for(i= 0; i < NOF_BAGS; i++) {
976 if((bs= tree->bag_store[i]) != NULL) {
977 if(FileWrite(bs, sizeof(_NodeBagPtr), NODE_BAG_SIZE, f) < NODE_BAG_SIZE) return FALSE;
978
979 for(j= 0; j < NODE_BAG_SIZE; j++) {
980 if(bs[j] != NULL) {
981 if(FileWrite(bs[j], sizeof(_NodeBag), 1, f) < 1) return FALSE;
982 }
983 }
984 }
985 }
986
987 /* save node's data */
988 cursor= tree_openCursor(tree, f, NULL);
989
990 res= saveNode(cursor);
991
992 FileClose(f);
993
994 tree_closeCursor(cursor);
995
996 return res;
997 }
998
999
1000 /***********************************************
1001 * Restore tree from the file
1002 */
restoreNode(TreeCursorPtr cursor)1003 static Boolean restoreNode(TreeCursorPtr cursor /* cursor->user_data is a file pointer */)
1004 {
1005
1006 if(cursor->node->size > sizeof(_NodeData)) {
1007 if(((cursor->node->data= MemNew(cursor->node->size)) == NULL) ||
1008 (FileRead(cursor->node->data, cursor->node->size, 1, (FILE*)(cursor->user_data)) < 1)) {
1009 return FALSE;
1010 }
1011 }
1012
1013 if(tree_child(cursor)) {
1014 do {
1015 if(!restoreNode(cursor)) return FALSE;
1016 }
1017 while(tree_sibling(cursor));
1018
1019 tree_parent(cursor);
1020 }
1021
1022 cursor->node->sys_data= NULL;
1023
1024 return TRUE;
1025 }
1026
tree_restore(CharPtr filename)1027 NLM_EXTERN TreePtr tree_restore(CharPtr filename)
1028 {
1029 TreePtr ntree;
1030 _BagStore bs;
1031 Int2 nodeDataSaved;
1032 int i, j;
1033 FILE* f;
1034
1035 f= FileOpen(filename, "rb");
1036 if(f == NULL) return NULL;
1037
1038 if((ntree= (TreePtr)MemNew(sizeof(Tree))) == NULL) {
1039 tree_Message("tree_restore", "Not enaugh memory", NO_MEM_MSG);
1040 return NULL;
1041 }
1042
1043 ntree->cursor= NULL;
1044 ntree->get_func= NULL;
1045 ntree->update_func= NULL;
1046 ntree->save_func= NULL;
1047
1048 for(i= 0; i < TREE_NOF_SPIES; ntree->spy[i++]= NULL) continue;
1049
1050 ntree->nof_spies= 0;
1051
1052 if((FileRead(&ntree->id4NewNode, sizeof(_NodeId), 1, f) < 1) ||
1053 (FileRead(&ntree->rootNodeId, sizeof(_NodeId), 1, f) < 1) ||
1054 (FileRead(&nodeDataSaved, sizeof(Int2), 1, f) < 1)) {
1055
1056 MemFree(ntree);
1057 FileClose(f);
1058 return NULL;
1059 }
1060
1061 if((nodeDataSaved != 0) && (nodeDataSaved != 1)) {
1062 /* this is wrong file */
1063 MemFree(ntree);
1064 FileClose(f);
1065 return NULL;
1066 }
1067
1068 nodeDataSaved= 1;
1069
1070 /* read tree structure itself */
1071 if(FileRead(ntree->bag_store, sizeof(_BagStore), NOF_BAGS, f) < NOF_BAGS) {
1072
1073 MemFree(ntree);
1074 FileClose(f);
1075 return NULL;
1076 }
1077
1078 for(i= 0; i != NOF_BAGS; i++) {
1079 if(ntree->bag_store[i] != NULL) {
1080 ntree->bag_store[i]= bs= (_BagStore)MemNew(sizeof(_NodeBagPtr)*NODE_BAG_SIZE);
1081 if(bs == NULL) {
1082 tree_Message("tree_restore", "Not enaugh memory", NO_MEM_MSG);
1083 FileClose(f);
1084 MemFree(ntree);
1085 return NULL;
1086 }
1087
1088 if(FileRead(bs, sizeof(_NodeBagPtr), NODE_BAG_SIZE, f) < NODE_BAG_SIZE) {
1089 FileClose(f);
1090 MemFree(bs);
1091 MemFree(ntree);
1092 return NULL;
1093 }
1094
1095 for(j= 0; j < NODE_BAG_SIZE; j++) {
1096 if(bs[j] != NULL) {
1097 if((bs[j]= (_NodeBagPtr)MemNew(sizeof(_NodeBag))) == NULL) {
1098 tree_Message("tree_restore", "Not enaugh memory", NO_MEM_MSG);
1099 FileClose(f);
1100 MemFree(bs);
1101 MemFree(ntree);
1102 return NULL;
1103 }
1104
1105 if(FileRead(bs[j], sizeof(_NodeBag), 1, f) < 1) {
1106 MemFree(bs[j]);
1107 FileClose(f);
1108 MemFree(bs);
1109 MemFree(ntree);
1110 return NULL;
1111 }
1112 }
1113 }
1114 }
1115 }
1116
1117
1118 if(nodeDataSaved) {
1119 /* we need to restore node's data */
1120 TreeCursorPtr cursor= tree_openCursor(ntree, f, NULL);
1121
1122 if(!restoreNode(cursor)) {
1123 FileClose(f);
1124 tree_closeCursor(cursor);
1125 MemFree(ntree);
1126 return NULL;
1127 }
1128
1129 tree_closeCursor(cursor);
1130 }
1131
1132 FileClose(f);
1133 return ntree;
1134 }
1135
1136
1137 /***************************************************************************
1138 * Get node data pointer !!! This function has to be used for callback functions only !!!
1139 * in any case you should not update the data using returned pointer
1140 */
tree_getNodeData(TreeCursorPtr cursor,Uint2Ptr data_size)1141 NLM_EXTERN VoidPtr tree_getNodeData(TreeCursorPtr cursor, Uint2Ptr data_size)
1142 {
1143 *data_size= cursor->node->size;
1144 if(*data_size > sizeof(_NodeData)) return cursor->node->data;
1145 else return &cursor->node->data;
1146 }
1147
1148 /***************************************************************************
1149 * Update node data !!! This function has to be used for callback functions only !!!
1150 * if you used tree_getNodeData for this node, pointer to node data will incorrect
1151 */
tree_updateNodeData(TreeCursorPtr cursor,VoidPtr node_data,Uint2 node_data_size)1152 NLM_EXTERN Boolean tree_updateNodeData(TreeCursorPtr cursor, VoidPtr node_data, Uint2 node_data_size)
1153 {
1154 if(cursor->tree->nof_spies > 0) {
1155 notify(cursor->tree, TREE_NODEDATA_UPDATE, cursor->node_id,
1156 cursor->node_id, node_data, node_data_size);
1157 }
1158
1159 if(cursor->node->size == node_data_size) {
1160 if(node_data_size <= sizeof(_NodeData)) {
1161 memcpy(&cursor->node->data, node_data, node_data_size);
1162 }
1163 else {
1164 memcpy(cursor->node->data, node_data, node_data_size);
1165 }
1166 }
1167 else if(node_data_size <= sizeof(_NodeData)) {
1168 if(cursor->node->size > sizeof(_NodeData)) MemFree(cursor->node->data);
1169 memcpy(&cursor->node->data, node_data, node_data_size);
1170 cursor->node->size= node_data_size;
1171 }
1172 else if(node_data_size < cursor->node->size) {
1173 memcpy(cursor->node->data, node_data, node_data_size);
1174 cursor->node->size= node_data_size;
1175 }
1176 else {
1177
1178 if(cursor->node->size > sizeof(_NodeData)) MemFree(cursor->node->data);
1179
1180 if((cursor->node->data= MemNew(node_data_size)) == NULL) return FALSE;
1181 memcpy(cursor->node->data, node_data, node_data_size);
1182 cursor->node->size= node_data_size;
1183 }
1184
1185 if(cursor->tree->nof_spies > 0) {
1186 notify(cursor->tree, TREE_NODEDATA_UPD_DONE, cursor->node_id,
1187 cursor->node_id, node_data, node_data_size);
1188 }
1189
1190 return TRUE;
1191 }
1192
1193 /********************************************************************
1194 * Get node data. This function calls load_func callback if provided
1195 */
tree_getNode(TreeCursorPtr cursor,Uint4 format,Uint2Ptr data_size)1196 NLM_EXTERN VoidPtr tree_getNode(TreeCursorPtr cursor, Uint4 format, Uint2Ptr data_size)
1197 {
1198 if(cursor->tree->get_func != NULL) {
1199 return (*(cursor->tree->get_func))(cursor, format, data_size);
1200 }
1201 else {
1202 VoidPtr n_data;
1203
1204 *data_size= 0;
1205
1206 if((n_data= MemNew(cursor->node->size)) == NULL) return NULL;
1207
1208 if(cursor->node->size > sizeof(_NodeData)) {
1209 memcpy(n_data, cursor->node->data, cursor->node->size);
1210 }
1211 else {
1212 memcpy(n_data, &cursor->node->data, cursor->node->size);
1213 }
1214 *data_size= cursor->node->size;
1215 return n_data;
1216 }
1217 }
1218
1219 /*********************************************************************
1220 * Update node data
1221 */
tree_updateNode(TreeCursorPtr cursor,Uint4 format,VoidPtr node_data,Uint2 node_data_size)1222 NLM_EXTERN Boolean tree_updateNode(TreeCursorPtr cursor, Uint4 format, VoidPtr node_data, Uint2 node_data_size)
1223 {
1224 if(cursor->tree->update_func != NULL) {
1225 Boolean res;
1226
1227 if(cursor->tree->nof_spies > 0) {
1228 notify(cursor->tree, TREE_NODE_UPDATE, cursor->node_id,
1229 cursor->node_id, node_data, node_data_size);
1230 }
1231 res= (*(cursor->tree->update_func))(cursor, format, node_data, node_data_size);
1232
1233 if(cursor->tree->nof_spies > 0) {
1234 notify(cursor->tree, TREE_NODE_UPD_DONE, cursor->node_id,
1235 cursor->node_id, node_data, node_data_size);
1236 }
1237 return res;
1238 }
1239 else {
1240 return tree_updateNodeData(cursor, node_data, node_data_size);
1241 }
1242 }
1243
1244 /***********************************************
1245 * Get level number for node.
1246 * Root is on level 0
1247 * Children of root are on level 1
1248 * etc.
1249 */
tree_getLevel(TreeCursorPtr cursor)1250 NLM_EXTERN Int4 tree_getLevel(TreeCursorPtr cursor)
1251 {
1252 TreeCursorPtr t_cursor;
1253 Int4 level;
1254
1255 t_cursor= tree_openCursor(cursor->tree, NULL, NULL);
1256 tree_toNode(t_cursor, cursor->node_id);
1257
1258 for(level= 0; tree_parent(t_cursor); level++) continue;
1259
1260 tree_closeCursor(t_cursor);
1261
1262 return level;
1263 }
1264
1265 /***********************************************
1266 * Check that node pointed by cursor2 is descendant
1267 * of node pointed by cursor1
1268 */
tree_isDescendant(TreeCursorPtr cursor1,TreeCursorPtr cursor2)1269 NLM_EXTERN Boolean tree_isDescendant(TreeCursorPtr cursor1, TreeCursorPtr cursor2)
1270 {
1271 TreeCursorPtr t_cursor;
1272 Boolean res= FALSE;
1273
1274 t_cursor= tree_openCursor(cursor2->tree, NULL, NULL);
1275 tree_toNode(t_cursor, cursor2->node_id);
1276
1277 while(tree_parent(t_cursor)) {
1278 if(t_cursor->node_id.idi == cursor1->node_id.idi) {
1279 res= TRUE;
1280 break;
1281 }
1282 }
1283 tree_closeCursor(t_cursor);
1284
1285 return res;
1286 }
1287
tree_setGetNodeFunc(TreePtr tree,TreeGetFunc GetNodeFunction)1288 NLM_EXTERN TreeGetFunc tree_setGetNodeFunc(TreePtr tree, TreeGetFunc GetNodeFunction)
1289 {
1290 TreeGetFunc old;
1291
1292 old= tree->get_func;
1293 tree->get_func= GetNodeFunction;
1294 return old;
1295 }
1296
tree_setUpdateNodeFunc(TreePtr tree,TreeUpdateFunc UpdateNodeFunction)1297 NLM_EXTERN TreeUpdateFunc tree_setUpdateNodeFunc(TreePtr tree, TreeUpdateFunc UpdateNodeFunction)
1298 {
1299 TreeUpdateFunc old;
1300
1301 old= tree->update_func;
1302 tree->update_func= UpdateNodeFunction;
1303 return old;
1304 }
1305
tree_setSaveNodeFunc(TreePtr tree,TreeSaveFunc SaveNodeFunction)1306 NLM_EXTERN TreeSaveFunc tree_setSaveNodeFunc(TreePtr tree, TreeSaveFunc SaveNodeFunction)
1307 {
1308 TreeSaveFunc old;
1309
1310 old= tree->save_func;
1311 tree->save_func= SaveNodeFunction;
1312 return old;
1313 }
1314
tree_addSpy(TreePtr tree,TreeSpyFunc Spy,VoidPtr spy_data)1315 NLM_EXTERN Int2 tree_addSpy(TreePtr tree, TreeSpyFunc Spy, VoidPtr spy_data)
1316 {
1317 Int2 i;
1318
1319 if(tree->nof_spies >= TREE_NOF_SPIES) return -1;
1320
1321 for(i= 0; i < TREE_NOF_SPIES; i++) {
1322 if(tree->spy[i] == NULL) {
1323 tree->nof_spies++;
1324 tree->spy[i]= Spy;
1325 tree->spy_data[i]= spy_data;
1326 return i;
1327 }
1328 }
1329
1330 tree->nof_spies= TREE_NOF_SPIES;
1331 return -1;
1332 }
1333
tree_getSpyData(TreePtr tree,Int2 spy_id)1334 NLM_EXTERN VoidPtr tree_getSpyData(TreePtr tree, Int2 spy_id)
1335 {
1336 return ((spy_id >= 0) && (spy_id < TREE_NOF_SPIES) && (tree->spy[spy_id] != NULL))?
1337 tree->spy_data[spy_id] : NULL;
1338 }
1339
tree_delSpy(TreePtr tree,Int2 spy_id)1340 NLM_EXTERN Boolean tree_delSpy(TreePtr tree, Int2 spy_id)
1341 {
1342 if((spy_id >= 0) && (spy_id < TREE_NOF_SPIES) && (tree->spy[spy_id] != NULL)) {
1343 tree->nof_spies--;
1344 tree->spy[spy_id]= NULL;
1345 return TRUE;
1346 }
1347
1348 return FALSE;
1349 }
1350
1351