| 68 | } |
| 69 | |
| 70 | bool TOpaqueTrieIterator::Backward() { |
| 71 | if (AtEmptyValue) |
| 72 | return false; |
| 73 | |
| 74 | if (!Trie.Length) { |
| 75 | if (EmptyValue) { |
| 76 | // A trie that has only the empty value; |
| 77 | // we are not at the empty value, so move to it. |
| 78 | AtEmptyValue = true; |
| 79 | return true; |
| 80 | } else { |
| 81 | // Empty trie. |
| 82 | return false; |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | if (Forks.Empty()) { |
| 87 | TFork fork(Trie.Data, 0, Trie.Length, Trie.SkipFunction); |
| 88 | fork.LastDirection(); |
| 89 | Forks.Push(fork); |
| 90 | } else { |
| 91 | TFork* topFork = &Forks.Top(); |
| 92 | while (!topFork->PrevDirection()) { |
| 93 | if (topFork->Node.GetOffset() >= Trie.Length) |
| 94 | return false; |
| 95 | Forks.Pop(); |
| 96 | if (!Forks.Empty()) { |
| 97 | topFork = &Forks.Top(); |
| 98 | } else { |
| 99 | // When there are no more forks, |
| 100 | // we have to iterate over the empty value. |
| 101 | if (!EmptyValue) |
| 102 | return false; |
| 103 | AtEmptyValue = true; |
| 104 | return true; |
| 105 | } |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | Y_ASSERT(!Forks.Empty()); |
| 110 | while (Forks.Top().CurrentDirection != D_FINAL && !HasMaxKeyLength()) { |
| 111 | TFork nextFork = Forks.Top().NextFork(Trie.SkipFunction); |
| 112 | nextFork.LastDirection(); |
| 113 | Forks.Push(nextFork); |
| 114 | } |
| 115 | TFork& top = Forks.Top(); |
| 116 | static_assert(D_FINAL < D_NEXT, "relative order of NEXT and FINAL directions has changed"); |
| 117 | if (HasMaxKeyLength() && top.CurrentDirection == D_NEXT && top.HasDirection(D_FINAL)) { |
| 118 | top.PrevDirection(); |
| 119 | } |
| 120 | if (MeasureNarrowKey() == 0) { |
| 121 | // This is the '\0' key, skip it and get to the EmptyValue. |
| 122 | AtEmptyValue = true; |
| 123 | Forks.Clear(); |
| 124 | } |
| 125 | return true; |
| 126 | } |
| 127 |
no test coverage detected