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 */
|
