source: icXML/icXML-0.95/src/icxmlc/XMLNamespaceBindingSet.hpp @ 3602

Last change on this file since 3602 was 3602, checked in by cameron, 5 years ago

Namespace bug fix for icXML-0.95

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