traverse: navigates the tree downward to locate the target or its closest position
()
| 327 | |
| 328 | // traverse: navigates the tree downward to locate the target or its closest position |
| 329 | func (s *SMT) traverse() (err lib.ErrorI) { |
| 330 | // execute main loop |
| 331 | for { |
| 332 | var currentKey []byte |
| 333 | // add current to traversed |
| 334 | s.traversed.Nodes = append(s.traversed.Nodes, s.current.copy()) |
| 335 | // decide to move left or right based on the bit-value of the key |
| 336 | switch s.pathBit = s.target.Key.bitAt(s.bitPos); s.pathBit { |
| 337 | case LeftChild: // move down to the left |
| 338 | currentKey = s.current.LeftChildKey |
| 339 | case RightChild: // move down to the right |
| 340 | currentKey = s.current.RightChildKey |
| 341 | } |
| 342 | // load current node from the store |
| 343 | s.current, err = s.getNode(currentKey) |
| 344 | if err != nil { |
| 345 | return |
| 346 | } |
| 347 | // defensive nil check |
| 348 | if s.current == nil { |
| 349 | return ErrInvalidMerkleTree() |
| 350 | } |
| 351 | // load the bytes into the key |
| 352 | s.current.Key.fromBytes(currentKey) |
| 353 | // update the greatest common prefix and the bit position based on the new current key |
| 354 | s.target.Key.greatestCommonPrefix(&s.bitPos, s.gcp, s.current.Key) |
| 355 | // exit conditions, current != gcp || current == target |
| 356 | if !s.current.Key.equals(s.gcp) || s.target.Key.equals(s.gcp) { |
| 357 | return // exit loop |
| 358 | } |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | // rehash() recalculate hashes from the current node upwards until |
| 363 | // a) the next operation key is LTE the right sibling's key, after truncating it to the right sibling's key length |