The Tor Browser / file comparison

comparison: intl/icu/source/common/propsvec.c

intl/icu/source/common/propsvec.c

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:3661ad717174
1 /*
2 *******************************************************************************
3 *
4 * Copyright (C) 2002-2011, International Business Machines
5 * Corporation and others. All Rights Reserved.
6 *
7 *******************************************************************************
8 * file name: propsvec.c
9 * encoding: US-ASCII
10 * tab size: 8 (not used)
11 * indentation:4
12 *
13 * created on: 2002feb22
14 * created by: Markus W. Scherer
15 *
16 * Store bits (Unicode character properties) in bit set vectors.
17 */
18
19 #include <stdlib.h>
20 #include "unicode/utypes.h"
21 #include "cmemory.h"
22 #include "utrie.h"
23 #include "utrie2.h"
24 #include "uarrsort.h"
25 #include "propsvec.h"
26 #include "uassert.h"
27
28 struct UPropsVectors {
29 uint32_t *v;
30 int32_t columns; /* number of columns, plus two for start & limit values */
31 int32_t maxRows;
32 int32_t rows;
33 int32_t prevRow; /* search optimization: remember last row seen */
34 UBool isCompacted;
35 };
36
37 #define UPVEC_INITIAL_ROWS (1<<12)
38 #define UPVEC_MEDIUM_ROWS ((int32_t)1<<16)
39 #define UPVEC_MAX_ROWS (UPVEC_MAX_CP+1)
40
41 U_CAPI UPropsVectors * U_EXPORT2
42 upvec_open(int32_t columns, UErrorCode *pErrorCode) {
43 UPropsVectors *pv;
44 uint32_t *v, *row;
45 uint32_t cp;
46
47 if(U_FAILURE(*pErrorCode)) {
48 return NULL;
49 }
50 if(columns<1) {
51 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
52 return NULL;
53 }
54 columns+=2; /* count range start and limit columns */
55
56 pv=(UPropsVectors *)uprv_malloc(sizeof(UPropsVectors));
57 v=(uint32_t *)uprv_malloc(UPVEC_INITIAL_ROWS*columns*4);
58 if(pv==NULL || v==NULL) {
59 uprv_free(pv);
60 uprv_free(v);
61 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
62 return NULL;
63 }
64 uprv_memset(pv, 0, sizeof(UPropsVectors));
65 pv->v=v;
66 pv->columns=columns;
67 pv->maxRows=UPVEC_INITIAL_ROWS;
68 pv->rows=2+(UPVEC_MAX_CP-UPVEC_FIRST_SPECIAL_CP);
69
70 /* set the all-Unicode row and the special-value rows */
71 row=pv->v;
72 uprv_memset(row, 0, pv->rows*columns*4);
73 row[0]=0;
74 row[1]=0x110000;
75 row+=columns;
76 for(cp=UPVEC_FIRST_SPECIAL_CP; cp<=UPVEC_MAX_CP; ++cp) {
77 row[0]=cp;
78 row[1]=cp+1;
79 row+=columns;
80 }
81 return pv;
82 }
83
84 U_CAPI void U_EXPORT2
85 upvec_close(UPropsVectors *pv) {
86 if(pv!=NULL) {
87 uprv_free(pv->v);
88 uprv_free(pv);
89 }
90 }
91
92 static uint32_t *
93 _findRow(UPropsVectors *pv, UChar32 rangeStart) {
94 uint32_t *row;
95 int32_t columns, i, start, limit, prevRow;
96
97 columns=pv->columns;
98 limit=pv->rows;
99 prevRow=pv->prevRow;
100
101 /* check the vicinity of the last-seen row (start searching with an unrolled loop) */
102 row=pv->v+prevRow*columns;
103 if(rangeStart>=(UChar32)row[0]) {
104 if(rangeStart<(UChar32)row[1]) {
105 /* same row as last seen */
106 return row;
107 } else if(rangeStart<(UChar32)(row+=columns)[1]) {
108 /* next row after the last one */
109 pv->prevRow=prevRow+1;
110 return row;
111 } else if(rangeStart<(UChar32)(row+=columns)[1]) {
112 /* second row after the last one */
113 pv->prevRow=prevRow+2;
114 return row;
115 } else if((rangeStart-(UChar32)row[1])<10) {
116 /* we are close, continue looping */
117 prevRow+=2;
118 do {
119 ++prevRow;
120 row+=columns;
121 } while(rangeStart>=(UChar32)row[1]);
122 pv->prevRow=prevRow;
123 return row;
124 }
125 } else if(rangeStart<(UChar32)pv->v[1]) {
126 /* the very first row */
127 pv->prevRow=0;
128 return pv->v;
129 }
130
131 /* do a binary search for the start of the range */
132 start=0;
133 while(start<limit-1) {
134 i=(start+limit)/2;
135 row=pv->v+i*columns;
136 if(rangeStart<(UChar32)row[0]) {
137 limit=i;
138 } else if(rangeStart<(UChar32)row[1]) {
139 pv->prevRow=i;
140 return row;
141 } else {
142 start=i;
143 }
144 }
145
146 /* must be found because all ranges together always cover all of Unicode */
147 pv->prevRow=start;
148 return pv->v+start*columns;
149 }
150
151 U_CAPI void U_EXPORT2
152 upvec_setValue(UPropsVectors *pv,
153 UChar32 start, UChar32 end,
154 int32_t column,
155 uint32_t value, uint32_t mask,
156 UErrorCode *pErrorCode) {
157 uint32_t *firstRow, *lastRow;
158 int32_t columns;
159 UChar32 limit;
160 UBool splitFirstRow, splitLastRow;
161
162 /* argument checking */
163 if(U_FAILURE(*pErrorCode)) {
164 return;
165 }
166 if( pv==NULL ||
167 start<0 || start>end || end>UPVEC_MAX_CP ||
168 column<0 || column>=(pv->columns-2)
169 ) {
170 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
171 return;
172 }
173 if(pv->isCompacted) {
174 *pErrorCode=U_NO_WRITE_PERMISSION;
175 return;
176 }
177 limit=end+1;
178
179 /* initialize */
180 columns=pv->columns;
181 column+=2; /* skip range start and limit columns */
182 value&=mask;
183
184 /* find the rows whose ranges overlap with the input range */
185
186 /* find the first and last rows, always successful */
187 firstRow=_findRow(pv, start);
188 lastRow=_findRow(pv, end);
189
190 /*
191 * Rows need to be split if they partially overlap with the
192 * input range (only possible for the first and last rows)
193 * and if their value differs from the input value.
194 */
195 splitFirstRow= (UBool)(start!=(UChar32)firstRow[0] && value!=(firstRow[column]&mask));
196 splitLastRow= (UBool)(limit!=(UChar32)lastRow[1] && value!=(lastRow[column]&mask));
197
198 /* split first/last rows if necessary */
199 if(splitFirstRow || splitLastRow) {
200 int32_t count, rows;
201
202 rows=pv->rows;
203 if((rows+splitFirstRow+splitLastRow)>pv->maxRows) {
204 uint32_t *newVectors;
205 int32_t newMaxRows;
206
207 if(pv->maxRows<UPVEC_MEDIUM_ROWS) {
208 newMaxRows=UPVEC_MEDIUM_ROWS;
209 } else if(pv->maxRows<UPVEC_MAX_ROWS) {
210 newMaxRows=UPVEC_MAX_ROWS;
211 } else {
212 /* Implementation bug, or UPVEC_MAX_ROWS too low. */
213 *pErrorCode=U_INTERNAL_PROGRAM_ERROR;
214 return;
215 }
216 newVectors=(uint32_t *)uprv_malloc(newMaxRows*columns*4);
217 if(newVectors==NULL) {
218 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
219 return;
220 }
221 uprv_memcpy(newVectors, pv->v, rows*columns*4);
222 firstRow=newVectors+(firstRow-pv->v);
223 lastRow=newVectors+(lastRow-pv->v);
224 uprv_free(pv->v);
225 pv->v=newVectors;
226 pv->maxRows=newMaxRows;
227 }
228
229 /* count the number of row cells to move after the last row, and move them */
230 count = (int32_t)((pv->v+rows*columns)-(lastRow+columns));
231 if(count>0) {
232 uprv_memmove(
233 lastRow+(1+splitFirstRow+splitLastRow)*columns,
234 lastRow+columns,
235 count*4);
236 }
237 pv->rows=rows+splitFirstRow+splitLastRow;
238
239 /* split the first row, and move the firstRow pointer to the second part */
240 if(splitFirstRow) {
241 /* copy all affected rows up one and move the lastRow pointer */
242 count = (int32_t)((lastRow-firstRow)+columns);
243 uprv_memmove(firstRow+columns, firstRow, count*4);
244 lastRow+=columns;
245
246 /* split the range and move the firstRow pointer */
247 firstRow[1]=firstRow[columns]=(uint32_t)start;
248 firstRow+=columns;
249 }
250
251 /* split the last row */
252 if(splitLastRow) {
253 /* copy the last row data */
254 uprv_memcpy(lastRow+columns, lastRow, columns*4);
255
256 /* split the range and move the firstRow pointer */
257 lastRow[1]=lastRow[columns]=(uint32_t)limit;
258 }
259 }
260
261 /* set the "row last seen" to the last row for the range */
262 pv->prevRow=(int32_t)((lastRow-(pv->v))/columns);
263
264 /* set the input value in all remaining rows */
265 firstRow+=column;
266 lastRow+=column;
267 mask=~mask;
268 for(;;) {
269 *firstRow=(*firstRow&mask)|value;
270 if(firstRow==lastRow) {
271 break;
272 }
273 firstRow+=columns;
274 }
275 }
276
277 U_CAPI uint32_t U_EXPORT2
278 upvec_getValue(const UPropsVectors *pv, UChar32 c, int32_t column) {
279 uint32_t *row;
280 UPropsVectors *ncpv;
281
282 if(pv->isCompacted || c<0 || c>UPVEC_MAX_CP || column<0 || column>=(pv->columns-2)) {
283 return 0;
284 }
285 ncpv=(UPropsVectors *)pv;
286 row=_findRow(ncpv, c);
287 return row[2+column];
288 }
289
290 U_CAPI uint32_t * U_EXPORT2
291 upvec_getRow(const UPropsVectors *pv, int32_t rowIndex,
292 UChar32 *pRangeStart, UChar32 *pRangeEnd) {
293 uint32_t *row;
294 int32_t columns;
295
296 if(pv->isCompacted || rowIndex<0 || rowIndex>=pv->rows) {
297 return NULL;
298 }
299
300 columns=pv->columns;
301 row=pv->v+rowIndex*columns;
302 if(pRangeStart!=NULL) {
303 *pRangeStart=(UChar32)row[0];
304 }
305 if(pRangeEnd!=NULL) {
306 *pRangeEnd=(UChar32)row[1]-1;
307 }
308 return row+2;
309 }
310
311 static int32_t U_CALLCONV
312 upvec_compareRows(const void *context, const void *l, const void *r) {
313 const uint32_t *left=(const uint32_t *)l, *right=(const uint32_t *)r;
314 const UPropsVectors *pv=(const UPropsVectors *)context;
315 int32_t i, count, columns;
316
317 count=columns=pv->columns; /* includes start/limit columns */
318
319 /* start comparing after start/limit but wrap around to them */
320 i=2;
321 do {
322 if(left[i]!=right[i]) {
323 return left[i]<right[i] ? -1 : 1;
324 }
325 if(++i==columns) {
326 i=0;
327 }
328 } while(--count>0);
329
330 return 0;
331 }
332
333 U_CAPI void U_EXPORT2
334 upvec_compact(UPropsVectors *pv, UPVecCompactHandler *handler, void *context, UErrorCode *pErrorCode) {
335 uint32_t *row;
336 int32_t i, columns, valueColumns, rows, count;
337 UChar32 start, limit;
338
339 /* argument checking */
340 if(U_FAILURE(*pErrorCode)) {
341 return;
342 }
343 if(handler==NULL) {
344 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
345 return;
346 }
347 if(pv->isCompacted) {
348 return;
349 }
350
351 /* Set the flag now: Sorting and compacting destroys the builder data structure. */
352 pv->isCompacted=TRUE;
353
354 rows=pv->rows;
355 columns=pv->columns;
356 U_ASSERT(columns>=3); /* upvec_open asserts this */
357 valueColumns=columns-2; /* not counting start & limit */
358
359 /* sort the properties vectors to find unique vector values */
360 uprv_sortArray(pv->v, rows, columns*4,
361 upvec_compareRows, pv, FALSE, pErrorCode);
362 if(U_FAILURE(*pErrorCode)) {
363 return;
364 }
365
366 /*
367 * Find and set the special values.
368 * This has to do almost the same work as the compaction below,
369 * to find the indexes where the special-value rows will move.
370 */
371 row=pv->v;
372 count=-valueColumns;
373 for(i=0; i<rows; ++i) {
374 start=(UChar32)row[0];
375
376 /* count a new values vector if it is different from the current one */
377 if(count<0 || 0!=uprv_memcmp(row+2, row-valueColumns, valueColumns*4)) {
378 count+=valueColumns;
379 }
380
381 if(start>=UPVEC_FIRST_SPECIAL_CP) {
382 handler(context, start, start, count, row+2, valueColumns, pErrorCode);
383 if(U_FAILURE(*pErrorCode)) {
384 return;
385 }
386 }
387
388 row+=columns;
389 }
390
391 /* count is at the beginning of the last vector, add valueColumns to include that last vector */
392 count+=valueColumns;
393
394 /* Call the handler once more to signal the start of delivering real values. */
395 handler(context, UPVEC_START_REAL_VALUES_CP, UPVEC_START_REAL_VALUES_CP,
396 count, row-valueColumns, valueColumns, pErrorCode);
397 if(U_FAILURE(*pErrorCode)) {
398 return;
399 }
400
401 /*
402 * Move vector contents up to a contiguous array with only unique
403 * vector values, and call the handler function for each vector.
404 *
405 * This destroys the Properties Vector structure and replaces it
406 * with an array of just vector values.
407 */
408 row=pv->v;
409 count=-valueColumns;
410 for(i=0; i<rows; ++i) {
411 /* fetch these first before memmove() may overwrite them */
412 start=(UChar32)row[0];
413 limit=(UChar32)row[1];
414
415 /* add a new values vector if it is different from the current one */
416 if(count<0 || 0!=uprv_memcmp(row+2, pv->v+count, valueColumns*4)) {
417 count+=valueColumns;
418 uprv_memmove(pv->v+count, row+2, valueColumns*4);
419 }
420
421 if(start<UPVEC_FIRST_SPECIAL_CP) {
422 handler(context, start, limit-1, count, pv->v+count, valueColumns, pErrorCode);
423 if(U_FAILURE(*pErrorCode)) {
424 return;
425 }
426 }
427
428 row+=columns;
429 }
430
431 /* count is at the beginning of the last vector, add one to include that last vector */
432 pv->rows=count/valueColumns+1;
433 }
434
435 U_CAPI const uint32_t * U_EXPORT2
436 upvec_getArray(const UPropsVectors *pv, int32_t *pRows, int32_t *pColumns) {
437 if(!pv->isCompacted) {
438 return NULL;
439 }
440 if(pRows!=NULL) {
441 *pRows=pv->rows;
442 }
443 if(pColumns!=NULL) {
444 *pColumns=pv->columns-2;
445 }
446 return pv->v;
447 }
448
449 U_CAPI uint32_t * U_EXPORT2
450 upvec_cloneArray(const UPropsVectors *pv,
451 int32_t *pRows, int32_t *pColumns, UErrorCode *pErrorCode) {
452 uint32_t *clonedArray;
453 int32_t byteLength;
454
455 if(U_FAILURE(*pErrorCode)) {
456 return NULL;
457 }
458 if(!pv->isCompacted) {
459 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
460 return NULL;
461 }
462 byteLength=pv->rows*(pv->columns-2)*4;
463 clonedArray=(uint32_t *)uprv_malloc(byteLength);
464 if(clonedArray==NULL) {
465 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
466 return NULL;
467 }
468 uprv_memcpy(clonedArray, pv->v, byteLength);
469 if(pRows!=NULL) {
470 *pRows=pv->rows;
471 }
472 if(pColumns!=NULL) {
473 *pColumns=pv->columns-2;
474 }
475 return clonedArray;
476 }
477
478 U_CAPI UTrie2 * U_EXPORT2
479 upvec_compactToUTrie2WithRowIndexes(UPropsVectors *pv, UErrorCode *pErrorCode) {
480 UPVecToUTrie2Context toUTrie2={ NULL };
481 upvec_compact(pv, upvec_compactToUTrie2Handler, &toUTrie2, pErrorCode);
482 utrie2_freeze(toUTrie2.trie, UTRIE2_16_VALUE_BITS, pErrorCode);
483 if(U_FAILURE(*pErrorCode)) {
484 utrie2_close(toUTrie2.trie);
485 toUTrie2.trie=NULL;
486 }
487 return toUTrie2.trie;
488 }
489
490 /*
491 * TODO(markus): Add upvec_16BitsToUTrie2() function that enumerates all rows, extracts
492 * some 16-bit field and builds and returns a UTrie2.
493 */
494
495 U_CAPI void U_CALLCONV
496 upvec_compactToUTrie2Handler(void *context,
497 UChar32 start, UChar32 end,
498 int32_t rowIndex, uint32_t *row, int32_t columns,
499 UErrorCode *pErrorCode) {
500 UPVecToUTrie2Context *toUTrie2=(UPVecToUTrie2Context *)context;
501 if(start<UPVEC_FIRST_SPECIAL_CP) {
502 utrie2_setRange32(toUTrie2->trie, start, end, (uint32_t)rowIndex, TRUE, pErrorCode);
503 } else {
504 switch(start) {
505 case UPVEC_INITIAL_VALUE_CP:
506 toUTrie2->initialValue=rowIndex;
507 break;
508 case UPVEC_ERROR_VALUE_CP:
509 toUTrie2->errorValue=rowIndex;
510 break;
511 case UPVEC_START_REAL_VALUES_CP:
512 toUTrie2->maxValue=rowIndex;
513 if(rowIndex>0xffff) {
514 /* too many rows for a 16-bit trie */
515 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
516 } else {
517 toUTrie2->trie=utrie2_open(toUTrie2->initialValue,
518 toUTrie2->errorValue, pErrorCode);
519 }
520 break;
521 default:
522 break;
523 }
524 }
525 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial