tree_test.mx raw

   1  package iskra
   2  
   3  import "testing"
   4  
   5  func TestNewTree(t *testing.T) {
   6  	tr := NewInMemoryTree(100)
   7  	if tr.EntryCount() != 0 {
   8  		t.Fatal("new tree should have 0 entries")
   9  	}
  10  }
  11  
  12  func TestInsertAndWalk(t *testing.T) {
  13  	tr := NewInMemoryTree(100)
  14  	content := []byte("hello")
  15  	key := SegmentKey(StageSRC, content)
  16  	ri := tr.Insert(KindToBranch(KindFunc), key, "hello", KindFunc, StageSRC)
  17  	if ri == NullLatticeRec {
  18  		t.Fatal("Insert returned NullRec")
  19  	}
  20  	_, _, found := tr.WalkAll(key)
  21  	if !found {
  22  		t.Fatal("inserted key not found")
  23  	}
  24  	if tr.EntryCount() != 1 {
  25  		t.Fatal("expected 1 entry, got " | fmt_int(tr.EntryCount()))
  26  	}
  27  }
  28  
  29  func TestWalkMiss(t *testing.T) {
  30  	tr := NewInMemoryTree(100)
  31  	key := SegmentKey(StageSRC, []byte("hello"))
  32  	tr.Insert(KindToBranch(KindFunc), key, "hello", KindFunc, StageSRC)
  33  	missKey := SegmentKey(StageSRC, []byte("goodbye"))
  34  	_, _, found := tr.WalkAll(missKey)
  35  	if found {
  36  		t.Fatal("non-existent key should not be found")
  37  	}
  38  }
  39  
  40  func TestInsertMany(t *testing.T) {
  41  	tr := NewInMemoryTree(200)
  42  	n := 100
  43  	keys := []uint64{:0:n}
  44  	for i := 0; i < n; i++ {
  45  		content := []byte("seg_" | string(rune('A'+i%26)) | string(rune('0'+i/26)))
  46  		key := SegmentKey(StageSRC, content)
  47  		tr.Insert(KindToBranch(KindFunc), key, "seg", KindFunc, StageSRC)
  48  		keys = append(keys, key)
  49  	}
  50  	if tr.EntryCount() != n {
  51  		t.Fatal("expected " | fmt_int(n) | " entries, got " | fmt_int(tr.EntryCount()))
  52  	}
  53  	for _, key := range keys {
  54  		_, _, found := tr.WalkAll(key)
  55  		if !found {
  56  			t.Fatal("key not found after bulk insert")
  57  		}
  58  	}
  59  }
  60  
  61  func TestLookupMeta(t *testing.T) {
  62  	tr := NewInMemoryTree(100)
  63  	content := []byte("fn body")
  64  	key := SegmentKey(StageSRC, content)
  65  	tr.Insert(KindToBranch(KindFunc), key, "MyFunc", KindFunc, StageSRC)
  66  	found := tr.LookupMeta(key)
  67  	if found == nil {
  68  		t.Fatal("LookupMeta returned nil")
  69  	}
  70  	if found.StageTag != StageSRC {
  71  		t.Fatal("wrong stage tag")
  72  	}
  73  	if found.Kind != KindFunc {
  74  		t.Fatal("wrong kind")
  75  	}
  76  }
  77  
  78  func TestLookupMetaMiss(t *testing.T) {
  79  	tr := NewInMemoryTree(100)
  80  	key := SegmentKey(StageSRC, []byte("missing"))
  81  	found := tr.LookupMeta(key)
  82  	if found != nil {
  83  		t.Fatal("LookupMeta should return nil for missing key")
  84  	}
  85  }
  86  
  87  func TestFormAt(t *testing.T) {
  88  	tr := NewInMemoryTree(100)
  89  	content := []byte("fn body")
  90  	key := SegmentKey(StageSRC, content)
  91  	ri := tr.Insert(KindToBranch(KindFunc), key, "DecodeRune", KindFunc, StageSRC)
  92  	form := tr.FormAt(ri)
  93  	if form != "DecodeRune" {
  94  		t.Fatal("wrong form: " | form)
  95  	}
  96  }
  97  
  98  func fmt_int(n int) string {
  99  	if n == 0 {
 100  		return "0"
 101  	}
 102  	neg := n < 0
 103  	if neg {
 104  		n = -n
 105  	}
 106  	buf := []byte{:0:20}
 107  	for n > 0 {
 108  		buf = append(buf, byte('0'+n%10))
 109  		n /= 10
 110  	}
 111  	if neg {
 112  		buf = append(buf, '-')
 113  	}
 114  	for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
 115  		buf[i], buf[j] = buf[j], buf[i]
 116  	}
 117  	return string(buf)
 118  }
 119