[RFC PATCH 10/12] [squash] Rename btree to trie
Ákos Uzonyi
uzonyi.akos at gmail.com
Fri Jun 12 14:33:54 UTC 2020
---
Makefile.am | 2 +-
pidns.c | 30 ++++++-------
btree.c => trie.c | 112 +++++++++++++++++++++++-----------------------
btree.h => trie.h | 50 ++++++++++-----------
4 files changed, 97 insertions(+), 97 deletions(-)
rename btree.c => trie.c (63%)
rename btree.h => trie.h (61%)
diff --git a/Makefile.am b/Makefile.am
index 2717d292..aa9a8d78 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -68,7 +68,7 @@ libstrace_a_SOURCES = \
bpf_fprog.h \
bpf_seccomp_filter.c \
bpf_sock_filter.c \
- btree.c \
+ trie.c \
btrfs.c \
cacheflush.c \
capability.c \
diff --git a/pidns.c b/pidns.c
index cd233144..07c53012 100644
--- a/pidns.c
+++ b/pidns.c
@@ -14,12 +14,12 @@
#include <sys/types.h>
#include <sys/stat.h>
-#include "btree.h"
+#include "trie.h"
#include "nsfs.h"
#include "xmalloc.h"
-struct btree *ns_pid_to_proc_pid[PT_COUNT];
-struct btree *proc_data_cache;
+struct trie *ns_pid_to_proc_pid[PT_COUNT];
+struct trie *proc_data_cache;
static const char tid_str[] = "NSpid:\t";
static const char tgid_str[] = "NStgid:\t";
@@ -88,9 +88,9 @@ pidns_init(void)
return;
for (int i = 0; i < PT_COUNT; i++)
- ns_pid_to_proc_pid[i] = btree_create(6, 16, 16, 64, 0);
+ ns_pid_to_proc_pid[i] = trie_create(6, 16, 16, 64, 0);
- proc_data_cache = btree_create(6, 16, 16, lg2(get_pid_max() - 1), 0);
+ proc_data_cache = trie_create(6, 16, 16, lg2(get_pid_max() - 1), 0);
inited = true;
}
@@ -98,26 +98,26 @@ pidns_init(void)
static void
put_proc_pid(uint64_t ns, int ns_pid, enum pid_type type, int proc_pid)
{
- struct btree *b = (struct btree *) btree_get(ns_pid_to_proc_pid[type], ns);
+ struct trie *b = (struct trie *) trie_get(ns_pid_to_proc_pid[type], ns);
if (!b) {
int pid_max = get_pid_max();
uint8_t pid_max_size = lg2(pid_max - 1);
uint8_t pid_max_size_lg = lg2(pid_max_size - 1);
- b = btree_create(pid_max_size_lg, 16, 16, pid_max_size, 0);
+ b = trie_create(pid_max_size_lg, 16, 16, pid_max_size, 0);
- btree_set(ns_pid_to_proc_pid[type], ns, (uint64_t) b);
+ trie_set(ns_pid_to_proc_pid[type], ns, (uint64_t) b);
}
- btree_set(b, ns_pid, proc_pid);
+ trie_set(b, ns_pid, proc_pid);
}
static int
get_cached_proc_pid(uint64_t ns, int ns_pid, enum pid_type type)
{
- struct btree *b = (struct btree *) btree_get(ns_pid_to_proc_pid[type], ns);
+ struct trie *b = (struct trie *) trie_get(ns_pid_to_proc_pid[type], ns);
if (!b)
return 0;
- return btree_get(b, ns_pid);
+ return trie_get(b, ns_pid);
}
/**
@@ -354,7 +354,7 @@ get_our_ns(void)
static struct proc_data *
get_or_create_proc_data(int proc_pid)
{
- struct proc_data *pd = (struct proc_data *) btree_get(proc_data_cache, proc_pid);
+ struct proc_data *pd = (struct proc_data *) trie_get(proc_data_cache, proc_pid);
if (!pd) {
pd = calloc(1, sizeof(*pd));
@@ -362,7 +362,7 @@ get_or_create_proc_data(int proc_pid)
return NULL;
pd->proc_pid = proc_pid;
- btree_set(proc_data_cache, proc_pid, (uint64_t) pd);
+ trie_set(proc_data_cache, proc_pid, (uint64_t) pd);
}
return pd;
@@ -397,7 +397,7 @@ fail:
if (pd)
free(pd);
- btree_set(proc_data_cache, pd->proc_pid, (uint64_t) NULL);
+ trie_set(proc_data_cache, pd->proc_pid, (uint64_t) NULL);
return false;
}
@@ -578,7 +578,7 @@ translate_pid(struct tcb *tcp, int from_id, enum pid_type type, int *proc_pid_pt
}
/* Iterate through the cache, find potential proc_data */
- btree_iterate_keys(proc_data_cache, 0, get_pid_max(), 0, proc_data_cache_iterator_fn, &tip);
+ trie_iterate_keys(proc_data_cache, 0, get_pid_max(), 0, proc_data_cache_iterator_fn, &tip);
/* (proc_data_cache_iterator_fn takes care about updating proc_data) */
if (tip.result_id)
goto translate_pid_exit;
diff --git a/btree.c b/trie.c
similarity index 63%
rename from btree.c
rename to trie.c
index dd64e212..e205bf97 100644
--- a/btree.c
+++ b/trie.c
@@ -7,12 +7,12 @@
#include <stdint.h>
#include <stdlib.h>
-#include "btree.h"
+#include "trie.h"
static const uint8_t ptr_sz_lg = (sizeof(uint64_t *) == 8 ? 6 : 5);
bool
-btree_check(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
+trie_check(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
uint8_t data_block_size_lg, uint8_t key_size)
{
if (item_size_lg > 6)
@@ -30,14 +30,14 @@ btree_check(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
}
void
-btree_init(struct btree *b, uint8_t item_size_lg, uint8_t ptr_block_size_lg,
+trie_init(struct trie *b, uint8_t item_size_lg, uint8_t ptr_block_size_lg,
uint8_t data_block_size_lg, uint8_t key_size, uint64_t set_value)
{
- assert(btree_check(item_size_lg, ptr_block_size_lg, data_block_size_lg,
+ assert(trie_check(item_size_lg, ptr_block_size_lg, data_block_size_lg,
key_size));
b->set_value = set_value;
- b->data = BTREE_UNSET;
+ b->data = TRIE_UNSET;
b->item_size_lg = item_size_lg;
b->ptr_block_size_lg = ptr_block_size_lg;
b->data_block_size_lg = data_block_size_lg;
@@ -45,7 +45,7 @@ btree_init(struct btree *b, uint8_t item_size_lg, uint8_t ptr_block_size_lg,
}
static uint8_t
-btree_get_depth(struct btree *b)
+trie_get_depth(struct trie *b)
{
return (b->key_size - (b->data_block_size_lg - b->item_size_lg) +
b->ptr_block_size_lg - ptr_sz_lg - 1) / (b->ptr_block_size_lg - ptr_sz_lg);
@@ -53,13 +53,13 @@ btree_get_depth(struct btree *b)
/**
* Returns lg2 of block size for the specific level of B-tree. If max_depth
- * provided is less than zero, it is calculated via btree_get_depth call.
+ * provided is less than zero, it is calculated via trie_get_depth call.
*/
static uint8_t
-btree_get_block_size(struct btree *b, uint8_t depth, int max_depth)
+trie_get_block_size(struct trie *b, uint8_t depth, int max_depth)
{
if (max_depth < 0)
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(b);
/* Last level contains data and we allow it having a different size */
if (depth == max_depth)
@@ -80,12 +80,12 @@ btree_get_block_size(struct btree *b, uint8_t depth, int max_depth)
* at the specific level.
*/
static uint8_t
-btree_get_block_bit_offs(struct btree *b, uint8_t depth, int max_depth)
+trie_get_block_bit_offs(struct trie *b, uint8_t depth, int max_depth)
{
uint8_t offs;
if (max_depth < 0)
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(b);
if (depth == max_depth)
return 0;
@@ -96,19 +96,19 @@ btree_get_block_bit_offs(struct btree *b, uint8_t depth, int max_depth)
return offs;
/* data_block_size + remainder */
- offs += btree_get_block_size(b, max_depth - 1, max_depth) - ptr_sz_lg;
+ offs += trie_get_block_size(b, max_depth - 1, max_depth) - ptr_sz_lg;
offs += (max_depth - depth - 2) * (b->ptr_block_size_lg - ptr_sz_lg);
return offs;
}
-struct btree *
-btree_create(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
+struct trie *
+trie_create(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
uint8_t data_block_size_lg, uint8_t key_size, uint64_t set_value)
{
- struct btree *b;
+ struct trie *b;
- if (!btree_check(item_size_lg, ptr_block_size_lg, data_block_size_lg,
+ if (!trie_check(item_size_lg, ptr_block_size_lg, data_block_size_lg,
key_size))
return NULL;
@@ -116,14 +116,14 @@ btree_create(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
if (!b)
return NULL;
- btree_init(b, item_size_lg, ptr_block_size_lg, data_block_size_lg,
+ trie_init(b, item_size_lg, ptr_block_size_lg, data_block_size_lg,
key_size, set_value);
return b;
}
static uint64_t
-btree_filler(uint64_t val, uint8_t item_size)
+trie_filler(uint64_t val, uint8_t item_size)
{
val &= (1 << (1 << item_size)) - 1;
@@ -134,7 +134,7 @@ btree_filler(uint64_t val, uint8_t item_size)
}
static uint64_t *
-btree_get_block(struct btree *b, uint64_t key, bool auto_create)
+trie_get_block(struct trie *b, uint64_t key, bool auto_create)
{
void **cur_block = &(b->data);
unsigned i;
@@ -145,12 +145,12 @@ btree_get_block(struct btree *b, uint64_t key, bool auto_create)
if (b->key_size < 64 && key > (uint64_t) 1 << b->key_size)
return NULL;
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(b);
for (cur_depth = 0; cur_depth <= max_depth; cur_depth++) {
- sz = btree_get_block_size(b, cur_depth, max_depth);
+ sz = trie_get_block_size(b, cur_depth, max_depth);
- if (*cur_block == BTREE_SET || *cur_block == BTREE_UNSET) {
+ if (*cur_block == TRIE_SET || *cur_block == TRIE_UNSET) {
void *old_val = *cur_block;
if (!auto_create)
@@ -158,17 +158,17 @@ btree_get_block(struct btree *b, uint64_t key, bool auto_create)
*cur_block = xcalloc(1 << sz, 8);
- if (old_val == BTREE_SET) {
- uint64_t fill_value = cur_depth == max_depth ? b->set_value : (uintptr_t) BTREE_SET;
+ if (old_val == TRIE_SET) {
+ uint64_t fill_value = cur_depth == max_depth ? b->set_value : (uintptr_t) TRIE_SET;
uint8_t fill_size = cur_depth == max_depth ? b->item_size_lg : ptr_sz_lg;
for (i = 0; i < ((unsigned int)1 << (sz - 3)); i++)
- ((uint64_t *) *cur_block)[i] = btree_filler(fill_value, fill_size);
+ ((uint64_t *) *cur_block)[i] = trie_filler(fill_value, fill_size);
}
}
if (cur_depth < max_depth) {
- size_t pos = (key >> btree_get_block_bit_offs(b,
+ size_t pos = (key >> trie_get_block_bit_offs(b,
cur_depth, max_depth)) & ((1 << (sz - ptr_sz_lg)) - 1);
cur_block = (((void **) (*cur_block)) + pos);
@@ -179,9 +179,9 @@ btree_get_block(struct btree *b, uint64_t key, bool auto_create)
}
bool
-btree_set(struct btree *b, uint64_t key, uint64_t val)
+trie_set(struct trie *b, uint64_t key, uint64_t val)
{
- uint64_t *data = btree_get_block(b, key, true);
+ uint64_t *data = trie_get_block(b, key, true);
size_t mask = (1 << (b->data_block_size_lg - b->item_size_lg)) - 1;
size_t pos = (key & mask) >> (6 - b->item_size_lg);
@@ -203,7 +203,7 @@ btree_set(struct btree *b, uint64_t key, uint64_t val)
#if 0
int
-btree_mask_set(struct btree *b, uint64_t key, uint8_t mask_bits)
+trie_mask_set(struct trie *b, uint64_t key, uint8_t mask_bits)
{
}
@@ -212,23 +212,23 @@ btree_mask_set(struct btree *b, uint64_t key, uint8_t mask_bits)
* key.
*/
int
-btree_mask_unset(struct btree *b, uint64_t key, uint8_t mask_bits)
+trie_mask_unset(struct trie *b, uint64_t key, uint8_t mask_bits)
{
}
int
-btree_interval_set(struct btree *b, uint64_t begin, uint64_t end, uint64_t val)
+trie_interval_set(struct trie *b, uint64_t begin, uint64_t end, uint64_t val)
{
}
uint64_t
-btree_get_next_set_key(struct btree *b, uint64_t key)
+trie_get_next_set_key(struct trie *b, uint64_t key)
{
}
#endif
static uint64_t
-btree_data_block_get(struct btree *b, uint64_t *data, uint64_t key)
+trie_data_block_get(struct trie *b, uint64_t *data, uint64_t key)
{
size_t mask;
size_t pos;
@@ -236,7 +236,7 @@ btree_data_block_get(struct btree *b, uint64_t *data, uint64_t key)
if (!data)
return 0;
- if ((void *) data == (void *) BTREE_SET)
+ if ((void *) data == (void *) TRIE_SET)
return b->set_value;
mask = (1 << (b->data_block_size_lg - b->item_size_lg)) - 1;
@@ -251,35 +251,35 @@ btree_data_block_get(struct btree *b, uint64_t *data, uint64_t key)
}
uint64_t
-btree_get(struct btree *b, uint64_t key)
+trie_get(struct trie *b, uint64_t key)
{
- return btree_data_block_get(b, btree_get_block(b, key, false), key);
+ return trie_data_block_get(b, trie_get_block(b, key, false), key);
}
static uint64_t
-btree_iterate_keys_block(struct btree *b, enum btree_iterate_flags flags,
- btree_iterate_fn fn, void *fn_data,
+trie_iterate_keys_block(struct trie *b, enum trie_iterate_flags flags,
+ trie_iterate_fn fn, void *fn_data,
uint64_t **block, uint64_t start, uint64_t end,
uint8_t depth, uint8_t max_depth)
{
if (start > end)
return 0;
- if ((block == BTREE_SET && !(flags & BTREE_ITERATE_KEYS_SET)) ||
- (block == BTREE_UNSET && !(flags & BTREE_ITERATE_KEYS_UNSET)))
+ if ((block == TRIE_SET && !(flags & TRIE_ITERATE_KEYS_SET)) ||
+ (block == TRIE_UNSET && !(flags & TRIE_ITERATE_KEYS_UNSET)))
return 0;
- if (block == BTREE_SET || block == BTREE_UNSET || depth == max_depth) {
+ if (block == TRIE_SET || block == TRIE_UNSET || depth == max_depth) {
for (uint64_t i = start; i <= end; i++)
- fn(fn_data, i, btree_data_block_get(b, (uint64_t *) block, i));
+ fn(fn_data, i, trie_data_block_get(b, (uint64_t *) block, i));
return end - start + 1; //TODO: overflow
}
- uint8_t parent_block_bit_off = depth == 0 ? b->key_size : btree_get_block_bit_offs(b, depth - 1, max_depth);
+ uint8_t parent_block_bit_off = depth == 0 ? b->key_size : trie_get_block_bit_offs(b, depth - 1, max_depth);
uint64_t first_key_in_block = start & (uint64_t) -1 << parent_block_bit_off;
- uint8_t block_bit_off = btree_get_block_bit_offs(b, depth, max_depth);
+ uint8_t block_bit_off = trie_get_block_bit_offs(b, depth, max_depth);
uint8_t block_key_bits = parent_block_bit_off - block_bit_off;
uint64_t mask = ((uint64_t) 1 << (block_key_bits)) - 1;
uint64_t start_index = (start >> block_bit_off) & mask;
@@ -297,7 +297,7 @@ btree_iterate_keys_block(struct btree *b, enum btree_iterate_flags flags,
if (child_end > end)
child_end = end;
- count += btree_iterate_keys_block(b, flags, fn, fn_data,
+ count += trie_iterate_keys_block(b, flags, fn, fn_data,
(uint64_t **) block[i], child_start, child_end,
depth + 1, max_depth);
}
@@ -305,40 +305,40 @@ btree_iterate_keys_block(struct btree *b, enum btree_iterate_flags flags,
return count;
}
-uint64_t btree_iterate_keys(struct btree *b, uint64_t start, uint64_t end,
- enum btree_iterate_flags flags, btree_iterate_fn fn,
+uint64_t trie_iterate_keys(struct trie *b, uint64_t start, uint64_t end,
+ enum trie_iterate_flags flags, trie_iterate_fn fn,
void *fn_data)
{
- return btree_iterate_keys_block(b, flags, fn, fn_data, b->data,
- start, end, 0, btree_get_depth(b));
+ return trie_iterate_keys_block(b, flags, fn, fn_data, b->data,
+ start, end, 0, trie_get_depth(b));
}
void
-btree_free_block(struct btree *b, uint64_t **block, uint8_t depth,
+trie_free_block(struct trie *b, uint64_t **block, uint8_t depth,
int max_depth)
{
size_t sz;
size_t i;
- if (block == BTREE_SET || block == BTREE_UNSET)
+ if (block == TRIE_SET || block == TRIE_UNSET)
return;
if (max_depth < 0)
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(b);
if (depth >= max_depth)
goto free_block;
- sz = 1 << (btree_get_block_size(b, depth, max_depth) - ptr_sz_lg);
+ sz = 1 << (trie_get_block_size(b, depth, max_depth) - ptr_sz_lg);
for (i = 0; i < sz; i++)
- btree_free_block(b, (uint64_t **) (block[i]), depth + 1, max_depth);
+ trie_free_block(b, (uint64_t **) (block[i]), depth + 1, max_depth);
free_block:
free(block);
}
void
-btree_free(struct btree *b)
+trie_free(struct trie *b)
{
- btree_free_block(b, b->data, 0, -1);
+ trie_free_block(b, b->data, 0, -1);
free(b);
}
diff --git a/btree.h b/trie.h
similarity index 61%
rename from btree.h
rename to trie.h
index 08e8f867..084b4702 100644
--- a/btree.h
+++ b/trie.h
@@ -1,17 +1,17 @@
-#ifndef STRACE_BTREE_H
-#define STRACE_BTREE_H
+#ifndef STRACE_TRIE_H
+#define STRACE_TRIE_H
/* Simple B-tree interface */
-#define BTREE_SET ((void *) ~(intptr_t) 0)
-#define BTREE_UNSET ((void *) NULL)
+#define TRIE_SET ((void *) ~(intptr_t) 0)
+#define TRIE_UNSET ((void *) NULL)
#define PTR_BLOCK_SIZE_LG_MAX 24
#define DATA_BLOCK_SIZE_LG_MAX 23
-enum btree_iterate_flags {
- BTREE_ITERATE_KEYS_SET = 1 << 0,
- BTREE_ITERATE_KEYS_UNSET = 1 << 1,
+enum trie_iterate_flags {
+ TRIE_ITERATE_KEYS_SET = 1 << 0,
+ TRIE_ITERATE_KEYS_UNSET = 1 << 1,
};
/**
@@ -22,8 +22,8 @@ enum btree_iterate_flags {
* * The key can be up to 64 bits in size.
* * It has separate configuration for pointer block size and data block size.
* * It can be used for mask storage - supports storing the flag that all keys
- * are set/unset in the middle tree layers. See also btree_mask_set() and
- * btree_mask_unset().
+ * are set/unset in the middle tree layers. See also trie_mask_set() and
+ * trie_mask_unset().
*
* How bits of key are used for different block levels:
*
@@ -37,7 +37,7 @@ enum btree_iterate_flags {
* As of now, it doesn't implement any mechanisms for resizing/changing key
* size. De-fragmentation is also unsupported currently.
*/
-struct btree {
+struct trie {
uint64_t set_value; /**< Default set value */
void *data;
uint8_t item_size_lg; /**< Item size log2, in bits, 0..6. */
@@ -48,43 +48,43 @@ struct btree {
uint8_t key_size; /**< Key size, in bits, 1..64. */
};
-typedef void (*btree_iterate_fn)(void *data, uint64_t key, uint64_t val);
+typedef void (*trie_iterate_fn)(void *data, uint64_t key, uint64_t val);
-bool btree_check(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
+bool trie_check(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
uint8_t data_block_size_lg, uint8_t key_size);
-void btree_init(struct btree *b, uint8_t item_size_lg,
+void trie_init(struct trie *b, uint8_t item_size_lg,
uint8_t ptr_block_size_lg, uint8_t data_block_size_lg,
uint8_t key_size, uint64_t set_value);
-struct btree * btree_create(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
+struct trie * trie_create(uint8_t item_size_lg, uint8_t ptr_block_size_lg,
uint8_t data_block_size_lg, uint8_t key_size,
uint64_t set_value);
-bool btree_set(struct btree *b, uint64_t key, uint64_t val);
+bool trie_set(struct trie *b, uint64_t key, uint64_t val);
#if 0
/**
* Sets to the value b->set_value all keys with 0-ed bits of mask equivalent to
* corresponding bits in key.
*/
-int btree_mask_set(struct btree *b, uint64_t key, uint8_t mask_bits);
+int trie_mask_set(struct trie *b, uint64_t key, uint8_t mask_bits);
/**
* Sets to 0 all keys with 0-ed bits of mask equivalent to corresponding bits in
* key.
*/
-int btree_mask_unset(struct btree *b, uint64_t key, uint8_t mask_bits);
-int btree_interval_set(struct btree *b, uint64_t begin, uint64_t end,
+int trie_mask_unset(struct trie *b, uint64_t key, uint8_t mask_bits);
+int trie_interval_set(struct trie *b, uint64_t begin, uint64_t end,
uint64_t val);
-uint64_t btree_get_next_set_key(struct btree *b, uint64_t key);
+uint64_t trie_get_next_set_key(struct trie *b, uint64_t key);
#endif
-uint64_t btree_iterate_keys(struct btree *b, uint64_t start, uint64_t end,
- enum btree_iterate_flags flags, btree_iterate_fn fn,
+uint64_t trie_iterate_keys(struct trie *b, uint64_t start, uint64_t end,
+ enum trie_iterate_flags flags, trie_iterate_fn fn,
void *fn_data);
-uint64_t btree_get(struct btree *b, uint64_t key);
+uint64_t trie_get(struct trie *b, uint64_t key);
-void btree_free_block(struct btree *b, uint64_t **block, uint8_t depth,
+void trie_free_block(struct trie *b, uint64_t **block, uint8_t depth,
int max_depth);
-void btree_free(struct btree *b);
+void trie_free(struct trie *b);
-#endif /* !STRACE_BTREE_H */
+#endif /* !STRACE_TRIE_H */
--
2.27.0
More information about the Strace-devel
mailing list