... |
... |
@@ -94,8 +94,8 @@ |
94
|
94
|
|
95
|
95
|
|
96
|
96
|
idx = hash & cache->mask;
|
97
|
|
- if ( idx < cache->p )
|
98
|
|
- idx = hash & ( 2 * cache->mask + 1 );
|
|
97
|
+ if ( idx >= cache->p )
|
|
98
|
+ idx = hash & ( cache->mask >> 1 );
|
99
|
99
|
|
100
|
100
|
return cache->buckets + idx;
|
101
|
101
|
}
|
... |
... |
@@ -113,9 +113,9 @@ |
113
|
113
|
for (;;)
|
114
|
114
|
{
|
115
|
115
|
FTC_Node node, *pnode;
|
116
|
|
- FT_UFast p = cache->p;
|
117
|
|
- FT_UFast mask = cache->mask;
|
118
|
|
- FT_UFast count = mask + p + 1; /* number of buckets */
|
|
116
|
+ FT_UFast p = cache->p;
|
|
117
|
+ FT_UFast size = cache->mask + 1; /* available size */
|
|
118
|
+ FT_UFast half = size >> 1;
|
119
|
119
|
|
120
|
120
|
|
121
|
121
|
/* do we need to expand the buckets array? */
|
... |
... |
@@ -124,23 +124,24 @@ |
124
|
124
|
FTC_Node new_list = NULL;
|
125
|
125
|
|
126
|
126
|
|
|
127
|
+ /* a single bucket to split */
|
|
128
|
+ pnode = cache->buckets + p - half;
|
|
129
|
+
|
127
|
130
|
/* try to expand the buckets array _before_ splitting
|
128
|
131
|
* the bucket lists
|
129
|
132
|
*/
|
130
|
|
- if ( p >= mask )
|
|
133
|
+ if ( ++p >= size )
|
131
|
134
|
{
|
132
|
135
|
FT_Memory memory = cache->memory;
|
133
|
136
|
FT_Error error;
|
134
|
137
|
|
135
|
138
|
|
136
|
139
|
/* if we can't expand the array, leave immediately */
|
137
|
|
- if ( FT_RENEW_ARRAY( cache->buckets,
|
138
|
|
- ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
|
|
140
|
+ if ( FT_RENEW_ARRAY( cache->buckets, size, size * 2 ) )
|
139
|
141
|
break;
|
140
|
|
- }
|
141
|
142
|
|
142
|
|
- /* split a single bucket */
|
143
|
|
- pnode = cache->buckets + p;
|
|
143
|
+ cache->mask = 2 * size - 1;
|
|
144
|
+ }
|
144
|
145
|
|
145
|
146
|
for (;;)
|
146
|
147
|
{
|
... |
... |
@@ -148,7 +149,7 @@ |
148
|
149
|
if ( !node )
|
149
|
150
|
break;
|
150
|
151
|
|
151
|
|
- if ( node->hash & ( mask + 1 ) )
|
|
152
|
+ if ( node->hash & half )
|
152
|
153
|
{
|
153
|
154
|
*pnode = node->link;
|
154
|
155
|
node->link = new_list;
|
... |
... |
@@ -158,53 +159,38 @@ |
158
|
159
|
pnode = &node->link;
|
159
|
160
|
}
|
160
|
161
|
|
161
|
|
- cache->buckets[p + mask + 1] = new_list;
|
|
162
|
+ cache->buckets[p - 1] = new_list;
|
162
|
163
|
|
163
|
164
|
cache->slack += FTC_HASH_MAX_LOAD;
|
164
|
|
-
|
165
|
|
- if ( p >= mask )
|
166
|
|
- {
|
167
|
|
- cache->mask = 2 * mask + 1;
|
168
|
|
- cache->p = 0;
|
169
|
|
- }
|
170
|
|
- else
|
171
|
|
- cache->p = p + 1;
|
|
165
|
+ cache->p = p;
|
172
|
166
|
}
|
173
|
167
|
|
174
|
168
|
/* do we need to shrink the buckets array? */
|
175
|
|
- else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
|
|
169
|
+ else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
|
176
|
170
|
{
|
177
|
|
- FT_UFast old_index = p + mask;
|
178
|
|
- FTC_Node* pold;
|
179
|
|
-
|
180
|
|
-
|
181
|
|
- if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
|
|
171
|
+ if ( p <= FTC_HASH_INITIAL_SIZE )
|
182
|
172
|
break;
|
183
|
173
|
|
184
|
|
- if ( p == 0 )
|
|
174
|
+ if ( p-- <= half )
|
185
|
175
|
{
|
186
|
176
|
FT_Memory memory = cache->memory;
|
187
|
177
|
FT_Error error;
|
188
|
178
|
|
189
|
179
|
|
190
|
180
|
/* if we can't shrink the array, leave immediately */
|
191
|
|
- if ( FT_QRENEW_ARRAY( cache->buckets,
|
192
|
|
- ( mask + 1 ) * 2, mask + 1 ) )
|
|
181
|
+ if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
|
193
|
182
|
break;
|
194
|
183
|
|
195
|
|
- cache->mask >>= 1;
|
196
|
|
- p = cache->mask;
|
|
184
|
+ cache->mask = half - 1;
|
|
185
|
+ half >>= 1;
|
197
|
186
|
}
|
198
|
|
- else
|
199
|
|
- p--;
|
200
|
187
|
|
201
|
|
- pnode = cache->buckets + p;
|
|
188
|
+ pnode = cache->buckets + p - half;
|
202
|
189
|
while ( *pnode )
|
203
|
190
|
pnode = &(*pnode)->link;
|
204
|
191
|
|
205
|
|
- pold = cache->buckets + old_index;
|
206
|
|
- *pnode = *pold;
|
207
|
|
- *pold = NULL;
|
|
192
|
+ *pnode = cache->buckets[p];
|
|
193
|
+ cache->buckets[p] = NULL;
|
208
|
194
|
|
209
|
195
|
cache->slack -= FTC_HASH_MAX_LOAD;
|
210
|
196
|
cache->p = p;
|
... |
... |
@@ -336,8 +322,8 @@ |
336
|
322
|
FT_Error error;
|
337
|
323
|
|
338
|
324
|
|
339
|
|
- cache->p = 0;
|
340
|
|
- cache->mask = FTC_HASH_INITIAL_SIZE - 1;
|
|
325
|
+ cache->p = FTC_HASH_INITIAL_SIZE;
|
|
326
|
+ cache->mask = 2 * FTC_HASH_INITIAL_SIZE - 1;
|
341
|
327
|
cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
|
342
|
328
|
|
343
|
329
|
FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
|
... |
... |
@@ -351,11 +337,9 @@ |
351
|
337
|
if ( cache && cache->buckets )
|
352
|
338
|
{
|
353
|
339
|
FTC_Manager manager = cache->manager;
|
|
340
|
+ FT_UFast count = cache->p;
|
354
|
341
|
FT_UFast i;
|
355
|
|
- FT_UFast count;
|
356
|
|
-
|
357
|
342
|
|
358
|
|
- count = cache->p + cache->mask + 1;
|
359
|
343
|
|
360
|
344
|
for ( i = 0; i < count; i++ )
|
361
|
345
|
{
|
... |
... |
@@ -562,12 +546,12 @@ |
562
|
546
|
FTC_Cache_RemoveFaceID( FTC_Cache cache,
|
563
|
547
|
FTC_FaceID face_id )
|
564
|
548
|
{
|
565
|
|
- FT_UFast i, count;
|
566
|
549
|
FTC_Manager manager = cache->manager;
|
567
|
550
|
FTC_Node frees = NULL;
|
|
551
|
+ FT_UFast count = cache->p;
|
|
552
|
+ FT_UFast i;
|
568
|
553
|
|
569
|
554
|
|
570
|
|
- count = cache->p + cache->mask + 1;
|
571
|
555
|
for ( i = 0; i < count; i++ )
|
572
|
556
|
{
|
573
|
557
|
FTC_Node* pnode = cache->buckets + i;
|