src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

evaluate.go (797B)

      1 package bdd
      2 
      3 const resultOffset int32 = 100_000_000
      4 const intsPerNode = 3
      5 
      6 // Evaluate traverses a compiled BDD node array and returns the result index.
      7 // nodes is a flat array of [condIdx, hi, lo] triples (1-indexed).
      8 // root is the root node reference. evalCond returns true/false for condition index.
      9 func Evaluate(nodes []int32, root int32, evalCond func(int) bool) int32 {
     10 	ref := root
     11 	for {
     12 		if ref >= resultOffset {
     13 			return ref - resultOffset
     14 		}
     15 		if ref == 1 || ref == -1 {
     16 			return 0 // NoMatchRule
     17 		}
     18 
     19 		complement := ref < 0
     20 		nodeIdx := ref
     21 		if complement {
     22 			nodeIdx = -ref
     23 		}
     24 		base := (nodeIdx - 1) * intsPerNode
     25 		condIdx := nodes[base]
     26 		hi := nodes[base+1]
     27 		lo := nodes[base+2]
     28 
     29 		if complement != evalCond(int(condIdx)) {
     30 			ref = hi
     31 		} else {
     32 			ref = lo
     33 		}
     34 	}
     35 }