summaryrefslogtreecommitdiff
path: root/include/util/rbtree.h
blob: 07f2ce9234a699304907f37a91bae3fa0f231473 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/* SPDX-License-Identifier: LGPL-3.0-or-later */
/*
 * rbtree.h
 *
 * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
 */
#ifndef SQFS_RBTREE_H
#define SQFS_RBTREE_H

#include "config.h"
#include "sqfs/predef.h"
#include "mempool.h"
#include "compat.h"

#include <stddef.h>

typedef struct rbtree_node_t {
	struct rbtree_node_t *left;
	struct rbtree_node_t *right;
	sqfs_u32 value_offset;
	sqfs_u32 is_red : 1;
	sqfs_u32 pad0 : 31;

	sqfs_u8 data[];
} rbtree_node_t;

typedef struct rbtree_t {
	rbtree_node_t *root;

#ifndef NO_CUSTOM_ALLOC
	mem_pool_t *pool;
#endif

	int (*key_compare)(const void *ctx,
			   const void *lhs, const void *hrs);

	size_t key_size;
	size_t key_size_padded;

	size_t value_size;

	void *key_context;
} rbtree_t;

static SQFS_INLINE void *rbtree_node_key(rbtree_node_t *n)
{
	return n->data;
}

static SQFS_INLINE void *rbtree_node_value(rbtree_node_t *n)
{
	return n->data + n->value_offset;
}

#ifdef __cplusplus
extern "C" {
#endif

SQFS_INTERNAL int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize,
			      int(*key_compare)(const void *, const void *,
						const void *));

SQFS_INTERNAL void rbtree_cleanup(rbtree_t *tree);

SQFS_INTERNAL int rbtree_copy(const rbtree_t *tree, rbtree_t *out);

SQFS_INTERNAL int rbtree_insert(rbtree_t *tree, const void *key,
				const void *value);

SQFS_INTERNAL rbtree_node_t *rbtree_lookup(const rbtree_t *tree,
					   const void *key);

#ifdef __cplusplus
}
#endif

#endif /* TOOLS_RBTREE_H */