home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / tools / ulxfrm / ucmp16.c next >
Encoding:
C/C++ Source or Header  |  1999-08-16  |  11.0 KB  |  403 lines
  1. /*
  2. *****************************************************************************************
  3. *                                                                                       *
  4. * COPYRIGHT:                                                                            *
  5. *   (C) Copyright Taligent, Inc.,  1997                                                 *
  6. *   (C) Copyright International Business Machines Corporation,  1997-1998               *
  7. *   Licensed Material - Program-Property of IBM - All Rights Reserved.                  *
  8. *   US Government Users Restricted Rights - Use, duplication, or disclosure             *
  9. *   restricted by GSA ADP Schedule Contract with IBM Corp.                              *
  10. *                                                                                       *
  11. *****************************************************************************************
  12. */
  13. /*===============================================================================
  14.  *
  15.  * File cmpshrta.cpp
  16.  *
  17.  * Modification History:
  18.  *
  19.  *  Date        Name        Description
  20.  *  2/5/97      aliu        Added CompactIntArray streamIn and streamOut methods.
  21.  *  3/4/97      aliu        Tuned performance of CompactIntArray constructor,
  22.  * 05/07/97     helena      Added isBogus()
  23.  *                          based on performance data indicating that this was slow.
  24.  * 07/15/98        erm            Synched with Java 1.2 CompactShortArray.java.
  25.  * 07/30/98        erm            Added changes from 07/29/98 code review.
  26.  *===============================================================================
  27.  */
  28. #include "ucmp16.h"
  29. #include "cmemory.h"
  30.  
  31.  
  32.  
  33.  
  34.  
  35. #define arrayRegionMatches(source, sourceStart, target, targetStart, len) (icu_memcmp(&source[sourceStart], &target[targetStart], len * sizeof(int16_t)) != 0)
  36.  
  37. /* internal constants*/
  38. #define UCMP16_kMaxUnicode_int 65535
  39. #define UCMP16_kUnicodeCount_int (UCMP16_kMaxUnicode_int + 1)
  40. #define UCMP16_kBlockShift_int 7
  41. #define UCMP16_kBlockCount_int (1 << UCMP16_kBlockShift_int)
  42. #define UCMP16_kBlockBytes_int (UCMP16_kBlockCount_int * sizeof(int16_t))
  43. #define UCMP16_kIndexShift_int (16 - UCMP16_kBlockShift_int)
  44. #define UCMP16_kIndexCount_int (1 << UCMP16_kIndexShift_int)
  45. #define UCMP16_kBlockMask_int (UCMP16_kBlockCount_int - 1)
  46.  
  47.  
  48. const int32_t UCMP16_kMaxUnicode = UCMP16_kMaxUnicode_int;
  49. const int32_t UCMP16_kUnicodeCount = UCMP16_kUnicodeCount_int;
  50. const int32_t UCMP16_kBlockShift = UCMP16_kBlockShift_int;
  51. const int32_t UCMP16_kBlockCount = UCMP16_kBlockCount_int;
  52. const int32_t UCMP16_kBlockBytes = UCMP16_kBlockBytes_int;
  53. const int32_t UCMP16_kIndexShift = UCMP16_kIndexShift_int;
  54. const int32_t UCMP16_kIndexCount = UCMP16_kIndexCount_int;
  55. const uint32_t UCMP16_kBlockMask = UCMP16_kBlockMask_int;
  56.  
  57. /**
  58.  * Sets the array to the invalid memory state.
  59.  */
  60. static CompactShortArray* setToBogus(CompactShortArray* array);
  61. static void touchBlock(CompactShortArray* this,
  62.                int32_t i,
  63.                int16_t value);
  64. static bool_t blockTouched(const CompactShortArray* this,
  65.                int32_t i);
  66.  
  67.  
  68. /* debug flags*/
  69. /*=======================================================*/
  70.  
  71. int32_t ucmp16_getkUnicodeCount()
  72. {return UCMP16_kUnicodeCount;}
  73.  
  74. int32_t ucmp16_getkBlockCount()
  75. {return UCMP16_kBlockCount;}
  76.  
  77. int32_t ucmp16_getkIndexCount()
  78. { return UCMP16_kIndexCount;}
  79.  
  80. CompactShortArray* ucmp16_open(int16_t defaultValue)
  81. {
  82.   int32_t i;
  83.   CompactShortArray* this = (CompactShortArray*) icu_malloc(sizeof(CompactShortArray));
  84.   if (this == NULL) return NULL;
  85.   
  86.   this->fCount = UCMP16_kUnicodeCount;
  87.   this->fCompact = FALSE; 
  88.   this->fBogus = FALSE;
  89.   this->fArray = NULL;
  90.   this->fIndex = NULL;
  91.   this->fHashes = NULL; 
  92.   this->fDefaultValue = defaultValue;
  93.   
  94.   this->fArray = (int16_t*)icu_malloc(UCMP16_kUnicodeCount * sizeof(int16_t));
  95.   if (this->fArray == NULL)
  96.     {
  97.       this->fBogus = TRUE;
  98.       return NULL;
  99.     }
  100.   
  101.   this->fIndex = (uint16_t*)icu_malloc(UCMP16_kIndexCount * sizeof(uint16_t));
  102.   if (this->fIndex == NULL)
  103.     {
  104.       icu_free(this->fArray);
  105.       this->fArray = NULL;
  106.       
  107.       this->fBogus = TRUE;
  108.       return NULL;
  109.     }
  110.   
  111.   this->kBlockShift = UCMP16_kBlockShift;
  112.   this->kBlockMask = UCMP16_kBlockMask;
  113.   for (i = 0; i < UCMP16_kUnicodeCount; i += 1)
  114.     {
  115.       this->fArray[i] = defaultValue;
  116.     }
  117.   
  118.   this->fHashes =(int32_t*)icu_malloc(UCMP16_kIndexCount * sizeof(int32_t));
  119.   if (this->fHashes == NULL)
  120.     {
  121.       icu_free(this->fArray);
  122.       icu_free(this->fIndex);
  123.       this->fBogus = TRUE;
  124.       return NULL;
  125.     }
  126.   
  127.   for (i = 0; i < UCMP16_kIndexCount; i += 1)
  128.     {
  129.       this->fIndex[i] = (uint16_t)(i << UCMP16_kBlockShift);
  130.       this->fHashes[i] = 0;
  131.     }
  132.   
  133.   return this;
  134. }
  135.  
  136. CompactShortArray* ucmp16_openAdopt(uint16_t *indexArray,
  137.                     int16_t *newValues, 
  138.                     int32_t count,
  139.                     int16_t defaultValue)
  140. {
  141.   CompactShortArray* this = (CompactShortArray*) icu_malloc(sizeof(CompactShortArray));
  142.   if (this == NULL) return NULL;
  143.   this->fHashes = NULL;
  144.   this->fCount = count; 
  145.   this->fDefaultValue = defaultValue;
  146.   this->fBogus = FALSE;
  147.   this->fArray = newValues;
  148.   this->fIndex = indexArray;
  149.   this->fCompact = count < UCMP16_kUnicodeCount;
  150.   this->kBlockShift = UCMP16_kBlockShift;
  151.   this->kBlockMask = UCMP16_kBlockMask;
  152.  
  153.   return this;
  154. }
  155.  
  156. CompactShortArray* ucmp16_openAdoptWithBlockShift(uint16_t *indexArray,
  157.                           int16_t *newValues,
  158.                           int32_t count,
  159.                           int16_t defaultValue,
  160.                           int32_t blockShift)
  161. {
  162.   CompactShortArray* this = ucmp16_openAdopt(indexArray,
  163.                          newValues,
  164.                          count,
  165.                          defaultValue);
  166.   if (this == NULL) return NULL;
  167.   
  168.   this->kBlockShift  = blockShift;
  169.   this->kBlockMask = (uint32_t) (((uint32_t)1 << (uint32_t)blockShift) - (uint32_t)1);
  170.   
  171.   return this;
  172. }
  173.  
  174. /*=======================================================*/
  175.  
  176. void ucmp16_close(CompactShortArray* this)
  177. {
  178.   icu_free(this->fArray);
  179.   icu_free(this->fIndex);
  180.   icu_free(this->fHashes);
  181.   icu_free(this);
  182.  
  183.   return;
  184. }
  185.  
  186. CompactShortArray* setToBogus(CompactShortArray* this)
  187. {
  188.   icu_free(this->fArray);
  189.   this->fArray = NULL;
  190.   
  191.   icu_free(this->fIndex);
  192.   this->fIndex = NULL;
  193.   
  194.   icu_free(this->fHashes);
  195.   this->fHashes = NULL;
  196.   
  197.   this->fCount = 0;
  198.   this->fCompact = FALSE;
  199.   this->fBogus = TRUE;
  200.   
  201.   return this;
  202. }
  203.  
  204.  
  205. void ucmp16_expand(CompactShortArray* this)
  206. {
  207.   if (this->fCompact)
  208.     {
  209.       int32_t i;
  210.       int16_t *tempArray = (int16_t*)icu_malloc(UCMP16_kUnicodeCount * sizeof(int16_t));
  211.       
  212.       if (tempArray == NULL)
  213.     {
  214.       this->fBogus = TRUE;
  215.       return;
  216.     }
  217.       
  218.       for (i = 0; i < UCMP16_kUnicodeCount; i += 1)
  219.     {
  220.       tempArray[i] = ucmp16_get(this, (UChar)i);  /* HSYS : How expand?*/
  221.         }
  222.       
  223.       for (i = 0; i < (1 << (16 - this->kBlockShift)); i += 1)
  224.     {
  225.       this->fIndex[i] = (uint16_t)(i<<this->kBlockShift);
  226.         }
  227.       
  228.       icu_free(this->fArray);
  229.       this->fArray = tempArray;
  230.       this->fCompact = FALSE;
  231.     }
  232. }
  233.  
  234. void ucmp16_set(CompactShortArray* this,
  235.         UChar c,
  236.         int16_t value)
  237. {
  238.   if (this->fCompact)
  239.     {
  240.       ucmp16_expand(this);
  241.       if (this->fBogus) return;
  242.     }
  243.   
  244.   this->fArray[(int32_t)c] = value;
  245.   
  246.   if (value != this->fDefaultValue)
  247.     {
  248.       touchBlock(this, c >> this->kBlockShift, value);
  249.     }
  250. }
  251.  
  252.  
  253. void ucmp16_setRange(CompactShortArray* this, 
  254.              UChar start,
  255.              UChar end,
  256.              int16_t value)
  257. {
  258.   int32_t i;
  259.   if (this->fCompact)
  260.     {
  261.       ucmp16_expand(this);
  262.       if (this->fBogus)  return;
  263.     }
  264.   if (value != this->fDefaultValue)
  265.     {
  266.       for (i = start; i <= end; i += 1)
  267.     {
  268.        this->fArray[i] = value;
  269.       touchBlock(this, i >> this->kBlockShift, value);
  270.     }
  271.     }
  272.   else
  273.     {
  274.       for (i = start; i <= end; i += 1)      this->fArray[i] = value;
  275.     }
  276. }
  277.  
  278.  
  279. /*=======================================================*/
  280. void ucmp16_compact(CompactShortArray* this)
  281. {
  282.   if (!this->fCompact)
  283.     {
  284.       int32_t limitCompacted = 0;
  285.       int32_t i, iBlockStart;
  286.       int16_t iUntouched = -1;
  287.       
  288.       for (i = 0, iBlockStart = 0; i < (1 << (16 - this->kBlockShift)); i += 1, iBlockStart += (1 << this->kBlockShift))
  289.     {
  290.       bool_t touched = blockTouched(this, i);
  291.       
  292.       this->fIndex[i] = 0xFFFF;
  293.       
  294.       if (!touched && iUntouched != -1)
  295.         {
  296.           /* If no values in this block were set, we can just set its
  297.            * index to be the same as some other block with no values
  298.            * set, assuming we've seen one yet.
  299.            */
  300.           this->fIndex[i] = iUntouched;
  301.             }
  302.       else
  303.         {
  304.           int32_t j, jBlockStart;
  305.           
  306.           for (j = 0, jBlockStart = 0;
  307.            j < limitCompacted;
  308.            j += 1, jBlockStart += (1 << this->kBlockShift))
  309.         {
  310.           if (this->fHashes[i] == this->fHashes[j] &&
  311.               arrayRegionMatches(this->fArray,
  312.                      iBlockStart,
  313.                      this->fArray, 
  314.                      jBlockStart,
  315.                      (1 << this->kBlockShift)))
  316.             {
  317.               this->fIndex[i] = (int16_t)jBlockStart;
  318.                     }
  319.                 }
  320.           
  321.                 /* TODO: verify this is correct*/
  322.           if (this->fIndex[i] == 0xFFFF)
  323.         {
  324.           /* we didn't match, so copy & update*/
  325.           icu_memcpy(&(this->fArray[jBlockStart]), 
  326.                  &(this->fArray[iBlockStart]),
  327.                  (1 << this->kBlockShift)*sizeof(int16_t));
  328.           
  329.           this->fIndex[i] = (int16_t)jBlockStart;
  330.           this->fHashes[j] = this->fHashes[i];
  331.           limitCompacted += 1;
  332.           
  333.           if (!touched)
  334.             {
  335.               /* If this is the first untouched block we've seen,*/
  336.               /* remember its index.*/
  337.               iUntouched = (int16_t)jBlockStart;
  338.                     }
  339.                 }
  340.             }
  341.         }
  342.  
  343.         /* we are done compacting, so now make the array shorter*/
  344.       {
  345.     int32_t newSize = limitCompacted * (1 << this->kBlockShift);
  346.     int16_t *result = (int16_t*) icu_malloc(sizeof(int16_t) * newSize);
  347.     
  348.     icu_memcpy(result, this->fArray, newSize * sizeof(int16_t));
  349.     
  350.     icu_free(this->fArray);
  351.     this->fArray = result;
  352.     this->fCount = newSize;
  353.     icu_free(this->fHashes);
  354.     this->fHashes = NULL;
  355.     
  356.     this->fCompact = TRUE;
  357.       }
  358.     }
  359. }
  360.  
  361. /**
  362.  * Query whether a specified block was "touched", i.e. had a value set.
  363.  * Untouched blocks can be skipped when compacting the array
  364.  */
  365.  
  366. int16_t ucmp16_getDefaultValue(const CompactShortArray* this)
  367. {
  368.   return this->fDefaultValue;
  369. }
  370.  
  371.  
  372. void touchBlock(CompactShortArray* this,
  373.         int32_t i,
  374.         int16_t value)
  375. {
  376.   this->fHashes[i] = (this->fHashes[i] + (value << 1)) | 1;
  377. }
  378.  
  379. bool_t blockTouched(const CompactShortArray* this, int32_t i)
  380. {
  381.   return (this->fHashes[i] != 0);
  382. }
  383.  
  384.  
  385. const int16_t*
  386. ucmp16_getArray(const CompactShortArray* this)
  387. {
  388.     return this->fArray;
  389. }
  390.  
  391. const uint16_t*
  392. ucmp16_getIndex(const CompactShortArray* this)
  393. {
  394.     return this->fIndex;
  395. }
  396.  
  397. uint32_t 
  398. ucmp16_getCount(const CompactShortArray* this)
  399. {
  400.     return this->fCount;
  401. }
  402.  
  403.