... |
... |
@@ -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? */
|
... |
... |
@@ -127,20 +127,22 @@ |
127
|
127
|
/* try to expand the buckets array _before_ splitting
|
128
|
128
|
* the bucket lists
|
129
|
129
|
*/
|
130
|
|
- if ( p >= mask )
|
|
130
|
+ if ( p == size )
|
131
|
131
|
{
|
132
|
132
|
FT_Memory memory = cache->memory;
|
133
|
133
|
FT_Error error;
|
134
|
134
|
|
135
|
135
|
|
136
|
136
|
/* if we can't expand the array, leave immediately */
|
137
|
|
- if ( FT_RENEW_ARRAY( cache->buckets,
|
138
|
|
- ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
|
|
137
|
+ if ( FT_QRENEW_ARRAY( cache->buckets, size, size * 2 ) )
|
139
|
138
|
break;
|
|
139
|
+
|
|
140
|
+ cache->mask = 2 * size - 1;
|
|
141
|
+ half = size;
|
140
|
142
|
}
|
141
|
143
|
|
142
|
|
- /* split a single bucket */
|
143
|
|
- pnode = cache->buckets + p;
|
|
144
|
+ /* the bucket to split */
|
|
145
|
+ pnode = cache->buckets + p - half;
|
144
|
146
|
|
145
|
147
|
for (;;)
|
146
|
148
|
{
|
... |
... |
@@ -148,7 +150,7 @@ |
148
|
150
|
if ( !node )
|
149
|
151
|
break;
|
150
|
152
|
|
151
|
|
- if ( node->hash & ( mask + 1 ) )
|
|
153
|
+ if ( node->hash & half )
|
152
|
154
|
{
|
153
|
155
|
*pnode = node->link;
|
154
|
156
|
node->link = new_list;
|
... |
... |
@@ -158,56 +160,50 @@ |
158
|
160
|
pnode = &node->link;
|
159
|
161
|
}
|
160
|
162
|
|
161
|
|
- cache->buckets[p + mask + 1] = new_list;
|
|
163
|
+ cache->buckets[p] = new_list;
|
162
|
164
|
|
163
|
165
|
cache->slack += FTC_HASH_MAX_LOAD;
|
|
166
|
+ cache->p = p + 1;
|
164
|
167
|
|
165
|
|
- if ( p >= mask )
|
166
|
|
- {
|
167
|
|
- cache->mask = 2 * mask + 1;
|
168
|
|
- cache->p = 0;
|
169
|
|
- }
|
170
|
|
- else
|
171
|
|
- cache->p = p + 1;
|
|
168
|
+ FT_TRACE2(( "ftc_cache_resize: cache %u increased to %u hashes\n",
|
|
169
|
+ cache->index, cache->p ));
|
172
|
170
|
}
|
173
|
171
|
|
174
|
172
|
/* do we need to shrink the buckets array? */
|
175
|
|
- else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
|
|
173
|
+ else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
|
176
|
174
|
{
|
177
|
|
- FT_UFast old_index = p + mask;
|
178
|
|
- FTC_Node* pold;
|
|
175
|
+ FTC_Node old_list = cache->buckets[--p];
|
179
|
176
|
|
180
|
177
|
|
181
|
|
- if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
|
|
178
|
+ if ( p < FTC_HASH_INITIAL_SIZE )
|
182
|
179
|
break;
|
183
|
180
|
|
184
|
|
- if ( p == 0 )
|
|
181
|
+ if ( p == half )
|
185
|
182
|
{
|
186
|
183
|
FT_Memory memory = cache->memory;
|
187
|
184
|
FT_Error error;
|
188
|
185
|
|
189
|
186
|
|
190
|
187
|
/* if we can't shrink the array, leave immediately */
|
191
|
|
- if ( FT_QRENEW_ARRAY( cache->buckets,
|
192
|
|
- ( mask + 1 ) * 2, mask + 1 ) )
|
|
188
|
+ if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
|
193
|
189
|
break;
|
194
|
190
|
|
195
|
|
- cache->mask >>= 1;
|
196
|
|
- p = cache->mask;
|
|
191
|
+ cache->mask = half - 1;
|
197
|
192
|
}
|
198
|
|
- else
|
199
|
|
- p--;
|
200
|
193
|
|
201
|
|
- pnode = cache->buckets + p;
|
|
194
|
+ /* the bucket to merge */
|
|
195
|
+ pnode = cache->buckets + p - half;
|
|
196
|
+
|
202
|
197
|
while ( *pnode )
|
203
|
198
|
pnode = &(*pnode)->link;
|
204
|
199
|
|
205
|
|
- pold = cache->buckets + old_index;
|
206
|
|
- *pnode = *pold;
|
207
|
|
- *pold = NULL;
|
|
200
|
+ *pnode = old_list;
|
208
|
201
|
|
209
|
202
|
cache->slack -= FTC_HASH_MAX_LOAD;
|
210
|
203
|
cache->p = p;
|
|
204
|
+
|
|
205
|
+ FT_TRACE2(( "ftc_cache_resize: cache %u decreased to %u hashes\n",
|
|
206
|
+ cache->index, cache->p ));
|
211
|
207
|
}
|
212
|
208
|
|
213
|
209
|
/* otherwise, the hash table is balanced */
|
... |
... |
@@ -336,11 +332,11 @@ |
336
|
332
|
FT_Error error;
|
337
|
333
|
|
338
|
334
|
|
339
|
|
- cache->p = 0;
|
|
335
|
+ cache->p = FTC_HASH_INITIAL_SIZE;
|
340
|
336
|
cache->mask = FTC_HASH_INITIAL_SIZE - 1;
|
341
|
337
|
cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
|
342
|
338
|
|
343
|
|
- FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
|
|
339
|
+ FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE );
|
344
|
340
|
return error;
|
345
|
341
|
}
|
346
|
342
|
|
... |
... |
@@ -351,11 +347,9 @@ |
351
|
347
|
if ( cache && cache->buckets )
|
352
|
348
|
{
|
353
|
349
|
FTC_Manager manager = cache->manager;
|
|
350
|
+ FT_UFast count = cache->p;
|
354
|
351
|
FT_UFast i;
|
355
|
|
- FT_UFast count;
|
356
|
|
-
|
357
|
352
|
|
358
|
|
- count = cache->p + cache->mask + 1;
|
359
|
353
|
|
360
|
354
|
for ( i = 0; i < count; i++ )
|
361
|
355
|
{
|
... |
... |
@@ -562,12 +556,12 @@ |
562
|
556
|
FTC_Cache_RemoveFaceID( FTC_Cache cache,
|
563
|
557
|
FTC_FaceID face_id )
|
564
|
558
|
{
|
565
|
|
- FT_UFast i, count;
|
566
|
559
|
FTC_Manager manager = cache->manager;
|
567
|
560
|
FTC_Node frees = NULL;
|
|
561
|
+ FT_UFast count = cache->p;
|
|
562
|
+ FT_UFast i;
|
568
|
563
|
|
569
|
564
|
|
570
|
|
- count = cache->p + cache->mask + 1;
|
571
|
565
|
for ( i = 0; i < count; i++ )
|
572
|
566
|
{
|
573
|
567
|
FTC_Node* pnode = cache->buckets + i;
|