1/* -*- c-basic-offset: 2 -*- */
2/*
3 Copyright(C) 2011-2016 Brazil
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License version 2.1 as published by the Free Software Foundation.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public
15 License along with this library; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17*/
18
19#pragma once
20
21#include "dat.hpp"
22
23namespace grn {
24namespace dat {
25
26class GRN_DAT_API Check {
27 public:
28 Check() : value_(0) {}
29
30 bool operator==(const Check &rhs) const {
31 return value_ == rhs.value_;
32 }
33
34 // The most significant bit represents whether or not the node ID is used as
35 // an offset. Note that the MSB is independent of the other bits.
36 bool is_offset() const {
37 return (value_ & IS_OFFSET_FLAG) == IS_OFFSET_FLAG;
38 }
39
40 UInt32 except_is_offset() const {
41 GRN_DAT_DEBUG_THROW_IF(is_phantom());
42 return value_ & ~IS_OFFSET_FLAG;
43 }
44
45 // A phantom node is a node that has never been used, and such a node is also
46 // called an empty element. Phantom nodes form a doubly linked list in each
47 // block, and the linked list is represented by next() and prev().
48 bool is_phantom() const {
49 return (value_ & IS_PHANTOM_FLAG) == IS_PHANTOM_FLAG;
50 }
51
52 UInt32 next() const {
53 GRN_DAT_DEBUG_THROW_IF(!is_phantom());
54 return (value_ >> NEXT_SHIFT) & BLOCK_MASK;
55 }
56 UInt32 prev() const {
57 GRN_DAT_DEBUG_THROW_IF(!is_phantom());
58 return (value_ >> PREV_SHIFT) & BLOCK_MASK;
59 }
60
61 // A label is attached to each non-phantom node. A label is represented by
62 // a byte except for a terminal label '\256'. Note that a phantom node always
63 // returns an invalid label with its phantom bit flag so as to reject invalid
64 // transitions.
65 UInt32 label() const {
66 return value_ & (IS_PHANTOM_FLAG | LABEL_MASK);
67 }
68
69 // A non-phantom node has the labels of the first child and the next sibling.
70 // Note that INVALID_LABEL is stored if the node has no child nodes or has
71 // no more siblings.
72 UInt32 child() const {
73 return (value_ >> CHILD_SHIFT) & LABEL_MASK;
74 }
75 UInt32 sibling() const {
76 return (value_ >> SIBLING_SHIFT) & LABEL_MASK;
77 }
78
79 void set_is_offset(bool x) {
80 if (x) {
81 GRN_DAT_DEBUG_THROW_IF(is_offset());
82 value_ |= IS_OFFSET_FLAG;
83 } else {
84 GRN_DAT_DEBUG_THROW_IF(!is_offset());
85 value_ &= ~IS_OFFSET_FLAG;
86 }
87 }
88
89 void set_except_is_offset(UInt32 x) {
90 GRN_DAT_DEBUG_THROW_IF(is_phantom());
91 GRN_DAT_DEBUG_THROW_IF((x & IS_OFFSET_FLAG) == IS_OFFSET_FLAG);
92 value_ = (value_ & IS_OFFSET_FLAG) | x;
93 }
94
95 // To reject a transition to an incomplete node, set_is_phantom() invalidates
96 // its label and links when it becomes non-phantom.
97 void set_is_phantom(bool x) {
98 if (x) {
99 GRN_DAT_DEBUG_THROW_IF(is_phantom());
100 value_ |= IS_PHANTOM_FLAG;
101 } else {
102 GRN_DAT_DEBUG_THROW_IF(!is_phantom());
103 value_ = (value_ & IS_OFFSET_FLAG) | (INVALID_LABEL << CHILD_SHIFT) |
104 (INVALID_LABEL << SIBLING_SHIFT) | INVALID_LABEL;
105 }
106 }
107
108 void set_next(UInt32 x) {
109 GRN_DAT_DEBUG_THROW_IF(!is_phantom());
110 GRN_DAT_DEBUG_THROW_IF(x > BLOCK_MASK);
111 value_ = (value_ & ~(BLOCK_MASK << NEXT_SHIFT)) | (x << NEXT_SHIFT);
112 }
113 void set_prev(UInt32 x) {
114 GRN_DAT_DEBUG_THROW_IF(!is_phantom());
115 GRN_DAT_DEBUG_THROW_IF(x > BLOCK_MASK);
116 value_ = (value_ & ~(BLOCK_MASK << PREV_SHIFT)) | (x << PREV_SHIFT);
117 }
118
119 void set_label(UInt32 x) {
120 GRN_DAT_DEBUG_THROW_IF(is_phantom());
121 GRN_DAT_DEBUG_THROW_IF(x > MAX_LABEL);
122 value_ = (value_ & ~LABEL_MASK) | x;
123 }
124
125 void set_child(UInt32 x) {
126 GRN_DAT_DEBUG_THROW_IF(is_phantom());
127 GRN_DAT_DEBUG_THROW_IF(x > MAX_LABEL);
128 value_ = (value_ & ~(LABEL_MASK << CHILD_SHIFT)) | (x << CHILD_SHIFT);
129 }
130 void set_sibling(UInt32 x) {
131 GRN_DAT_DEBUG_THROW_IF(is_phantom());
132 GRN_DAT_DEBUG_THROW_IF(label() > MAX_LABEL);
133 GRN_DAT_DEBUG_THROW_IF((sibling() != INVALID_LABEL) && (x == INVALID_LABEL));
134 value_ = (value_ & ~(LABEL_MASK << SIBLING_SHIFT)) | (x << SIBLING_SHIFT);
135 }
136
137 private:
138 UInt32 value_;
139
140 static const UInt32 IS_OFFSET_FLAG = 1U << 31;
141 static const UInt32 IS_PHANTOM_FLAG = 1U << 30;
142 static const UInt32 NEXT_SHIFT = 9;
143 static const UInt32 PREV_SHIFT = 18;
144 static const UInt32 CHILD_SHIFT = 9;
145 static const UInt32 SIBLING_SHIFT = 18;
146};
147
148} // namespace dat
149} // namespace grn
150