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 } 526
