data_structures
src
data_structures
rbt
rbt_floor.c
Go to the documentation of this file.
1
/* ************************************************************************** */
3
/* */
4
/* ::: :::::::: */
5
/* rbt_floor.c :+: :+: :+: */
6
/* +:+ +:+ +:+ */
7
/* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8
/* +#+#+#+#+#+ +#+ */
9
/* Created: 2020/07/18 21:21:33 by unite #+# #+# */
10
/* Updated: 2020/07/18 21:24:19 by unite ### ########.fr */
11
/* */
12
/* ************************************************************************** */
13
14
#include "
rbt.h
"
15
16
static
const
t_rbt_node
*rbt_floor_recur(
const
t_rbt
*rbt,
const
t_rbt_node
*h,
17
const
void
*key)
18
{
19
int
cmp;
20
const
t_rbt_node
*x;
21
22
if
(!h)
23
return
(NULL);
24
cmp = rbt->
key_type
->
cmp
(key, h->
key
);
25
if
(cmp == 0)
26
return
(h);
27
if
(cmp < 0)
28
return
(rbt_floor_recur(rbt, h->
left
, key));
29
x = rbt_floor_recur(rbt, h->
right
, key);
30
return
(x ? x : h);
31
}
32
33
void
*
rbt_floor
(
const
t_rbt
*rbt,
const
void
*key)
34
{
35
const
t_rbt_node
*node;
36
37
if
(!rbt || !key)
38
return
(NULL);
39
node = rbt_floor_recur(rbt, rbt->
root
, key);
40
return
(node ? node->
key
: NULL);
41
}
s_rbt
A left-leaning red-black binary search tree.
Definition:
rbt.h:72
s_type::cmp
int(* cmp)(const void *, const void *)
(optional) A function ponter used to compare members of this data type
Definition:
types.h:52
s_rbt_node::right
struct s_rbt_node * right
The right child.
Definition:
rbt.h:56
rbt_floor
void * rbt_floor(const t_rbt *rbt, const void *key)
Returns the largest key less than or equal to the specified key.
Definition:
rbt_floor.c:33
s_rbt_node::left
struct s_rbt_node * left
The left child.
Definition:
rbt.h:55
s_rbt_node::key
void * key
The key.
Definition:
rbt.h:53
s_rbt::key_type
const t_type * key_type
The type of keys in the tree.
Definition:
rbt.h:75
rbt.h
s_rbt_node
A node in a red-black tree.
Definition:
rbt.h:51
s_rbt::root
t_rbt_node * root
The root of the tree.
Definition:
rbt.h:74
Generated by
1.8.16