From 04be35ecaa02cd4fa090d099d7f6d34dbdb03ad8 Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Tue, 9 Apr 2019 16:25:29 +0200
Subject: [PATCH] Trie index: storing existence of indices

---
 lib/tindex.c      | 37 ++++++++++++++++++++++++++++++++++---
 lib/tindex.h      | 16 +---------------
 lib/tindex_test.c |  3 ++-
 3 files changed, 37 insertions(+), 19 deletions(-)

diff --git a/lib/tindex.c b/lib/tindex.c
index e49d3ce1f..fedbe95ae 100644
--- a/lib/tindex.c
+++ b/lib/tindex.c
@@ -26,6 +26,7 @@ union tindex_data {
 
 struct tindex {
   union tindex_data *index_data;
+  u64 *exists;
   pool *p;
   struct idm idm;
   u8 unit_size;
@@ -40,6 +41,7 @@ tindex_new(pool *p)
   ti->unit_size = TI_MIN_UNIT_SIZE;
   ti->address_size = TI_MIN_ADDRESS_SIZE;
   ti->index_data = mb_allocz(p, ti->unit_size * (1 << ti->address_size));
+  ti->exists = mb_allocz(p, (1 << (ti->address_size - 3)));
   idm_init(&(ti->idm), p, (1 << (ti->address_size - 5)), (1 << ti->address_size));
   u32 rootnode = idm_alloc(&(ti->idm));
   ASSERT(rootnode == 1);
@@ -234,6 +236,24 @@ static inline uint tindex_input_bits(const u64 *bits_in, const uint blen, uint *
   return ilen;
 }
 
+static inline void
+tindex_exists_set(const struct tindex *ti, const u64 idx)
+{
+  ti->exists[idx / 64] |= (1ULL << (idx % 64));
+}
+
+static inline u64
+tindex_exists(const struct tindex *ti, const u64 idx)
+{
+  return (ti->exists[idx / 64] & (1ULL << (idx % 64)));
+}
+
+static inline void
+tindex_exists_clear(const struct tindex *ti, const u64 idx)
+{
+  ti->exists[idx / 64] &= ~(1ULL << (idx % 64));
+}
+
 const char dump_indent[] = "                                                                ";
 #define INDENT (dump_indent + sizeof(dump_indent) - depth - 1)
 
@@ -263,7 +283,7 @@ _tindex_dump(const struct tindex *ti, u64 idx, uint depth, uint bit)
   if (depth)
     dlen++;
 
-  debug("%s0x%x/%u (%lu)\n", INDENT, data, dlen, idx);
+  debug("%s0x%x/%u (%lu %c)\n", INDENT, data, dlen, idx, tindex_exists(ti, idx) ? '*' : ' ');
   u64 left = tindex_left(ti, idx, usize, asize, addrmask);
   if (left)
     _tindex_dump(ti, left, depth+1, 0);
@@ -325,11 +345,19 @@ tindex_find(struct tindex *ti, const u64 *bits_in, const uint blen, const int cr
       ilen = tindex_input_bits(bits_in, blen, &bpos, 1, &bits);
 
       /* No more bits, we're done */
-      if (!ilen)
+      if (!ilen) {
+	/* Existence bits fiddling */
+	if (create)
+	  tindex_exists_set(ti, idx);
+	else if (!tindex_exists(ti, idx))
+	  return 0;
+
 	return idx;
+      }
 
       /* Just one bit, to be sure */
       ASSERT(bits < 2);
+      ASSERT(ilen == 1);
 
       /* Go left or right? */
       u64 nidx = bits ? tindex_right(ti, idx, usize, asize, addrmask) : tindex_left(ti, idx, usize, asize, addrmask);
@@ -410,8 +438,10 @@ tindex_find(struct tindex *ti, const u64 *bits_in, const uint blen, const int cr
     /* Grow there a branch if it has to be grown, otherwise return */
     if (split)
       break;
-    else
+    else {
+      tindex_exists_set(ti, midx);
       return midx;
+    }
   }
 
   /* Growing a new branch */
@@ -426,6 +456,7 @@ tindex_find(struct tindex *ti, const u64 *bits_in, const uint blen, const int cr
     /* End of input data */
     if ((ilen < dsize - 1) || !tindex_input_bits(bits_in, blen, &bpos, 1, &dataright)) {
       tindex_put(ti, idx, usize, asize, dsize, dshift, data, ilen, 0, 0, uidx);
+      tindex_exists_set(ti, idx);
       return idx;
     }
 
diff --git a/lib/tindex.h b/lib/tindex.h
index acd65c42d..bdc31ba52 100644
--- a/lib/tindex.h
+++ b/lib/tindex.h
@@ -10,21 +10,7 @@
 #include "nest/bird.h"
 
 /**
- * tindex_bitcheck() callback is called by tindex_find() repeatedly
- * to get input bits as needed. Maximal number of bits is
- * given in @len; it shall be replaced the actual number of bits
- * returned. The bits shall be returned in LSB of the return value.
- * If (and only if) no bits are remaining, @len shall be changed,
- * otherwise the callee must always return full bit string.
- *
- * This is intended to be implemented as a nested function in
- * a library call using this tree index.
- **/
-
-typedef u64 (*tindex_bitcheck)(u8 *len);
-
-/**
- * Allocate a new tr[ei]e index from the given pool
+ * Allocate a new trie index from the given pool
  * @p: pool to allocate from
  *
  * Returns the allocated tindex structure.
diff --git a/lib/tindex_test.c b/lib/tindex_test.c
index e11af414f..4698b8a37 100644
--- a/lib/tindex_test.c
+++ b/lib/tindex_test.c
@@ -19,6 +19,7 @@ struct test_trie {
 
 static inline void test_trie_add(struct test_trie *tt, u64 data) {
   u64 idx = tindex_find(tt->ti, &data, 64, 1);
+  bt_assert(idx > 0);
 
   u64 nlen = tt->len;
   while (idx > nlen)
@@ -57,7 +58,7 @@ t_simple(void)
   }
 
   for (u64 i = 0; i < 20; i++)
-    bt_assert(test_trie_get(&tt, i) == 1);
+    bt_assert_msg(test_trie_get(&tt, i) == 1, "Index %lu shall be in trie", i);
 
   return 1;
 }
-- 
2.47.2