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

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

Initial check-in of icXML 0.8 source files

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