source: icXML/icXML-devel/src/icxmlc/XMLSymbolTable.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: 21.0 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: XMLSymbolTable.hpp 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#if !defined(XERCESC_INCLUDE_GUARD_XML_SYMBOL_TABLE_HPP)
14#define XERCESC_INCLUDE_GUARD_XML_SYMBOL_TABLE_HPP
15
16#include <icxmlc/stringpool.h>
17#include <icxmlc/XMLSymbol.hpp>
18#include <icxmlc/HashTable.hpp>
19#include <icxmlc/XMLStringU.hpp>
20#include <icxmlc/PopCounter.hpp>
21#include <icxmlc/XMLStreamIterator.hpp>
22#include <icxmlc/XMLReferenceTable.hpp>
23#include <xercesc/util/XMLString.hpp>
24#include <xercesc/util/TransService.hpp>
25#include <icxmlc/XMLConfig.hpp>
26
27// TODO: split the hash table and data portion of the symbol and reference tables so that the symbols themselves are localized
28// in the XMLParser and the content vs. att val content is stored in seperate hash tables.
29
30XERCES_CPP_NAMESPACE_BEGIN
31
32class XMLScanner;
33class XMLTranscoder;
34class XMLNamespaceResolver;
35
36/* -------------------------------------------------------------------------------------------- */
37
38class XMLSymbolTable
39{
40        template<class XMLScanner> friend class XMLParserImpl;
41
42public:
43
44        XMLSymbolTable
45        (
46                XMLTranscoder *                         transcoder
47        , XMLScanner *              scanner
48                , XMLNamespaceResolver *        namespaceResolver
49                , MemoryManager * const         manager       
50        )
51        : fSymbolTable()
52        , fSymbolPool(manager)
53        , fNamespaceResolver(namespaceResolver)
54        , fTranscoder(transcoder)
55    , fScanner(scanner)
56        , fStartPosition(0)
57        , fResumeSymbol(0)
58        , fMemoryManager(manager)
59        {
60
61        }
62
63        ~XMLSymbolTable()
64        {
65                fNamespaceResolver = 0;
66        }
67
68        XMLSymbol * operator[](const gid_t gid)
69        {
70                return fSymbolTable[gid];
71        }
72
73        const XMLSymbol * operator[](const gid_t gid) const
74        {
75                return fSymbolTable[gid];
76        }
77
78
79        template <unsigned int CodeUnitSize>
80        IDISA_ALWAYS_INLINE
81        unsigned int resolve
82        (
83                const BitBlock *                        symbolStream
84                , const XMLByte * const         source
85                , const size_t                          index
86                , const size_t                          count
87                , unsigned int                          symbolCount
88                , SymbolArray &                         symbolArray
89                , const bool                            internal = 0
90        );
91
92        template <unsigned int CodeUnitSize>
93        IDISA_ALWAYS_INLINE
94        unsigned int resolve
95        (
96                const BitBlock *                                symbolStream
97                , const XMLByte * const                 source
98                , const size_t                                  index
99                , const size_t                                  count
100                , unsigned int                                  symbolCount
101                , SymbolArray &                                 symbolArray
102                , const XMLComplexRefArray &    refArray
103                , const XMLSize_t                               refCount
104                , const XMLSize_t                               refSymbolCount
105                , const XMLReferenceTable &             referenceTable
106                , const bool                                    internal = 0
107        );
108
109        void setTranscoder(XMLTranscoder * transcoder)
110        {
111                fTranscoder = transcoder;
112        }
113
114        XMLTranscoder * getTranscoder() const
115        {
116                return fTranscoder;
117        }
118
119protected:
120
121        /**
122         * get the entry with the matching symbol if it exists within this
123         * hash table
124         * @param id the correspondence id
125         * @return the symbol or NULL
126        */     
127    IDISA_ALWAYS_INLINE
128        gid_t   
129        addOrFind
130        (
131                const XMLByte                   * const rawSymbol
132                , const XMLSize_t                               rawLength
133        );
134
135    IDISA_ALWAYS_INLINE
136        gid_t
137        addOrFindInternal
138        (
139                const XMLCh                             * const key
140                , const XMLSize_t                               length
141        );
142
143    gid_t
144    add
145    (
146        const XMLByte                   * const rawSymbol
147        , const XMLSize_t                               rawLength
148    );
149
150    gid_t
151    addInternal
152    (
153        const XMLCh                             * const key
154        , const XMLSize_t                               length
155        , const XMLByte         * const unencodedKey
156        , const XMLSize_t               unencodedLength
157    );
158
159public:
160
161        int                                                                                                                                             fStartPosition;
162        bool                                                                                                                                    fResumeSymbol;
163
164private:
165
166        HashTable<XMLSymbol, XMLByte, INITIAL_SYMBOL_TABLE_CAPACITY>                    fSymbolTable;
167        StringPool<XMLByte, INITIAL_SYMBOL_TABLE_STRING_POOL_SIZE>                              fSymbolPool;
168        XMLNamespaceResolver *                                                                                                  fNamespaceResolver;
169        XMLTranscoder *                                                                                                                 fTranscoder;
170    XMLScanner *                                                            fScanner;
171        MemoryManager * const                                                                                                   fMemoryManager;
172};
173
174/// ------------------------------------------------------------------------------------------------------------------------------------
175
176template <unsigned int CodeUnitSize>
177unsigned int XMLSymbolTable::resolve
178(
179    const BitBlock *                    symbolStream
180    , const XMLByte * const             source
181    , const size_t                              index
182    , const size_t                              count
183    , unsigned int                              symbolCount
184    , SymbolArray &                             symbolArray
185    , const bool                                internal
186)
187{
188    XMLStreamIterator symbolItr
189    (
190        symbolStream
191        , CONST_LOG_2(CodeUnitSize)
192        , index
193        , count
194    );
195
196    #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
197    size_t offsetIndex = 0;
198    XMLByte DATA_BLOCK[66] = {'|', 0};
199    enum
200    {
201        DATA_BLOCK_SIZE = (BLOCK_SIZE * CodeUnitSize)
202        , LOG_2_DATA_BLOCK_SIZE = CONST_LOG_2(DATA_BLOCK_SIZE)
203    };
204    #endif
205
206    int startPosition = fStartPosition;
207    int endPosition;
208    bool resumeSymbol = 0;
209
210    // would assigned gotos be more efficient here? they only work in gcc unfortunetly.
211    switch (fResumeSymbol)
212    {
213        case 0: while (unlikely(symbolItr.next(startPosition)))
214                {
215        case 1:     if (unlikely(!symbolItr.next(endPosition)))
216                    {
217                        resumeSymbol = 1;
218                        break;
219                    }
220
221                    #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
222                    for (; offsetIndex <= (endPosition >> LOG_2_DATA_BLOCK_SIZE); offsetIndex++)
223                    {
224                        for (unsigned int scanOffset = 0; scanOffset < DATA_BLOCK_SIZE; scanOffset += 64)
225                        {
226                            const size_t offset = (offsetIndex << LOG_2_DATA_BLOCK_SIZE) | scanOffset;
227                            const XMLByte * byteStream = &source[offset - 1];
228
229                            for (unsigned int i = 1; i <= 64; i++)
230                            {
231                                XMLByte c = byteStream[i];
232                                if (c < 32) c = ' ';
233                                DATA_BLOCK[i] = c;
234                            }
235
236                            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
237                            DEBUG_SYMBOL_MESSAGE(
238                                 XERCES_STD_QUALIFIER setw(5) <<
239                                 (offset) <<
240                                 XERCES_STD_QUALIFIER setw(0) <<
241                                 DATA_BLOCK );
242                            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
243                        }
244                    }
245                    #endif
246
247                    gid_t gid;
248                    if (internal)
249                    {
250                        gid = addOrFindInternal(reinterpret_cast<const XMLCh*>(&source[startPosition]), (endPosition - startPosition) / sizeof(XMLCh));
251                    }
252                    else
253                    {
254                        gid = addOrFind(&source[startPosition], endPosition - startPosition);
255                    }
256
257                    DEBUG_SYMBOL_MESSAGE
258                    (
259                       "SYMBOL: " << fSymbolTable[gid]
260                        << " @ {" << startPosition << ',' << endPosition << '}'
261                        << " gid=" << gid
262                        << " idx=" << symbolCount
263                    );
264
265                    symbolArray[symbolCount++] = gid;
266
267                }
268    }
269
270    #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
271    for (; offsetIndex < count; offsetIndex++)
272    {
273        for (unsigned int scanOffset = 0; scanOffset < DATA_BLOCK_SIZE; scanOffset += 64)
274        {
275            const size_t offset = (offsetIndex << LOG_2_DATA_BLOCK_SIZE) | scanOffset;
276            const XMLByte * byteStream = &source[offset - 1];
277
278            for (unsigned int i = 1; i <= 64; i++)
279            {
280                XMLByte c = byteStream[i];
281                if (c < 32) c = ' ';
282                DATA_BLOCK[i] = c;
283            }
284
285            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
286            DEBUG_SYMBOL_MESSAGE(
287                 XERCES_STD_QUALIFIER setw(5) <<
288                 (offset) <<
289                 XERCES_STD_QUALIFIER setw(0) <<
290                 DATA_BLOCK );
291            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
292        }
293    }
294    #endif
295
296    fResumeSymbol = resumeSymbol;
297    fStartPosition = startPosition;
298
299    return symbolCount;
300}
301
302template <unsigned int CodeUnitSize>
303unsigned int XMLSymbolTable::resolve
304(
305    const BitBlock *                            symbolStream
306    , const XMLByte * const                     source
307    , const size_t                                      index
308    , const size_t                                      count
309    , unsigned int                                      symbolCount
310    , SymbolArray &                                     symbolArray
311    , const XMLComplexRefArray &        refArray
312    , const XMLSize_t                           refCount
313    , const XMLSize_t                           refSymbolCount
314    , const XMLReferenceTable &         referenceTable
315    , const bool                                        internal
316)
317{
318
319    PopCounter<3> symbolCounter;
320    for (size_t i = index; i < count; i++)
321    {
322        symbolCounter.tally(symbolStream[i]);
323    }
324
325    XMLSize_t knownSymbolCount = symbolCount + (symbolCounter.count() >> 1) + refSymbolCount;
326    if (unlikely(knownSymbolCount >= symbolArray.capacity()))
327    {
328        symbolArray.resizeToFit(symbolCount, knownSymbolCount);
329    }
330
331    size_t startPosition = fStartPosition;
332    size_t endPosition;
333    size_t refIndex = 0;
334    bool resumeSymbol = fResumeSymbol;
335    size_t refPosition = refArray[0].pos;
336    size_t startIndex = index;
337
338    #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
339    size_t offsetIndex = 0;
340    XMLByte DATA_BLOCK[66] = {'|', 0};
341    enum
342    {
343        DATA_BLOCK_SIZE = (BLOCK_SIZE * CodeUnitSize)
344        , LOG_2_DATA_BLOCK_SIZE = CONST_LOG_2(DATA_BLOCK_SIZE)
345    };
346    #endif
347
348    for (bool allRefsAccountedFor = 0;;)
349    {
350        size_t endIndex = refPosition >> LOG_2_BLOCK_SIZE;
351
352        if (likely(endIndex > startIndex))
353        {
354            XMLStreamIterator symbolItr
355            (
356                symbolStream
357                , CONST_LOG_2(CodeUnitSize)
358                , startIndex
359                , endIndex
360            );
361
362            // would assigned gotos be more efficient here? they only work in gcc unfortunetly.
363            switch (resumeSymbol)
364            {
365                case 0: while (unlikely(symbolItr.next(startPosition)))
366                        {
367                case 1:     if (unlikely(!symbolItr.next(endPosition)))
368                            {
369                                resumeSymbol = 1;
370                                break;
371                            }
372
373                            resumeSymbol = 0;
374
375                            #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
376                            for (; offsetIndex <= (endPosition >> LOG_2_DATA_BLOCK_SIZE); offsetIndex++)
377                            {
378                                for (unsigned int scanOffset = 0; scanOffset < DATA_BLOCK_SIZE; scanOffset += 64)
379                                {
380                                    const size_t offset = (offsetIndex << LOG_2_DATA_BLOCK_SIZE) | scanOffset;
381                                    const XMLByte * byteStream = &source[offset - 1];
382
383                                    for (unsigned int i = 1; i <= 64; i++)
384                                    {
385                                        XMLByte c = byteStream[i];
386                                        if (c < 32) c = ' ';
387                                        DATA_BLOCK[i] = c;
388                                    }
389
390                                    DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
391                                    DEBUG_SYMBOL_MESSAGE(
392                                         XERCES_STD_QUALIFIER setw(5) <<
393                                         (offset) <<
394                                         XERCES_STD_QUALIFIER setw(0) <<
395                                         DATA_BLOCK );
396                                    DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
397                                }
398                            }
399                            #endif
400
401                            gid_t gid;
402                            if (internal)
403                            {
404                                gid = addOrFindInternal(reinterpret_cast<const XMLCh*>(&source[startPosition]), (endPosition - startPosition) / sizeof(XMLCh));
405                            }
406                            else
407                            {
408                                gid = addOrFind(&source[startPosition], endPosition - startPosition);
409                            }
410
411                            #ifdef PRINT_DEBUG_MESSAGE
412                            DEBUG_SYMBOL_MESSAGE
413                            (
414                               "SYMBOL: " << fSymbolTable[gid]
415                                << " @ {" << startPosition << ',' << endPosition << '}'
416                                << " gid=" << gid
417                                << " idx=" << symbolCount
418                            );
419                            #endif
420
421                            symbolArray[symbolCount++] = gid;
422
423                        }
424            }
425        }
426
427        if (unlikely(allRefsAccountedFor)) break;
428
429        startIndex = endIndex + 1;
430
431        XMLStreamIterator symbolRefItr
432        (
433            symbolStream
434            , CONST_LOG_2(CodeUnitSize)
435            , endIndex
436            , startIndex
437        );
438
439        #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
440        for (; offsetIndex <= endIndex; offsetIndex++)
441        {
442            for (unsigned int scanOffset = 0; scanOffset < DATA_BLOCK_SIZE; scanOffset += 64)
443            {
444                const size_t offset = (offsetIndex << LOG_2_DATA_BLOCK_SIZE) | scanOffset;
445                const XMLByte * byteStream = &source[offset - 1];
446
447                for (unsigned int i = 1; i <= 64; i++)
448                {
449                    XMLByte c = byteStream[i];
450                    if (c < 32) c = ' ';
451                    DATA_BLOCK[i] = c;
452                }
453
454                DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
455                DEBUG_SYMBOL_MESSAGE(
456                     XERCES_STD_QUALIFIER setw(5) <<
457                     (offset) <<
458                     XERCES_STD_QUALIFIER setw(0) <<
459                     DATA_BLOCK );
460                DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
461            }
462        }
463        #endif
464
465        // somewhere in this block, we have a ref. check for it.
466        switch (resumeSymbol)
467        {
468            case 0: while (unlikely(symbolRefItr.next(startPosition)))
469                    {
470            case 1:     if (unlikely(!symbolRefItr.next(endPosition)))
471                        {
472                            resumeSymbol = 1;
473                            break;
474                        }
475
476                        resumeSymbol = 0;
477
478                        while (refPosition < startPosition)
479                        {
480                            const gid_t gid = refArray[refIndex].gid;
481                            const XMLReference * const ref = referenceTable[gid];
482
483                            Array<gid_t>::copy(ref->getSymbolArray(), &symbolArray[symbolCount], ref->getSymbolCount());
484
485                            #ifdef PRINT_DEBUG_MESSAGE
486                            DEBUG_SYMBOL_MESSAGE(" ** INSERTING " << ref->getSymbolCount() << " SYMBOLS FROM " << gid << ':' << ref->fRefNameString)
487                            for (size_t index = 0; index < ref->getSymbolCount(); index++)
488                            {
489                                gid_t gid = symbolArray[symbolCount + index];
490
491                                DEBUG_SYMBOL_MESSAGE
492                                (
493                                   "SYMBOL: \"" << fSymbolTable[gid]
494                                    << "\" @ {" << refPosition << '}'
495                                    << " gid=" << gid
496                                    << " idx=" << (symbolCount + index)
497                                );
498                            }
499                            #endif
500
501
502                            symbolCount += ref->getSymbolCount();
503
504                            if (unlikely(++refIndex == refCount))
505                            {
506                                allRefsAccountedFor = 1;
507                                refPosition = count << LOG_2_BLOCK_SIZE;
508                            }
509                            else
510                            {
511                                refPosition = refArray[refIndex].pos;
512                            }
513                        }
514
515                        gid_t gid;
516                        if (internal)
517                        {
518                            gid = addOrFindInternal(reinterpret_cast<const XMLCh*>(&source[startPosition]), (endPosition - startPosition) / sizeof(XMLCh));
519                        }
520                        else
521                        {
522                            gid = addOrFind(&source[startPosition], endPosition - startPosition);
523                        }
524
525                        DEBUG_SYMBOL_MESSAGE
526                        (
527                           "SYMBOL: \"" << fSymbolTable[gid]
528                            << "\" @ {" << startPosition << ',' << endPosition << '}'
529                            << " gid=" << gid
530                            << " idx=" << symbolCount
531                        );
532
533                        symbolArray[symbolCount++] = gid;
534                    }
535        }
536
537        while (refPosition < (startIndex << LOG_2_BLOCK_SIZE))
538        {
539            const gid_t gid = refArray[refIndex].gid;
540            const XMLReference * const ref = referenceTable[gid];
541
542            Array<gid_t>::copy(ref->getSymbolArray(), &symbolArray[symbolCount], ref->getSymbolCount());
543
544            #ifdef PRINT_DEBUG_MESSAGE
545            DEBUG_SYMBOL_MESSAGE(" ** INSERTING " << ref->getSymbolCount() << " SYMBOLS FROM " << gid << ':' << ref->fRefNameString << '*');
546            for (size_t index = 0; index < ref->getSymbolCount(); index++)
547            {
548                gid_t gid = symbolArray[symbolCount + index];
549
550                DEBUG_SYMBOL_MESSAGE
551                (
552                   "SYMBOL: \"" << fSymbolTable[gid]
553                    << "\" @ {" << refPosition << '}'
554                    << " gid=" << gid
555                    << " idx=" << (symbolCount + index)
556                );
557            }
558            #endif
559
560            symbolCount += ref->getSymbolCount();
561
562            if (unlikely(++refIndex == refCount))
563            {
564                allRefsAccountedFor = 1;
565                refPosition = count << LOG_2_BLOCK_SIZE;
566            }
567            else
568            {
569                refPosition = refArray[refIndex].pos;
570            }
571        }
572    }
573
574    #if defined(PRINT_DEBUG_MESSAGE) && !defined(PRINT_DEBUG_IGNORE_SYMBOL_STREAM_MESSAGES)
575    for (; offsetIndex < count; offsetIndex++)
576    {
577        for (unsigned int scanOffset = 0; scanOffset < DATA_BLOCK_SIZE; scanOffset += 64)
578        {
579            const size_t offset = (offsetIndex << LOG_2_DATA_BLOCK_SIZE) | scanOffset;
580            const XMLByte * byteStream = &source[offset - 1];
581
582            for (unsigned int i = 1; i <= 64; i++)
583            {
584                XMLByte c = byteStream[i];
585                if (c < 32) c = ' ';
586                DATA_BLOCK[i] = c;
587            }
588
589            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
590            DEBUG_SYMBOL_MESSAGE(
591                 XERCES_STD_QUALIFIER setw(5) <<
592                 (offset) <<
593                 XERCES_STD_QUALIFIER setw(0) <<
594                 DATA_BLOCK );
595            DEBUG_SYMBOL_MESSAGE("----------------------------------------------------------------------");
596        }
597    }
598    #endif
599
600    fResumeSymbol = resumeSymbol;
601    fStartPosition = startPosition;
602
603    return symbolCount;
604}
605
606gid_t
607XMLSymbolTable::addOrFind
608(
609    const XMLByte                       * const key
610    , const XMLSize_t                           length
611)
612{
613    gid_t gid = fSymbolTable.find(key, length);
614    if (unlikely(gid == -1))
615    {
616        gid = add(key, length);
617    }
618    return gid;
619}
620
621gid_t
622XMLSymbolTable::addOrFindInternal
623(
624    const XMLCh                         * const key
625    , const XMLSize_t                           length
626)
627{
628    XMLByte * unencodedKey = (XMLByte *)fMemoryManager->allocate((length * 4) + (sizeof(BytePack) / sizeof(XMLCh)));
629    XMLSize_t unencodedLength;
630
631    unencodedLength = fTranscoder->transcodeTo(key, length, unencodedKey, length * 4, unencodedLength, XMLTranscoder::UnRep_Throw);
632
633    gid_t gid = fSymbolTable.find(unencodedKey, unencodedLength);
634    if (unlikely(gid == -1))
635    {
636        gid = addInternal(key, length, unencodedKey, unencodedLength);
637    }
638    fMemoryManager->deallocate(unencodedKey);
639    return gid;
640}
641
642XERCES_CPP_NAMESPACE_END
643
644#endif // XML_SYMBOL_TABLE_H
Note: See TracBrowser for help on using the repository browser.