src/thirdparty/VirtualDub/h/vd2/system/vdstl_hashmap.h

   1 //      VirtualDub - Video processing and capture application
   2 //      System library component
   3 //      Copyright (C) 1998-2010 Avery Lee, All Rights Reserved.
   4 //
   5 //      Beginning with 1.6.0, the VirtualDub system library is licensed
   6 //      differently than the remainder of VirtualDub.  This particular file is
   7 //      thus licensed as follows (the "zlib" license):
   8 //
   9 //      This software is provided 'as-is', without any express or implied
  10 //      warranty.  In no event will the authors be held liable for any
  11 //      damages arising from the use of this software.
  12 //
  13 //      Permission is granted to anyone to use this software for any purpose,
  14 //      including commercial applications, and to alter it and redistribute it
  15 //      freely, subject to the following restrictions:
  16 //
  17 //      1.      The origin of this software must not be misrepresented; you must
  18 //              not claim that you wrote the original software. If you use this
  19 //              software in a product, an acknowledgment in the product
  20 //              documentation would be appreciated but is not required.
  21 //      2.      Altered source versions must be plainly marked as such, and must
  22 //              not be misrepresented as being the original software.
  23 //      3.      This notice may not be removed or altered from any source
  24 //              distribution.
  25
  26 #ifndef f_VD2_SYSTEM_VDSTL_HASHMAP_H
  27 #define f_VD2_SYSTEM_VDSTL_HASHMAP_H
  28
  29 #include <vd2/system/vdstl_hash.h>
  30 #include <vd2/system/vdstl_hashtable.h>
  31 #include <functional>
  32
  33 template<class K, class V, class Hash = vdhash<K>, class Pred = std::equal_to<K>, class A = std::allocator<vdhashtable_node<std::pair<K, V> > > >
  34 class vdhashmap : public vdhashtable<std::pair<K, V> > {
  35 protected:
  36         using vdhashtable<std::pair<K, V> >::mpBucketStart;
  37         using vdhashtable<std::pair<K, V> >::mpBucketEnd;
  38         using vdhashtable<std::pair<K, V> >::mBucketCount;
  39         using vdhashtable<std::pair<K, V> >::mElementCount;
  40         using vdhashtable<std::pair<K, V> >::sEmptyBucket;
  41
  42 public:
  43         typedef typename vdhashtable<std::pair<K, V> >::node_type node_type;
  44         typedef typename vdhashtable<std::pair<K, V> >::value_type value_type;
  45         typedef typename vdhashtable<std::pair<K, V> >::size_type size_type;
  46         typedef typename vdhashtable<std::pair<K, V> >::difference_type difference_type;
  47         typedef typename vdhashtable<std::pair<K, V> >::pointer pointer;
  48         typedef typename vdhashtable<std::pair<K, V> >::const_pointer const_pointer;
  49         typedef typename vdhashtable<std::pair<K, V> >::reference reference;
  50         typedef typename vdhashtable<std::pair<K, V> >::const_reference const_reference;
  51         typedef typename vdhashtable<std::pair<K, V> >::iterator iterator;
  52         typedef typename vdhashtable<std::pair<K, V> >::const_iterator const_iterator;
  53         typedef typename vdhashtable<std::pair<K, V> >::local_iterator local_iterator;
  54         typedef typename vdhashtable<std::pair<K, V> >::const_local_iterator const_local_iterator;
  55         typedef K key_type;
  56         typedef V mapped_type;
  57         typedef Hash hasher;
  58         typedef Pred key_equal;
  59         typedef A allocator_type;
  60         typedef std::pair<iterator, bool> insert_return_type;
  61
  62         vdhashmap();
  63         vdhashmap(const vdhashmap&);
  64         ~vdhashmap();
  65
  66         vdhashmap& operator=(const vdhashmap&);
  67
  68         mapped_type&            operator[](const K& key);
  69
  70         allocator_type get_allocator() const;
  71
  72         // iterators
  73         using vdhashtable<value_type>::begin;
  74         using vdhashtable<value_type>::end;
  75 //      iterator                        begin();                        Inherited.
  76 //      const_iterator          begin() const;          Inherited.
  77 //      iterator                        end();                          Inherited.
  78 //      const_iterator          end() const;            Inherited.
  79
  80         // modifiers
  81         insert_return_type      insert(const key_type& key);
  82         insert_return_type      insert(const std::pair<K, V>& obj);
  83 //      iterator                        insert(iterator hint, const value_type& obj);                   // TODO
  84 //      const_iterator          insert(const_iterator hint, const value_type& obj);     // TODO
  85
  86         template<class U>
  87         insert_return_type      insert_as(const U& k);  // extension
  88
  89         iterator                        erase(iterator position);
  90         const_iterator          erase(const_iterator position);
  91         size_type                       erase(const key_type& k);
  92 //      iterator                        erase(iterator first, iterator last);                           // TODO
  93 //      const_iterator          erase(const_iterator first, const_iterator last);       // TODO
  94         void                            clear();
  95
  96         // observers
  97         hasher                          hash_function() const;
  98         key_equal                       key_eq() const;
  99
 100         // lookup
 101         iterator                        find(const key_type& k);
 102         const_iterator          find(const key_type& k) const;
 103         size_type                       count(const key_type& k) const;
 104         std::pair<iterator, iterator>   equal_range(const key_type& k);
 105         std::pair<const_iterator, const_iterator>       equal_range(const key_type& k) const;
 106
 107         // lookup (extensions)
 108         template<class U>
 109         iterator                        find_as(const U& k);
 110
 111         template<class U>
 112         const_iterator          find_as(const U& k) const;
 113
 114         // bucket interface
 115 //      size_type                       bucket_count() const;                           Inherited.
 116 //      size_type                       max_bucket_count() const;                       Inherited.
 117 //      size_type                       bucket_size(size_type n) const;         Inherited.
 118         size_type                       bucket(const key_type& k) const;
 119         local_iterator          begin(size_type n);
 120         const_local_iterator    begin(size_type n) const;
 121         local_iterator          end(size_type n);
 122         const_local_iterator    end(size_type n) const;
 123
 124         // hash policy
 125 //      float                           load_factor() const;                            // TODO
 126 //      float                           max_load_factor() const;                        // TODO
 127 //      void                            max_load_factor(float z);                       // TODO
 128         void                            rehash(size_type n);
 129
 130 protected:
 131         void                            rehash_to_size(size_type n);
 132         void                            reset();
 133
 134         A mAllocator;
 135         typename A::template rebind<vdhashtable_base_node *>::other mBucketAllocator;
 136         Hash mHasher;
 137         Pred mPred;
 138 };
 139
 140 template<class K, class V, class Hash, class Pred, class A>
 141 vdhashmap<K, V, Hash, Pred, A>::vdhashmap() {
 142 }
 143
 144 template<class K, class V, class Hash, class Pred, class A>
 145 vdhashmap<K, V, Hash, Pred, A>::vdhashmap(const vdhashmap& src)
 146         : mHasher(src.mHasher)
 147         , mPred(src.mPred)
 148 {
 149         rehash_to_size(src.mElementCount);
 150
 151         try {
 152                 for(vdhashtable_base_node **bucket = mpBucketStart; bucket != mpBucketEnd; ++bucket) {
 153                         vdhashtable_base_node *p = *bucket;
 154
 155                         while(p) {
 156                                 vdhashtable_base_node *next = p->mpHashNext;
 157                                 node_type *node = static_cast<node_type *>(p);
 158
 159                                 insert(node->mData);
 160
 161                                 p = next;
 162                         }
 163
 164                         *bucket = NULL;
 165                 }
 166         } catch(...) {
 167                 reset();
 168                 throw;
 169         }
 170 }
 171
 172 template<class K, class V, class Hash, class Pred, class A>
 173 vdhashmap<K, V, Hash, Pred, A>::~vdhashmap() {
 174         reset();
 175 }
 176
 177 template<class K, class V, class Hash, class Pred, class A>
 178 vdhashmap<K, V, Hash, Pred, A>& vdhashmap<K, V, Hash, Pred, A>::operator=(const vdhashmap& src) {
 179         if (&src != this) {
 180                 clear();
 181
 182                 mHasher = src.mHasher;
 183                 mPred = src.mPred;
 184
 185                 for(vdhashtable_base_node **bucket = src.mpBucketStart; bucket != src.mpBucketEnd; ++bucket) {
 186                         vdhashtable_base_node *p = *bucket;
 187
 188                         while(p) {
 189                                 vdhashtable_base_node *next = p->mpHashNext;
 190                                 node_type *node = static_cast<node_type *>(p);
 191
 192                                 insert(node->mData);
 193
 194                                 p = next;
 195                         }
 196
 197                         *bucket = NULL;
 198                 }
 199         }
 200
 201         return *this;
 202 }
 203
 204 template<class K, class V, class Hash, class Pred, class A>
 205 typename vdhashmap<K, V, Hash, Pred, A>::mapped_type& vdhashmap<K, V, Hash, Pred, A>::operator[](const K& key) {
 206         return insert(key).first->second;
 207 }
 208
 209 template<class K, class V, class Hash, class Pred, class A>
 210 typename vdhashmap<K, V, Hash, Pred, A>::allocator_type vdhashmap<K, V, Hash, Pred, A>::get_allocator() const {
 211         return A();
 212 }
 213
 214 // modifiers
 215 template<class K, class V, class Hash, class Pred, class A>
 216 typename vdhashmap<K, V, Hash, Pred, A>::insert_return_type vdhashmap<K, V, Hash, Pred, A>::insert(const key_type& key) {
 217         if (mElementCount >= mBucketCount)
 218                 rehash_to_size(mElementCount + 1);
 219
 220         size_type bucket = mHasher(key) % mBucketCount;
 221
 222         for(node_type *p = static_cast<node_type *>(mpBucketStart[bucket]); p; p = static_cast<node_type *>(p->mpHashNext)) {
 223                 if (mPred(p->mData.first, key))
 224                         return std::pair<iterator, bool>(iterator(p, &mpBucketStart[bucket], mpBucketEnd), false);
 225         }
 226
 227         node_type *node = mAllocator.allocate(1);
 228         try {
 229                 new(node) node_type(static_cast<node_type *>(mpBucketStart[bucket]), value_type(key, V()));
 230         } catch(...) {
 231                 mAllocator.deallocate(node, 1);
 232                 throw;
 233         }
 234
 235         mpBucketStart[bucket] = node;
 236         ++mElementCount;
 237
 238         return std::pair<iterator, bool>(iterator(node, &mpBucketStart[bucket], mpBucketEnd), true);
 239 }
 240
 241 template<class K, class V, class Hash, class Pred, class A>
 242 typename vdhashmap<K, V, Hash, Pred, A>::insert_return_type vdhashmap<K, V, Hash, Pred, A>::insert(const std::pair<K, V>& obj) {
 243         if (mElementCount >= mBucketCount)
 244                 rehash_to_size(mElementCount + 1);
 245
 246         size_type bucket = mHasher(obj.first) % mBucketCount;
 247
 248         for(node_type *p = static_cast<node_type *>(mpBucketStart[bucket]); p; p = static_cast<node_type *>(p->mpHashNext)) {
 249                 if (mPred(p->mData.first, obj.first))
 250                         return std::pair<iterator, bool>(iterator(p, &mpBucketStart[bucket], mpBucketEnd), false);
 251         }
 252
 253         node_type *node = mAllocator.allocate(1);
 254         try {
 255                 new(node) node_type(static_cast<node_type *>(mpBucketStart[bucket]), obj);
 256         } catch(...) {
 257                 mAllocator.deallocate(node, 1);
 258                 throw;
 259         }
 260
 261         mpBucketStart[bucket] = node;
 262         ++mElementCount;
 263
 264         return std::pair<iterator, bool>(iterator(node, &mpBucketStart[bucket], mpBucketEnd), true);
 265 }
 266
 267 template<class K, class V, class Hash, class Pred, class A>
 268 template<class U>
 269 typename vdhashmap<K, V, Hash, Pred, A>::insert_return_type vdhashmap<K, V, Hash, Pred, A>::insert_as(const U& key) {
 270         if (mElementCount >= mBucketCount)
 271                 rehash_to_size(mElementCount + 1);
 272
 273         size_type bucket = mHasher(key) % mBucketCount;
 274
 275         for(node_type *p = static_cast<node_type *>(mpBucketStart[bucket]); p; p = static_cast<node_type *>(p->mpHashNext)) {
 276                 if (mPred(p->mData.first, key))
 277                         return std::pair<iterator, bool>(iterator(p, &mpBucketStart[bucket], mpBucketEnd), false);
 278         }
 279
 280         node_type *node = mAllocator.allocate(1);
 281         try {
 282                 new(node) node_type(static_cast<node_type *>(mpBucketStart[bucket]));
 283
 284                 try {
 285                         node->mData.first = key;
 286                 } catch(...) {
 287                         node->~node_type();
 288                 }
 289
 290         } catch(...) {
 291                 mAllocator.deallocate(node, 1);
 292                 throw;
 293         }
 294
 295         mpBucketStart[bucket] = node;
 296         ++mElementCount;
 297
 298         return std::pair<iterator, bool>(iterator(node, &mpBucketStart[bucket], mpBucketEnd), true);
 299 }
 300
 301 template<class K, class V, class Hash, class Pred, class A>
 302 typename vdhashmap<K, V, Hash, Pred, A>::iterator vdhashmap<K, V, Hash, Pred, A>::erase(iterator position) {
 303         size_type bucket = mHasher(position->first) % mBucketCount;
 304         vdhashtable_base_node *prev = NULL;
 305         vdhashtable_base_node *p = mpBucketStart[bucket];
 306
 307         while(&static_cast<node_type *>(p)->mData != &*position) {
 308                 prev = p;
 309                 p = p->mpHashNext;
 310         }
 311
 312         vdhashtable_base_node *next = p->mpHashNext;
 313         if (prev)
 314                 prev->mpHashNext = next;
 315         else
 316                 mpBucketStart[bucket] = next;
 317
 318         node_type *node = static_cast<node_type *>(p);
 319         node->~node_type();
 320         mAllocator.deallocate(node, 1);
 321         --mElementCount;
 322
 323         return iterator(next, &mpBucketStart[bucket], mpBucketEnd);
 324 }
 325
 326 template<class K, class V, class Hash, class Pred, class A>
 327 typename vdhashmap<K, V, Hash, Pred, A>::const_iterator vdhashmap<K, V, Hash, Pred, A>::erase(const_iterator position) {
 328         size_type bucket = mHasher(position->first) % mBucketCount;
 329         vdhashtable_base_node *prev = NULL;
 330         vdhashtable_base_node *p = mpBucketStart[bucket];
 331
 332         while(&static_cast<const node_type *>(p)->mData != &*position) {
 333                 prev = p;
 334                 p = p->mpHashNext;
 335         }
 336
 337         vdhashtable_base_node *next = p->mpHashNext;
 338         if (prev)
 339                 prev->mpHashNext = next;
 340         else
 341                 mpBucketStart[bucket] = next;
 342
 343         node_type *node = static_cast<node_type *>(p);
 344         node->~node_type();
 345         mAllocator.deallocate(node, 1);
 346         --mElementCount;
 347
 348         return const_iterator(next, &mpBucketStart[bucket], mpBucketEnd);
 349 }
 350
 351 template<class K, class V, class Hash, class Pred, class A>
 352 typename vdhashmap<K, V, Hash, Pred, A>::size_type vdhashmap<K, V, Hash, Pred, A>::erase(const key_type& k) {
 353         if (!mBucketCount)
 354                 return 0;
 355
 356         size_type bucket = mHasher(k) % mBucketCount;
 357         vdhashtable_base_node *prev = NULL;
 358         vdhashtable_base_node *p = mpBucketStart[bucket];
 359
 360         while(p) {
 361                 node_type *node = static_cast<node_type *>(p);
 362
 363                 if (mPred(node->mData.first, k)) {
 364                         vdhashtable_base_node *next = p->mpHashNext;
 365
 366                         if (prev)
 367                                 prev->mpHashNext = next;
 368                         else
 369                                 mpBucketStart[bucket] = next;
 370
 371                         node->~node_type();
 372                         mAllocator.deallocate(node, 1);
 373                         --mElementCount;
 374                         return 1;
 375                 }
 376
 377                 prev = p;
 378                 p = p->mpHashNext;
 379         }
 380
 381         return 0;
 382 }
 383
 384 template<class K, class V, class Hash, class Pred, class A>
 385 void vdhashmap<K, V, Hash, Pred, A>::clear() {
 386         for(vdhashtable_base_node **bucket = mpBucketStart; bucket != mpBucketEnd; ++bucket) {
 387                 vdhashtable_base_node *p = *bucket;
 388
 389                 while(p) {
 390                         vdhashtable_base_node *next = p->mpHashNext;
 391                         node_type *node = static_cast<node_type *>(p);
 392
 393                         node->~node_type();
 394
 395                         mAllocator.deallocate(node, 1);
 396
 397                         p = next;
 398                 }
 399
 400                 *bucket = NULL;
 401         }
 402
 403         mElementCount = 0;
 404 }
 405
 406 // observers
 407 template<class K, class V, class Hash, class Pred, class A>
 408 typename vdhashmap<K, V, Hash, Pred, A>::hasher vdhashmap<K, V, Hash, Pred, A>::hash_function() const {
 409         return mHasher;
 410 }
 411
 412 template<class K, class V, class Hash, class Pred, class A>
 413 typename vdhashmap<K, V, Hash, Pred, A>::key_equal vdhashmap<K, V, Hash, Pred, A>::key_eq() const {
 414         return mPred;
 415 }
 416
 417 // lookup
 418 template<class K, class V, class Hash, class Pred, class A>
 419 typename vdhashmap<K, V, Hash, Pred, A>::iterator vdhashmap<K, V, Hash, Pred, A>::find(const key_type& k) {
 420         if (!mBucketCount)
 421                 return iterator();
 422
 423         size_type bucket = mHasher(k) % mBucketCount;
 424
 425         for(vdhashtable_base_node *p = mpBucketStart[bucket]; p; p = p->mpHashNext) {
 426                 node_type *node = static_cast<node_type *>(p);
 427
 428                 if (mPred(node->mData.first, k))
 429                         return iterator(node, &mpBucketStart[bucket], mpBucketEnd);
 430         }
 431
 432         return iterator();
 433 }
 434
 435 template<class K, class V, class Hash, class Pred, class A>
 436 typename vdhashmap<K, V, Hash, Pred, A>::const_iterator vdhashmap<K, V, Hash, Pred, A>::find(const key_type& k) const {
 437         if (!mBucketCount)
 438                 return iterator();
 439
 440         size_type bucket = mHasher(k) % mBucketCount;
 441
 442         for(const vdhashtable_base_node *p = mpBucketStart[bucket]; p; p = p->mpHashNext) {
 443                 const node_type *node = static_cast<const node_type *>(p);
 444
 445                 if (mPred(node->mData.first, k))
 446                         return const_iterator(const_cast<vdhashtable_base_node *>(static_cast<const vdhashtable_base_node *>(node)), &mpBucketStart[bucket], mpBucketEnd);
 447         }
 448
 449         return iterator();
 450 }
 451
 452 template<class K, class V, class Hash, class Pred, class A>
 453 typename vdhashmap<K, V, Hash, Pred, A>::size_type vdhashmap<K, V, Hash, Pred, A>::count(const key_type& k) const {
 454         return find(k) != end() ? 1 : 0;
 455 }
 456
 457 template<class K, class V, class Hash, class Pred, class A>
 458 std::pair<typename vdhashmap<K, V, Hash, Pred, A>::iterator, typename vdhashmap<K, V, Hash, Pred, A>::iterator> vdhashmap<K, V, Hash, Pred, A>::equal_range(const key_type& k) {
 459         iterator it = find(k);
 460         iterator itEnd;
 461
 462         if (it == itEnd)
 463                 return std::make_pair(itEnd, itEnd);
 464
 465         itEnd = it;
 466         ++itEnd;
 467
 468         return std::make_pair<it, itEnd>();
 469 }
 470
 471 template<class K, class V, class Hash, class Pred, class A>
 472 std::pair<typename vdhashmap<K, V, Hash, Pred, A>::const_iterator, typename vdhashmap<K, V, Hash, Pred, A>::const_iterator> vdhashmap<K, V, Hash, Pred, A>::equal_range(const key_type& k) const {
 473         const_iterator it = find(k);
 474         const_iterator itEnd;
 475
 476         if (it == itEnd)
 477                 return std::make_pair(itEnd, itEnd);
 478
 479         itEnd = it;
 480         ++itEnd;
 481
 482         return std::make_pair(it, itEnd);
 483 }
 484
 485 template<class K, class V, class Hash, class Pred, class A>
 486 template<class U>
 487 typename vdhashmap<K, V, Hash, Pred, A>::iterator vdhashmap<K, V, Hash, Pred, A>::find_as(const U& k) {
 488         if (!mBucketCount)
 489                 return iterator();
 490
 491         size_type bucket = mHasher(k) % mBucketCount;
 492
 493         for(vdhashtable_base_node *p = mpBucketStart[bucket]; p; p = p->mpHashNext) {
 494                 node_type *node = static_cast<node_type *>(p);
 495
 496                 if (mPred(node->mData.first, k))
 497                         return iterator(node, &mpBucketStart[bucket], mpBucketEnd);
 498         }
 499
 500         return iterator();
 501 }
 502
 503 template<class K, class V, class Hash, class Pred, class A>
 504 template<class U>
 505 typename vdhashmap<K, V, Hash, Pred, A>::const_iterator vdhashmap<K, V, Hash, Pred, A>::find_as(const U& k) const {
 506         if (!mBucketCount)
 507                 return iterator();
 508
 509         size_type bucket = mHasher(k) % mBucketCount;
 510
 511         for(const vdhashtable_base_node *p = mpBucketStart[bucket]; p; p = p->mpHashNext) {
 512                 const node_type *node = static_cast<const node_type *>(p);
 513
 514                 if (mPred(node->mData.first, k))
 515                         return const_iterator(const_cast<vdhashtable_base_node *>(static_cast<const vdhashtable_base_node *>(node)), &mpBucketStart[bucket], mpBucketEnd);
 516         }
 517
 518         return iterator();
 519 }
 520
 521 // bucket interface
 522 template<class K, class V, class Hash, class Pred, class A>
 523 typename vdhashmap<K, V, Hash, Pred, A>::size_type vdhashmap<K, V, Hash, Pred, A>::bucket(const key_type& k) const {
 524         size_type bucket = 0;
 525
 526         if (mBucketCount)
 527                 bucket = mHasher(k) % mBucketCount;
 528
 529         return bucket;
 530 }
 531
 532 template<class K, class V, class Hash, class Pred, class A>
 533 typename vdhashmap<K, V, Hash, Pred, A>::local_iterator vdhashmap<K, V, Hash, Pred, A>::begin(size_type n) {
 534         return local_iterator(mpBucketStart[n]);
 535 }
 536
 537 template<class K, class V, class Hash, class Pred, class A>
 538 typename vdhashmap<K, V, Hash, Pred, A>::const_local_iterator vdhashmap<K, V, Hash, Pred, A>::begin(size_type n) const {
 539         return const_local_iterator(mpBucketStart[n]);
 540 }
 541
 542 template<class K, class V, class Hash, class Pred, class A>
 543 typename vdhashmap<K, V, Hash, Pred, A>::local_iterator vdhashmap<K, V, Hash, Pred, A>::end(size_type n) {
 544         return local_iterator(NULL);
 545 }
 546
 547 template<class K, class V, class Hash, class Pred, class A>
 548 typename vdhashmap<K, V, Hash, Pred, A>::const_local_iterator vdhashmap<K, V, Hash, Pred, A>::end(size_type n) const {
 549         return const_local_iterator(NULL);
 550 }
 551
 552 // hash policy
 553 template<class K, class V, class Hash, class Pred, class A>
 554 void vdhashmap<K, V, Hash, Pred, A>::rehash(size_type n) {
 555         if (!n)
 556                 n = 1;
 557
 558         if (mBucketCount == n)
 559                 return;
 560
 561         vdhashtable_base_node **newBuckets = mBucketAllocator.allocate(n + 1);
 562
 563         for(size_type i=0; i<=n; ++i)
 564                 newBuckets[i] = NULL;
 565
 566         const size_type m = mBucketCount;
 567         for(size_type i=0; i<m; ++i) {
 568                 for(vdhashtable_base_node *p = mpBucketStart[i]; p;) {
 569                         vdhashtable_base_node *next = p->mpHashNext;
 570                         const value_type& vt = static_cast<vdhashtable_node<value_type> *>(p)->mData;
 571                         size_t bucket = mHasher(vt.first) % n;
 572
 573                         vdhashtable_base_node *head = newBuckets[bucket];
 574
 575                         p->mpHashNext = head;
 576                         newBuckets[bucket] = p;
 577
 578                         p = next;
 579                 }
 580         }
 581
 582         if (mpBucketStart != &sEmptyBucket)
 583                 mBucketAllocator.deallocate(mpBucketStart, (mpBucketEnd - mpBucketStart) + 1);
 584
 585         mpBucketStart = newBuckets;
 586         mpBucketEnd = newBuckets + n;
 587         mBucketCount = n;
 588 }
 589
 590 template<class K, class V, class Hash, class Pred, class A>
 591 void vdhashmap<K, V, Hash, Pred, A>::rehash_to_size(size_type n) {
 592         size_type buckets = compute_bucket_count(n);
 593         rehash(buckets);
 594 }
 595
 596 template<class K, class V, class Hash, class Pred, class A>
 597 void vdhashmap<K, V, Hash, Pred, A>::reset() {
 598         clear();
 599
 600         if (mpBucketStart != &sEmptyBucket)
 601                 mBucketAllocator.deallocate(mpBucketStart, (mpBucketEnd - mpBucketStart) + 1);
 602 }
 603
 604 #endif  // f_VD2_SYSTEM_VDSTL_HASHMAP_H