home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / common / ucmp16.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-08-16  |  11.2 KB  |  384 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_obj 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_obj,
  62.                int32_t i,
  63.                int16_t value);
  64. static bool_t blockTouched(const CompactShortArray* this_obj,
  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. CompactShortArray* ucmp16_open(int16_t defaultValue)
  78. {
  79.   int32_t i;
  80.   CompactShortArray* this_obj = (CompactShortArray*) icu_malloc(sizeof(CompactShortArray));
  81.   if (this_obj == NULL) return NULL;
  82.   
  83.   this_obj->fCount = UCMP16_kUnicodeCount;
  84.   this_obj->fCompact = FALSE; 
  85.   this_obj->fBogus = FALSE;
  86.   this_obj->fArray = NULL;
  87.   this_obj->fIndex = NULL;
  88.   this_obj->fHashes = NULL; 
  89.   this_obj->fDefaultValue = defaultValue;
  90.   
  91.   this_obj->fArray = (int16_t*)icu_malloc(UCMP16_kUnicodeCount * sizeof(int16_t));
  92.   if (this_obj->fArray == NULL)
  93.     {
  94.       this_obj->fBogus = TRUE;
  95.       return NULL;
  96.     }
  97.   
  98.   this_obj->fIndex = (uint16_t*)icu_malloc(UCMP16_kIndexCount * sizeof(uint16_t));
  99.   if (this_obj->fIndex == NULL)
  100.     {
  101.       icu_free(this_obj->fArray);
  102.       this_obj->fArray = NULL;
  103.       
  104.       this_obj->fBogus = TRUE;
  105.       return NULL;
  106.     }
  107.   
  108.   this_obj->kBlockShift = UCMP16_kBlockShift;
  109.   this_obj->kBlockMask = UCMP16_kBlockMask;
  110.   for (i = 0; i < UCMP16_kUnicodeCount; i += 1)
  111.     {
  112.       this_obj->fArray[i] = defaultValue;
  113.     }
  114.   
  115.   this_obj->fHashes =(int32_t*)icu_malloc(UCMP16_kIndexCount * sizeof(int32_t));
  116.   if (this_obj->fHashes == NULL)
  117.     {
  118.       icu_free(this_obj->fArray);
  119.       icu_free(this_obj->fIndex);
  120.       this_obj->fBogus = TRUE;
  121.       return NULL;
  122.     }
  123.   
  124.   for (i = 0; i < UCMP16_kIndexCount; i += 1)
  125.     {
  126.       this_obj->fIndex[i] = (uint16_t)(i << UCMP16_kBlockShift);
  127.       this_obj->fHashes[i] = 0;
  128.     }
  129.   
  130.   return this_obj;
  131. }
  132.  
  133. CompactShortArray* ucmp16_openAdopt(uint16_t *indexArray,
  134.                     int16_t *newValues, 
  135.                     int32_t count,
  136.                     int16_t defaultValue)
  137. {
  138.   CompactShortArray* this_obj = (CompactShortArray*) icu_malloc(sizeof(CompactShortArray));
  139.   if (this_obj == NULL) return NULL;
  140.   this_obj->fHashes = NULL;
  141.   this_obj->fCount = count; 
  142.   this_obj->fDefaultValue = defaultValue;
  143.   this_obj->fBogus = FALSE;
  144.   this_obj->fArray = newValues;
  145.   this_obj->fIndex = indexArray;
  146.   this_obj->fCompact = count < UCMP16_kUnicodeCount;
  147.   this_obj->kBlockShift = UCMP16_kBlockShift;
  148.   this_obj->kBlockMask = UCMP16_kBlockMask;
  149.  
  150.   return this_obj;
  151. }
  152.  
  153. CompactShortArray* ucmp16_openAdoptWithBlockShift(uint16_t *indexArray,
  154.                           int16_t *newValues,
  155.                           int32_t count,
  156.                           int16_t defaultValue,
  157.                           int32_t blockShift)
  158. {
  159.   CompactShortArray* this_obj = ucmp16_openAdopt(indexArray,
  160.                          newValues,
  161.                          count,
  162.                          defaultValue);
  163.   if (this_obj == NULL) return NULL;
  164.   
  165.   this_obj->kBlockShift  = blockShift;
  166.   this_obj->kBlockMask = (uint32_t) (((uint32_t)1 << (uint32_t)blockShift) - (uint32_t)1);
  167.   
  168.   return this_obj;
  169. }
  170.  
  171. /*=======================================================*/
  172.  
  173. void ucmp16_close(CompactShortArray* this_obj)
  174. {
  175.   icu_free(this_obj->fArray);
  176.   icu_free(this_obj->fIndex);
  177.   icu_free(this_obj->fHashes);
  178.   icu_free(this_obj);
  179.  
  180.   return;
  181. }
  182.  
  183. CompactShortArray* setToBogus(CompactShortArray* this_obj)
  184. {
  185.   icu_free(this_obj->fArray);
  186.   this_obj->fArray = NULL;
  187.   
  188.   icu_free(this_obj->fIndex);
  189.   this_obj->fIndex = NULL;
  190.   
  191.   icu_free(this_obj->fHashes);
  192.   this_obj->fHashes = NULL;
  193.   
  194.   this_obj->fCount = 0;
  195.   this_obj->fCompact = FALSE;
  196.   this_obj->fBogus = TRUE;
  197.   
  198.   return this_obj;
  199. }
  200.  
  201.  
  202. void ucmp16_expand(CompactShortArray* this_obj)
  203. {
  204.   if (this_obj->fCompact)
  205.     {
  206.       int32_t i;
  207.       int16_t *tempArray = (int16_t*)icu_malloc(UCMP16_kUnicodeCount * sizeof(int16_t));
  208.       
  209.       if (tempArray == NULL)
  210.     {
  211.       this_obj->fBogus = TRUE;
  212.       return;
  213.     }
  214.       
  215.       for (i = 0; i < UCMP16_kUnicodeCount; i += 1)
  216.     {
  217.       tempArray[i] = ucmp16_get(this_obj, (UChar)i);  /* HSYS : How expand?*/
  218.         }
  219.       
  220.       for (i = 0; i < (1 << (16 - this_obj->kBlockShift)); i += 1)
  221.     {
  222.       this_obj->fIndex[i] = (uint16_t)(i<<this_obj->kBlockShift);
  223.         }
  224.       
  225.       icu_free(this_obj->fArray);
  226.       this_obj->fArray = tempArray;
  227.       this_obj->fCompact = FALSE;
  228.     }
  229. }
  230.  
  231. void ucmp16_set(CompactShortArray* this_obj,
  232.         UChar c,
  233.         int16_t value)
  234. {
  235.   if (this_obj->fCompact)
  236.     {
  237.       ucmp16_expand(this_obj);
  238.       if (this_obj->fBogus) return;
  239.     }
  240.   
  241.   this_obj->fArray[(int32_t)c] = value;
  242.   
  243.   if (value != this_obj->fDefaultValue)
  244.     {
  245.       touchBlock(this_obj, c >> this_obj->kBlockShift, value);
  246.     }
  247. }
  248.  
  249.  
  250. void ucmp16_setRange(CompactShortArray* this_obj, 
  251.              UChar start,
  252.              UChar end,
  253.              int16_t value)
  254. {
  255.   int32_t i;
  256.   if (this_obj->fCompact)
  257.     {
  258.       ucmp16_expand(this_obj);
  259.       if (this_obj->fBogus)  return;
  260.     }
  261.   if (value != this_obj->fDefaultValue)
  262.     {
  263.       for (i = start; i <= end; i += 1)
  264.     {
  265.        this_obj->fArray[i] = value;
  266.       touchBlock(this_obj, i >> this_obj->kBlockShift, value);
  267.     }
  268.     }
  269.   else
  270.     {
  271.       for (i = start; i <= end; i += 1)      this_obj->fArray[i] = value;
  272.     }
  273. }
  274.  
  275.  
  276. /*=======================================================*/
  277. void ucmp16_compact(CompactShortArray* this_obj)
  278. {
  279.   if (!this_obj->fCompact)
  280.     {
  281.       int32_t limitCompacted = 0;
  282.       int32_t i, iBlockStart;
  283.       int16_t iUntouched = -1;
  284.       
  285.       for (i = 0, iBlockStart = 0; i < (1 << (16 - this_obj->kBlockShift)); i += 1, iBlockStart += (1 << this_obj->kBlockShift))
  286.     {
  287.       bool_t touched = blockTouched(this_obj, i);
  288.       
  289.       this_obj->fIndex[i] = 0xFFFF;
  290.       
  291.       if (!touched && iUntouched != -1)
  292.         {
  293.           /* If no values in this_obj block were set, we can just set its
  294.            * index to be the same as some other block with no values
  295.            * set, assuming we've seen one yet.
  296.            */
  297.           this_obj->fIndex[i] = iUntouched;
  298.             }
  299.       else
  300.         {
  301.           int32_t j, jBlockStart;
  302.           
  303.           for (j = 0, jBlockStart = 0;
  304.            j < limitCompacted;
  305.            j += 1, jBlockStart += (1 << this_obj->kBlockShift))
  306.         {
  307.           if (this_obj->fHashes[i] == this_obj->fHashes[j] &&
  308.               arrayRegionMatches(this_obj->fArray,
  309.                      iBlockStart,
  310.                      this_obj->fArray, 
  311.                      jBlockStart,
  312.                      (1 << this_obj->kBlockShift)))
  313.             {
  314.               this_obj->fIndex[i] = (int16_t)jBlockStart;
  315.                     }
  316.                 }
  317.           
  318.                 /* TODO: verify this_obj is correct*/
  319.           if (this_obj->fIndex[i] == 0xFFFF)
  320.         {
  321.           /* we didn't match, so copy & update*/
  322.           icu_memcpy(&(this_obj->fArray[jBlockStart]), 
  323.                  &(this_obj->fArray[iBlockStart]),
  324.                  (1 << this_obj->kBlockShift)*sizeof(int16_t));
  325.           
  326.           this_obj->fIndex[i] = (int16_t)jBlockStart;
  327.           this_obj->fHashes[j] = this_obj->fHashes[i];
  328.           limitCompacted += 1;
  329.           
  330.           if (!touched)
  331.             {
  332.               /* If this_obj is the first untouched block we've seen,*/
  333.               /* remember its index.*/
  334.               iUntouched = (int16_t)jBlockStart;
  335.                     }
  336.                 }
  337.             }
  338.         }
  339.  
  340.         /* we are done compacting, so now make the array shorter*/
  341.       {
  342.     int32_t newSize = limitCompacted * (1 << this_obj->kBlockShift);
  343.     int16_t *result = (int16_t*) icu_malloc(sizeof(int16_t) * newSize);
  344.     
  345.     icu_memcpy(result, this_obj->fArray, newSize * sizeof(int16_t));
  346.     
  347.     icu_free(this_obj->fArray);
  348.     this_obj->fArray = result;
  349.     this_obj->fCount = newSize;
  350.     icu_free(this_obj->fHashes);
  351.     this_obj->fHashes = NULL;
  352.     
  353.     this_obj->fCompact = TRUE;
  354.       }
  355.     }
  356. }
  357.  
  358. /**
  359.  * Query whether a specified block was "touched", i.e. had a value set.
  360.  * Untouched blocks can be skipped when compacting the array
  361.  */
  362.  
  363. int16_t ucmp16_getDefaultValue(const CompactShortArray* this_obj)
  364. {
  365.   return this_obj->fDefaultValue;
  366. }
  367.  
  368.  
  369. void touchBlock(CompactShortArray* this_obj,
  370.         int32_t i,
  371.         int16_t value)
  372. {
  373.   this_obj->fHashes[i] = (this_obj->fHashes[i] + (value << 1)) | 1;
  374. }
  375.  
  376. bool_t blockTouched(const CompactShortArray* this_obj, int32_t i)
  377. {
  378.   return (this_obj->fHashes[i] != 0);
  379. }
  380.  
  381.  
  382.  
  383.  
  384.