1 /*
2  * FTGL - OpenGL font library
3  *
4  * Copyright (c) 2001-2004 Henry Maddocks <ftgl@opengl.geek.nz>
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining
7  * a copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sublicense, and/or sell copies of the Software, and to
11  * permit persons to whom the Software is furnished to do so, subject to
12  * the following conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
21  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
22  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
23  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24  */
25 
26 #ifndef    __FTCharToGlyphIndexMap__
27 #define    __FTCharToGlyphIndexMap__
28 
29 #include <stdlib.h>
30 
31 #include "FTGL/ftgl.h"
32 
33 /**
34  * Provides a non-STL alternative to the STL map<unsigned long, unsigned long>
35  * which maps character codes to glyph indices inside FTCharmap.
36  *
37  * Implementation:
38  *   - NumberOfBuckets buckets are considered.
39  *   - Each bucket has BucketSize entries.
40  *   - When the glyph index for the character code C has to be stored, the
41  *     bucket this character belongs to is found using 'C div BucketSize'.
42  *     If this bucket has not been allocated yet, do it now.
43  *     The entry in the bucked is found using 'C mod BucketSize'.
44  *     If it is set to IndexNotFound, then the glyph entry has not been set.
45  *   - Try to mimic the calls made to the STL map API.
46  *
47  * Caveats:
48  *   - The glyph index is now a signed long instead of unsigned long, so
49  *     the special value IndexNotFound (= -1) can be used to specify that the
50  *     glyph index has not been stored yet.
51  */
52 class FTCharToGlyphIndexMap
53 {
54     public:
55         typedef unsigned long CharacterCode;
56         typedef signed long GlyphIndex;
57 
58         // XXX: always ensure that 1 << (3 * BucketIdxBits) >= UnicodeValLimit
59         static const int BucketIdxBits = 7;
60         static const int BucketIdxSize = 1 << BucketIdxBits;
61         static const int BucketIdxMask = BucketIdxSize - 1;
62 
63         static const CharacterCode UnicodeValLimit = 0x110000;
64         static const int IndexNotFound = -1;
65 
FTCharToGlyphIndexMap()66         FTCharToGlyphIndexMap()
67         {
68             Indices = 0;
69         }
70 
~FTCharToGlyphIndexMap()71         virtual ~FTCharToGlyphIndexMap()
72         {
73             // Free all buckets
74             clear();
75         }
76 
clear()77         inline void clear()
78         {
79             for(int j = 0; Indices && j < BucketIdxSize; j++)
80             {
81                 for(int i = 0; Indices[j] && i < BucketIdxSize; i++)
82                 {
83                     delete[] Indices[j][i];
84                     Indices[j][i] = 0;
85                 }
86                 delete[] Indices[j];
87                 Indices[j] = 0;
88             }
89             delete[] Indices;
90             Indices = 0;
91         }
92 
find(CharacterCode c)93         GlyphIndex find(CharacterCode c)
94         {
95             int OuterIdx = (c >> (BucketIdxBits * 2)) & BucketIdxMask;
96             int InnerIdx = (c >> BucketIdxBits) & BucketIdxMask;
97             int Offset = c & BucketIdxMask;
98 
99             if (c >= UnicodeValLimit || !Indices
100                  || !Indices[OuterIdx] || !Indices[OuterIdx][InnerIdx])
101                 return 0;
102 
103             GlyphIndex g = Indices[OuterIdx][InnerIdx][Offset];
104 
105             return (g != IndexNotFound) ? g : 0;
106         }
107 
insert(CharacterCode c,GlyphIndex g)108         void insert(CharacterCode c, GlyphIndex g)
109         {
110             int OuterIdx = (c >> (BucketIdxBits * 2)) & BucketIdxMask;
111             int InnerIdx = (c >> BucketIdxBits) & BucketIdxMask;
112             int Offset = c & BucketIdxMask;
113 
114             if (c >= UnicodeValLimit)
115                 return;
116 
117             if (!Indices)
118             {
119                 Indices = new GlyphIndex** [BucketIdxSize];
120                 for(int i = 0; i < BucketIdxSize; i++)
121                     Indices[i] = 0;
122             }
123 
124             if (!Indices[OuterIdx])
125             {
126                 Indices[OuterIdx] = new GlyphIndex* [BucketIdxSize];
127                 for(int i = 0; i < BucketIdxSize; i++)
128                     Indices[OuterIdx][i] = 0;
129             }
130 
131             if (!Indices[OuterIdx][InnerIdx])
132             {
133                 Indices[OuterIdx][InnerIdx] = new GlyphIndex [BucketIdxSize];
134                 for(int i = 0; i < BucketIdxSize; i++)
135                     Indices[OuterIdx][InnerIdx][i] = IndexNotFound;
136             }
137 
138             Indices[OuterIdx][InnerIdx][Offset] = g;
139         }
140 
141     private:
142         GlyphIndex*** Indices;
143 };
144 
145 #endif  //  __FTCharToGlyphIndexMap__
146 
147