Line data    Source code

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