00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifdef HAVE_CONFIG_H
00018 # include <dtn-config.h>
00019 #endif
00020
00021 #include <ctype.h>
00022 #include <string.h>
00023 #include <oasys/util/SafeRange.h>
00024 #include <oasys/util/StringAppender.h>
00025 #include <oasys/util/StringBuffer.h>
00026 #include "SequenceID.h"
00027
00028 namespace dtn {
00029
00030
00031 SequenceID::SequenceID()
00032 {
00033 }
00034
00035
00036 const char*
00037 SequenceID::comp2str(comp_t eq)
00038 {
00039 switch(eq) {
00040 case LT: return "less than";
00041 case GT: return "greater than";
00042 case EQ: return "equal to";
00043 case NEQ: return "uncomparable to";
00044 default: NOTREACHED;
00045 }
00046 }
00047
00048
00049 void
00050 SequenceID::add(const EndpointID& eid, u_int64_t counter)
00051 {
00052 vector_.push_back(Entry(eid, counter));
00053 }
00054
00055
00056 void
00057 SequenceID::add(const EndpointID& eid, const std::string& identifier)
00058 {
00059 vector_.push_back(Entry(eid, identifier));
00060 }
00061
00062
00063 const SequenceID::Entry&
00064 SequenceID::get_entry(const EndpointID& eid) const
00065 {
00066 for (const_iterator i = begin(); i != end(); ++i) {
00067 if (i->eid_ == eid) {
00068 return *i;
00069 }
00070 }
00071
00072 static Entry null_entry;
00073 return null_entry;
00074 }
00075
00076
00077 u_int64_t
00078 SequenceID::get_counter(const EndpointID& eid) const
00079 {
00080 return get_entry(eid).counter_;
00081 }
00082
00083
00084 std::string
00085 SequenceID::get_identifier(const EndpointID& eid) const
00086 {
00087 return get_entry(eid).identifier_;
00088 }
00089
00090
00091 int
00092 SequenceID::format(char* buf, size_t sz) const
00093 {
00094 oasys::StringAppender sa(buf, sz);
00095
00096 sa.append('<');
00097 for (const_iterator i = begin(); i != end(); ++i)
00098 {
00099 if (i->type_ == COUNTER) {
00100 sa.appendf("%s(%s %llu)",
00101 (i == begin()) ? "" : " ",
00102 i->eid_.c_str(),
00103 U64FMT(i->counter_));
00104 } else if (i->type_ == IDENTIFIER) {
00105 sa.appendf("%s(%s %s)",
00106 (i == begin()) ? "" : " ",
00107 i->eid_.c_str(),
00108 i->identifier_.c_str());
00109 } else {
00110 NOTREACHED;
00111 }
00112 }
00113 sa.append('>');
00114
00115 return sa.desired_length();
00116 }
00117
00118
00119 std::string
00120 SequenceID::to_str() const
00121 {
00122 oasys::StaticStringBuffer<256> buf;
00123 buf.appendf("*%p", this);
00124 return (std::string)buf.c_str();
00125 }
00126
00127
00128 bool
00129 SequenceID::parse(const std::string& str)
00130 {
00131 #define EAT_WS() while (isspace(sr[idx])) { idx++; }
00132 #define MATCH_CHAR(_c) do { \
00133 if (sr[idx] != _c) { goto bad; } else { idx++; } \
00134 } while (0)
00135
00136 EntryVec old_vec = vector_;
00137 vector_.clear();
00138
00139 oasys::SafeRange<const char> sr(str.c_str(), str.size());
00140
00141 try
00142 {
00143 size_t idx = 0;
00144 const char *start;
00145 char *end;
00146
00147 MATCH_CHAR('<');
00148 EAT_WS();
00149 while (sr[idx] == '(')
00150 {
00151 MATCH_CHAR('(');
00152 start = &sr[idx];
00153
00154 do {
00155 ++idx;
00156 } while (!isspace(sr[idx]));
00157
00158 EndpointID eid(start, &sr[idx] - start);
00159 if (! eid.valid()) {
00160 goto bad;
00161 }
00162
00163 EAT_WS();
00164
00165 bool isnum = true;
00166 size_t idx2 = idx;
00167 do {
00168
00169
00170 if (! (isalnum(sr[idx2]) ||
00171 sr[idx2] == '_' ||
00172 sr[idx2] == '-' ) )
00173 {
00174 goto bad;
00175 }
00176
00177 isnum = isnum && isdigit(sr[idx2]);
00178 ++idx2;
00179
00180 } while (sr[idx2] != ')' && sr[idx2] != '\0');
00181
00182 if (isnum) {
00183 u_int64_t counter = strtoull(&sr[idx], &end, 10);
00184 ASSERT(end == &sr[idx2]);
00185 vector_.push_back(Entry(eid, counter));
00186
00187 } else {
00188 std::string identifier(&sr[idx], idx2-idx);
00189 vector_.push_back(Entry(eid, identifier));
00190 }
00191
00192 idx = idx2;
00193 MATCH_CHAR(')');
00194 EAT_WS();
00195 }
00196
00197 if (sr[idx] != '>')
00198 {
00199 goto bad;
00200 }
00201
00202 return true;
00203 }
00204 catch (oasys::SafeRange<const char>::Error e)
00205 {
00206
00207 }
00208
00209 bad:
00210 vector_.swap(old_vec);
00211 return false;
00212
00213 #undef EAT_WS
00214 #undef MATCH_CHAR
00215 }
00216
00217
00218 SequenceID::comp_t
00219 SequenceID::compare(const SequenceID& other) const
00220 {
00221 if (empty() && other.empty())
00222 {
00223 return EQ;
00224 }
00225
00226
00227
00228
00229
00230
00231
00232 comp_t cur_state = EQ;
00233 cur_state = compare_one_way(other, *this, cur_state);
00234 ASSERT(cur_state != ILL);
00235
00236 if (cur_state != NEQ)
00237 {
00238
00239
00240 switch (cur_state) {
00241 case LT: cur_state = GT; break;
00242 case GT: cur_state = LT; break;
00243 case EQ: cur_state = EQ; break;
00244 case NEQ:
00245 case ILL:
00246 NOTREACHED;
00247 }
00248
00249 cur_state = compare_one_way(*this, other, cur_state);
00250 }
00251
00252 return cur_state;
00253 }
00254
00255
00256 SequenceID::comp_t
00257 SequenceID::compare_one_way(const SequenceID& lv,
00258 const SequenceID& rv,
00259 comp_t cur_state)
00260 {
00261
00262 static comp_t states[4][3] = {
00263
00264
00265 { LT, LT, NEQ },
00266 { LT, EQ, GT },
00267 { NEQ, GT, GT },
00268 { NEQ, NEQ, NEQ }
00269 };
00270
00271
00272
00273 #define next_state(_cur_state, _cur_comp) \
00274 states[(_cur_state) + 1][(_cur_comp) + 1]
00275
00276 for (const_iterator i = lv.begin(); i != lv.end(); ++i)
00277 {
00278 const Entry& left = lv.get_entry(i->eid_);
00279 const Entry& right = rv.get_entry(i->eid_);
00280
00281 cur_state = next_state(cur_state, compare_entries(left, right));
00282
00283
00284
00285 if (cur_state == NEQ)
00286 {
00287 return NEQ;
00288 }
00289 }
00290
00291 return cur_state;
00292
00293 #undef next_state
00294 }
00295
00296
00297 SequenceID::comp_t
00298 SequenceID::compare_entries(const Entry& left, const Entry& right)
00299 {
00300 if (left.type_ == COUNTER || left.type_ == EMPTY)
00301 {
00302
00303
00304 if (right.type_ == IDENTIFIER)
00305 {
00306 return NEQ;
00307 }
00308
00309 if (left.counter_ == right.counter_)
00310 {
00311 return EQ;
00312 }
00313 else if (left.counter_ < right.counter_)
00314 {
00315 return LT;
00316 }
00317 else
00318 {
00319 return GT;
00320 }
00321 }
00322 else if (left.type_ == IDENTIFIER)
00323 {
00324
00325
00326
00327 if (right.type_ != IDENTIFIER)
00328 {
00329 return NEQ;
00330 }
00331
00332 if (left.identifier_ != right.identifier_)
00333 {
00334 return NEQ;
00335 }
00336 else
00337 {
00338 return EQ;
00339 }
00340 }
00341
00342 NOTREACHED;
00343 }
00344
00345
00346 void
00347 SequenceID::assign(const SequenceID& other)
00348 {
00349 vector_ = other.vector_;
00350 }
00351
00352
00353 void
00354 SequenceID::update(const SequenceID& other)
00355 {
00356 for (const_iterator other_entry = other.begin();
00357 other_entry != other.end();
00358 ++other_entry)
00359 {
00360 iterator my_entry = begin();
00361 while (my_entry != end()) {
00362 if (other_entry->eid_ == my_entry->eid_)
00363 break;
00364 ++my_entry;
00365 }
00366
00367 if (my_entry == end())
00368 {
00369 if (other_entry->type_ == COUNTER) {
00370 add(other_entry->eid_, other_entry->counter_);
00371
00372 } else if (other_entry->type_ == IDENTIFIER) {
00373 add(other_entry->eid_, other_entry->identifier_);
00374
00375 } else {
00376 NOTREACHED;
00377 }
00378
00379 continue;
00380 }
00381
00382 if (other_entry->type_ != my_entry->type_) {
00383 PANIC("can't update with mismatched types");
00384 }
00385
00386 if (other_entry->type_ == COUNTER &&
00387 other_entry->counter_ > my_entry->counter_)
00388 {
00389 my_entry->counter_ = other_entry->counter_;
00390 }
00391
00392 if (other_entry->type_ == IDENTIFIER &&
00393 other_entry->identifier_ != my_entry->identifier_)
00394 {
00395
00396 my_entry->identifier_ = other_entry->identifier_;
00397 }
00398 }
00399 }
00400
00401 }