Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2015 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : #ifndef BASE_MAP_UTIL_H
       5             : #define BASE_MAP_UTIL_H
       6             : 
       7             : /*
       8             :  * map_difference
       9             :  *
      10             :  * Given two sorted maps, invoke add, delete or equal functors for values
      11             :  * that are:
      12             :  *  add - present in the second map but not in the first;
      13             :  *  delete - present in the first map but not in the second;
      14             :  *  equal - present in both maps;
      15             :  */
      16             : template <typename ForwardIterator,
      17             :     typename AddFunctor,
      18             :     typename DelFunctor,
      19             :     typename EqFunctor>
      20             : void map_difference(ForwardIterator __first1, ForwardIterator __last1,
      21             :                     ForwardIterator __first2, ForwardIterator __last2,
      22             :                     AddFunctor __add_fn, DelFunctor __del_fn,
      23             :                     EqFunctor __eq_fn) {
      24             :     while (__first1 != __last1 && __first2 != __last2) {
      25             :         if (__first1->first < __first2->first) {
      26             :             __del_fn(__first1);
      27             :             ++__first1;
      28             :         } else if (__first1->first > __first2->first) {
      29             :             __add_fn(__first2);
      30             :             ++__first2;
      31             :         } else {
      32             :             __eq_fn(__first1, __first2);
      33             :             ++__first1;
      34             :             ++__first2;
      35             :         }
      36             :     }
      37             :     for (; __first1 != __last1;  ++__first1) {
      38             :         __del_fn(__first1);
      39             :     }
      40             :     for (; __first2 != __last2;  ++__first2) {
      41             :         __add_fn(__first2);
      42             :     }
      43             : }
      44             : 
      45             : //
      46             : // map_difference
      47             : //
      48             : // Given a map and the begin/end iterators for a sorted std container and a
      49             : // compare functor, invoke add, delete or equal functors for values that are:
      50             : //  add - present in the container but not in the map;
      51             : //  delete - present in the map but not in the container;
      52             : //  equal - present in both the container and the map;
      53             : //
      54             : template <typename MapType,
      55             :     typename ForwardIterator,
      56             :     typename CompFunctor,
      57             :     typename AddFunctor,
      58             :     typename DelFunctor,
      59             :     typename EqFunctor>
      60         210 : void map_difference(MapType *map, ForwardIterator first, ForwardIterator last,
      61             :                     CompFunctor comp_fn, AddFunctor add_fn,
      62             :                     DelFunctor del_fn, EqFunctor eq_fn) {
      63         210 :     typename MapType::iterator it1 = map->begin(), next1 = map->begin();
      64         210 :     ForwardIterator it2 = first;
      65         334 :     while (it1 != map->end() && it2 != last) {
      66         124 :         int result = comp_fn(it1, it2);
      67         124 :         if (result < 0) {
      68          22 :             ++next1;
      69          22 :             del_fn(it1);
      70          22 :             it1 = next1;
      71         102 :         } else if (result > 0) {
      72          15 :             add_fn(it2);
      73          15 :             ++it2;
      74             :         } else {
      75          87 :             eq_fn(it1, it2);
      76          87 :             ++it1;
      77          87 :             ++it2;
      78             :         }
      79         124 :         next1 = it1;
      80             :     }
      81         248 :     for (next1 = it1; it1 != map->end(); it1 = next1) {
      82          38 :         ++next1;
      83          38 :         del_fn(it1);
      84             :     }
      85         343 :     for (; it2 != last; ++it2) {
      86         133 :         add_fn(it2);
      87             :     }
      88         210 : }
      89             : 
      90             : //
      91             : // map_synchronize
      92             : //
      93             : // Given two maps synchronize the 1st (current) map with the 2nd (future)
      94             : // one by invoking add or delete functors for values that are:
      95             : //   add - present in the 2nd map but not in the 1st;
      96             : //   delete - present in the 1st map but not in the 2nd;
      97             : //
      98             : // The add/delete functors are responsible for adding/deleting appropriate
      99             : // elements to/from the 1st map.
     100             : //
     101             : template <typename MapType, typename AddFunctor, typename DelFunctor>
     102      103418 : void map_synchronize(MapType *map1, const MapType *map2,
     103             :                      AddFunctor add_fn, DelFunctor del_fn) {
     104      103418 :     typename MapType::iterator it1 = map1->begin(), next1 = map1->begin();
     105      103418 :     typename MapType::const_iterator it2 = map2->begin();
     106      117273 :     while (it1 != map1->end() && it2 != map2->end()) {
     107       13855 :         if (it1->first < it2->first) {
     108         362 :             ++next1;
     109         362 :             del_fn(it1);
     110         362 :             it1 = next1;
     111       13493 :         } else if (it1->first > it2->first) {
     112         558 :             add_fn(it2);
     113         558 :             ++it2;
     114             :         } else {
     115       12935 :             ++it1;
     116       12935 :             ++it2;
     117             :         }
     118       13855 :         next1 = it1;
     119             :     }
     120      130143 :     for (next1 = it1; it1 != map1->end(); it1 = next1) {
     121       26725 :         ++next1;
     122       26725 :         del_fn(it1);
     123             :     }
     124      129947 :     for (; it2 != map2->end(); ++it2) {
     125       26529 :         add_fn(it2);
     126             :     }
     127      103418 : }
     128             : 
     129             : #endif  // BASE_MAP_UTIL_H