src/Utils/QuickHashMap.h

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2007-2007 - TortoiseSVN\r
   4 \r
   5 // This program is free software; you can redistribute it and/or\r
   6 // modify it under the terms of the GNU General Public License\r
   7 // as published by the Free Software Foundation; either version 2\r
   8 // of the License, or (at your option) any later version.\r
   9 \r
  10 // This program is distributed in the hope that it will be useful,\r
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13 // GNU General Public License for more details.\r
  14 \r
  15 // You should have received a copy of the GNU General Public License\r
  16 // along with this program; if not, write to the Free Software Foundation,\r
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
  18 //\r
  19 #pragma once\r
  20 \r
  21 ///////////////////////////////////////////////////////////////\r
  22 // necessary includes\r
  23 ///////////////////////////////////////////////////////////////\r
  24 \r
  25 #include "QuickHash.h"\r
  26 \r
  27 \r
  28 /**\r
  29  * A quick associative container that maps K (key) to V (value) instances.\r
  30  * K must implicitly convert to size_t.\r
  31  */\r
  32 template<class K, class V>\r
  33 class quick_hash_map\r
  34 {\r
  35 private:\r
  36 \r
  37     /// our actual data container\r
  38     struct element_type\r
  39     {\r
  40         K key;\r
  41         V value;\r
  42 \r
  43         element_type (K key, const V& value)\r
  44             : key (key), value (value)\r
  45         {\r
  46         }\r
  47     };\r
  48 \r
  49     typedef std::vector<element_type> data_type;\r
  50     data_type data;\r
  51 \r
  52         /**\r
  53          * A simple string hash function that satisfies quick_hash interface\r
  54          * requirements.\r
  55          *\r
  56          * NULL strings are supported and are mapped to index 0.\r
  57          * Hence, the dictionary must contain the empty string at index 0.\r
  58          */\r
  59         class CHashFunction\r
  60         {\r
  61         private:\r
  62 \r
  63                 /// the data container we index with the hash\r
  64                 /// (used to map key -> (key, value))\r
  65         typedef typename quick_hash_map<K, V>::data_type data_type; \r
  66         data_type* data;\r
  67 \r
  68         public:\r
  69 \r
  70                 // simple construction\r
  71 \r
  72                 CHashFunction (data_type* map)\r
  73             : data (map)\r
  74         {\r
  75         }\r
  76 \r
  77                 // required typedefs and constants\r
  78 \r
  79                 typedef K value_type;\r
  80                 typedef size_t index_type;\r
  81 \r
  82                 enum {NO_INDEX = LogCache::NO_INDEX};\r
  83 \r
  84                 /// the actual hash function\r
  85         size_t operator() (value_type value) const\r
  86         {\r
  87             return value;\r
  88         }\r
  89 \r
  90                 /// dictionary lookup\r
  91                 value_type value (index_type index) const\r
  92         {\r
  93             return (*data)[index].key;\r
  94         }\r
  95 \r
  96                 /// lookup and comparison\r
  97                 bool equal (value_type value, index_type index) const\r
  98         {\r
  99             return value == (*data)[index].key;\r
 100         }\r
 101         };\r
 102 \r
 103     friend class CHashFunction;\r
 104 \r
 105     // hash index over this container\r
 106 \r
 107     quick_hash<CHashFunction> hash;\r
 108 \r
 109 public:\r
 110 \r
 111     // publicly available types\r
 112 \r
 113         typedef typename K key_type;\r
 114         typedef typename V value_type;\r
 115 \r
 116     class const_iterator\r
 117     {\r
 118     private:\r
 119 \r
 120         typedef typename quick_hash_map<K,V>::data_type::const_iterator iterator;\r
 121         typedef typename quick_hash_map<K,V>::element_type value_type;\r
 122 \r
 123         iterator iter;\r
 124 \r
 125     public:\r
 126 \r
 127         // construction\r
 128 \r
 129         const_iterator (iterator iter)\r
 130             : iter (iter)\r
 131         {\r
 132         }\r
 133 \r
 134                 // pointer-like behavior\r
 135 \r
 136                 const V& operator*() const\r
 137                 {\r
 138                         return iter->value;\r
 139                 }\r
 140 \r
 141         const value_type* operator->() const\r
 142                 {\r
 143                         return &*iter;\r
 144                 }\r
 145 \r
 146         // comparison\r
 147 \r
 148         bool operator== (const const_iterator& rhs) const\r
 149         {\r
 150             return iter == rhs.iter;\r
 151         }\r
 152 \r
 153         bool operator!= (const const_iterator& rhs) const\r
 154         {\r
 155             return iter != rhs.iter;\r
 156         }\r
 157 \r
 158                 // move pointer\r
 159 \r
 160                 const_iterator& operator++()            // prefix\r
 161                 {\r
 162             iter++;\r
 163                         return *this;\r
 164                 }\r
 165 \r
 166                 const_iterator operator++(int)  // postfix\r
 167                 {\r
 168                         const_iterator result (*this);\r
 169                         operator++();\r
 170                         return result;\r
 171                 }\r
 172 \r
 173         const_iterator& operator+= (size_t diff)\r
 174         {\r
 175             iter += diff;\r
 176             return *this;\r
 177         }\r
 178 \r
 179         const_iterator& operator-= (size_t diff)\r
 180         {\r
 181             iter += diff;\r
 182             return *this;\r
 183         }\r
 184 \r
 185         const_iterator operator+ (size_t diff) const\r
 186         {\r
 187             return const_iterator (*this) += diff;\r
 188         }\r
 189 \r
 190         const_iterator operator- (size_t diff) const\r
 191         {\r
 192             return const_iterator (*this) -= diff;\r
 193         }\r
 194     };\r
 195 \r
 196     friend class const_iterator;\r
 197 \r
 198         // construction\r
 199     // (default-implemented destruction works as desired)\r
 200 \r
 201         quick_hash_map() \r
 202                 : hash (CHashFunction (&data))\r
 203         {\r
 204         }\r
 205         \r
 206         quick_hash_map (const quick_hash_map& rhs) \r
 207                 : hash (CHashFunction (&data))\r
 208         {\r
 209                 operator=(rhs);\r
 210         }\r
 211 \r
 212         // assignment\r
 213 \r
 214         quick_hash_map& operator= (const quick_hash_map& rhs) \r
 215         {\r
 216                 hash = rhs.hash;\r
 217                 data = rhs.data;\r
 218 \r
 219                 return *this;\r
 220         }\r
 221         \r
 222         // data access\r
 223         \r
 224         const_iterator begin() const\r
 225     {\r
 226         return data.begin();\r
 227     }\r
 228 \r
 229         const_iterator end() const\r
 230     {\r
 231         return data.end();\r
 232     }\r
 233 \r
 234     const_iterator find (key_type key) const\r
 235         {\r
 236         size_t index = hash.find (key);\r
 237         return index == LogCache::NO_INDEX \r
 238             ? end() \r
 239             : begin() + index;\r
 240         }\r
 241         \r
 242     // insert a new key, value pair\r
 243 \r
 244         void insert (key_type key, const value_type& value)\r
 245         {\r
 246                 assert (find (key) == end());\r
 247                 \r
 248         data.push_back (element_type (key, value));\r
 249         hash.insert (key, data.size()-1);\r
 250         }\r
 251 \r
 252         void reserve (size_t min_bucket_count)\r
 253         {\r
 254         if (data.capacity() < min_bucket_count)\r
 255         {\r
 256             data.reserve (min_bucket_count);\r
 257             hash.reserve (min_bucket_count);\r
 258         }\r
 259         }\r
 260 \r
 261         // get rid of all entries\r
 262 \r
 263         void clear()\r
 264         {\r
 265         hash.clear();\r
 266         data.clear();\r
 267         }\r
 268 };\r