source: icXML/icXML-devel/src/icxmlc/XMLNamespaceBindingSet.hpp @ 3103

Last change on this file since 3103 was 3103, checked in by cameron, 6 years ago

Initial imports for icXML v0.9

File size: 28.4 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: XMLNamespaceBindingSet.hpp 276 2013-03-21 22:31:52Z nigelm $
10 *
11 */
12
13#ifndef XMLNAMESPACEBINDINGTABLE_HPP
14#define XMLNAMESPACEBINDINGTABLE_HPP
15
16#include <icxmlc/XMLConfig.hpp>
17#include <icxmlc/Array.hpp>
18#include <simd-lib/bitblock.hpp>
19
20typedef ScanWord binding_t;
21
22#ifdef _MSC_VER
23#include <intrin.h> // _BitScanForward
24#endif
25
26class BindingSet;
27class BindingSetIterator;
28class FixedBindingSet;
29template<binding_t, binding_t> class BindingSets;
30
31//TODO: given that I know the binding sets will always be some power of 2 in size, I should be able to use
32//a trick to dynamically 'unroll' the loops at run time.
33
34#define CONSTRUCT_GROUP_OPERATOR_HEADER(RETURN_TYPE, OPERATOR_TYPE)     \
35                IDISA_ALWAYS_INLINE \
36                RETURN_TYPE & OPERATOR_TYPE(const FixedBindingSet & otherSet); \
37                IDISA_ALWAYS_INLINE \
38                RETURN_TYPE & OPERATOR_TYPE(const BindingSet & otherSet); \
39                IDISA_ALWAYS_INLINE \
40                RETURN_TYPE & OPERATOR_TYPE(const binding_t * otherSet)
41
42#define CONSTRUCT_NEW_GROUP_OPERATOR_HEADER(RETURN_TYPE, OPERATOR_TYPE) \
43                IDISA_ALWAYS_INLINE \
44                RETURN_TYPE OPERATOR_TYPE(const FixedBindingSet & otherSet) const; \
45                IDISA_ALWAYS_INLINE \
46                RETURN_TYPE OPERATOR_TYPE(const BindingSet & otherSet) const; \
47                IDISA_ALWAYS_INLINE \
48                RETURN_TYPE OPERATOR_TYPE(const binding_t * otherSet) const
49
50#define CONSTRUCT_SINGLE_OPERATOR_HEADER(RETURN_TYPE, OPERATOR_TYPE)    \
51                IDISA_ALWAYS_INLINE \
52                RETURN_TYPE & OPERATOR_TYPE(const binding_t id)
53
54#define CONSTRUCT_NEW_SINGLE_OPERATOR_HEADER(RETURN_TYPE, OPERATOR_TYPE)        \
55                IDISA_ALWAYS_INLINE \
56                RETURN_TYPE OPERATOR_TYPE(const binding_t id) const \
57
58/// *********************************************************************************************** ///
59
60class FixedBindingSet
61{
62                template<binding_t, binding_t> friend class BindingSets;
63
64                friend class BindingSet;
65
66                friend class BindingSetIterator;
67        friend class MaskedBindingSetIterator;
68
69                typedef binding_t (*binary_op_t)(const binding_t, const binding_t);
70
71        public:
72
73                ~FixedBindingSet()
74                {
75
76                }
77
78                enum
79                {
80                        BITS_PER_BINDING = sizeof(binding_t) * 8
81                        , LOG_2_BITS_PER_BINDING = CONST_LOG_2(BITS_PER_BINDING)
82                };
83
84                // --------------------------------------------------------------------------------------------------
85
86                IDISA_ALWAYS_INLINE
87                bool operator[](const binding_t id) const;
88
89        IDISA_ALWAYS_INLINE
90        const binding_t * getBitSet() const;
91
92        IDISA_ALWAYS_INLINE
93        size_t size() const;
94
95                // --------------------------------------------------------------------------------------------------
96
97                IDISA_ALWAYS_INLINE
98                FixedBindingSet & operator=(FixedBindingSet & otherSet);
99
100                IDISA_ALWAYS_INLINE
101                FixedBindingSet & operator=(BindingSet & otherSet);
102
103                IDISA_ALWAYS_INLINE
104                FixedBindingSet & operator=(const binding_t val);
105
106                // --------------------------------------------------------------------------------------------------
107
108                IDISA_ALWAYS_INLINE
109                bool operator==(const FixedBindingSet & otherSet) const;
110
111                IDISA_ALWAYS_INLINE
112                bool operator==(const BindingSet & otherSet) const;
113
114                // --------------------------------------------------------------------------------------------------
115
116                IDISA_ALWAYS_INLINE
117                bool mask_and_extract(const FixedBindingSet & otherSet, const binding_t id) const;
118
119                IDISA_ALWAYS_INLINE
120                bool mask_and_extract(const BindingSet & otherSet, const binding_t id) const;
121
122                // --------------------------------------------------------------------------------------------------
123
124                CONSTRUCT_NEW_GROUP_OPERATOR_HEADER(BindingSet, operator^);
125                CONSTRUCT_GROUP_OPERATOR_HEADER(FixedBindingSet, operator^=);
126
127                // --------------------------------------------------------------------------------------------------
128
129                CONSTRUCT_NEW_GROUP_OPERATOR_HEADER(BindingSet, operator&);
130                CONSTRUCT_GROUP_OPERATOR_HEADER(FixedBindingSet, operator&=);
131
132                // --------------------------------------------------------------------------------------------------
133
134                CONSTRUCT_NEW_GROUP_OPERATOR_HEADER(BindingSet, operator+);
135                CONSTRUCT_NEW_SINGLE_OPERATOR_HEADER(BindingSet, operator+);
136                CONSTRUCT_GROUP_OPERATOR_HEADER(FixedBindingSet, operator+=);
137                CONSTRUCT_SINGLE_OPERATOR_HEADER(FixedBindingSet, operator+=);
138
139                // --------------------------------------------------------------------------------------------------
140
141                CONSTRUCT_NEW_GROUP_OPERATOR_HEADER(BindingSet, operator-);
142                CONSTRUCT_GROUP_OPERATOR_HEADER(FixedBindingSet, operator-=);
143                CONSTRUCT_NEW_SINGLE_OPERATOR_HEADER(BindingSet, operator-);
144                CONSTRUCT_SINGLE_OPERATOR_HEADER(FixedBindingSet, operator-=);
145
146                // --------------------------------------------------------------------------------------------------
147
148                IDISA_ALWAYS_INLINE
149                bool isEmpty();
150
151                // --------------------------------------------------------------------------------------------------
152
153                IDISA_ALWAYS_INLINE
154                int first(const FixedBindingSet & mask) const;
155
156                IDISA_ALWAYS_INLINE
157                int first(const BindingSet & mask) const;
158
159                IDISA_ALWAYS_INLINE
160                int first(const binding_t * mask) const;
161
162                #ifdef PRINT_DEBUG_MESSAGE
163                IDISA_ALWAYS_INLINE
164                std::ostream & operator << (std::ostream & out) const
165                {
166                        char delimiter = '{';
167                        char closer = '0';
168
169                        for (binding_t i = 0; i < _capacity; i++)
170                        {
171                                binding_t itr = _bindingSet[i];
172
173                                while (itr)
174                                {
175                                        const binding_t pos =
176                                                (i << FixedBindingSet::LOG_2_BITS_PER_BINDING) | scan_forward_zeroes(itr);
177
178                                        out << delimiter << pos;
179
180                                        delimiter = ',';
181                                        closer = '}';
182
183                                        itr &= (itr - 1);
184                                }
185
186                        }
187                        out << closer;
188
189                        return out;
190                }
191
192                friend std::ostream & operator << (std::ostream & out, const FixedBindingSet & set);
193                #endif
194
195                // --------------------------------------------------------------------------------------------------
196
197                IDISA_ALWAYS_INLINE
198                binding_t capacity() const
199                {
200                        return _capacity << FixedBindingSet::LOG_2_BITS_PER_BINDING;
201                }
202
203        protected:
204
205                FixedBindingSet(binding_t * fixedSet, const binding_t capacity)
206                : _bindingSet(fixedSet)
207                , _capacity(capacity)
208                {
209
210                }
211
212        protected:
213
214                IDISA_ALWAYS_INLINE
215        static bool bittest(const binding_t bitArray, const binding_t pos)
216                {
217                        #if defined(_MSC_VER) && defined(_M_X64)
218                return _bittest64((__int64*)&bitArray, pos);
219                        #elif defined(_MSC_VER) && defined(_M_X86)
220                return _bittest(&bitArray, pos);
221                        #else
222                // this ought to generate the bittest (bt) instruction if n
223                const binding_t ONE = 1;
224                return bitArray & (ONE << (pos & (BITS_PER_BINDING - 1)));
225            #endif
226                }
227
228                IDISA_ALWAYS_INLINE
229                static binding_t binary_xor(const binding_t a, const binding_t b)
230                {
231                        return a ^ b;
232                }
233
234                IDISA_ALWAYS_INLINE
235                static binding_t binary_and(const binding_t a, const binding_t b)
236                {
237                        return a & b;
238                }
239
240                IDISA_ALWAYS_INLINE
241                static binding_t binary_andc(const binding_t a, const binding_t b)
242                {
243                        return a & ~b;
244                }
245
246                IDISA_ALWAYS_INLINE
247                static binding_t binary_or(const binding_t a, const binding_t b)
248                {
249                        return a | b;
250                }
251
252                template<binary_op_t binary_op>
253                IDISA_ALWAYS_INLINE
254                void do_operation(const binding_t value)
255                {
256                        const binding_t idx = (value >> LOG_2_BITS_PER_BINDING);
257                        const binding_t pos = (value & (BITS_PER_BINDING - 1));
258                        const binding_t one = 1; //needed to prevent gcc from thinking this is a 32-bit int
259                        const binding_t val = (one << pos);
260                        _bindingSet[idx] = binary_op(_bindingSet[idx], val);
261                }
262
263                template<binary_op_t binary_op>
264                IDISA_ALWAYS_INLINE
265                void do_operation(const binding_t * otherSet)
266                {
267                        do_operation<binary_op>(otherSet, this->_bindingSet);
268                }
269
270                template<binary_op_t binary_op>
271                IDISA_ALWAYS_INLINE
272                void do_operation(const binding_t value, binding_t * result) const
273                {
274                        const binding_t idx = (value >> LOG_2_BITS_PER_BINDING);
275                        const binding_t pos = (value & (BITS_PER_BINDING - 1));
276                        const binding_t one = 1; //needed to prevent gcc from thinking this is a 32-bit int
277                        const binding_t val = (one << pos);
278
279                        for (binding_t i = 0; unlikely(i < idx); i++)
280                        {
281                                result[i] = _bindingSet[i];
282                        }
283                        result[idx] = binary_op(_bindingSet[idx], val);
284                        for (binding_t i = idx + 1; unlikely(i < _capacity); i++)
285                        {
286                                result[i] = _bindingSet[i];
287                        }
288                }
289
290                template<binary_op_t binary_op>
291                IDISA_ALWAYS_INLINE
292                void do_operation(const binding_t * otherSet, binding_t * result) const
293                {
294                        result[0] = binary_op(_bindingSet[0], otherSet[0]);
295                        for (binding_t i = 1; unlikely(i < _capacity); i++)
296                        {
297                                result[i] = binary_op(_bindingSet[i], otherSet[i]);
298                        }
299                }
300
301                IDISA_ALWAYS_INLINE
302                void assign(binding_t * set, const binding_t capacity)
303                {
304                        _bindingSet = set;
305                        _capacity = capacity;
306                }
307
308        protected:
309
310                binding_t *                                                                                     _bindingSet;
311        size_t                                              _capacity;
312};
313
314class BindingSet : public FixedBindingSet
315{
316                template<binding_t, binding_t> friend class BindingSets;
317
318                friend class FixedBindingSet;
319
320                friend class BindingSetIterator;
321
322        public:
323
324                BindingSet()
325                : FixedBindingSet(&_internalSet, 1)
326                , _internalSet(0)
327                {
328
329                }
330
331                BindingSet(const BindingSet & bindingSet)
332                : FixedBindingSet(0, bindingSet._capacity)
333                , _internalSet(0)
334                {
335                        if (_capacity == 1)
336                        {
337                                _internalSet = bindingSet._internalSet;
338                                _bindingSet = &_internalSet;
339                        }
340                        else
341                        {
342                                _bindingSet = Array<binding_t>::allocate(_capacity);
343                                Array<binding_t>::copy(bindingSet._bindingSet, _bindingSet, _capacity);
344                        }
345                }
346
347                IDISA_ALWAYS_INLINE
348                BindingSet & operator=(const BindingSet & otherSet)
349                {
350                        if (unlikely(_capacity < otherSet._capacity))
351                        {
352                                deallocateIfNecessary();
353                                _capacity = otherSet._capacity;
354                                _bindingSet = Array<binding_t>::allocate(otherSet._capacity);
355                        }
356                        Array<binding_t>::copy(otherSet._bindingSet, _bindingSet, otherSet._capacity);
357                        Array<binding_t>::memzero(&_bindingSet[otherSet._capacity], _capacity - otherSet._capacity);
358                        return *this;
359                }
360
361        IDISA_ALWAYS_INLINE
362        BindingSet & operator=(const binding_t val);
363
364                BindingSet(const binding_t capacity)
365                : FixedBindingSet
366                (
367                        likely(capacity == 1) ? &_internalSet : Array<binding_t>::allocate(capacity)
368                        , capacity
369                )
370                , _internalSet(0)
371                {
372                        if (unlikely(capacity != 1))
373                        {
374                                Array<binding_t>::memzero(this->_bindingSet, capacity);
375                        }
376                }
377
378                ~BindingSet()
379                {
380                        deallocateIfNecessary();
381                }
382
383                enum
384                {
385                        BITS_PER_BINDING = sizeof(binding_t) * 8
386                        , LOG_2_BITS_PER_BINDING = CONST_LOG_2(BITS_PER_BINDING)
387                };
388
389                // --------------------------------------------------------------------------------------------------
390
391                IDISA_ALWAYS_INLINE
392                void expand(const size_t minimum)
393                {
394                        DEBUG_MESSAGE("expand(" << minimum << ')')
395
396                        const binding_t capacity = _capacity;
397                        //how many binding_t blocks are needed?
398                        const binding_t newCapacity =
399                                max
400                                (
401                                        capacity << 1
402                                        , (minimum + FixedBindingSet::BITS_PER_BINDING - 1) >> FixedBindingSet::LOG_2_BITS_PER_BINDING
403                                );
404
405                        binding_t * newBindingSet = Array<binding_t>::allocate(newCapacity);
406
407                        Array<binding_t>::copy(&_bindingSet[0], &newBindingSet[0], capacity);
408                        Array<binding_t>::memzero(&newBindingSet[capacity], newCapacity - capacity);
409
410                        deallocateIfNecessary();
411
412                        this->_bindingSet = newBindingSet;
413                        this->_capacity = newCapacity;
414                }
415
416        private:
417
418                IDISA_ALWAYS_INLINE
419                void deallocateIfNecessary()
420                {
421                        if (this->_bindingSet != &_internalSet)
422                        {
423                                Array<binding_t>::deallocate(this->_bindingSet);
424                                this->_bindingSet = &_internalSet;
425                        }
426                }
427
428        private:
429
430                binding_t                                                                                       _internalSet;
431};
432
433// --------------------------------------------------------------------------------------------------
434
435bool FixedBindingSet::operator[](const binding_t id) const
436{
437    return bittest(_bindingSet[id >> LOG_2_BITS_PER_BINDING], id);
438}
439
440const binding_t * FixedBindingSet::getBitSet() const
441{
442    return &_bindingSet[0];
443}
444
445size_t FixedBindingSet::size() const
446{
447    return _capacity;
448}
449
450// --------------------------------------------------------------------------------------------------
451
452FixedBindingSet & FixedBindingSet::operator=(FixedBindingSet & otherSet)
453{
454        assign(otherSet._bindingSet, otherSet._capacity);
455        return *this;
456}
457
458FixedBindingSet & FixedBindingSet::operator=(BindingSet & otherSet)
459{
460        assign(otherSet._bindingSet, otherSet._capacity);
461        return *this;
462}
463
464FixedBindingSet & FixedBindingSet::operator=(const binding_t val)
465{
466    if (CONST_EXPR(val == 0))
467    {
468        Array<binding_t>::memzero(_bindingSet, _capacity);
469    }
470    else
471    {
472        Array<binding_t>::set(_bindingSet, val, _capacity);
473    }
474        return *this;
475}
476
477BindingSet & BindingSet::operator=(const binding_t val)
478{
479    if (CONST_EXPR(val == 0))
480    {
481        Array<binding_t>::memzero(_bindingSet, _capacity);
482    }
483    else
484    {
485        Array<binding_t>::set(_bindingSet, val, _capacity);
486    }
487    return *this;
488}
489
490
491// --------------------------------------------------------------------------------------------------
492
493bool FixedBindingSet::operator==(const FixedBindingSet & otherSet) const
494{
495        if (unlikely(_capacity != otherSet._capacity)) return 0;
496
497        binding_t diff = _bindingSet[0] ^ otherSet._bindingSet[0];
498        for (binding_t i = 1; unlikely(i < _capacity); i++)
499        {
500                diff |= _bindingSet[i] ^ otherSet._bindingSet[i];
501        }
502        return (diff == 0);
503}
504
505bool FixedBindingSet::operator==(const BindingSet & otherSet) const
506{
507        if (unlikely(_capacity != otherSet._capacity)) return 0;
508
509        binding_t diff = _bindingSet[0] ^ otherSet._bindingSet[0];
510        for (binding_t i = 1; unlikely(i < _capacity); i++)
511        {
512                diff |= _bindingSet[i] ^ otherSet._bindingSet[i];
513        }
514        return (diff == 0);
515}
516
517// --------------------------------------------------------------------------------------------------
518
519bool FixedBindingSet::mask_and_extract(const FixedBindingSet & otherSet, const binding_t id) const
520{
521        const binding_t idx = id >> LOG_2_BITS_PER_BINDING;
522        ASSUME(idx == 0);
523        const binding_t maskedSet = _bindingSet[idx] & otherSet._bindingSet[idx];
524    return bittest(maskedSet, id);
525}
526
527bool FixedBindingSet::mask_and_extract(const BindingSet & otherSet, const binding_t id) const
528{
529        const binding_t idx = id >> LOG_2_BITS_PER_BINDING;
530        ASSUME(idx == 0);
531        const binding_t maskedSet = _bindingSet[idx] & otherSet._bindingSet[idx];
532    return bittest(maskedSet, id);
533}
534
535// --------------------------------------------------------------------------------------------------
536
537#define CONSTRUCT_GROUP_OPERATOR_FUNCTION(RETURN_TYPE, OPERATOR_TYPE, OPERATOR_FUNCTION)        \
538        RETURN_TYPE & RETURN_TYPE::OPERATOR_TYPE(const FixedBindingSet & otherSet) \
539        { \
540                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet._bindingSet); \
541                return *this; \
542        } \
543        RETURN_TYPE & RETURN_TYPE::OPERATOR_TYPE(const BindingSet & otherSet) \
544        { \
545                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet._bindingSet); \
546                return *this; \
547        } \
548        RETURN_TYPE & RETURN_TYPE::OPERATOR_TYPE(const binding_t * otherSet) \
549        { \
550                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet); \
551                return *this; \
552        }
553
554#define CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION(RETURN_TYPE, OPERATOR_TYPE, OPERATOR_FUNCTION)    \
555        RETURN_TYPE FixedBindingSet::OPERATOR_TYPE(const FixedBindingSet & otherSet) const \
556        { \
557                BindingSet result(_capacity); \
558                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet._bindingSet, result._bindingSet); \
559                return result; \
560        } \
561        RETURN_TYPE FixedBindingSet::OPERATOR_TYPE(const BindingSet & otherSet) const \
562        { \
563                BindingSet result(_capacity); \
564                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet._bindingSet, result._bindingSet); \
565                return result; \
566        } \
567        RETURN_TYPE FixedBindingSet::OPERATOR_TYPE(const binding_t * otherSet) const \
568        { \
569                BindingSet result(_capacity); \
570                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(otherSet, result._bindingSet); \
571                return result; \
572        }
573
574#define CONSTRUCT_SINGLE_OPERATOR_FUNCTION(RETURN_TYPE, OPERATOR_TYPE, OPERATOR_FUNCTION)       \
575        RETURN_TYPE & FixedBindingSet::OPERATOR_TYPE(const binding_t id) \
576        { \
577                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(id); \
578                return *this; \
579        }
580
581#define CONSTRUCT_NEW_SINGLE_OPERATOR_FUNCTION(RETURN_TYPE, OPERATOR_TYPE, OPERATOR_FUNCTION)   \
582        RETURN_TYPE FixedBindingSet::OPERATOR_TYPE(const binding_t id) const \
583        { \
584                RETURN_TYPE result(_capacity); \
585                do_operation<FixedBindingSet::OPERATOR_FUNCTION>(id, result._bindingSet); \
586                return result; \
587        }
588
589// --------------------------------------------------------------------------------------------------
590
591CONSTRUCT_GROUP_OPERATOR_FUNCTION(FixedBindingSet, operator^=, binary_xor)
592CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION(BindingSet, operator^, binary_xor)
593
594// --------------------------------------------------------------------------------------------------
595
596CONSTRUCT_GROUP_OPERATOR_FUNCTION(FixedBindingSet, operator&=, binary_and)
597CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION(BindingSet, operator&, binary_and)
598
599// --------------------------------------------------------------------------------------------------
600
601CONSTRUCT_SINGLE_OPERATOR_FUNCTION(FixedBindingSet, operator+=, binary_or)
602CONSTRUCT_GROUP_OPERATOR_FUNCTION(FixedBindingSet, operator+=, binary_or)
603CONSTRUCT_NEW_SINGLE_OPERATOR_FUNCTION(BindingSet, operator+, binary_or)
604CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION(BindingSet, operator+, binary_or)
605
606// --------------------------------------------------------------------------------------------------
607
608CONSTRUCT_SINGLE_OPERATOR_FUNCTION(FixedBindingSet, operator-=, binary_andc)
609CONSTRUCT_GROUP_OPERATOR_FUNCTION(FixedBindingSet, operator-=, binary_andc)
610CONSTRUCT_NEW_SINGLE_OPERATOR_FUNCTION(BindingSet, operator-, binary_andc)
611CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION(BindingSet, operator-, binary_andc)
612
613// --------------------------------------------------------------------------------------------------
614
615IDISA_ALWAYS_INLINE
616bool FixedBindingSet::isEmpty()
617{
618        register binding_t bits = _bindingSet[0];
619        for (binding_t i = 1; unlikely(i < _capacity); i++)
620        {
621                bits |= _bindingSet[i];
622        }
623        return (bits == 0);
624}
625
626// --------------------------------------------------------------------------------------------------
627
628IDISA_ALWAYS_INLINE
629int FixedBindingSet::first(const FixedBindingSet & mask) const
630{
631        return first(mask._bindingSet);
632}
633
634IDISA_ALWAYS_INLINE
635int FixedBindingSet::first(const BindingSet & mask) const
636{
637        return first(mask._bindingSet);
638}
639
640IDISA_ALWAYS_INLINE
641int FixedBindingSet::first(const binding_t * mask) const
642{
643        register binding_t t;
644        register binding_t i = 0;
645        register binding_t count = _capacity;
646
647        do
648        {
649                t = (_bindingSet[i] & mask[i]);
650
651                if (t)
652                {
653                        return (i << LOG_2_BITS_PER_BINDING) | scan_forward_zeroes(t);
654                }
655                i++;
656        }
657        while (--count != 0);
658
659        return -1;
660}
661
662/// *********************************************************************************************** ///
663
664template<binding_t initialSetCount, binding_t initialBitCapacity = FixedBindingSet::BITS_PER_BINDING>
665class BindingSets
666{
667                friend class BindingSetIterator;
668
669                enum
670                {
671                        INITIAL_BINDING_CAPACITY =
672                                (initialBitCapacity + FixedBindingSet::BITS_PER_BINDING - 1) / FixedBindingSet::BITS_PER_BINDING
673
674                        , LOG_2_INITIAL_BINDING_CAPACITY =
675                                CONST_LOG_2(INITIAL_BINDING_CAPACITY)
676                };
677
678        public:
679
680                BindingSets()
681                : _bindingSets(_internalSets)
682                , _log2BitCapacity(LOG_2_INITIAL_BINDING_CAPACITY)
683                , _setCapacity(initialSetCount)
684                {
685                        Array<binding_t>::memzero(_internalSets, initialSetCount * INITIAL_BINDING_CAPACITY);
686                }
687
688                ~BindingSets()
689                {
690                        deallocateIfNecessary();
691                }
692
693                IDISA_ALWAYS_INLINE
694                binding_t * get(const binding_t i)
695                {
696                        return &_bindingSets[i << _log2BitCapacity];
697                }
698
699                IDISA_ALWAYS_INLINE
700                const binding_t * get(const binding_t i) const
701                {
702                        return &_bindingSets[i << _log2BitCapacity];
703                }
704
705
706                IDISA_ALWAYS_INLINE
707                void set(const binding_t i, BindingSet & otherSet)
708                {
709                        binding_t * _bindingSet = get(i);
710                        binding_t _capacity = 1 << _log2BitCapacity;
711
712                        Array<binding_t>::copy(otherSet._bindingSet, _bindingSet, otherSet._capacity);
713                        Array<binding_t>::memzero(&_bindingSet[otherSet._capacity], _capacity - otherSet._capacity);
714                }
715
716                IDISA_ALWAYS_INLINE
717                FixedBindingSet operator[](const binding_t i)
718                {
719                        return FixedBindingSet(&_bindingSets[i << _log2BitCapacity], (binding_t)(1) << _log2BitCapacity);
720                }
721
722                IDISA_ALWAYS_INLINE
723                const FixedBindingSet operator[](const binding_t i) const
724                {
725                        return FixedBindingSet(&_bindingSets[i << _log2BitCapacity], (binding_t)(1) << _log2BitCapacity);
726                }
727
728                IDISA_ALWAYS_INLINE
729                void increaseBitCapacity(const size_t minimum = 0)
730                {
731                        DEBUG_MESSAGE("BindingSets::increaseBitCapacity(" << minimum << ')')
732
733                        //how many binding_t blocks do we have currently?
734                        const binding_t bitCapacity = this->bitCapacity() >> FixedBindingSet::LOG_2_BITS_PER_BINDING;
735                        const binding_t setCapacity = this->setCapacity();
736
737                        //how many binding_t blocks are needed?
738                        const binding_t newBitCapacity =
739                                max
740                                (
741                                        bitCapacity * 2
742                                        , (minimum + FixedBindingSet::BITS_PER_BINDING - 1) >> FixedBindingSet::LOG_2_BITS_PER_BINDING
743                                );
744
745                        const binding_t capacity = bitCapacity * setCapacity;
746                        const binding_t newCapacity = newBitCapacity * setCapacity;
747
748                        binding_t * newBindingSet = Array<binding_t>::allocate(newCapacity);
749
750                        // copy the old data over into the expanded array into the appropriate positions
751                        binding_t i = 0;
752                        binding_t j = 0;
753
754                        do
755                        {
756                                Array<binding_t>::copy(&_bindingSets[i], &newBindingSet[j], bitCapacity);
757                                Array<binding_t>::memzero(&newBindingSet[j + bitCapacity], newBitCapacity - bitCapacity);
758                                i += bitCapacity;
759                                j += newBitCapacity;
760                        }
761                        while (i < capacity);
762
763                        // set the new array in place and delete the old one if needbe
764                        deallocateIfNecessary();
765                        _bindingSets = newBindingSet;
766                        _log2BitCapacity = scan_forward_zeroes(newBitCapacity);
767                }
768
769                IDISA_ALWAYS_INLINE
770                void increaseSetCapacity(const size_t minumum = 0)
771                {
772                        DEBUG_MESSAGE("BindingSets::increaseSetCapacity(" << minumum << ')')
773
774                        //how many binding_t blocks do we have currently?
775                        const binding_t bitCapacity = this->bitCapacity() >> FixedBindingSet::LOG_2_BITS_PER_BINDING;
776                        const binding_t setCapacity = this->setCapacity();
777
778                        //how many sets are needed?
779                        const binding_t newSetCapacity =
780                                max
781                                (
782                                        setCapacity * 2
783                                        , minumum + (initialSetCount - minumum % initialSetCount)
784                                );
785
786                        const binding_t capacity = bitCapacity * setCapacity;
787                        const binding_t newCapacity = bitCapacity * newSetCapacity;
788
789                        binding_t * newBindingSet = Array<binding_t>::allocate(newCapacity);
790
791                        // copy the old data over into the expanded array into the appropriate positions
792                        Array<binding_t>::copy(&_bindingSets[0], &newBindingSet[0], capacity);
793                        Array<binding_t>::memzero(&newBindingSet[capacity], newCapacity - capacity);
794
795                        // set the new array in place and delete the old one if needbe
796                        deallocateIfNecessary();
797                        _bindingSets = newBindingSet;
798                        _setCapacity = newSetCapacity;
799                }
800
801
802//              IDISA_ALWAYS_INLINE
803//              void expand(const size_t minimumCapacity)
804//              {
805//                      DEBUG_MESSAGE("BindingSets::expand(" << minimumCapacity << ')')
806
807//                      // construct a new array with double the capacity for each set,
808//                      // and double the number of sets (i.e., 4x the current capacity).
809
810//                      // construct a new array with double the capacity for each set,
811//                      // and double the number of sets (i.e., 4x the current capacity).
812
813//                      const binding_t newCapacity = (capacity() * 4);
814//                      binding_t * newBindingSet = Array<binding_t>::allocate(newCapacity);
815
816//                      // copy the old data over into the expanded array into the appropriate positions
817//                      binding_t origOffset = 0;
818//                      const binding_t sizeOfBindingSet = (1 << _log2SizeOfBindingSet);
819
820//                      binding_t newOffset = 0;
821//                      const binding_t sizeOfNewBindingSet = (sizeOfBindingSet << 1);
822
823//                      do
824//                      {
825//                              binding_t i = 0;
826
827//                              for (; i < sizeOfBindingSet; i++)
828//                              {
829//                                      newBindingSet[newOffset + i] = _bindingSets[origOffset + i];
830//                              }
831//                              origOffset += sizeOfBindingSet;
832
833//                              for (; i < sizeOfNewBindingSet; i++)
834//                              {
835//                                      newBindingSet[newOffset + i] = 0;
836//                              }
837//                              newOffset += sizeOfNewBindingSet;
838//                      }
839//                      while (origOffset < capacity());
840
841//                      // set the new array in place and delete the old one if needbe
842//                      deallocateIfNecessary();
843//                      _bindingSets = newBindingSet;
844//                      _log2SizeOfBindingSet++;
845//              }
846
847                IDISA_ALWAYS_INLINE
848                binding_t bitCapacity() const
849                {
850                        return (1 << _log2BitCapacity) << FixedBindingSet::LOG_2_BITS_PER_BINDING;
851                }
852
853                IDISA_ALWAYS_INLINE
854                binding_t setCapacity() const
855                {
856                        return _setCapacity;
857                }
858
859        private:
860
861                IDISA_ALWAYS_INLINE
862                void deallocateIfNecessary()
863                {
864                        if (_bindingSets != (binding_t*)_internalSets)
865                        {
866                                Array<binding_t>::deallocate(_bindingSets);
867                                _bindingSets = (binding_t*)_internalSets;
868                        }
869                }
870
871        private:
872
873                binding_t *                                                                                                             _bindingSets;
874                binding_t                                                                                                               _log2BitCapacity;
875                binding_t                                                                                                               _setCapacity;
876                binding_t                                                                                                               _internalSets[initialSetCount * INITIAL_BINDING_CAPACITY];
877};
878
879
880/// *********************************************************************************************** ///
881class BindingSetIterator
882{
883        public:
884
885                BindingSetIterator(const FixedBindingSet & set)
886        : fBindingSet(set._bindingSet)
887        , fCapacity(set._capacity)
888        , fIndex(0)
889        , fIterator(fBindingSet[0])
890                {
891
892                }
893
894                BindingSetIterator(const binding_t * set, const binding_t bitCapacity)
895        : fBindingSet(set)
896        , fCapacity(bitCapacity >> FixedBindingSet::LOG_2_BITS_PER_BINDING)
897        , fIndex(0)
898        , fIterator(fBindingSet[0])
899                {
900
901                }
902
903
904                IDISA_ALWAYS_INLINE
905                bool first()
906                {
907            fIndex = 0;
908            fIterator = fBindingSet[0];
909                        return next();
910                }
911
912                IDISA_ALWAYS_INLINE
913                bool next()
914                {
915            while (unlikely(fIterator == 0))
916                        {
917                if (unlikely(++fIndex >= fCapacity))
918                                {
919                                        return 0;
920                                }
921                fIterator = fBindingSet[fIndex];
922                        }
923            fPos = (fIndex << FixedBindingSet::LOG_2_BITS_PER_BINDING) | scan_forward_zeroes(fIterator);
924
925            fIterator &= (fIterator - 1);
926
927                        return 1;
928                }
929
930                IDISA_ALWAYS_INLINE
931        int pos() const { return fPos; }
932
933        private:
934
935        const binding_t *                               fBindingSet;
936        const binding_t                                 fCapacity;
937        binding_t                                               fIndex;
938        binding_t                                               fIterator;
939        binding_t                                               fPos;
940};
941
942
943class MaskedBindingSetIterator
944{
945    public:
946
947        MaskedBindingSetIterator(const FixedBindingSet & set, const FixedBindingSet & mask, const bool complement = true)
948        : fBindingSet(set._bindingSet)
949        , fMaskSet(mask._bindingSet)
950        , fCapacity(min(set._capacity, mask._capacity))
951        , fIndex(0)
952        , fIterator(getIterator(0))
953        , fComplement(complement)
954        {
955
956        }
957
958        IDISA_ALWAYS_INLINE
959        bool first()
960        {
961            fIndex = 0;
962            fIterator = getIterator(0);
963            return next();
964        }
965
966        IDISA_ALWAYS_INLINE
967        bool next()
968        {
969            while (unlikely(fIterator == 0))
970            {
971                if (unlikely(++fIndex >= fCapacity))
972                {
973                    return 0;
974                }
975                fIterator = getIterator(fIndex);
976            }
977            fPos = (fIndex << FixedBindingSet::LOG_2_BITS_PER_BINDING) | scan_forward_zeroes(fIterator);
978
979            fIterator &= (fIterator - 1);
980
981            return 1;
982        }
983
984        IDISA_ALWAYS_INLINE
985        int pos() const { return fPos; }
986
987    private:
988
989        IDISA_ALWAYS_INLINE
990        binding_t getIterator(size_t index) const
991        {
992            return fBindingSet[index] & (fComplement ? ~fMaskSet[index] : fMaskSet[index]);
993        }
994
995
996    private:
997
998        const binding_t *                               fBindingSet;
999        const binding_t *                               fMaskSet;
1000        const binding_t                                 fCapacity;
1001        binding_t                                               fIndex;
1002        binding_t                                               fIterator;
1003        binding_t                                               fPos;
1004        const bool                      fComplement;
1005};
1006
1007/// *********************************************************************************************** ///
1008
1009#ifdef PRINT_DEBUG_MESSAGE
1010inline std::ostream & operator << (std::ostream & out, const FixedBindingSet & set)
1011{
1012        char delimiter = '{';
1013        char closer = '0';
1014
1015        BindingSetIterator itr(set);
1016
1017        while (itr.next())
1018        {
1019                out << delimiter << itr.pos();
1020                delimiter = ',';
1021                closer = '}';
1022        }
1023        out << closer;
1024
1025        return out;
1026}
1027#endif
1028
1029/// *********************************************************************************************** ///
1030
1031#undef CONSTRUCT_NEW_SINGLE_OPERATOR_FUNCTION
1032#undef CONSTRUCT_SINGLE_OPERATOR_FUNCTION
1033#undef CONSTRUCT_NEW_SINGLE_OPERATOR_HEADER
1034#undef CONSTRUCT_SINGLE_OPERATOR_HEADER
1035#undef CONSTRUCT_GROUP_OPERATOR_FUNCTION
1036#undef CONSTRUCT_GROUP_OPERATOR_HEADER
1037#undef CONSTRUCT_NEW_GROUP_OPERATOR_FUNCTION
1038#undef CONSTRUCT_NEW_GROUP_OPERATOR_HEADER
1039
1040#endif // XMLNAMESPACEBINDINGTABLE_HPP
Note: See TracBrowser for help on using the repository browser.