ceph/src/boost/libs/intrusive/example/doc_assoc_optimized_code.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2013
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 //[doc_assoc_optimized_code_normal_find
  13 #include <boost/intrusive/set.hpp>
  14 #include <boost/intrusive/unordered_set.hpp>
  15 #include <cstring>
  16
  17 using namespace boost::intrusive;
  18
  19 // Hash function for strings
  20 struct StrHasher
  21 {
  22    std::size_t operator()(const char *str) const
  23    {
  24       std::size_t seed = 0;
  25       for(; *str; ++str)   boost::hash_combine(seed, *str);
  26       return seed;
  27    }
  28 };
  29
  30 class Expensive : public set_base_hook<>, public unordered_set_base_hook<>
  31 {
  32    std::string key_;
  33    // Other members...
  34
  35    public:
  36    Expensive(const char *key)
  37       :  key_(key)
  38       {}  //other expensive initializations...
  39
  40    const std::string & get_key() const
  41       {  return key_;   }
  42
  43    friend bool operator <  (const Expensive &a, const Expensive &b)
  44       {  return a.key_ < b.key_;  }
  45
  46    friend bool operator == (const Expensive &a, const Expensive &b)
  47       {  return a.key_ == b.key_;  }
  48
  49    friend std::size_t hash_value(const Expensive &object)
  50       {  return StrHasher()(object.get_key().c_str());  }
  51 };
  52
  53 // A set and unordered_set that store Expensive objects
  54 typedef set<Expensive>           Set;
  55 typedef unordered_set<Expensive> UnorderedSet;
  56
  57 // Search functions
  58 Expensive *get_from_set(const char* key, Set &set_object)
  59 {
  60    Set::iterator it = set_object.find(Expensive(key));
  61    if( it == set_object.end() )     return 0;
  62    return &*it;
  63 }
  64
  65 Expensive *get_from_uset(const char* key, UnorderedSet &uset_object)
  66 {
  67    UnorderedSet::iterator it = uset_object.find(Expensive (key));
  68    if( it == uset_object.end() )  return 0;
  69    return &*it;
  70 }
  71 //]
  72
  73 //[doc_assoc_optimized_code_optimized_find
  74 // These compare Expensive and a c-string
  75 struct StrExpComp
  76 {
  77    bool operator()(const char *str, const Expensive &c) const
  78    {  return std::strcmp(str, c.get_key().c_str()) < 0;  }
  79
  80    bool operator()(const Expensive &c, const char *str) const
  81    {  return std::strcmp(c.get_key().c_str(), str) < 0;  }
  82 };
  83
  84 struct StrExpEqual
  85 {
  86    bool operator()(const char *str, const Expensive &c) const
  87    {  return std::strcmp(str, c.get_key().c_str()) == 0;  }
  88
  89    bool operator()(const Expensive &c, const char *str) const
  90    {  return std::strcmp(c.get_key().c_str(), str) == 0;  }
  91 };
  92
  93 // Optimized search functions
  94 Expensive *get_from_set_optimized(const char* key, Set &set_object)
  95 {
  96    Set::iterator it = set_object.find(key, StrExpComp());
  97    if( it == set_object.end() )   return 0;
  98    return &*it;
  99 }
 100
 101 Expensive *get_from_uset_optimized(const char* key, UnorderedSet &uset_object)
 102 {
 103    UnorderedSet::iterator it = uset_object.find(key, StrHasher(), StrExpEqual());
 104    if( it == uset_object.end() )  return 0;
 105    return &*it;
 106 }
 107 //]
 108
 109 //[doc_assoc_optimized_code_normal_insert
 110 // Insertion functions
 111 bool insert_to_set(const char* key, Set &set_object)
 112 {
 113    Expensive *pobject = new Expensive(key);
 114    bool success = set_object.insert(*pobject).second;
 115    if(!success)   delete pobject;
 116    return success;
 117 }
 118
 119 bool insert_to_uset(const char* key, UnorderedSet &uset_object)
 120 {
 121    Expensive *pobject = new Expensive(key);
 122    bool success = uset_object.insert(*pobject).second;
 123    if(!success)   delete pobject;
 124    return success;
 125 }
 126 //]
 127
 128 //[doc_assoc_optimized_code_optimized_insert
 129 // Optimized insertion functions
 130 bool insert_to_set_optimized(const char* key, Set &set_object)
 131 {
 132    Set::insert_commit_data insert_data;
 133    bool success = set_object.insert_check(key, StrExpComp(), insert_data).second;
 134    if(success) set_object.insert_commit(*new Expensive(key), insert_data);
 135    return success;
 136 }
 137
 138 bool insert_to_uset_optimized(const char* key, UnorderedSet &uset_object)
 139 {
 140    UnorderedSet::insert_commit_data insert_data;
 141    bool success = uset_object.insert_check
 142       (key, StrHasher(), StrExpEqual(), insert_data).second;
 143    if(success) uset_object.insert_commit(*new Expensive(key), insert_data);
 144    return success;
 145 }
 146 //]
 147
 148 int main()
 149 {
 150    Set set;
 151    UnorderedSet::bucket_type buckets[10];
 152    UnorderedSet unordered_set(UnorderedSet::bucket_traits(buckets, 10));
 153
 154    const char * const expensive_key
 155       = "A long string that avoids small string optimization";
 156
 157    Expensive value(expensive_key);
 158
 159    if(get_from_set(expensive_key, set)){
 160       return 1;
 161    }
 162
 163    if(get_from_uset(expensive_key, unordered_set)){
 164       return 1;
 165    }
 166
 167    if(get_from_set_optimized(expensive_key, set)){
 168       return 1;
 169    }
 170
 171    if(get_from_uset_optimized(expensive_key, unordered_set)){
 172       return 1;
 173    }
 174
 175    Set::iterator setit =  set.insert(value).first;
 176    UnorderedSet::iterator unordered_setit =  unordered_set.insert(value).first;
 177
 178    if(!get_from_set(expensive_key, set)){
 179       return 1;
 180    }
 181
 182    if(!get_from_uset(expensive_key, unordered_set)){
 183       return 1;
 184    }
 185
 186    if(!get_from_set_optimized(expensive_key, set)){
 187       return 1;
 188    }
 189
 190    if(!get_from_uset_optimized(expensive_key, unordered_set)){
 191       return 1;
 192    }
 193
 194    set.erase(setit);
 195    unordered_set.erase(unordered_setit);
 196
 197    if(!insert_to_set(expensive_key, set)){
 198       return 1;
 199    }
 200
 201    if(!insert_to_uset(expensive_key, unordered_set)){
 202       return 1;
 203    }
 204
 205    {
 206       Expensive *ptr = &*set.begin();
 207       set.clear();
 208       delete ptr;
 209    }
 210
 211    {
 212       Expensive *ptr = &*unordered_set.begin();
 213       unordered_set.clear();
 214       delete ptr;
 215    }
 216
 217    if(!insert_to_set_optimized(expensive_key, set)){
 218       return 1;
 219    }
 220
 221    if(!insert_to_uset_optimized(expensive_key, unordered_set)){
 222       return 1;
 223    }
 224
 225    {
 226       Expensive *ptr = &*set.begin();
 227       set.clear();
 228       delete ptr;
 229    }
 230
 231    {
 232       Expensive *ptr = &*unordered_set.begin();
 233       unordered_set.clear();
 234       delete ptr;
 235    }
 236
 237    setit       =  set.insert(value).first;
 238    unordered_setit   =  unordered_set.insert(value).first;
 239
 240    if(insert_to_set(expensive_key, set)){
 241       return 1;
 242    }
 243
 244    if(insert_to_uset(expensive_key, unordered_set)){
 245       return 1;
 246    }
 247
 248    if(insert_to_set_optimized(expensive_key, set)){
 249       return 1;
 250    }
 251
 252    if(insert_to_uset_optimized(expensive_key, unordered_set)){
 253       return 1;
 254    }
 255
 256    set.erase(value);
 257    unordered_set.erase(value);
 258
 259    return 0;
 260 }