← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/blender/intrepid-updates

« back to all changes in this revision

Viewing changes to extern/qdune/qdtl/qdtl.h

  • Committer: Bazaar Package Importer
  • Author(s): Cyril Brulebois
  • Date: 2008-08-08 02:45:40 UTC
  • mfrom: (12.1.14 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080808024540-kkjp7ekfivzhuw3l
Tags: 2.46+dfsg-4
http://bugs.debian.org/492280
* Fix python syntax warning in import_dxf.py, which led to nasty output
  in installation/upgrade logs during byte-compilation, using a patch
  provided by the script author (Closes: #492280):
   - debian/patches/45_fix_python_syntax_warning

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/qdune/qdtl/qdtl.h
 
1
//--------------------------------------------------------------------------------
 
2
// sort of the 'QuietDune Template Library' ;)
 
3
// Various implementations of arrays, linked lists, hashtables, tree's, etc..
 
4
// Originally contained even more variations of each, but now only what is
 
5
// actually used in the program. Should really each be moved to its own file.
 
6
// Was mostly created for possibly easier specialized optimization issues vs. stl.
 
7
// But didn't really get around to that, so all of these could be thrown out
 
8
// and use the stl instead. But it was useful as a learning experience anyway...
 
9
//--------------------------------------------------------------------------------
 
10
 
 
11
#ifndef __QDTL_H
 
12
#define __QDTL_H
 
13
 
 
14
#ifdef _MSC_VER
 
15
#pragma warning(disable : 4996)
 
16
#endif
 
17
#include <cassert>
 
18
#include <cstring>
 
19
 
 
20
#include "QDRender.h"
 
21
__BEGIN_QDRENDER
 
22
 
 
23
// fixed size array
 
24
template<typename T>
 
25
class fsArray_t
 
26
{
 
27
public:
 
28
        fsArray_t():array(NULL), _size(0) {}
 
29
        fsArray_t(size_t Size):array(NULL), _size(0) { resize(Size); }
 
30
        fsArray_t(const fsArray_t &fa):array(NULL), _size(0) { copy(fa); }
 
31
        ~fsArray_t() { _free(); }
 
32
        fsArray_t& operator=(const fsArray_t& fa) { copy(fa);  return *this; }
 
33
        void resize(size_t Size) { _free();  _size = Size;   array = new T [_size]; }
 
34
        T& operator[](size_t i) { return array[i]; }
 
35
        T& operator[](size_t i) const { return array[i]; }
 
36
        size_t size() const { return _size; }
 
37
        bool empty() const { return (_size == 0); }
 
38
        typedef T* iterator;
 
39
        typedef const T* const_iterator;
 
40
        iterator begin() { return array; }
 
41
        iterator end() { return array + _size; }
 
42
        const_iterator begin() const { return array; }
 
43
        const_iterator end() const { return array + _size; }
 
44
protected:
 
45
        void _free() { if (array) delete[] array;  array = NULL;  _size = _size = 0; }
 
46
        void copy(const fsArray_t& fa)
 
47
        {
 
48
                _free();  resize(fa._size);
 
49
                for (size_t i=0; i<_size; ++i) array[i] = fa.array[i];
 
50
        }
 
51
        T* array;
 
52
        size_t _size;
 
53
};
 
54
 
 
55
// generic growable array class, similar to STL vector, can be used as stack/list as well,
 
56
template <typename T>
 
57
class array_t
 
58
{
 
59
private:
 
60
        //array_t(const array_t& a);
 
61
        //array_t& operator=(const array_t& a);
 
62
public:
 
63
        array_t():array(NULL), curidx(0), maxidx(0) {}
 
64
        array_t(const array_t& a)
 
65
        {
 
66
                array = new T [a.maxidx];
 
67
                for (size_t i=0; i<a.maxidx; ++i) array[i] = a.array[i];
 
68
                curidx = a.curidx;
 
69
                maxidx = a.maxidx;
 
70
        }
 
71
        array_t(size_t initsize)
 
72
        {
 
73
                curidx = maxidx = initsize;
 
74
                array = new T [maxidx];
 
75
                memset(array, 0, maxidx*sizeof(T));
 
76
        }
 
77
        ~array_t()
 
78
        {
 
79
                if (array) {
 
80
                        delete[] array;
 
81
                        array = NULL;
 
82
                }
 
83
        }
 
84
        array_t& operator=(const array_t& a)
 
85
        {
 
86
                // don't delete if enough space already
 
87
                if (array && (a.maxidx <= maxidx)) {
 
88
                        for (size_t i=0; i<a.curidx; ++i) array[i] = a.array[i];
 
89
                        curidx = a.curidx;
 
90
                        return *this;
 
91
                }
 
92
                if (array) delete[] array;
 
93
                array = new T [a.maxidx];
 
94
                for (size_t i=0; i<a.maxidx; ++i) array[i] = a.array[i];
 
95
                curidx = a.curidx;
 
96
                maxidx = a.maxidx;
 
97
                return *this;
 
98
        }
 
99
        void clear() { curidx = 0; } // no delete, just set index back to 0
 
100
        void resize(size_t newsize)
 
101
        {
 
102
                // do nothing if newsize less or equal to already allocated space
 
103
                if (array && (newsize <= maxidx)) return;
 
104
                maxidx = newsize;
 
105
                T* na = new T [maxidx];
 
106
                memset(na, 0, maxidx*sizeof(T));
 
107
                if (array) {
 
108
                        for (size_t i=0; i<curidx; ++i) na[i] = array[i];
 
109
                        delete[] array;
 
110
                }
 
111
                curidx = newsize;
 
112
                array = na;
 
113
        }
 
114
        // as above, but does not copy old contents
 
115
        void resize_clear(size_t newsize)
 
116
        {
 
117
                // only clear if newsize less or equal to already allocated space (if any)
 
118
                if (array && (newsize <= maxidx)) { curidx = 0;  return; }
 
119
                maxidx = newsize;
 
120
                if (array) delete[] array;
 
121
                array = new T [maxidx];
 
122
                curidx = 0;
 
123
        }
 
124
        // add item to array
 
125
        void push_back(const T& item) { checkCapacity();  array[curidx++] = item; }
 
126
        /*
 
127
        // returns reference to first item
 
128
        T& front() const { return array[0]; }
 
129
        // pops first item from the array, does not do anything if array empty
 
130
        void pop_front() { if (curidx) { curidx--;  memmove(array, array+1, curidx*sizeof(T)); } }
 
131
        // returns reference to last item
 
132
        T& back() const { return array[curidx-1]; }
 
133
        // pops last item from the array, does not do anything if array empty
 
134
        void pop_back() { if (curidx) curidx--; }
 
135
        // pops and returns last item from the array, aborts if array empty
 
136
        T& pop() { assert(curidx!=0);  return array[--curidx]; }
 
137
        */
 
138
        // array access, DOES NO BOUNDS CHECKING!!!!
 
139
        T& operator[](size_t i) { return array[i]; }
 
140
        T& operator[](size_t i) const { return array[i]; }
 
141
        // same, but does check bounds, aborts if trying to access array beyond bounds
 
142
        T& at(size_t i) { assert(i<curidx);  return array[i]; }
 
143
        bool empty() const { return (curidx==0); }
 
144
        size_t size() const { return curidx; }
 
145
        size_t capacity() const { return maxidx; }
 
146
        // returns true if item is contained in array
 
147
        bool contains(const T& item) const
 
148
        {
 
149
                for (size_t i=0; i<curidx; ++i)
 
150
                        if (array[i] == item) return true;
 
151
                return false;
 
152
        }
 
153
        // returns index number of item in array, if not found, returns -1
 
154
        int index(const T& item) const
 
155
        {
 
156
                for (size_t i = 0; i<curidx; ++i)
 
157
                        if (array[i] == item) return i;
 
158
                return -1;
 
159
        }
 
160
        // for iterator emulation
 
161
        typedef T* iterator;
 
162
        typedef const T* const_iterator;
 
163
        iterator begin() { return &array[0]; }
 
164
        iterator end() { return &array[curidx]; }
 
165
        const_iterator begin() const { return &array[0]; }
 
166
        const_iterator end() const { return &array[curidx]; }
 
167
protected:
 
168
        // check if more memory needed
 
169
        void checkCapacity()
 
170
        {
 
171
                if (curidx >= maxidx) {
 
172
                        maxidx = (maxidx==0) ? 1 : (maxidx << 1);
 
173
                        T* na = new T [maxidx];
 
174
                        if (array) {
 
175
                                for (size_t i=0; i<curidx; ++i) na[i] = array[i];
 
176
                                delete[] array;
 
177
                        }
 
178
                        array = na;
 
179
                }
 
180
        }
 
181
        T* array;
 
182
        size_t curidx, maxidx;
 
183
};
 
184
//------------------------------------------------------------------------------
 
185
 
 
186
// associative linked list
 
187
template<typename keytype, typename datatype>
 
188
class alist_t
 
189
{
 
190
private:
 
191
        alist_t(const alist_t& L);
 
192
        alist_t& operator=(const alist_t& L);
 
193
public:
 
194
        alist_t() : list(NULL), maxitems(0) {}
 
195
        ~alist_t() { clear(); }
 
196
        void insert(const keytype& k, const datatype& item)
 
197
        {
 
198
                list = new link_t(k, item, list);
 
199
                ++maxitems;
 
200
        }
 
201
        // remove item, search by item key,
 
202
        // returns false if item was not found, does not delete data!
 
203
        bool remove(const keytype& k)
 
204
        {
 
205
                for (link_t *L=list, *pL=NULL; L!=NULL; pL=L, L=L->next) {
 
206
                        if (L->k == k) {
 
207
                                if (pL)
 
208
                                        pL->next = L->next;
 
209
                                else
 
210
                                        list = L->next;
 
211
                                delete L;
 
212
                                --maxitems;
 
213
                                return true;
 
214
                        }
 
215
                }
 
216
                return false;
 
217
        }
 
218
        datatype* find(const keytype& k) const
 
219
        {
 
220
                for (link_t* L=list; L!=NULL; L=L->next)
 
221
                        if (L->k == k) return &L->d;
 
222
                return NULL;
 
223
        }
 
224
        size_t size() const { return maxitems; }
 
225
        void clear()
 
226
        {
 
227
                link_t* L = list;
 
228
                while (L) {
 
229
                        link_t* tmp = L->next;
 
230
                        delete L;
 
231
                        L = tmp;
 
232
                }
 
233
                list = NULL;
 
234
                maxitems = 0;
 
235
        }
 
236
        // if list has allocated data, use this to delete it properly.
 
237
        // just for convenience, probably should really leave it to user though...
 
238
        void clear_delete()
 
239
        {
 
240
                link_t* it = list;
 
241
                while (it) {
 
242
                        link_t* tmp = it->next;
 
243
                        delete it->d;
 
244
                        delete it;
 
245
                        it = tmp;
 
246
                }
 
247
                list = NULL;
 
248
                maxitems = 0;
 
249
        }
 
250
        // as above, array version
 
251
        void clear_delete_array()
 
252
        {
 
253
                link_t* it = list;
 
254
                while (it) {
 
255
                        link_t* tmp = it->next;
 
256
                        delete[] it->d;
 
257
                        delete it;
 
258
                        it = tmp;
 
259
                }
 
260
                list = NULL;
 
261
                maxitems = 0;
 
262
        }
 
263
protected:
 
264
        struct link_t
 
265
        {
 
266
                link_t(const keytype& _k, const datatype& _d, link_t* n):k(_k), d(_d), next(n) {}
 
267
                keytype k;
 
268
                datatype d;
 
269
                link_t* next;
 
270
        };
 
271
        link_t *list;
 
272
        size_t maxitems;
 
273
};
 
274
 
 
275
// as above, for string keys
 
276
template<typename datatype>
 
277
class sklist_t
 
278
{
 
279
private:
 
280
        sklist_t(const sklist_t& L);
 
281
        sklist_t& operator=(const sklist_t& L);
 
282
public:
 
283
        sklist_t():list(NULL), curitem(NULL), maxitems(0) {}
 
284
        ~sklist_t() { clear(); }
 
285
        void clear()
 
286
        {
 
287
                link_t* L = list;
 
288
                while (L) {
 
289
                        link_t* pL = L->next;
 
290
                        delete[] L->name;
 
291
                        delete L;
 
292
                        L = pL;
 
293
                }
 
294
                list = curitem = NULL;
 
295
                maxitems = 0;
 
296
        }
 
297
        void insert(const char* name, const datatype& item)
 
298
        {
 
299
                link_t* L = new link_t;
 
300
                L->name = new char[strlen(name) + 1];
 
301
                strcpy(L->name, name);
 
302
                L->data = item;
 
303
                L->next = list;
 
304
                list = L;
 
305
                maxitems++;
 
306
        }
 
307
        datatype* find(const char* name) const
 
308
        {
 
309
                for (link_t* L=list; L!=NULL; L=L->next)
 
310
                        if (!strcmp(name, L->name)) return &L->data;
 
311
                return NULL;
 
312
        }
 
313
        void remove(const char* name, datatype& dt)
 
314
        {
 
315
                for (link_t *L=list, *pL=NULL; L!=NULL; pL=L, L=L->next)
 
316
                        if (!strcmp(name, L->name)) {
 
317
                                if (pL)
 
318
                                        pL->next = L->next;
 
319
                                else
 
320
                                        list = L->next;
 
321
                                dt = L->data;
 
322
                                delete[] L->name;
 
323
                                delete L;
 
324
                                --maxitems;
 
325
                                return;
 
326
                        }
 
327
        }
 
328
        inline bool empty() const { return (maxitems == 0); }
 
329
        inline size_t size() const { return maxitems; }
 
330
        inline datatype* first() { return ((curitem = list)==NULL) ? NULL : &curitem->data; }
 
331
        inline datatype* next()
 
332
        {
 
333
                return (curitem==NULL) ? NULL : (((curitem = curitem->next)==NULL) ? NULL : &curitem->data);
 
334
        }
 
335
        // returns key string, use with first/next
 
336
        inline char* getName() { return (curitem==NULL) ? NULL : curitem->name; }
 
337
protected:
 
338
        struct link_t
 
339
        {
 
340
                char* name;
 
341
                datatype data;
 
342
                link_t* next;
 
343
        };
 
344
        link_t *list, *curitem;
 
345
        size_t maxitems;
 
346
};
 
347
 
 
348
//------------------------------------------------------------------------------
 
349
 
 
350
// more experiments, Andersson tree, C++ implementation of Jullienne Walker's jsw_atree library
 
351
// see http://eternallyconfuzzled.com/jsw_home.aspx
 
352
// Works quite well, could possibly be used as replacement for map<>
 
353
template<typename keytype, typename datatype>
 
354
class aatree_t
 
355
{
 
356
public:
 
357
        aatree_t():numitems(0) { nil.link[0] = nil.link[1] = root = &nil; }
 
358
        ~aatree_t() { clear(); }
 
359
        // mtds
 
360
        void clear()
 
361
        {
 
362
                node_t *save, *it = root;
 
363
                while (it != &nil) {
 
364
                        if (it->link[0] == &nil) {
 
365
                                save = it->link[1];
 
366
                                delete it;
 
367
                        }
 
368
                        else {
 
369
                                save = it->link[0];
 
370
                                it->link[0] = save->link[1];
 
371
                                save->link[1] = it;
 
372
                        }
 
373
                        it = save;
 
374
                }
 
375
                root = &nil;
 
376
                numitems = 0;
 
377
        }
 
378
        void clear_delete()
 
379
        {
 
380
                node_t *save, *it = root;
 
381
                while (it != &nil) {
 
382
                        if (it->link[0] == &nil) {
 
383
                                save = it->link[1];
 
384
                                delete it->data;
 
385
                                delete it;
 
386
                        }
 
387
                        else {
 
388
                                save = it->link[0];
 
389
                                it->link[0] = save->link[1];
 
390
                                save->link[1] = it;
 
391
                        }
 
392
                        it = save;
 
393
                }
 
394
                root = &nil;
 
395
                numitems = 0;
 
396
        }
 
397
        datatype* find(const keytype& key) const
 
398
        {
 
399
                node_t* it = root;
 
400
                while (it != &nil) {
 
401
                        if (it->key == key) return &it->data;
 
402
                        it = it->link[it->key < key];
 
403
                }
 
404
                return NULL;
 
405
        }
 
406
        void insert(const keytype& key, const datatype& data)
 
407
        {
 
408
                if (root == &nil) // Empty tree case
 
409
                        root = new node_t(1, key, data, &nil);
 
410
                else {
 
411
                        // if key already exists, replace item
 
412
                        node_t *it = root, *path[64];
 
413
                        int dir, top = 0;
 
414
                        // Find a spot and save the path
 
415
                        for (;;) {
 
416
                                assert(top < 64);
 
417
                                path[top++] = it;
 
418
                                dir = (it->key < key);
 
419
                                if (it->link[dir] == &nil) break;
 
420
                                it = it->link[dir];
 
421
                        }
 
422
                        // Create a new item
 
423
                        it->link[dir] = new node_t(1, key, data, &nil);
 
424
                        // Walk back and rebalance
 
425
                        while (--top >=  0) {
 
426
                                // Which child?
 
427
                                if (top != 0) dir = ((path[top - 1]->link[1] == path[top]));
 
428
                                skew(path[top]);
 
429
                                split(path[top]);
 
430
                                // Fix the parent
 
431
                                if (top != 0)
 
432
                                        path[top - 1]->link[dir] = path[top];
 
433
                                else
 
434
                                        root = path[top];
 
435
                        }
 
436
                }
 
437
                ++numitems;
 
438
        }
 
439
        // remove item, does not delete data!
 
440
        bool remove(const keytype& key)
 
441
        {
 
442
                if (root == &nil) return false;
 
443
 
 
444
                node_t *it = root, *path[64];
 
445
                int dir=0, top = 0;
 
446
 
 
447
                /* Find node to remove and save path */
 
448
                for (;;) {
 
449
                        assert(top < 64);
 
450
                        path[top++] = it;
 
451
                        if (it == &nil) return false;
 
452
                        if (it->key == key) break;
 
453
                        dir = (it->key < key);
 
454
                        it = it->link[dir];
 
455
                }
 
456
 
 
457
                // Remove the found node
 
458
                if ((it->link[0] == &nil) || (it->link[1] == &nil))
 
459
                {
 
460
                        // Single child case
 
461
                        int dir2 = (it->link[0] == &nil);
 
462
 
 
463
                        // Unlink the item
 
464
                        if (--top != 0)
 
465
                                path[top - 1]->link[dir] = it->link[dir2];
 
466
                        else
 
467
                                root = it->link[1];
 
468
 
 
469
                        delete it;
 
470
                }
 
471
                else {
 
472
                        // Two child case
 
473
                        node_t *heir = it->link[1], *prev = it;
 
474
 
 
475
                        while (heir->link[0] != &nil) {
 
476
                                assert(top < 64);
 
477
                                path[top++] = prev = heir;
 
478
                                heir = heir->link[0];
 
479
                        }
 
480
 
 
481
                        //      Order is important!
 
482
                        //      (free item, replace item, free heir)
 
483
                        it->key = heir->key;
 
484
                        it->data = heir->data;
 
485
                        prev->link[prev == it] = heir->link[1];
 
486
                        delete heir;
 
487
                }
 
488
 
 
489
                /* Walk back up and rebalance */
 
490
                while (--top >= 0) {
 
491
                        node_t *up = path[top];
 
492
 
 
493
                        if (top != 0)
 
494
                                dir = (path[top - 1]->link[1] == up);
 
495
 
 
496
                        // Rebalance (aka. black magic)
 
497
                        if ((up->link[0]->level < up->level - 1) || (up->link[1]->level < up->level - 1))
 
498
                        {
 
499
                                if (up->link[1]->level > --up->level)
 
500
                                        up->link[1]->level = up->level;
 
501
 
 
502
                                // Order is important!
 
503
                                skew(up);
 
504
                                skew(up->link[1]);
 
505
                                skew(up->link[1]->link[1]);
 
506
                                split(up);
 
507
                                split(up->link[1]);
 
508
                        }
 
509
 
 
510
                        // Fix the parent
 
511
                        if ( top != 0 )
 
512
                                path[top - 1]->link[dir] = up;
 
513
                        else
 
514
                                root = up;
 
515
                }
 
516
        
 
517
                --numitems;
 
518
                return true;
 
519
        }
 
520
        bool empty() const { return (numitems == 0); }
 
521
        size_t size() const { return numitems; }
 
522
        size_t nodesize() const { return sizeof(node_t); }
 
523
protected:
 
524
        struct node_t
 
525
        {
 
526
                node_t():level(0)  { link[0] = link[1] = NULL; }
 
527
                node_t(int L, const keytype &K, const datatype &D, node_t* il):level(L), key(K), data(D) { link[0] = link[1] = il; }
 
528
                int level;
 
529
                keytype key;
 
530
                datatype data;
 
531
                node_t* link[2];
 
532
        };
 
533
 
 
534
        // Remove left horizontal links
 
535
        inline void skew(node_t* &t)
 
536
        {
 
537
                if ((t->link[0]->level == t->level) && (t->level != 0)) {
 
538
                        node_t *save = t->link[0];
 
539
                        t->link[0] = save->link[1];
 
540
                        save->link[1] = t;
 
541
                        t = save;
 
542
                }
 
543
        }
 
544
        // Remove consecutive horizontal links
 
545
        inline void split(node_t* &t)
 
546
        {
 
547
                if ((t->link[1]->link[1]->level == t->level) && (t->level != 0)) {
 
548
                        node_t *save = t->link[1];
 
549
                        t->link[1] = save->link[0];
 
550
                        save->link[0] = t;
 
551
                        t = save;
 
552
                        ++t->level;
 
553
                }
 
554
        }
 
555
 
 
556
        node_t nil, *root;
 
557
        size_t numitems;
 
558
};
 
559
 
 
560
//------------------------------------------------------------------------------
 
561
// hashtable_t/Map
 
562
 
 
563
unsigned int hashfunc(const unsigned char* data, unsigned int len);
 
564
 
 
565
// simple generic hashtable
 
566
template<typename hashtype, typename datatype, unsigned int log2_size=10>       // default of 1024 buckets
 
567
class hashtable_t
 
568
{
 
569
public:
 
570
        hashtable_t():numitems(0) {}
 
571
        ~hashtable_t() {}
 
572
        void insert(const hashtype& key, const datatype& data)
 
573
        {
 
574
                ++numitems;
 
575
                values[hashfunc(reinterpret_cast<const unsigned char*>(&key), sizeof(key)) & ((1 << log2_size)-1)].insert(key, data);
 
576
        }
 
577
        datatype* find(const hashtype& key) const
 
578
        {
 
579
                return values[hashfunc(reinterpret_cast<const unsigned char*>(&key), sizeof(key)) & ((1 << log2_size)-1)].find(key);
 
580
        }
 
581
        bool remove(const hashtype& key)
 
582
        {
 
583
                if (values[hashfunc(reinterpret_cast<const unsigned char*>(&key), sizeof(key)) & ((1 << log2_size)-1)].remove(key)) {
 
584
                        --numitems;
 
585
                        return true;
 
586
                }
 
587
                return false;
 
588
        }       
 
589
        void clear()
 
590
        {
 
591
                if (numitems) {
 
592
                        for (unsigned int n=0; n<(1 << log2_size); n++)
 
593
                                values[n].clear();
 
594
                        numitems = 0;
 
595
                }
 
596
        }
 
597
        // used for case where items are allocated when added
 
598
        void clear_delete()
 
599
        {
 
600
                for (unsigned int n=0; n<(1 << log2_size); n++)
 
601
                        values[n].clear_delete();
 
602
                numitems = 0;
 
603
        }
 
604
        size_t size() const { return numitems; }
 
605
        bool empty() const { return (numitems == 0); }
 
606
        void stats() const
 
607
        {
 
608
                int minbk=0x7fffffff, maxbk=-1;
 
609
                int minit=0x7fffffff, maxit=-1;
 
610
                for (unsigned int n=0; n<(1 << log2_size); n++) {
 
611
                        const int sz = (int)values[n].size();
 
612
                        if (sz < minit) { minbk = n;  minit = sz; }
 
613
                        if (sz > maxit) { maxbk = n;  maxit = sz; }
 
614
                }
 
615
                printf("hashtable_t() bucket %d has least items %d\n", minbk, minit);
 
616
                printf("hashtable_t() bucket %d has most items %d\n", maxbk, maxit);
 
617
        }
 
618
private:
 
619
        alist_t<hashtype, datatype> values[1 << log2_size];
 
620
        size_t numitems;
 
621
};
 
622
 
 
623
 
 
624
// as above, strings as key
 
625
template<typename datatype, unsigned int log2_size=10>  // default of 1024 buckets
 
626
class hashmap_t
 
627
{
 
628
public:
 
629
        hashmap_t():maxitems(0), curbk(0) {}
 
630
        ~hashmap_t() {}
 
631
        void insert(const char* name, const datatype &data)
 
632
        {
 
633
                values[hashfunc(reinterpret_cast<const unsigned char*>(name),
 
634
                                (unsigned int)strlen(name)) & ((1 << log2_size)-1)].insert(name, data);
 
635
                maxitems++;
 
636
        }
 
637
        datatype* find(const char* name) const
 
638
        {
 
639
                return values[hashfunc(reinterpret_cast<const unsigned char*>(name),
 
640
                                       (unsigned int)strlen(name)) & ((1 << log2_size)-1)].find(name);
 
641
        }
 
642
        void remove(const char* name, datatype& dt)
 
643
        {
 
644
                values[hashfunc(reinterpret_cast<const unsigned char*>(name),
 
645
                                (unsigned int)strlen(name)) & ((1 << log2_size)-1)].remove(name, dt);
 
646
                if (dt) --maxitems;
 
647
        }
 
648
        size_t size() const { return maxitems; }
 
649
        void clear()
 
650
        {
 
651
                for (unsigned int i=0; i<(1 << log2_size); ++i)
 
652
                        values[i].clear();
 
653
        }
 
654
        datatype* first()
 
655
        {
 
656
                // first non-empty bucket
 
657
                curbk = 0;
 
658
                if (maxitems == 0) return NULL;
 
659
                while (values[curbk].empty())
 
660
                        if (++curbk == (1 << log2_size)) return NULL;
 
661
                return values[curbk].first();
 
662
        }
 
663
        datatype* next()
 
664
        {
 
665
                if (curbk == (1 << log2_size)) return NULL;
 
666
                datatype* dt = values[curbk].next();
 
667
                if (dt == NULL) {       // next non-empty bucket
 
668
                        curbk++;
 
669
                        while (values[curbk].empty())
 
670
                                if (++curbk == (1 << log2_size)) return NULL;
 
671
                        dt = values[curbk].first();
 
672
                }
 
673
                return dt;
 
674
        }
 
675
        // returns key name string, use with first/next
 
676
        inline char* getName()
 
677
        {
 
678
                if (curbk == (1 << log2_size)) return NULL;
 
679
                return values[curbk].getName();
 
680
        }
 
681
private:
 
682
        sklist_t<datatype> values[1 << log2_size];
 
683
        size_t maxitems;
 
684
        unsigned int curbk;
 
685
};
 
686
 
 
687
__END_QDRENDER
 
688
 
 
689
#endif // __QDTL_H