BRL-CAD
rb_free.c
Go to the documentation of this file.
1 /* R B _ F R E E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1998-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdio.h>
24 #include <math.h>
25 #include "bu/rb.h"
26 #include "./rb_internals.h"
27 
28 
29 void
30 bu_rb_free(struct bu_rb_tree *tree, void (*free_data)(void *))
31 {
32  struct bu_rb_list *rblp;
33  struct bu_rb_node *node;
34  struct bu_rb_package *package;
35 
36  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
37 
38  /*
39  * Free all the nodes
40  */
41  while (BU_LIST_WHILE(rblp, bu_rb_list, &(tree->rbt_nodes.l))) {
42  BU_CKMAG(rblp, BU_RB_LIST_MAGIC, "red-black list element");
43  rb_free_node(rblp->rbl_node);
44  }
45 
46  /*
47  * Free all the packages
48  */
49  while (BU_LIST_WHILE(rblp, bu_rb_list, &(tree->rbt_packages.l))) {
50  BU_CKMAG(rblp, BU_RB_LIST_MAGIC, "red-black list element");
51  package = rblp->rbl_package;
52  BU_CKMAG(package, BU_RB_PKG_MAGIC, "red-black package");
53  if (free_data)
54  free_data(package->rbp_data);
55  rb_free_package(package);
56  }
57 
58  /*
59  * Free the tree's NIL sentinel
60  */
61  node = tree->rbt_empty_node;
62  bu_free((void *) node->rbn_left, "red-black left children");
63  bu_free((void *) node->rbn_right, "red-black right children");
64  bu_free((void *) node->rbn_parent, "red-black parents");
65  bu_free((void *) node->rbn_color, "red-black colors");
66  if (node->rbn_size)
67  bu_free((void *) node->rbn_size, "red-black size");
68  bu_free((void *) node->rbn_package, "red-black packages");
69  bu_free((void *) node, "red-black empty node");
70 
71  /*
72  * Free the tree itself
73  */
74  bu_free((void *) tree->rbt_root, "red-black roots");
75  bu_free((void *) tree->rbt_unique, "red-black uniqueness flags");
76  bu_free((void *) tree, "red-black tree");
77 }
78 
79 
80 void
81 rb_free_node(struct bu_rb_node *node)
82 {
83  struct bu_rb_tree *tree;
84 
85  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
86 
87  tree = node->rbn_tree;
88  if (RB_CURRENT(tree) == node)
89  RB_CURRENT(tree) = RB_NULL(tree);
90  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
91 
92  /*
93  * Remove node from the list of all nodes
94  */
95  BU_CKMAG(node->rbn_list_pos, BU_RB_LIST_MAGIC, "red-black list element");
96  BU_LIST_DEQUEUE(&(node->rbn_list_pos->l));
97 
98  bu_free((void *) node->rbn_parent, "red-black parents");
99  bu_free((void *) node->rbn_left, "red-black left children");
100  bu_free((void *) node->rbn_right, "red-black right children");
101  bu_free((void *) node->rbn_color, "red-black colors");
102  if (node->rbn_size)
103  bu_free((void *) node->rbn_size, "red-black size");
104  bu_free((void *) node->rbn_package, "red-black packages");
105  bu_free((void *) node->rbn_list_pos, "red-black list element");
106  bu_free((void *) node, "red-black node");
107 }
108 
109 
110 void
112 {
113  BU_CKMAG(package, BU_RB_PKG_MAGIC, "red-black package");
114 
115  /*
116  * Remove node from the list of all packages
117  */
119  "red-black list element");
120  BU_LIST_DEQUEUE(&(package->rbp_list_pos->l));
121 
122  bu_free((void *) package->rbp_node, "red-black package nodes");
123  bu_free((void *) package->rbp_list_pos, "red-black list element");
124  bu_free((void *) package, "red-black package");
125 }
126 
127 /*
128  * Local Variables:
129  * mode: C
130  * tab-width: 8
131  * indent-tabs-mode: t
132  * c-file-style: "stroustrup"
133  * End:
134  * ex: shiftwidth=4 tabstop=8
135  */
struct bu_rb_node ** rbn_parent
Definition: rb.h:208
struct bu_rb_list * rbn_list_pos
Definition: rb.h:215
struct bu_rb_node ** rbn_left
Definition: rb.h:209
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
Definition: rb.h:204
void rb_free_package(struct bu_rb_package *package)
Definition: rb_free.c:111
struct bu_rb_node ** rbp_node
Definition: rb.h:191
struct bu_rb_list rbt_packages
Definition: rb.h:126
struct bu_rb_list rbt_nodes
Definition: rb.h:125
struct bu_rb_node * rbt_empty_node
Definition: rb.h:127
Header file for the BRL-CAD common definitions.
#define RB_NULL(t)
Definition: rb_internals.h:48
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
#define RB_CURRENT(t)
Definition: rb_internals.h:47
struct bu_rb_list * rbp_list_pos
Definition: rb.h:192
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
int * rbn_size
Definition: rb.h:212
void rb_free_node(struct bu_rb_node *node)
Definition: rb_free.c:81
void * rbp_data
Definition: rb.h:193
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
char * rbn_color
Definition: rb.h:211
#define BU_RB_PKG_MAGIC
Definition: magic.h:62
char * rbt_unique
Definition: rb.h:123
struct bu_rb_package ** rbn_package
Definition: rb.h:213
void bu_rb_free(struct bu_rb_tree *tree, void(*free_data)(void *))
Definition: rb_free.c:30
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
struct bu_rb_node ** rbn_right
Definition: rb.h:210
struct bu_rb_node ** rbt_root
Definition: rb.h:122
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
struct bu_list l
Definition: rb.h:82
#define BU_RB_LIST_MAGIC
Definition: magic.h:60
Definition: rb.h:80