server/supernova/utilities/named_hash_entry.hpp

   1 //  Copyright (C) 2011 Tim Blechmann
   2 //
   3 //  This program is free software; you can redistribute it and/or modify
   4 //  it under the terms of the GNU General Public License as published by
   5 //  the Free Software Foundation; either version 2 of the License, or
   6 //  (at your option) any later version.
   7 //
   8 //  This program is distributed in the hope that it will be useful,
   9 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 //  GNU General Public License for more details.
  12 //
  13 //  You should have received a copy of the GNU General Public License
  14 //  along with this program; see the file COPYING.  If not, write to
  15 //  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16 //  Boston, MA 02111-1307, USA.
  17
  18 #ifndef UTILITIES_NAMED_HASH_ENTRY_HPP
  19 #define UTILITIES_NAMED_HASH_ENTRY_HPP
  20
  21 #include <string>
  22
  23 #include <boost/intrusive/unordered_set_hook.hpp>
  24 #include <boost/unordered_set.hpp>
  25
  26 #include "utils.hpp"
  27 #include "nova-tt/nova-tt/rw_mutex.hpp"
  28
  29 namespace nova   {
  30 namespace bi = boost::intrusive;
  31
  32 PURE inline bool strequal(const char * lhs, const char * rhs)
  33 {
  34     for(;;++lhs, ++rhs) {
  35         if (*lhs == 0) {
  36             if (*rhs == 0)
  37                 return true;
  38             else
  39                 return false;
  40         }
  41         if (*rhs == 0)
  42             return false;
  43         if (*lhs != *rhs)
  44             return false;
  45     }
  46 }
  47
  48 struct c_string
  49 {
  50 private:
  51     static const char * duplicate_string(const char * str, std::size_t length)
  52     {
  53         assert(strlen(str) == length);
  54
  55         length += 1; // for terminating \0
  56         char * string = malloc_aligned<char>(length);
  57
  58         strncpy(string, str, length);
  59         return string;
  60     }
  61
  62     static const char * duplicate_string(const char * str)
  63     {
  64         return duplicate_string(str, strlen(str));
  65     }
  66
  67     struct symbol_data
  68     {
  69         explicit symbol_data(const char * str):
  70             str(str), hash(string_hash(str))
  71         {}
  72
  73         explicit symbol_data(const char * str, size_t hash):
  74             str(str), hash(hash)
  75         {}
  76
  77         symbol_data(symbol_data const & rhs):
  78             str(rhs.str), hash(rhs.hash)
  79         {}
  80
  81         friend size_t hash_value(symbol_data const & value)
  82         {
  83             return value.hash;
  84         }
  85
  86         bool operator==(symbol_data const & rhs) const
  87         {
  88             return str == rhs.str;
  89         }
  90
  91         const char * str;
  92         size_t hash;
  93     };
  94
  95     struct hash_by_string
  96     {
  97         size_t operator()(const char * str) const
  98         {
  99             return string_hash(str);
 100         }
 101         size_t operator()(symbol_data const & data) const
 102         {
 103             return data.hash;
 104         }
 105     };
 106
 107     struct equal_by_string
 108     {
 109         static const char * get_string(const char * arg)
 110         {
 111             return arg;
 112         }
 113
 114         static const char * get_string(symbol_data const & arg)
 115         {
 116             return arg.str;
 117         }
 118
 119         template <typename T1, typename T2>
 120         bool operator()(T1 const & lhs, T2 const & rhs) const
 121         {
 122             return strequal(get_string(lhs), get_string(rhs));
 123         }
 124     };
 125
 126     class symbol_table
 127     {
 128         typedef boost::unordered_set<symbol_data> table_type;
 129         typedef std::pair<table_type::const_iterator, bool> lookup_result_type;
 130
 131 public:
 132         symbol_table(void):
 133             table(16384)
 134         {}
 135
 136         symbol_data const & find(const char * str, size_t strlen)
 137         {
 138             mutex.lock_shared();
 139             lookup_result_type lookup_result = symbol_lookup(str);
 140             mutex.unlock_shared();
 141             if (lookup_result.second)
 142                 return *lookup_result.first;
 143
 144             boost::unique_lock<nova::nonrecursive_rw_mutex> lock(mutex);
 145             lookup_result = symbol_lookup(str);
 146             if (lookup_result.second)
 147                 return *lookup_result.first;
 148
 149             std::pair<table_type::iterator, bool> inserted = table.insert(symbol_data(duplicate_string(str, strlen)));
 150             assert(inserted.second);
 151             return *inserted.first;
 152         }
 153
 154     private:
 155         lookup_result_type symbol_lookup(const char * str) const
 156         {
 157             table_type::iterator it = table.find(str, hash_by_string(), equal_by_string());
 158             return std::make_pair(it, it != table.end());
 159         }
 160
 161         table_type table;
 162         nova::nonrecursive_rw_mutex mutex;
 163     };
 164
 165     symbol_data lookup_string(const char * str, std::size_t length)
 166     {
 167         static symbol_table table;
 168         return table.find(str, length);
 169     }
 170
 171     symbol_data lookup_string(const char * str)
 172     {
 173         return lookup_string(str, strlen(str));
 174     }
 175
 176 public:
 177     c_string ():
 178         data(NULL, 0)
 179     {}
 180
 181     explicit c_string (const char * str):
 182         data(lookup_string(str))
 183     {}
 184
 185     c_string (std::string const & str):
 186         data(lookup_string(str.c_str(), str.size()))
 187     {}
 188
 189     c_string (const char * str, std::size_t length):
 190         data(lookup_string(str, length))
 191     {}
 192
 193     c_string (c_string const & rhs):
 194         data(rhs.data)
 195     {}
 196
 197     const char * c_str(void) const
 198     {
 199         return data.str;
 200     }
 201
 202     friend std::size_t hash_value(c_string const & value)
 203     {
 204         return value.data.hash;
 205     }
 206
 207     friend bool operator== (c_string const & lhs,
 208                             c_string const & rhs)
 209     {
 210         return lhs.data == rhs.data;
 211     }
 212
 213     friend bool operator< (c_string const & lhs,
 214                             c_string const & rhs)
 215     {
 216         return lhs.data.str < rhs.data.str;
 217     }
 218
 219
 220
 221     symbol_data data;
 222 };
 223
 224 class named_hash_entry:
 225     public bi::unordered_set_base_hook<>
 226 {
 227     const c_string name_;
 228
 229 public:
 230     named_hash_entry(const char * name):
 231         name_(name)
 232     {}
 233
 234     named_hash_entry(c_string const & name):
 235         name_(name)
 236     {}
 237
 238     named_hash_entry(std::string const & name):
 239         name_(name.c_str(), name.size())
 240     {}
 241
 242     const char * name(void) const
 243     {
 244         return name_.c_str();
 245     }
 246
 247     friend std::size_t hash_value(named_hash_entry const & that)
 248     {
 249         return that.hash();
 250     }
 251
 252     std::size_t hash(void) const
 253     {
 254         return name_.data.hash;
 255     }
 256
 257     friend bool operator== (named_hash_entry const & a,
 258                             named_hash_entry const & b)
 259     {
 260         return a.name_ == b.name_;
 261     }
 262 };
 263
 264 struct named_hash_equal
 265 {
 266     template<typename def>
 267     bool operator()(def const & lhs,
 268                     std::string const & rhs) const
 269     {
 270         return operator()(lhs.name(), rhs.c_str());
 271     }
 272
 273     template<typename def>
 274     bool operator()(std::string const & lhs,
 275                     def const & rhs) const
 276     {
 277         return operator()(lhs.c_str(), rhs.name());
 278     }
 279
 280     template<typename def>
 281     bool operator()(def const & lhs,
 282                     c_string const & rhs) const
 283     {
 284         return operator()(lhs.name(), rhs.c_str());
 285     }
 286
 287     template<typename def>
 288     bool operator()(c_string const & lhs,
 289                     def const & rhs) const
 290     {
 291         return operator()(lhs.c_str(), rhs.name());
 292     }
 293
 294     template<typename def>
 295     bool operator()(const char * lhs, def const & rhs) const
 296     {
 297         return operator()(lhs, rhs.name());
 298     }
 299
 300     template<typename def>
 301     bool operator()(def const & lhs, const char * rhs) const
 302     {
 303         return operator()(lhs.name(), rhs);
 304     }
 305
 306     bool operator()(const char * lhs, const char * rhs) const
 307     {
 308         return strequal(rhs, lhs);
 309     }
 310 };
 311
 312 struct named_hash_hash
 313 {
 314     template<typename def>
 315     std::size_t operator()(def const & arg)
 316     {
 317         return hash_value(arg);
 318     }
 319
 320     std::size_t operator()(const char * str)
 321     {
 322         return string_hash(str);
 323     }
 324
 325     std::size_t operator()(std::string const & str)
 326     {
 327         return string_hash(str.c_str());
 328     }
 329 };
 330
 331 }
 332
 333 #undef PURE
 334 #endif /* UTILITIES_NAMED_HASH_ENTRY_HPP */