1/*****************************************************************************
2
3Copyright (c) 2007, 2015, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18/******************************************************************//**
19@file include/ut0rbt.h
20Various utilities
21
22Created 2007-03-20 Sunny Bains
23*******************************************************/
24
25#ifndef INNOBASE_UT0RBT_H
26#define INNOBASE_UT0RBT_H
27
28#if !defined(IB_RBT_TESTING)
29#include "univ.i"
30#include "ut0mem.h"
31#else
32#include <stdio.h>
33#include <stdlib.h>
34#include <string.h>
35#include <assert.h>
36
37#define ut_malloc malloc
38#define ut_free free
39#define ulint unsigned long
40#define ut_a(c) assert(c)
41#define ut_error assert(0)
42#define ibool unsigned int
43#define TRUE 1
44#define FALSE 0
45#endif
46
47struct ib_rbt_node_t;
48typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
49typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
50typedef int (*ib_rbt_arg_compare)(const void*, const void* p1, const void* p2);
51
52/** Red black tree color types */
53enum ib_rbt_color_t {
54 IB_RBT_RED,
55 IB_RBT_BLACK
56};
57
58/** Red black tree node */
59struct ib_rbt_node_t {
60 ib_rbt_color_t color; /* color of this node */
61
62 ib_rbt_node_t* left; /* points left child */
63 ib_rbt_node_t* right; /* points right child */
64 ib_rbt_node_t* parent; /* points parent node */
65
66 char value[1]; /* Data value */
67};
68
69/** Red black tree instance.*/
70struct ib_rbt_t {
71 ib_rbt_node_t* nil; /* Black colored node that is
72 used as a sentinel. This is
73 pre-allocated too.*/
74
75 ib_rbt_node_t* root; /* Root of the tree, this is
76 pre-allocated and the first
77 data node is the left child.*/
78
79 ulint n_nodes; /* Total number of data nodes */
80
81 ib_rbt_compare compare; /* Fn. to use for comparison */
82 ib_rbt_arg_compare
83 compare_with_arg; /* Fn. to use for comparison
84 with argument */
85 ulint sizeof_value; /* Sizeof the item in bytes */
86 void* cmp_arg; /* Compare func argument */
87};
88
89/** The result of searching for a key in the tree, this is useful for
90a speedy lookup and insert if key doesn't exist.*/
91struct ib_rbt_bound_t {
92 const ib_rbt_node_t*
93 last; /* Last node visited */
94
95 int result; /* Result of comparing with
96 the last non-nil node that
97 was visited */
98};
99
100/* Size in elements (t is an rb tree instance) */
101#define rbt_size(t) (t->n_nodes)
102
103/* Check whether the rb tree is empty (t is an rb tree instance) */
104#define rbt_empty(t) (rbt_size(t) == 0)
105
106/* Get data value (t is the data type, n is an rb tree node instance) */
107#define rbt_value(t, n) ((t*) &n->value[0])
108
109/* Compare a key with the node value (t is tree, k is key, n is node)*/
110#define rbt_compare(t, k, n) (t->compare(k, n->value))
111
112/**********************************************************************//**
113Free an instance of a red black tree */
114void
115rbt_free(
116/*=====*/
117 ib_rbt_t* tree); /*!< in: rb tree to free */
118/**********************************************************************//**
119Create an instance of a red black tree
120@return rb tree instance */
121ib_rbt_t*
122rbt_create(
123/*=======*/
124 size_t sizeof_value, /*!< in: size in bytes */
125 ib_rbt_compare compare); /*!< in: comparator */
126/**********************************************************************//**
127Create an instance of a red black tree, whose comparison function takes
128an argument
129@return rb tree instance */
130ib_rbt_t*
131rbt_create_arg_cmp(
132/*===============*/
133 size_t sizeof_value, /*!< in: size in bytes */
134 ib_rbt_arg_compare
135 compare, /*!< in: comparator */
136 void* cmp_arg); /*!< in: compare fn arg */
137/**********************************************************************//**
138Delete a node from the red black tree, identified by key */
139ibool
140rbt_delete(
141/*=======*/
142 /* in: TRUE on success */
143 ib_rbt_t* tree, /* in: rb tree */
144 const void* key); /* in: key to delete */
145/**********************************************************************//**
146Remove a node from the red black tree, NOTE: This function will not delete
147the node instance, THAT IS THE CALLERS RESPONSIBILITY.
148@return the deleted node with the const. */
149ib_rbt_node_t*
150rbt_remove_node(
151/*============*/
152 ib_rbt_t* tree, /*!< in: rb tree */
153 const ib_rbt_node_t*
154 node); /*!< in: node to delete, this
155 is a fudge and declared const
156 because the caller has access
157 only to const nodes.*/
158/**********************************************************************//**
159Add data to the red black tree, identified by key (no dups yet!)
160@return inserted node */
161const ib_rbt_node_t*
162rbt_insert(
163/*=======*/
164 ib_rbt_t* tree, /*!< in: rb tree */
165 const void* key, /*!< in: key for ordering */
166 const void* value); /*!< in: data that will be
167 copied to the node.*/
168/**********************************************************************//**
169Add a new node to the tree, useful for data that is pre-sorted.
170@return appended node */
171const ib_rbt_node_t*
172rbt_add_node(
173/*=========*/
174 ib_rbt_t* tree, /*!< in: rb tree */
175 ib_rbt_bound_t* parent, /*!< in: parent */
176 const void* value); /*!< in: this value is copied
177 to the node */
178/**********************************************************************//**
179Return the left most data node in the tree
180@return left most node */
181const ib_rbt_node_t*
182rbt_first(
183/*======*/
184 const ib_rbt_t* tree); /*!< in: rb tree */
185/**********************************************************************//**
186Return the right most data node in the tree
187@return right most node */
188const ib_rbt_node_t*
189rbt_last(
190/*=====*/
191 const ib_rbt_t* tree); /*!< in: rb tree */
192/**********************************************************************//**
193Return the next node from current.
194@return successor node to current that is passed in. */
195const ib_rbt_node_t*
196rbt_next(
197/*=====*/
198 const ib_rbt_t* tree, /*!< in: rb tree */
199 const ib_rbt_node_t* /* in: current node */
200 current);
201/**********************************************************************//**
202Return the prev node from current.
203@return precedessor node to current that is passed in */
204const ib_rbt_node_t*
205rbt_prev(
206/*=====*/
207 const ib_rbt_t* tree, /*!< in: rb tree */
208 const ib_rbt_node_t* /* in: current node */
209 current);
210/**********************************************************************//**
211Search for the key, a node will be retuned in parent.last, whether it
212was found or not. If not found then parent.last will contain the
213parent node for the possibly new key otherwise the matching node.
214@return result of last comparison */
215int
216rbt_search(
217/*=======*/
218 const ib_rbt_t* tree, /*!< in: rb tree */
219 ib_rbt_bound_t* parent, /*!< in: search bounds */
220 const void* key); /*!< in: key to search */
221/**********************************************************************//**
222Search for the key, a node will be retuned in parent.last, whether it
223was found or not. If not found then parent.last will contain the
224parent node for the possibly new key otherwise the matching node.
225@return result of last comparison */
226int
227rbt_search_cmp(
228/*===========*/
229 const ib_rbt_t* tree, /*!< in: rb tree */
230 ib_rbt_bound_t* parent, /*!< in: search bounds */
231 const void* key, /*!< in: key to search */
232 ib_rbt_compare compare, /*!< in: comparator */
233 ib_rbt_arg_compare
234 arg_compare); /*!< in: fn to compare items
235 with argument */
236/**********************************************************************//**
237Merge the node from dst into src. Return the number of nodes merged.
238@return no. of recs merged */
239ulint
240rbt_merge_uniq(
241/*===========*/
242 ib_rbt_t* dst, /*!< in: dst rb tree */
243 const ib_rbt_t* src); /*!< in: src rb tree */
244#if defined UNIV_DEBUG || defined IB_RBT_TESTING
245/**********************************************************************//**
246Verify the integrity of the RB tree. For debugging. 0 failure else height
247of tree (in count of black nodes).
248@return TRUE if OK FALSE if tree invalid. */
249ibool
250rbt_validate(
251/*=========*/
252 const ib_rbt_t* tree); /*!< in: tree to validate */
253#endif /* UNIV_DEBUG || IB_RBT_TESTING */
254
255#endif /* INNOBASE_UT0RBT_H */
256