xorp

config_node_id.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8:
00003 
00004 // Copyright (c) 2001-2011 XORP, Inc and Others
00005 //
00006 // This program is free software; you can redistribute it and/or modify
00007 // it under the terms of the GNU Lesser General Public License, Version
00008 // 2.1, June 1999 as published by the Free Software Foundation.
00009 // Redistribution and/or modification of this program under the terms of
00010 // any other version of the GNU Lesser General Public License is not
00011 // permitted.
00012 // 
00013 // This program is distributed in the hope that it will be useful, but
00014 // WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00016 // see the GNU Lesser General Public License, Version 2.1, a copy of
00017 // which can be found in the XORP LICENSE.lgpl file.
00018 // 
00019 // XORP, Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00020 // http://xorp.net
00021 
00022 // $XORP: xorp/libproto/config_node_id.hh,v 1.12 2008/10/02 21:57:17 bms Exp $
00023 
00024 
00025 #ifndef __LIBPROTO_CONFIG_NODE_ID_HH__
00026 #define __LIBPROTO_CONFIG_NODE_ID_HH__
00027 
00028 
00029 #include "libxorp/xorp.h"
00030 #include "libxorp/xlog.h"
00031 #include "libxorp/exceptions.hh"
00032 
00033 
00034 
00035 
00036 
00037 //
00038 // Configuration Node ID support
00039 //
00040 
00052 class ConfigNodeId {
00053 public:
00054     typedef uint64_t UniqueNodeId;
00055     typedef uint64_t Position;
00056     typedef uint32_t InstanceId;
00057 
00068     explicit ConfigNodeId(const string& s) throw (InvalidString) {
00069     copy_in(s);
00070     }
00071 
00072 #ifdef XORP_USE_USTL
00073     ConfigNodeId() { }
00074 #endif
00075 
00082     ConfigNodeId(const UniqueNodeId& unique_node_id, const Position& position)
00083     : _unique_node_id(unique_node_id), _position(position) {}
00084 
00088     virtual ~ConfigNodeId() {}
00089 
00096     size_t copy_in(const string& from_string) throw (InvalidString);
00097 
00105     bool operator==(const ConfigNodeId& other) const;
00106 
00112     const UniqueNodeId& unique_node_id() const { return (_unique_node_id); }
00113 
00119     const Position& position() const { return (_position); }
00120 
00126     void set_instance_id(const InstanceId& v);
00127 
00135     void set_position(const Position& v) { _position = v; }
00136 
00145     const ConfigNodeId& generate_unique_node_id();
00146 
00153     string str() const {
00154     ostringstream ost;
00155     //
00156     // XXX: We use ostringstream instead of the c_format() facility
00157     // because the c_format() facility doesn't work well for uint64_t
00158     // integers: on 32-bit architectures the coversion specifier
00159     // has to be %llu, while on 64-bit architectures it should be %lu.
00160     // Note that this is c_format() specific problem and it doesn't
00161     // exist for the system printf().
00162     //
00163     ost << _unique_node_id << " " << _position;
00164     return ost.str();
00165     }
00166 
00172     bool is_empty() const { return (_unique_node_id == 0); }
00173 
00177     static ConfigNodeId ZERO() { return ConfigNodeId(0, 0); }
00178 
00179 private:
00180     UniqueNodeId    _unique_node_id;    // The unique node ID
00181     Position        _position;      // The position of the node
00182 };
00183 
00198 template <typename V>
00199 class ConfigNodeIdMap {
00200 public:
00201     typedef list<pair<ConfigNodeId, V> >    ValuesList;
00202     typedef typename ValuesList::iterator   iterator;
00203     typedef typename ValuesList::const_iterator const_iterator;
00204 
00208     ConfigNodeIdMap() {}
00209 
00213     virtual ~ConfigNodeIdMap() {}
00214 
00220     typename ConfigNodeIdMap::iterator begin() {
00221     return (_values_list.begin());
00222     }
00223 
00229     typename ConfigNodeIdMap::const_iterator begin() const {
00230     return _values_list.begin();
00231     }
00232 
00238     typename ConfigNodeIdMap::iterator end() { return (_values_list.end()); }
00239 
00245     typename ConfigNodeIdMap::const_iterator end() const {
00246     return _values_list.end();
00247     }
00248 
00255     typename ConfigNodeIdMap::iterator find(const ConfigNodeId& node_id);
00256 
00263     typename ConfigNodeIdMap::const_iterator find(const ConfigNodeId& node_id) const;
00264 
00278     pair<iterator, bool> insert(const ConfigNodeId& node_id,
00279                 const V& v) {
00280     return (insert_impl(node_id, v, false));
00281     }
00282 
00294     pair<iterator, bool> insert_out_of_order(
00295     const ConfigNodeId& node_id, const V& v) {
00296     return (insert_impl(node_id, v, true));
00297     }
00298 
00305     size_t erase(const ConfigNodeId& node_id);
00306 
00312     void erase(ConfigNodeIdMap::iterator iter);
00313 
00317     void clear();
00318 
00325     string str() const;
00326 
00332     size_t size() const { return (_node_id2iter.size()); }
00333 
00339     bool empty() const { return (size() == 0); }
00340 
00341 private:
00359     pair<iterator, bool> insert_impl(const ConfigNodeId& node_id,
00360                      const V& v,
00361                      bool ignore_missing_previous_element);
00362 
00363     typedef map<ConfigNodeId::UniqueNodeId, iterator> NodeId2IterMap;
00364 
00365     NodeId2IterMap  _node_id2iter;      // The node ID to iterator map
00366     ValuesList      _values_list;       // The list with the values
00367 };
00368 
00369 inline size_t
00370 ConfigNodeId::copy_in(const string& from_string) throw (InvalidString)
00371 {
00372     string::size_type space, ix;
00373     string s = from_string;
00374 
00375     if (s.empty()) {
00376     _unique_node_id = 0;
00377     _position = 0;
00378     return (from_string.size());
00379     }
00380 
00381     space = s.find(' ');
00382     if ((space == string::npos) || (space == 0) || (space >= s.size() - 1)) {
00383     xorp_throw(InvalidString,
00384            c_format("Bad ConfigNodeId \"%s\"", s.c_str()));
00385     }
00386 
00387     //
00388     // Check that everything from the beginning to "space" is digits,
00389     // and that everything after "space" to the end is also digits.
00390     //
00391     for (ix = 0; ix < space; ix++) {
00392     if (! xorp_isdigit(s[ix])) {
00393         xorp_throw(InvalidString,
00394                c_format("Bad ConfigNodeId \"%s\"", s.c_str()));
00395     }
00396     }
00397     for (ix = space + 1; ix < s.size(); ix++) {
00398     if (! xorp_isdigit(s[ix])) {
00399         xorp_throw(InvalidString,
00400                c_format("Bad ConfigNodeId \"%s\"", s.c_str()));
00401     }
00402     }
00403 
00404     //
00405     // Extract the unique node ID and the position.
00406     //
00407     string tmp_str = s.substr(0, space);
00408     _unique_node_id = strtoll(tmp_str.c_str(), (char **)NULL, 10);
00409     tmp_str = s.substr(space + 1);
00410     _position = strtoll(tmp_str.c_str(), (char **)NULL, 10);
00411 
00412     return (from_string.size());
00413 }
00414 
00415 inline bool
00416 ConfigNodeId::operator==(const ConfigNodeId& other) const
00417 {
00418     return ((_unique_node_id == other._unique_node_id)
00419         && (_position == other._position));
00420 }
00421 
00422 inline void
00423 ConfigNodeId::set_instance_id(const InstanceId& v)
00424 {
00425     // Set the upper 32 bits to the instance ID
00426     uint64_t h = (0xffffffffU & v);
00427     h = h << 32;
00428     _unique_node_id &= 0xffffffffU;
00429     _unique_node_id |= h;
00430 }
00431 
00432 inline const ConfigNodeId&
00433 ConfigNodeId::generate_unique_node_id()
00434 {
00435     // Check that the lower 32 bits of the unique node ID won't overflow
00436     XLOG_ASSERT((0xffffffffU & _unique_node_id) + 1 != 0);
00437 
00438     _unique_node_id++;
00439 
00440     return (*this);
00441 }
00442 
00443 template <typename V>
00444 inline typename ConfigNodeIdMap<V>::iterator
00445 ConfigNodeIdMap<V>::find(const ConfigNodeId& node_id)
00446 {
00447     typename NodeId2IterMap::iterator node_id_iter;
00448 
00449     node_id_iter = _node_id2iter.find(node_id.unique_node_id());
00450     if (node_id_iter == _node_id2iter.end())
00451     return (_values_list.end());
00452 
00453     return (node_id_iter->second);
00454 }
00455 
00456 template <typename V>
00457 inline typename ConfigNodeIdMap<V>::const_iterator
00458 ConfigNodeIdMap<V>::find(const ConfigNodeId& node_id) const
00459 {
00460     typename NodeId2IterMap::const_iterator node_id_iter;
00461 
00462     node_id_iter = _node_id2iter.find(node_id.unique_node_id());
00463     if (node_id_iter == _node_id2iter.end())
00464     return (_values_list.end());
00465 
00466     return (node_id_iter->second);
00467 }
00468 
00469 template <typename V>
00470 inline pair<typename ConfigNodeIdMap<V>::iterator, bool>
00471 ConfigNodeIdMap<V>::insert_impl(const ConfigNodeId& node_id, const V& v,
00472                 bool ignore_missing_previous_element)
00473 {
00474     typename NodeId2IterMap::iterator node_id_iter;
00475     typename ValuesList::iterator values_iter;
00476 
00477     node_id_iter = _node_id2iter.find(node_id.unique_node_id());
00478     if (node_id_iter != _node_id2iter.end()) {
00479     values_iter = node_id_iter->second;
00480     XLOG_ASSERT(values_iter != _values_list.end());
00481     return (make_pair(values_iter, false)); // Node already exists
00482     }
00483 
00484     // Find the iterator to the previous element
00485     values_iter = _values_list.begin();
00486     do {
00487     if (node_id.position() == 0) {
00488         // The first element
00489         values_iter = _values_list.begin();
00490         break;
00491     }
00492     if (_values_list.size() == 0) {
00493         if (! ignore_missing_previous_element) {
00494         // Error: no other elements found
00495         return (make_pair(_values_list.end(), false));
00496         }
00497         values_iter = _values_list.end();
00498         break;
00499     }
00500     // Find the iterator to the previous element
00501     node_id_iter = _node_id2iter.find(node_id.position());
00502     if (node_id_iter == _node_id2iter.end()) {
00503         if (! ignore_missing_previous_element) {
00504         // Error: the previous element is not found
00505         return (make_pair(_values_list.end(), false));
00506         }
00507         values_iter = _values_list.end();
00508         break;
00509     }
00510     values_iter = node_id_iter->second;
00511     // XXX: increment the iterator to point to the insert position
00512     ++values_iter;
00513     break;
00514     } while (false);
00515 
00516     // Insert the new element
00517     values_iter = _values_list.insert(values_iter, make_pair(node_id, v));
00518     XLOG_ASSERT(values_iter != _values_list.end());
00519     pair<typename NodeId2IterMap::iterator, bool> res = _node_id2iter.insert(
00520     make_pair(node_id.unique_node_id(), values_iter));
00521     XLOG_ASSERT(res.second == true);
00522 
00523     return (make_pair(values_iter, true));
00524 }
00525 
00526 template <typename V>
00527 inline size_t
00528 ConfigNodeIdMap<V>::erase(const ConfigNodeId& node_id)
00529 {
00530     typename NodeId2IterMap::iterator node_id_iter;
00531     typename ValuesList::iterator values_iter;
00532 
00533     node_id_iter = _node_id2iter.find(node_id.unique_node_id());
00534     if (node_id_iter == _node_id2iter.end())
00535     return (0);     // No element found to erase
00536 
00537     values_iter = node_id_iter->second;
00538     _node_id2iter.erase(node_id_iter);
00539     _values_list.erase(values_iter);
00540 
00541     return (1);         // One element erased
00542 }
00543 
00544 template <typename V>
00545 inline void
00546 ConfigNodeIdMap<V>::erase(ConfigNodeIdMap::iterator iter)
00547 {
00548     if (iter == _values_list.end())
00549     return;
00550 
00551     const ConfigNodeId& node_id = iter->first;
00552     erase(node_id);
00553 }
00554 
00555 template <typename V>
00556 inline void
00557 ConfigNodeIdMap<V>::clear()
00558 {
00559     _node_id2iter.clear();
00560     _values_list.clear();
00561 }
00562 
00563 template <typename V>
00564 inline string
00565 ConfigNodeIdMap<V>::str() const
00566 {
00567     typename ConfigNodeIdMap::const_iterator iter;
00568     string res;
00569     for (iter = _values_list.begin(); iter != _values_list.end(); ++iter) {
00570     if (iter != _values_list.begin())
00571         res += ", ";
00572     res += iter->first.str();
00573     }
00574     return (res);
00575 }
00576 
00577 #endif // __LIBPROTO_CONFIG_NODE_ID_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations