[RFC PATCH v3 10/14] [squash] Rename btree to trie
Ákos Uzonyi
uzonyi.akos at gmail.com
Sat Jun 13 11:25:32 UTC 2020
---
btree.c | 180 ++++++++++++++++++++++++++++----------------------------
btree.h | 56 +++++++++---------
pidns.c | 30 +++++-----
3 files changed, 133 insertions(+), 133 deletions(-)
diff --git a/btree.c b/btree.c
index dd64e212..0ba10f70 100644
--- a/btree.c
+++ b/btree.c
@@ -1,4 +1,4 @@
-/* Simple B-tree implementation for key-value mapping storage */
+/* Simple trie implementation for key-value mapping storage */
#include "defs.h"
@@ -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,47 +30,47 @@ 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 *t, 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->item_size_lg = item_size_lg;
- b->ptr_block_size_lg = ptr_block_size_lg;
- b->data_block_size_lg = data_block_size_lg;
- b->key_size = key_size;
+ t->set_value = set_value;
+ t->data = TRIE_UNSET;
+ t->item_size_lg = item_size_lg;
+ t->ptr_block_size_lg = ptr_block_size_lg;
+ t->data_block_size_lg = data_block_size_lg;
+ t->key_size = key_size;
}
static uint8_t
-btree_get_depth(struct btree *b)
+trie_get_depth(struct trie *t)
{
- 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);
+ return (t->key_size - (t->data_block_size_lg - t->item_size_lg) +
+ t->ptr_block_size_lg - ptr_sz_lg - 1) / (t->ptr_block_size_lg - ptr_sz_lg);
}
/**
- * 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.
+ * Returns lg2 of block size for the specific level of the trie. If max_depth
+ * 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 *t, uint8_t depth, int max_depth)
{
if (max_depth < 0)
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(t);
/* Last level contains data and we allow it having a different size */
if (depth == max_depth)
- return b->data_block_size_lg;
+ return t->data_block_size_lg;
/* Last level of the tree can be smaller */
if (depth == max_depth - 1)
- return (b->key_size -
- (b->data_block_size_lg - b->item_size_lg) - 1) %
- (b->ptr_block_size_lg - ptr_sz_lg) + 1 + ptr_sz_lg;
+ return (t->key_size -
+ (t->data_block_size_lg - t->item_size_lg) - 1) %
+ (t->ptr_block_size_lg - ptr_sz_lg) + 1 + ptr_sz_lg;
- return b->ptr_block_size_lg;
+ return t->ptr_block_size_lg;
}
#define round_down(a, b) (((a) / (b)) * (b))
@@ -80,50 +80,50 @@ 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 *t, uint8_t depth, int max_depth)
{
uint8_t offs;
if (max_depth < 0)
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(t);
if (depth == max_depth)
return 0;
- offs = b->data_block_size_lg - b->item_size_lg;
+ offs = t->data_block_size_lg - t->item_size_lg;
if (depth == max_depth - 1)
return offs;
/* data_block_size + remainder */
- offs += btree_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);
+ offs += trie_get_block_size(t, max_depth - 1, max_depth) - ptr_sz_lg;
+ offs += (max_depth - depth - 2) * (t->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 *t;
- 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;
- b = malloc(sizeof(*b));
- if (!b)
+ t = malloc(sizeof(*t));
+ if (!t)
return NULL;
- btree_init(b, item_size_lg, ptr_block_size_lg, data_block_size_lg,
+ trie_init(t, item_size_lg, ptr_block_size_lg, data_block_size_lg,
key_size, set_value);
- return b;
+ return t;
}
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,23 +134,23 @@ 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 *t, uint64_t key, bool auto_create)
{
- void **cur_block = &(b->data);
+ void **cur_block = &(t->data);
unsigned i;
uint8_t cur_depth;
uint8_t max_depth;
uint8_t sz;
- if (b->key_size < 64 && key > (uint64_t) 1 << b->key_size)
+ if (t->key_size < 64 && key > (uint64_t) 1 << t->key_size)
return NULL;
- max_depth = btree_get_depth(b);
+ max_depth = trie_get_depth(t);
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(t, 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;
- uint8_t fill_size = cur_depth == max_depth ? b->item_size_lg : ptr_sz_lg;
+ if (old_val == TRIE_SET) {
+ uint64_t fill_value = cur_depth == max_depth ? t->set_value : (uintptr_t) TRIE_SET;
+ uint8_t fill_size = cur_depth == max_depth ? t->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(t,
cur_depth, max_depth)) & ((1 << (sz - ptr_sz_lg)) - 1);
cur_block = (((void **) (*cur_block)) + pos);
@@ -179,20 +179,20 @@ 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 *t, uint64_t key, uint64_t val)
{
- uint64_t *data = btree_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);
+ uint64_t *data = trie_get_block(t, key, true);
+ size_t mask = (1 << (t->data_block_size_lg - t->item_size_lg)) - 1;
+ size_t pos = (key & mask) >> (6 - t->item_size_lg);
if (!data)
return false;
- if (b->item_size_lg == 6) {
+ if (t->item_size_lg == 6) {
data[pos] = val;
} else {
- size_t offs = (key & ((1 << (6 - b->item_size_lg)) - 1)) * (1 << b->item_size_lg);
- uint64_t mask = (((uint64_t) 1 << (1 << b->item_size_lg)) - 1) << offs;
+ size_t offs = (key & ((1 << (6 - t->item_size_lg)) - 1)) * (1 << t->item_size_lg);
+ uint64_t mask = (((uint64_t) 1 << (1 << t->item_size_lg)) - 1) << offs;
data[pos] &= ~mask;
data[pos] |= (val << offs) & mask;
@@ -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 *t, 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 *t, 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 *t, 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 *t, 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 *t, uint64_t *data, uint64_t key)
{
size_t mask;
size_t pos;
@@ -236,50 +236,50 @@ btree_data_block_get(struct btree *b, uint64_t *data, uint64_t key)
if (!data)
return 0;
- if ((void *) data == (void *) BTREE_SET)
- return b->set_value;
+ if ((void *) data == (void *) TRIE_SET)
+ return t->set_value;
- mask = (1 << (b->data_block_size_lg - b->item_size_lg)) - 1;
- pos = (key & mask) >> (6 - b->item_size_lg);
+ mask = (1 << (t->data_block_size_lg - t->item_size_lg)) - 1;
+ pos = (key & mask) >> (6 - t->item_size_lg);
- if (b->item_size_lg == 6)
+ if (t->item_size_lg == 6)
return data[pos];
- offs = (key & ((1 << (6 - b->item_size_lg)) - 1)) * (1 << b->item_size_lg);
+ offs = (key & ((1 << (6 - t->item_size_lg)) - 1)) * (1 << t->item_size_lg);
- return (data[pos] >> offs) & (((uint64_t)1 << (1 << b->item_size_lg)) - 1);
+ return (data[pos] >> offs) & (((uint64_t)1 << (1 << t->item_size_lg)) - 1);
}
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 *t, 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(t, (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 ? t->key_size : trie_get_block_bit_offs(t, 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(t, 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(t, 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 *t, 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(t, flags, fn, fn_data, t->data,
+ start, end, 0, trie_get_depth(t));
}
void
-btree_free_block(struct btree *b, uint64_t **block, uint8_t depth,
+trie_free_block(struct trie *t, 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(t);
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(t, 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(t, (uint64_t **) (block[i]), depth + 1, max_depth);
free_block:
free(block);
}
void
-btree_free(struct btree *b)
+trie_free(struct trie *t)
{
- btree_free_block(b, b->data, 0, -1);
- free(b);
+ trie_free_block(t, t->data, 0, -1);
+ free(t);
}
diff --git a/btree.h b/btree.h
index 08e8f867..32637e87 100644
--- a/btree.h
+++ b/btree.h
@@ -1,29 +1,29 @@
-#ifndef STRACE_BTREE_H
-#define STRACE_BTREE_H
+#ifndef STRACE_TRIE_H
+#define STRACE_TRIE_H
-/* Simple B-tree interface */
+/* Simple trie 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,
};
/**
- * B-tree control structure.
- * B-tree implemented here has the following properties:
+ * Trie control structure.
+ * Trie implemented here has the following properties:
* * It allows storing values of the same size, the size can vary from 1 bit to
* 64 bit values (only power of 2 sizes are allowed).
* * 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 *t, 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 *t, 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 *t, 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 *t, uint64_t key, uint8_t mask_bits);
+int trie_interval_set(struct trie *t, 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 *t, 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 *t, 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 *t, uint64_t key);
-void btree_free_block(struct btree *b, uint64_t **block, uint8_t depth,
+void trie_free_block(struct trie *t, uint64_t **block, uint8_t depth,
int max_depth);
-void btree_free(struct btree *b);
+void trie_free(struct trie *t);
-#endif /* !STRACE_BTREE_H */
+#endif /* !STRACE_TRIE_H */
diff --git a/pidns.c b/pidns.c
index cf127711..4bdec595 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;
--
2.27.0
More information about the Strace-devel
mailing list