compact.mx raw

   1  package lattice
   2  
   3  func (t *Tree) NeedsCompact() bool {
   4  	return len(t.Pending) > 0 || t.FreeCount > t.nCount/8
   5  }
   6  
   7  func (t *Tree) Compact() int {
   8  	for i := range t.Pending {
   9  		t.propagateOne(t.Pending[i])
  10  	}
  11  	t.Pending = t.Pending[:0]
  12  
  13  	if t.FreeCount == 0 {
  14  		return 0
  15  	}
  16  
  17  	moves := map[uint32]uint32{}
  18  	tail := t.nCount - 1
  19  
  20  	freeSet := map[uint32]bool{}
  21  	cur := t.FreeHead
  22  	for cur != NullIndex {
  23  		freeSet[cur] = true
  24  		next := t.getNode(cur).Children[0]
  25  		cur = next
  26  	}
  27  
  28  	for tail > 0 && freeSet[tail] {
  29  		delete(freeSet, tail)
  30  		tail--
  31  	}
  32  
  33  	for gap := range freeSet {
  34  		if gap >= tail {
  35  			continue
  36  		}
  37  		for tail > gap && freeSet[tail] {
  38  			delete(freeSet, tail)
  39  			tail--
  40  		}
  41  		if tail <= gap {
  42  			break
  43  		}
  44  		*t.getNode(gap) = *t.getNode(tail)
  45  		t.markNodeDirty(gap)
  46  		moves[tail] = gap
  47  		freeSet[tail] = true
  48  		tail--
  49  		for tail > 0 && freeSet[tail] {
  50  			delete(freeSet, tail)
  51  			tail--
  52  		}
  53  	}
  54  
  55  	newCount := tail + 1
  56  	for i := uint32(0); i < newCount; i++ {
  57  		node := t.getNode(i)
  58  		dirty := false
  59  		for ci := 0; ci < 4; ci++ {
  60  			if newIdx, ok := moves[node.Children[ci]]; ok {
  61  				node.Children[ci] = newIdx
  62  				dirty = true
  63  			}
  64  		}
  65  		if dirty {
  66  			t.markNodeDirty(i)
  67  		}
  68  	}
  69  	for ri := 0; ri < 3; ri++ {
  70  		if newIdx, ok := moves[t.Roots[ri]]; ok {
  71  			t.Roots[ri] = newIdx
  72  		}
  73  	}
  74  
  75  	reclaimed := int(t.FreeCount)
  76  	if t.cache == nil {
  77  		t.Nodes = t.Nodes[:newCount]
  78  	}
  79  	t.nCount = newCount
  80  	t.FreeHead = NullIndex
  81  	t.FreeCount = 0
  82  	return reclaimed
  83  }
  84  
  85  func (t *Tree) propagateOne(pe PendingExp) {
  86  	root := t.Roots[pe.Branch]
  87  	t.propagateSubtree(root, pe.Factor)
  88  }
  89  
  90  func (t *Tree) propagateSubtree(idx uint32, factor uint8) {
  91  	if idx == NullIndex {
  92  		return
  93  	}
  94  	node := t.getNode(idx)
  95  	if node.IsDeleted() {
  96  		return
  97  	}
  98  	if node.Mult > 1 {
  99  		node.Mult = 1
 100  		t.markNodeDirty(idx)
 101  	}
 102  	for ci := 0; ci <= node.KeyCount(); ci++ {
 103  		if node.Children[ci] != NullIndex {
 104  			t.propagateSubtree(node.Children[ci], factor)
 105  		}
 106  	}
 107  }
 108