Commit 75213482b69ab0b9ca95d1366f2a4a0064ab1d74
2010-05-23T18:55:36
Implement a 3-level bucket structure for glyphs, to account for all possible Unicode values as of now. Patch initially by SF user SilverDirk and slightly reworked.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
diff --git a/src/FTCharToGlyphIndexMap.h b/src/FTCharToGlyphIndexMap.h
index 70f7904..5e7d4e0 100644
--- a/src/FTCharToGlyphIndexMap.h
+++ b/src/FTCharToGlyphIndexMap.h
@@ -52,105 +52,95 @@
class FTCharToGlyphIndexMap
{
public:
-
typedef unsigned long CharacterCode;
typedef signed long GlyphIndex;
- enum
- {
- NumberOfBuckets = 256,
- BucketSize = 256,
- IndexNotFound = -1
- };
+ // XXX: always ensure that 1 << (3 * BucketIdxBits) >= UnicodeValLimit
+ static const int BucketIdxBits = 7;
+ static const int BucketIdxSize = 1 << BucketIdxBits;
+ static const int BucketIdxMask = BucketIdxSize - 1;
+
+ static const CharacterCode UnicodeValLimit = 0x110000;
+ static const int IndexNotFound = -1;
FTCharToGlyphIndexMap()
{
- this->Indices = 0;
+ Indices = 0;
}
virtual ~FTCharToGlyphIndexMap()
{
- if(this->Indices)
- {
- // Free all buckets
- this->clear();
-
- // Free main structure
- delete [] this->Indices;
- this->Indices = 0;
- }
+ // Free all buckets
+ clear();
}
inline void clear()
{
- if(this->Indices)
+ for(int j = 0; Indices && j < BucketIdxSize; j++)
{
- for(int i = 0; i < FTCharToGlyphIndexMap::NumberOfBuckets; i++)
+ for(int i = 0; Indices[j] && i < BucketIdxSize; i++)
{
- if(this->Indices[i])
- {
- delete [] this->Indices[i];
- this->Indices[i] = 0;
- }
+ delete[] Indices[j][i];
+ Indices[j][i] = 0;
}
+ delete[] Indices[j];
+ Indices[j] = 0;
}
+ delete[] Indices;
+ Indices = 0;
}
const GlyphIndex find(CharacterCode c)
{
- if(!this->Indices)
- {
- return 0;
- }
-
- // Find position of char code in buckets
- div_t pos = div(c, FTCharToGlyphIndexMap::BucketSize);
+ int OuterIdx = (c >> (BucketIdxBits * 2)) & BucketIdxMask;
+ int InnerIdx = (c >> BucketIdxBits) & BucketIdxMask;
+ int Offset = c & BucketIdxMask;
- if (pos.quot >= FTCharToGlyphIndexMap::NumberOfBuckets
- || !this->Indices[pos.quot])
- {
+ if (c >= UnicodeValLimit || !Indices
+ || !Indices[OuterIdx] || !Indices[OuterIdx][InnerIdx])
return 0;
- }
- const FTCharToGlyphIndexMap::GlyphIndex *ptr = &this->Indices[pos.quot][pos.rem];
- if(*ptr == FTCharToGlyphIndexMap::IndexNotFound)
- {
- return 0;
- }
+ GlyphIndex g = Indices[OuterIdx][InnerIdx][Offset];
- return *ptr;
+ return (g != IndexNotFound) ? g : 0;
}
void insert(CharacterCode c, GlyphIndex g)
{
- if(!this->Indices)
+ int OuterIdx = (c >> (BucketIdxBits * 2)) & BucketIdxMask;
+ int InnerIdx = (c >> BucketIdxBits) & BucketIdxMask;
+ int Offset = c & BucketIdxMask;
+
+ if (c >= UnicodeValLimit)
+ return;
+
+ if (!Indices)
{
- this->Indices = new GlyphIndex* [FTCharToGlyphIndexMap::NumberOfBuckets];
- for(int i = 0; i < FTCharToGlyphIndexMap::NumberOfBuckets; i++)
- {
- this->Indices[i] = 0;
- }
+ Indices = new GlyphIndex** [BucketIdxSize];
+ for(int i = 0; i < BucketIdxSize; i++)
+ Indices[i] = 0;
}
- // Find position of char code in buckets
- div_t pos = div(c, FTCharToGlyphIndexMap::BucketSize);
+ if (!Indices[OuterIdx])
+ {
+ Indices[OuterIdx] = new GlyphIndex* [BucketIdxSize];
+ for(int i = 0; i < BucketIdxSize; i++)
+ Indices[OuterIdx][i] = 0;
+ }
- // Allocate bucket if does not exist yet
- if(!this->Indices[pos.quot])
+ if (!Indices[OuterIdx][InnerIdx])
{
- this->Indices[pos.quot] = new GlyphIndex [FTCharToGlyphIndexMap::BucketSize];
- for(int i = 0; i < FTCharToGlyphIndexMap::BucketSize; i++)
- {
- this->Indices[pos.quot][i] = FTCharToGlyphIndexMap::IndexNotFound;
- }
+ Indices[OuterIdx][InnerIdx] = new GlyphIndex [BucketIdxSize];
+ for(int i = 0; i < BucketIdxSize; i++)
+ Indices[OuterIdx][InnerIdx][i] = IndexNotFound;
}
- this->Indices[pos.quot][pos.rem] = g;
+ Indices[OuterIdx][InnerIdx][Offset] = g;
}
private:
- GlyphIndex** Indices;
+ GlyphIndex*** Indices;
};
-
#endif // __FTCharToGlyphIndexMap__
+