|
1 /* |
|
2 * Copyright 2008 Intel Corporation |
|
3 * |
|
4 * Licensed under the Apache License, Version 2.0 (the "License"); |
|
5 * you may not use this file except in compliance with the License. |
|
6 * You may obtain a copy of the License at |
|
7 * |
|
8 * http://www.apache.org/licenses/LICENSE-2.0 |
|
9 * |
|
10 * Unless required by applicable law or agreed to in writing, software |
|
11 * distributed under the License is distributed on an "AS IS" BASIS, |
|
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
13 * See the License for the specific language governing permissions and |
|
14 * limitations under the License. |
|
15 */ |
|
16 |
|
17 #ifdef HAVE_CONFIG_H |
|
18 # include <dtn-config.h> |
|
19 #endif |
|
20 |
|
21 #include <ctype.h> |
|
22 #include <oasys/util/SafeRange.h> |
|
23 #include <oasys/util/StringAppender.h> |
|
24 #include <oasys/util/StringBuffer.h> |
|
25 #include "SequenceID.h" |
|
26 |
|
27 namespace dtn { |
|
28 |
|
29 //---------------------------------------------------------------------- |
|
30 SequenceID::SequenceID() |
|
31 { |
|
32 } |
|
33 |
|
34 //---------------------------------------------------------------------------- |
|
35 const char* |
|
36 SequenceID::comp2str(comp_t eq) |
|
37 { |
|
38 switch(eq) { |
|
39 case LT: return "less than"; |
|
40 case GT: return "greater than"; |
|
41 case EQ: return "equal to"; |
|
42 case NEQ: return "uncomparable to"; |
|
43 default: NOTREACHED; |
|
44 } |
|
45 } |
|
46 |
|
47 //---------------------------------------------------------------------- |
|
48 void |
|
49 SequenceID::add(const EndpointID& eid, u_int64_t counter) |
|
50 { |
|
51 vector_.push_back(Entry(eid, counter)); |
|
52 } |
|
53 |
|
54 //---------------------------------------------------------------------- |
|
55 void |
|
56 SequenceID::add(const EndpointID& eid, const std::string& identifier) |
|
57 { |
|
58 vector_.push_back(Entry(eid, identifier)); |
|
59 } |
|
60 |
|
61 //---------------------------------------------------------------------- |
|
62 const SequenceID::Entry& |
|
63 SequenceID::get_entry(const EndpointID& eid) const |
|
64 { |
|
65 for (const_iterator i = begin(); i != end(); ++i) { |
|
66 if (i->eid_ == eid) { |
|
67 return *i; |
|
68 } |
|
69 } |
|
70 |
|
71 static Entry null_entry; |
|
72 return null_entry; |
|
73 } |
|
74 |
|
75 //---------------------------------------------------------------------------- |
|
76 u_int64_t |
|
77 SequenceID::get_counter(const EndpointID& eid) const |
|
78 { |
|
79 return get_entry(eid).counter_; |
|
80 } |
|
81 |
|
82 //---------------------------------------------------------------------------- |
|
83 std::string |
|
84 SequenceID::get_identifier(const EndpointID& eid) const |
|
85 { |
|
86 return get_entry(eid).identifier_; |
|
87 } |
|
88 |
|
89 //---------------------------------------------------------------------------- |
|
90 int |
|
91 SequenceID::format(char* buf, size_t sz) const |
|
92 { |
|
93 oasys::StringAppender sa(buf, sz); |
|
94 |
|
95 sa.append('<'); |
|
96 for (const_iterator i = begin(); i != end(); ++i) |
|
97 { |
|
98 if (i->type_ == COUNTER) { |
|
99 sa.appendf("%s(%s %llu)", |
|
100 (i == begin()) ? "" : " ", |
|
101 i->eid_.c_str(), |
|
102 U64FMT(i->counter_)); |
|
103 } else if (i->type_ == IDENTIFIER) { |
|
104 sa.appendf("%s(%s %s)", |
|
105 (i == begin()) ? "" : " ", |
|
106 i->eid_.c_str(), |
|
107 i->identifier_.c_str()); |
|
108 } else { |
|
109 NOTREACHED; |
|
110 } |
|
111 } |
|
112 sa.append('>'); |
|
113 |
|
114 return sa.desired_length(); |
|
115 } |
|
116 |
|
117 //---------------------------------------------------------------------- |
|
118 std::string |
|
119 SequenceID::to_str() const |
|
120 { |
|
121 oasys::StaticStringBuffer<256> buf; |
|
122 buf.appendf("*%p", this); |
|
123 return (std::string)buf.c_str(); |
|
124 } |
|
125 |
|
126 //---------------------------------------------------------------------------- |
|
127 bool |
|
128 SequenceID::parse(const std::string& str) |
|
129 { |
|
130 #define EAT_WS() while (isspace(sr[idx])) { idx++; } |
|
131 #define MATCH_CHAR(_c) do { \ |
|
132 if (sr[idx] != _c) { goto bad; } else { idx++; } \ |
|
133 } while (0) |
|
134 |
|
135 EntryVec old_vec = vector_; |
|
136 vector_.clear(); |
|
137 |
|
138 oasys::SafeRange<const char> sr(str.c_str(), str.size()); |
|
139 |
|
140 try |
|
141 { |
|
142 size_t idx = 0; |
|
143 const char *start; |
|
144 char *end; |
|
145 |
|
146 MATCH_CHAR('<'); |
|
147 EAT_WS(); |
|
148 while (sr[idx] == '(') |
|
149 { |
|
150 MATCH_CHAR('('); |
|
151 start = &sr[idx]; |
|
152 |
|
153 do { |
|
154 ++idx; |
|
155 } while (!isspace(sr[idx])); |
|
156 |
|
157 EndpointID eid(start, &sr[idx] - start); |
|
158 if (! eid.valid()) { |
|
159 goto bad; |
|
160 } |
|
161 |
|
162 EAT_WS(); |
|
163 |
|
164 bool isnum = true; |
|
165 size_t idx2 = idx; |
|
166 do { |
|
167 // this check should handle the case of having no |
|
168 // value part in the entry as well as bogus characters |
|
169 if (! (isalnum(sr[idx2]) || |
|
170 sr[idx2] == '_' || |
|
171 sr[idx2] == '-' ) ) |
|
172 { |
|
173 goto bad; |
|
174 } |
|
175 |
|
176 isnum = isnum && isdigit(sr[idx2]); |
|
177 ++idx2; |
|
178 |
|
179 } while (sr[idx2] != ')' && sr[idx2] != '\0'); |
|
180 |
|
181 if (isnum) { |
|
182 u_int64_t counter = strtoull(&sr[idx], &end, 10); |
|
183 ASSERT(end == &sr[idx2]); |
|
184 vector_.push_back(Entry(eid, counter)); |
|
185 |
|
186 } else { |
|
187 std::string identifier(&sr[idx], idx2-idx); |
|
188 vector_.push_back(Entry(eid, identifier)); |
|
189 } |
|
190 |
|
191 idx = idx2; |
|
192 MATCH_CHAR(')'); |
|
193 EAT_WS(); |
|
194 } |
|
195 |
|
196 if (sr[idx] != '>') |
|
197 { |
|
198 goto bad; |
|
199 } |
|
200 |
|
201 return true; |
|
202 } |
|
203 catch (oasys::SafeRange<const char>::Error e) |
|
204 { |
|
205 // drop through to bad below |
|
206 } |
|
207 |
|
208 bad: |
|
209 vector_.swap(old_vec); |
|
210 return false; |
|
211 |
|
212 #undef EAT_WS |
|
213 #undef MATCH_CHAR |
|
214 } |
|
215 |
|
216 //---------------------------------------------------------------------------- |
|
217 SequenceID::comp_t |
|
218 SequenceID::compare(const SequenceID& other) const |
|
219 { |
|
220 if (empty() && other.empty()) |
|
221 { |
|
222 return EQ; |
|
223 } |
|
224 |
|
225 // We need to compare the sequence vectors in both directions, |
|
226 // since entries that exist in one but not the other are |
|
227 // implicitly zero. This approach unnecessarily repeats |
|
228 // comparisons but it's not a big deal since the vectors shouldn't |
|
229 // be very long. |
|
230 |
|
231 comp_t cur_state = EQ; |
|
232 cur_state = compare_one_way(other, *this, cur_state); |
|
233 ASSERT(cur_state != ILL); |
|
234 |
|
235 if (cur_state != NEQ) |
|
236 { |
|
237 // invert the state and call again, this time in the "forward" |
|
238 // direction |
|
239 switch (cur_state) { |
|
240 case LT: cur_state = GT; break; |
|
241 case GT: cur_state = LT; break; |
|
242 case EQ: cur_state = EQ; break; |
|
243 case NEQ: |
|
244 case ILL: |
|
245 NOTREACHED; |
|
246 } |
|
247 |
|
248 cur_state = compare_one_way(*this, other, cur_state); |
|
249 } |
|
250 |
|
251 return cur_state; |
|
252 } |
|
253 |
|
254 //---------------------------------------------------------------------------- |
|
255 SequenceID::comp_t |
|
256 SequenceID::compare_one_way(const SequenceID& lv, |
|
257 const SequenceID& rv, |
|
258 comp_t cur_state) |
|
259 { |
|
260 // State transition for comparing the vectors |
|
261 static comp_t states[4][3] = { |
|
262 /* cur_state cur_comparison */ |
|
263 /* LT EQ GT */ |
|
264 /* LT */ { LT, LT, NEQ }, |
|
265 /* EQ */ { LT, EQ, GT }, //<- new |
|
266 /* GT */ { NEQ, GT, GT }, //<- state |
|
267 /* NEQ */ { NEQ, NEQ, NEQ } |
|
268 }; |
|
269 |
|
270 // To align the enum (i.e. values -1 to 2) with the correct array |
|
271 // indices, we have to add one to the index values |
|
272 #define next_state(_cur_state, _cur_comp) \ |
|
273 states[(_cur_state) + 1][(_cur_comp) + 1] |
|
274 |
|
275 for (const_iterator i = lv.begin(); i != lv.end(); ++i) |
|
276 { |
|
277 const Entry& left = lv.get_entry(i->eid_); |
|
278 const Entry& right = rv.get_entry(i->eid_); |
|
279 |
|
280 cur_state = next_state(cur_state, compare_entries(left, right)); |
|
281 |
|
282 // once we get into NEQ state we can't ever get out so short |
|
283 // circuit the remainder of the comparisons |
|
284 if (cur_state == NEQ) |
|
285 { |
|
286 return NEQ; |
|
287 } |
|
288 } |
|
289 |
|
290 return cur_state; |
|
291 |
|
292 #undef next_state |
|
293 } |
|
294 |
|
295 //---------------------------------------------------------------------------- |
|
296 SequenceID::comp_t |
|
297 SequenceID::compare_entries(const Entry& left, const Entry& right) |
|
298 { |
|
299 if (left.type_ == COUNTER || left.type_ == EMPTY) |
|
300 { |
|
301 // if right is an identifier and the left is either a counter |
|
302 // or empty, they can't be equal |
|
303 if (right.type_ == IDENTIFIER) |
|
304 { |
|
305 return NEQ; |
|
306 } |
|
307 |
|
308 if (left.counter_ == right.counter_) |
|
309 { |
|
310 return EQ; |
|
311 } |
|
312 else if (left.counter_ < right.counter_) |
|
313 { |
|
314 return LT; |
|
315 } |
|
316 else |
|
317 { |
|
318 return GT; |
|
319 } |
|
320 } |
|
321 else if (left.type_ == IDENTIFIER) |
|
322 { |
|
323 // in the case of identifiers, the lack of a column entry is |
|
324 // not the same thing as an existing column with a value of |
|
325 // "", so if the right's type is counter OR empty, return NEQ |
|
326 if (right.type_ != IDENTIFIER) |
|
327 { |
|
328 return NEQ; |
|
329 } |
|
330 |
|
331 if (left.identifier_ != right.identifier_) |
|
332 { |
|
333 return NEQ; |
|
334 } |
|
335 else |
|
336 { |
|
337 return EQ; |
|
338 } |
|
339 } |
|
340 |
|
341 NOTREACHED; |
|
342 } |
|
343 |
|
344 //---------------------------------------------------------------------- |
|
345 void |
|
346 SequenceID::assign(const SequenceID& other) |
|
347 { |
|
348 vector_ = other.vector_; |
|
349 } |
|
350 |
|
351 //---------------------------------------------------------------------- |
|
352 void |
|
353 SequenceID::update(const SequenceID& other) |
|
354 { |
|
355 for (const_iterator other_entry = other.begin(); |
|
356 other_entry != other.end(); |
|
357 ++other_entry) |
|
358 { |
|
359 iterator my_entry = begin(); |
|
360 while (my_entry != end()) { |
|
361 if (other_entry->eid_ == my_entry->eid_) |
|
362 break; |
|
363 ++my_entry; |
|
364 } |
|
365 |
|
366 if (my_entry == end()) |
|
367 { |
|
368 if (other_entry->type_ == COUNTER) { |
|
369 add(other_entry->eid_, other_entry->counter_); |
|
370 |
|
371 } else if (other_entry->type_ == IDENTIFIER) { |
|
372 add(other_entry->eid_, other_entry->identifier_); |
|
373 |
|
374 } else { |
|
375 NOTREACHED; |
|
376 } |
|
377 |
|
378 continue; |
|
379 } |
|
380 |
|
381 if (other_entry->type_ != my_entry->type_) { |
|
382 PANIC("can't update with mismatched types"); |
|
383 } |
|
384 |
|
385 if (other_entry->type_ == COUNTER && |
|
386 other_entry->counter_ > my_entry->counter_) |
|
387 { |
|
388 my_entry->counter_ = other_entry->counter_; |
|
389 } |
|
390 |
|
391 if (other_entry->type_ == IDENTIFIER && |
|
392 other_entry->identifier_ != my_entry->identifier_) |
|
393 { |
|
394 // always replace |
|
395 my_entry->identifier_ = other_entry->identifier_; |
|
396 } |
|
397 } |
|
398 } |
|
399 |
|
400 } // namespace dtn |