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