BRL-CAD
rb_create.c
Go to the documentation of this file.
1 /* R B _ C R E A T 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 struct bu_rb_tree *
30 bu_rb_create(const char *description, int nm_orders, int (**compare_funcs)(const void *, const void *))
31 {
32  int order;
33  struct bu_rb_tree *tree;
34 
35  /*
36  * Allocate memory for the tree
37  */
38  BU_ALLOC(tree, struct bu_rb_tree);
39 
40  tree->rbt_root = (struct bu_rb_node **)
41  bu_malloc(nm_orders * sizeof(struct bu_rb_node),
42  "red-black roots");
43  tree->rbt_unique = (char *)
44  bu_malloc((size_t) lrint(ceil((double) (nm_orders / 8.0))),
45  "red-black uniqueness flags");
46  RB_NULL(tree) = (struct bu_rb_node *)
47  bu_malloc(sizeof(struct bu_rb_node),
48  "red-black empty node");
49  RB_NULL(tree)->rbn_parent = (struct bu_rb_node **)
50  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
51  "red-black parents");
52  RB_NULL(tree)->rbn_left = (struct bu_rb_node **)
53  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
54  "red-black left children");
55  RB_NULL(tree)->rbn_right = (struct bu_rb_node **)
56  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
57  "red-black right children");
58  RB_NULL(tree)->rbn_color = (char *)
59  bu_malloc((size_t) lrint(ceil((double) (nm_orders / 8.0))),
60  "red-black colors");
61  RB_NULL(tree)->rbn_size = (int *)
62  bu_malloc(nm_orders * sizeof(int),
63  "red-black subtree sizes");
64  RB_NULL(tree)->rbn_package = (struct bu_rb_package **)
65  bu_malloc(nm_orders * sizeof(struct bu_rb_package *),
66  "red-black packages");
67  /*
68  * Fill in the tree
69  */
71  tree->rbt_description = description;
72  tree->rbt_nm_orders = nm_orders;
73  tree->rbt_compar = compare_funcs;
74  tree->rbt_print = 0;
75  bu_rb_uniq_all_off(tree);
76  tree->rbt_debug = 0x0;
77  tree->rbt_current = RB_NULL(tree);
78  for (order = 0; order < nm_orders; ++order)
79  RB_ROOT(tree, order) = RB_NULL(tree);
80  BU_LIST_INIT(&(tree->rbt_nodes.l));
81  BU_LIST_INIT(&(tree->rbt_packages.l));
82 
83  /*
84  * Initialize the nil sentinel
85  */
86  RB_NULL(tree)->rbn_magic = BU_RB_NODE_MAGIC;
87  RB_NULL(tree)->rbn_tree = tree;
88  for (order = 0; order < nm_orders; ++order) {
89  RB_PARENT(RB_NULL(tree), order) = BU_RB_NODE_NULL;
90  RB_SET_COLOR(RB_NULL(tree), order, RB_BLK);
91  RB_LEFT_CHILD(RB_NULL(tree), order) = BU_RB_NODE_NULL;
92  RB_RIGHT_CHILD(RB_NULL(tree), order) = BU_RB_NODE_NULL;
93  RB_SIZE(RB_NULL(tree), order) = 0;
94  (RB_NULL(tree)->rbn_package)[order] = BU_RB_PKG_NULL;
95  }
96 
97  return tree;
98 }
99 
100 
101 struct bu_rb_tree *
102 bu_rb_create1(const char *description, int (*compare_func)(void))
103 {
104  int (**cfp)(const void *, const void *);
105 
106  cfp = (int (**)(const void *, const void *))
107  bu_malloc(sizeof(int (*)(const void *, const void *)), "red-black function table");
108  *cfp = (int (*)(const void *, const void *)) compare_func;
109  return bu_rb_create(description, 1, cfp);
110 }
111 
112 /*
113  * Local Variables:
114  * mode: C
115  * tab-width: 8
116  * indent-tabs-mode: t
117  * c-file-style: "stroustrup"
118  * End:
119  * ex: shiftwidth=4 tabstop=8
120  */
#define RB_PARENT(n, o)
Definition: rb_internals.h:60
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
Definition: rb.h:109
Definition: rb.h:204
struct bu_rb_tree * bu_rb_create1(const char *description, int(*compare_func)(void))
Definition: rb_create.c:102
#define BU_RB_NODE_NULL
Definition: rb.h:217
struct bu_rb_list rbt_packages
Definition: rb.h:126
struct bu_rb_list rbt_nodes
Definition: rb.h:125
uint32_t rbt_magic
Definition: rb.h:111
Header file for the BRL-CAD common definitions.
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61
#define RB_NULL(t)
Definition: rb_internals.h:48
struct bu_rb_node * rbt_current
Definition: rb.h:124
#define RB_SET_COLOR(n, o, c)
Definition: rb_internals.h:74
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
const char * rbt_description
Definition: rb.h:117
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
int rbt_nm_orders
Definition: rb.h:120
int(** rbt_compar)(const void *, const void *)
Definition: rb.h:121
#define BU_RB_PKG_NULL
Definition: rb.h:195
struct bu_rb_tree * bu_rb_create(const char *description, int nm_orders, int(**compare_funcs)(const void *, const void *))
Definition: rb_create.c:30
void bu_rb_uniq_all_off(struct bu_rb_tree *tree)
Definition: rb_insert.c:373
#define BU_LIST_INIT(_hp)
Definition: list.h:148
#define RB_BLK
Definition: rb_internals.h:81
char * rbt_unique
Definition: rb.h:123
void(* rbt_print)(void *)
Definition: rb.h:115
struct bu_rb_node ** rbt_root
Definition: rb.h:122
struct bu_list l
Definition: rb.h:82
int rbt_debug
Definition: rb.h:116
#define RB_SIZE(n, o)
Definition: rb_internals.h:71