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