data_structures
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