BRL-CAD
rb_search.c
Go to the documentation of this file.
1 /* R B _ S E A R C H . 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 <stdlib.h>
24 #include <stdio.h>
25 #include <math.h>
26 
27 #include "bu/rb.h"
28 #include "./rb_internals.h"
29 
30 
31 /**
32  * Search for a node in a red-black tree
33  *
34  * This function has four parameters: the root and order of the tree
35  * in which to search, the comparison function, and a data block
36  * containing the desired value of the key. On success, _rb_search()
37  * returns a pointer to the discovered node. Otherwise, it returns
38  * (tree->rbt_empty_node).
39  */
40 HIDDEN struct bu_rb_node *
41 _rb_search(struct bu_rb_node *root, int order_nm, int (*compare)(const void *, const void *), void *data)
42 {
43  int result;
44  struct bu_rb_tree *tree;
45 
46  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
47  tree = root->rbn_tree;
48  RB_CKORDER(tree, order_nm);
49 
50  while (1) {
51  if (root == RB_NULL(root->rbn_tree))
52  break;
53  if ((result = compare(data, RB_DATA(root, order_nm))) == 0)
54  break;
55  else if (result < 0)
56  root = RB_LEFT_CHILD(root, order_nm);
57  else /* result > 0 */
58  root = RB_RIGHT_CHILD(root, order_nm);
59  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
60  }
61  RB_CURRENT(tree) = root;
62  return root;
63 }
64 
65 
66 void *
67 bu_rb_search (struct bu_rb_tree *tree, int order, void *data)
68 {
69 
70  int (*compare)(const void *, const void *);
71  struct bu_rb_node *node;
72 
73  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
74  RB_CKORDER(tree, order);
75 
76  compare = RB_COMPARE_FUNC(tree, order);
77  node = _rb_search(RB_ROOT(tree, order), order, compare, data);
78  if (node == RB_NULL(tree))
79  return NULL;
80  else
81  return RB_DATA(node, order);
82 }
83 
84 
85 /*
86  * Local Variables:
87  * mode: C
88  * tab-width: 8
89  * indent-tabs-mode: t
90  * c-file-style: "stroustrup"
91  * End:
92  * ex: shiftwidth=4 tabstop=8
93  */
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
HIDDEN struct bu_rb_node * _rb_search(struct bu_rb_node *root, int order_nm, int(*compare)(const void *, const void *), void *data)
Definition: rb_search.c:41
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
void * bu_rb_search(struct bu_rb_tree *tree, int order, void *data)
Definition: rb_search.c:67
Definition: rb.h:204
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
#define HIDDEN
Definition: common.h:86
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
COMPLEX data[64]
Definition: fftest.c:34
#define RB_CURRENT(t)
Definition: rb_internals.h:47
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
#define RB_COMPARE_FUNC(t, o)
Definition: rb_internals.h:44
#define RB_DATA(n, o)
Definition: rb_internals.h:82