src/thirdparty/VirtualDub/h/vd2/system/vdstl_hashtable.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_HASHTABLE_H
  27 #define f_VD2_SYSTEM_VDSTL_HASHTABLE_H
  28
  29 ///////////////////////////////////////////////////////////////////////////////
  30 //      vdhashtable_base_node
  31 //
  32 struct vdhashtable_base_node {
  33         vdhashtable_base_node *mpHashNext;
  34 };
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37 //      vdhashtable_base
  38 //
  39 class vdhashtable_base {
  40 public:
  41         typedef size_t          size_type;
  42         typedef ptrdiff_t       difference_type;
  43
  44         vdhashtable_base();
  45
  46         // size and capacity
  47         bool            empty() const { return mElementCount == 0; }
  48         size_type       size() const { return mElementCount; }
  49         size_type       max_size() const { return (size_type)-1 >> 1; }
  50
  51         // bucket interface
  52         size_type                       bucket_count() const;
  53         size_type                       max_bucket_count() const;
  54         size_type                       bucket_size(size_type n) const;
  55
  56 protected:
  57         static size_type compute_bucket_count(size_type n);
  58
  59         size_type       mBucketCount;
  60         size_type       mElementCount;
  61         vdhashtable_base_node **mpBucketStart;
  62         vdhashtable_base_node **mpBucketEnd;
  63
  64         static vdhashtable_base_node *const sEmptyBucket;
  65 };
  66
  67 ///////////////////////////////////////////////////////////////////////////
  68
  69 template<class T>
  70 struct vdhashtable_node : public vdhashtable_base_node {
  71         T mData;
  72
  73         vdhashtable_node() {}
  74         vdhashtable_node(vdhashtable_node<T> *next) : mData() {
  75                 mpHashNext = next;
  76         }
  77
  78         vdhashtable_node(vdhashtable_node<T> *next, const T& val) : mData(val) {
  79                 mpHashNext = next;
  80         }
  81 };
  82
  83 ///////////////////////////////////////////////////////////////////////////
  84
  85 template<class T>
  86 class vdhashtable_local_iterator {
  87 public:
  88         typedef std::forward_iterator_tag iterator_category;
  89         typedef T value_type;
  90         typedef T* pointer;
  91         typedef T& reference;
  92         typedef size_t size_type;
  93         typedef ptrdiff_t difference_type;
  94
  95         vdhashtable_local_iterator(vdhashtable_base_node *node);
  96
  97         vdhashtable_local_iterator& operator++();
  98         vdhashtable_local_iterator operator++(int);
  99
 100         T& operator*() const;
 101         T* operator->() const;
 102
 103 private:
 104         template<class U> friend bool operator==(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<U>& y);
 105         template<class U> friend bool operator==(const vdhashtable_local_iterator<const U>& x, const vdhashtable_local_iterator<U>& y);
 106         template<class U> friend bool operator==(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<const U>& y);
 107         template<class U> friend bool operator!=(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<U>& y);
 108         template<class U> friend bool operator!=(const vdhashtable_local_iterator<const U>& x, const vdhashtable_local_iterator<U>& y);
 109         template<class U> friend bool operator!=(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<const U>& y);
 110
 111         vdhashtable_base_node *mpNode;
 112 };
 113
 114 template<class T>
 115 vdhashtable_local_iterator<T>::vdhashtable_local_iterator(vdhashtable_base_node *node)
 116         : mpNode(node)
 117 {
 118 }
 119
 120 template<class T>
 121 vdhashtable_local_iterator<T>& vdhashtable_local_iterator<T>::operator++() {
 122         mpNode = mpNode->mpHashNext;
 123         return *this;
 124 }
 125
 126 template<class T>
 127 vdhashtable_local_iterator<T> vdhashtable_local_iterator<T>::operator++(int) {
 128         vdhashtable_local_iterator prev(*this);
 129         mpNode = mpNode->mpHashNext;
 130         return prev;
 131 }
 132
 133 template<class T>
 134 T& vdhashtable_local_iterator<T>::operator*() const {
 135         return static_cast<vdhashtable_node<T> *>(mpNode)->mData;
 136 }
 137
 138 template<class T>
 139 T* vdhashtable_local_iterator<T>::operator->() const {
 140         return &static_cast<vdhashtable_node<T> *>(mpNode)->mData;
 141 }
 142
 143 template<class T>
 144 bool operator==(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<T>& y) {
 145         return x.mpNode == y.mpNode;
 146 }
 147
 148 template<class T>
 149 bool operator==(const vdhashtable_local_iterator<const T>& x, const vdhashtable_local_iterator<T>& y) {
 150         return x.mpNode == y.mpNode;
 151 }
 152
 153 template<class T>
 154 bool operator==(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<const T>& y) {
 155         return x.mpNode == y.mpNode;
 156 }
 157
 158 template<class T>
 159 bool operator!=(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<T>& y) {
 160         return x.mpNode != y.mpNode;
 161 }
 162
 163 template<class T>
 164 bool operator!=(const vdhashtable_local_iterator<const T>& x, const vdhashtable_local_iterator<T>& y) {
 165         return x.mpNode != y.mpNode;
 166 }
 167
 168 template<class T>
 169 bool operator!=(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<const T>& y) {
 170         return x.mpNode != y.mpNode;
 171 }
 172
 173 ///////////////////////////////////////////////////////////////////////////
 174
 175 template<class T> struct vdhashtable_iterator_nonconst {
 176         typedef T result;
 177 };
 178
 179 template<class T> struct vdhashtable_iterator_nonconst<const T> {
 180         typedef T result;
 181 };
 182
 183 template<class T>
 184 class vdhashtable_iterator {
 185         typedef typename vdhashtable_iterator_nonconst<T>::result T_NonConst;
 186 public:
 187         typedef std::forward_iterator_tag iterator_category;
 188         typedef T value_type;
 189         typedef T* pointer;
 190         typedef T& reference;
 191         typedef size_t size_type;
 192         typedef ptrdiff_t difference_type;
 193
 194         vdhashtable_iterator();
 195         vdhashtable_iterator(vdhashtable_base_node *node, vdhashtable_base_node **bucket, vdhashtable_base_node **bucketEnd);
 196         vdhashtable_iterator(const vdhashtable_iterator<T_NonConst>& src);
 197
 198         vdhashtable_iterator& operator++();
 199         vdhashtable_iterator operator++(int);
 200
 201         T& operator*() const;
 202         T* operator->() const;
 203
 204 private:
 205         friend class vdhashtable_iterator<const T>;
 206         template<class U> friend bool operator==(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<U>& y);
 207         template<class U> friend bool operator==(const vdhashtable_iterator<const U>& x, const vdhashtable_iterator<U>& y);
 208         template<class U> friend bool operator==(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<const U>& y);
 209         template<class U> friend bool operator!=(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<U>& y);
 210         template<class U> friend bool operator!=(const vdhashtable_iterator<const U>& x, const vdhashtable_iterator<U>& y);
 211         template<class U> friend bool operator!=(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<const U>& y);
 212
 213         vdhashtable_base_node *mpNode;
 214         vdhashtable_base_node **mpBucket;
 215         vdhashtable_base_node **mpBucketEnd;
 216 };
 217
 218 template<class T>
 219 vdhashtable_iterator<T>::vdhashtable_iterator()
 220         : mpNode(NULL)
 221         , mpBucket(NULL)
 222         , mpBucketEnd(NULL)
 223 {
 224 }
 225
 226 template<class T>
 227 vdhashtable_iterator<T>::vdhashtable_iterator(vdhashtable_base_node *node, vdhashtable_base_node **bucket, vdhashtable_base_node **bucketEnd)
 228         : mpNode(node)
 229         , mpBucket(bucket)
 230         , mpBucketEnd(bucketEnd)
 231 {
 232 }
 233
 234 template<class T>
 235 vdhashtable_iterator<T>::vdhashtable_iterator(const vdhashtable_iterator<T_NonConst>& src)
 236         : mpNode(src.mpNode)
 237         , mpBucket(src.mpBucket)
 238         , mpBucketEnd(src.mpBucketEnd)
 239 {
 240 }
 241
 242 template<class T>
 243 vdhashtable_iterator<T>& vdhashtable_iterator<T>::operator++() {
 244         mpNode = mpNode->mpHashNext;
 245
 246         while(!mpNode && ++mpBucket != mpBucketEnd)
 247                 mpNode = static_cast<vdhashtable_node<T> *>(*mpBucket);
 248
 249         return *this;
 250 }
 251
 252 template<class T>
 253 vdhashtable_iterator<T> vdhashtable_iterator<T>::operator++(int) {
 254         vdhashtable_iterator prev(*this);
 255         mpNode = mpNode->mpHashNext;
 256         return prev;
 257 }
 258
 259 template<class T>
 260 T& vdhashtable_iterator<T>::operator*() const {
 261         return static_cast<vdhashtable_node<T> *>(mpNode)->mData;
 262 }
 263
 264 template<class T>
 265 T* vdhashtable_iterator<T>::operator->() const {
 266         return &static_cast<vdhashtable_node<T> *>(mpNode)->mData;
 267 }
 268
 269 template<class T>
 270 bool operator==(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<T>& y) {
 271         return x.mpNode == y.mpNode;
 272 }
 273
 274 template<class T>
 275 bool operator==(const vdhashtable_iterator<const T>& x, const vdhashtable_iterator<T>& y) {
 276         return x.mpNode == y.mpNode;
 277 }
 278
 279 template<class T>
 280 bool operator==(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<const T>& y) {
 281         return x.mpNode == y.mpNode;
 282 }
 283
 284 template<class T>
 285 bool operator!=(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<T>& y) {
 286         return x.mpNode != y.mpNode;
 287 }
 288
 289 template<class T>
 290 bool operator!=(const vdhashtable_iterator<const T>& x, const vdhashtable_iterator<T>& y) {
 291         return x.mpNode != y.mpNode;
 292 }
 293
 294 template<class T>
 295 bool operator!=(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<const T>& y) {
 296         return x.mpNode != y.mpNode;
 297 }
 298
 299 ///////////////////////////////////////////////////////////////////////////
 300
 301 template<class T>
 302 class vdhashtable : public vdhashtable_base {
 303 public:
 304         typedef T value_type;
 305         typedef vdhashtable_node<value_type> node_type;
 306         typedef value_type *pointer;
 307         typedef const value_type *const_pointer;
 308         typedef value_type& reference;
 309         typedef const value_type& const_reference;
 310         typedef vdhashtable_iterator<value_type> iterator;
 311         typedef vdhashtable_iterator<const value_type> const_iterator;
 312         typedef vdhashtable_local_iterator<value_type> local_iterator;
 313         typedef vdhashtable_local_iterator<const value_type> const_local_iterator;
 314
 315         // iterators
 316         iterator                        begin();
 317         const_iterator          begin() const;
 318         iterator                        end();
 319         const_iterator          end() const;
 320 };
 321
 322 // iterators
 323 template<class T>
 324 typename vdhashtable<T>::iterator vdhashtable<T>::begin() {
 325         vdhashtable_base_node **bucket = mpBucketStart;
 326         vdhashtable_base_node *p = NULL;
 327
 328         while(bucket != mpBucketEnd) {
 329                 p = *bucket;
 330                 if (p)
 331                         break;
 332
 333                 ++bucket;
 334         }
 335
 336         return iterator(static_cast<node_type *>(p), bucket, mpBucketEnd);
 337 }
 338
 339 template<class T>
 340 typename vdhashtable<T>::const_iterator vdhashtable<T>::begin() const {
 341         vdhashtable_base_node **bucket = mpBucketStart;
 342         vdhashtable_base_node *p = NULL;
 343
 344         while(bucket != mpBucketEnd) {
 345                 p = *bucket;
 346                 if (p)
 347                         break;
 348
 349                 ++bucket;
 350         }
 351
 352         return const_iterator(static_cast<node_type *>(p), bucket, mpBucketEnd);
 353 }
 354
 355 template<class T>
 356 typename vdhashtable<T>::iterator vdhashtable<T>::end() {
 357         return iterator(NULL, NULL, NULL);
 358 }
 359
 360 template<class T>
 361 typename vdhashtable<T>::const_iterator vdhashtable<T>::end() const {
 362         return const_iterator(NULL, NULL, NULL);
 363 }
 364
 365 #endif  // f_VD2_SYSTEM_VDSTL_HASHTABLE_H