monotone

monotone Mtn Source Tree

Root/rev_height.cc

1// Copyright (C) 2006 Thomas Moschny <thomas.moschny@gmx.de>
2//
3// This program is made available under the GNU GPL version 2.0 or
4// greater. See the accompanying file COPYING for details.
5//
6// This program is distributed WITHOUT ANY WARRANTY; without even the
7// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8// PURPOSE.
9
10#include "base.hh"
11#include <sstream>
12
13#include "sanity.hh"
14#include "rev_height.hh"
15
16using std::ostream;
17using std::string;
18using std::ostringstream;
19
20/*
21 * Implementation note: hv, holding the raw revision height, is
22 * formally a string, but in fact is an array of u32 integers stored
23 * in big endian byte order. The same format is used for storing
24 * revision heights in the database. This has the advantage that we
25 * can use memcmp() for comparing them, which will be the most common
26 * operation for revision heights.
27 *
28 * One could also use vector<u32>. While this would be cleaner, it
29 * would force us to convert back and forth to the database format
30 * every now and then, and additionally inhibit the use of memcmp().
31 *
32 */
33
34// Internal manipulations
35size_t const width = sizeof(u32);
36
37static u32 read_at(string const & d, size_t pos)
38{
39 u32 value = 0;
40 size_t first = width * pos;
41
42 for (size_t i = first; i < first + width;)
43 {
44 value <<= 8;
45 value += d.at(i++) & 0xff;
46 }
47
48 return value;
49}
50
51static void write_at(string & d, size_t pos, u32 value)
52{
53 size_t first = width * pos;
54 for (size_t i = first + width ; i > first;)
55 {
56 d.at(--i) = value & 0xff;
57 value >>= 8;
58 }
59}
60
61static void append(string & d, u32 value)
62{
63 d.resize(d.size() + width); // make room
64 write_at(d, d.size() / width - 1, value);
65}
66
67// Creating derived heights
68rev_height rev_height::child_height(u32 nr) const
69{
70 string child = d;
71
72 if (nr == 0)
73 {
74 size_t pos = child.size() / width - 1;
75 u32 tmp = read_at(child, pos);
76 I(tmp < std::numeric_limits<u32>::max());
77 write_at(child, pos, tmp + 1);
78 }
79 else
80 {
81 append(child, nr - 1);
82 append(child, 0);
83 }
84 return rev_height(child);
85}
86
87rev_height rev_height::root_height()
88{
89 string root;
90 append(root, 0);
91 return rev_height(root);
92}
93
94// Human-readable output
95ostream & operator <<(ostream & os, rev_height const & h)
96{
97 bool first(true);
98 string const & d(h());
99
100 for (size_t i = 0; i < d.size() / width; ++i)
101 {
102 if (!first)
103os << '.';
104 os << read_at(d, i);
105 first = false;
106 }
107 return os;
108}
109
110void dump(rev_height const & h, string & out)
111{
112 ostringstream os;
113 os << h;
114 out = os.str();
115}
116
117
118#ifdef BUILD_UNIT_TESTS
119
120#include "unit_tests.hh"
121#include "randomizer.hh"
122
123UNIT_TEST(rev_height, count_up)
124{
125 rev_height h = rev_height::root_height().child_height(1);
126
127 I(h().size() / width == 3);
128 I(read_at(h(), 0) == 0);
129 I(read_at(h(), 1) == 0);
130 I(read_at(h(), 2) == 0);
131 UNIT_TEST_CHECK_THROW(read_at(h(), 3), std::out_of_range);
132
133 for (u32 n = 1; n < 10000; n++)
134 {
135 h = h.child_height(0);
136 I(read_at(h(), 0) == 0);
137 I(read_at(h(), 1) == 0);
138 I(read_at(h(), 2) == n);
139 }
140}
141
142UNIT_TEST(rev_height, children)
143{
144 rev_height h;
145 I(!h.valid());
146 h = rev_height::root_height();
147 I(h.valid());
148 MM(h);
149
150 randomizer rng;
151 for (u32 generations = 0; generations < 200; generations++)
152 {
153 L(FL("gen %d: %s") % generations % h);
154
155 // generate between five and ten children each time
156 u32 children = rng.uniform(5) + 5;
157 u32 survivor_no;
158
159 // take the first child 50% of the time, a randomly chosen second or
160 // subsequent child the rest of the time.
161 if (rng.flip())
162 survivor_no = 0;
163 else
164 survivor_no = 1 + rng.uniform(children - 2);
165
166 L(FL("gen %d: %d children, survivor %d")
167 % generations % children % survivor_no);
168
169 u32 parent_len = h().size() / width;
170 rev_height survivor;
171 MM(survivor);
172
173 for (u32 c = 0; c < children; c++)
174 {
175 rev_height child = h.child_height(c);
176 MM(child);
177 I(child.valid());
178 if (c == 0)
179 {
180 I(child().size() / width == parent_len);
181 I(read_at(child(), parent_len - 1)
182 == read_at(h(), parent_len - 1) + 1);
183 }
184 else
185 {
186 I(child().size() / width == parent_len + 2);
187 I(read_at(child(), parent_len - 1)
188 == read_at(h(), parent_len - 1));
189 I(read_at(child(), parent_len) == c - 1);
190 I(read_at(child(), parent_len + 1) == 0);
191 }
192 if (c == survivor_no)
193 survivor = child;
194 }
195 I(survivor.valid());
196 h = survivor;
197 }
198}
199
200UNIT_TEST(rev_height, comparisons)
201{
202 rev_height root(rev_height::root_height());
203 rev_height left(root.child_height(0));
204 rev_height right(root.child_height(1));
205
206 I(root < left);
207 I(root < right);
208 I(right < left);
209 for (u32 i = 0; i < 1000; i++)
210 {
211 rev_height rchild(right.child_height(0));
212 I(right < rchild);
213 I(rchild < left);
214 right = rchild;
215 }
216}
217
218#endif
219
220// Local Variables:
221// mode: C++
222// fill-column: 76
223// c-file-style: "gnu"
224// indent-tabs-mode: nil
225// End:
226// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status