[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