icuSources/common/propsvec.cpp

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