home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / c / objam01.lha / objam / runtime / sarray.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-10  |  11.7 KB  |  451 lines
  1. /*
  2. ** ObjectiveAmiga: Sparse Arrays for Objective C dispatch tables
  3. ** See GNU:lib/libobjam/ReadMe for details
  4. */
  5.  
  6.  
  7. #include <libraries/objc.h>
  8. #include <clib/objc_protos.h>
  9.  
  10. #include "misc.h" /* For the ANSI function emulations */
  11. #include "zone.h" /* For quick access to the default zone */
  12.  
  13.  
  14. int nbuckets = 0;
  15. int nindices = 0;
  16. int narrays = 0;
  17. int idxsize = 0;
  18.  
  19. int __nbuckets(void) {return nbuckets;}
  20. int __nindices(void) {return nindices;}
  21. int __narrays(void) {return narrays;}
  22. int __idxsize(void) {return idxsize;}
  23.  
  24. #ifdef OBJC_SPARSE2
  25. const char* __objc_sparse2_id = "2 level sparse indices";
  26. #endif
  27.  
  28. #ifdef OBJC_SPARSE3
  29. const char* __objc_sparse3_id = "3 level sparse indices";
  30. #endif
  31.  
  32. void
  33. sarray_at_put(struct sarray* array, sidx index, void* element)
  34. {
  35. #ifdef OBJC_SPARSE3
  36.   struct sindex** the_index;
  37. #endif
  38.   struct sbucket** the_bucket;
  39. #ifdef OBJC_SPARSE3
  40.   size_t ioffset;
  41. #endif
  42.   size_t boffset;
  43.   size_t eoffset;
  44. #ifdef PRECOMPUTE_SELECTORS
  45.   union sofftype xx; 
  46.   xx.idx = index;
  47. #ifdef OBJC_SPARSE3
  48.   ioffset = xx.off.ioffset;
  49. #endif
  50.   boffset = xx.off.boffset;
  51.   eoffset = xx.off.eoffset;
  52. #else /* not PRECOMPUTE_SELECTORS */
  53. #ifdef OBJC_SPARSE3
  54.   ioffset = index/INDEX_CAPACITY;
  55.   boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
  56.   eoffset = index%BUCKET_SIZE;
  57. #else
  58.   boffset = index/BUCKET_SIZE;
  59.   eoffset = index%BUCKET_SIZE;
  60. #endif
  61. #endif /* not PRECOMPUTE_SELECTORS */
  62.  
  63.   assert(soffset_decode(index) < array->capacity); /* Range check */
  64.  
  65. #ifdef OBJC_SPARSE3
  66.   the_index = &(array->indices[ioffset]);
  67.   the_bucket = &((*the_index)->buckets[boffset]);
  68. #else
  69.   the_bucket = &(array->buckets[boffset]);
  70. #endif
  71.   
  72.   if ((*the_bucket)->elems[eoffset] == element)
  73.     return;        /* great! we just avoided a lazy copy */
  74.  
  75. #ifdef OBJC_SPARSE3
  76.  
  77.   /* First, perform lazy copy/allocation of index if needed */
  78.  
  79.   if ((*the_index) == array->empty_index) {
  80.  
  81.     /* The index was previously empty, allocate a new */
  82.     *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
  83.     memcpy(*the_index, array->empty_index, sizeof(struct sindex));
  84.     (*the_index)->version = array->version;
  85.     the_bucket = &((*the_index)->buckets[boffset]);
  86.     nindices += 1;
  87.     
  88.   } else if ((*the_index)->version != array->version) {
  89.  
  90.     /* This index must be lazy copied */
  91.     struct sindex* old_index = *the_index;
  92.     *the_index = (struct sindex*)__objc_xmalloc(sizeof(struct sindex));
  93.     memcpy( *the_index,old_index, sizeof(struct sindex));
  94.     (*the_index)->version = array->version;
  95.     the_bucket = &((*the_index)->buckets[boffset]);
  96.     nindices += 1;
  97.     
  98.   }
  99.  
  100. #endif /* OBJC_SPARSE3 */
  101.  
  102.   /* next, perform lazy allocation/copy of the bucket if needed */
  103.  
  104.   if ((*the_bucket) == array->empty_bucket) {
  105.  
  106.     /* The bucket was previously empty (or something like that), */
  107.     /* allocate a new.  This is the effect of `lazy' allocation */  
  108.     *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
  109.     memcpy( *the_bucket,array->empty_bucket, sizeof(struct sbucket));
  110.     (*the_bucket)->version = array->version;
  111.     nbuckets += 1;
  112.  
  113.   } else if ((*the_bucket)->version != array->version) {
  114.  
  115.     /* Perform lazy copy. */
  116.     struct sbucket* old_bucket = *the_bucket;
  117.     *the_bucket = (struct sbucket*)__objc_xmalloc(sizeof(struct sbucket));
  118.     memcpy( *the_bucket,old_bucket, sizeof(struct sbucket));
  119.     (*the_bucket)->version = array->version;
  120.     nbuckets += 1;
  121.  
  122.   }
  123.   (*the_bucket)->elems[eoffset] = element;
  124. }
  125.  
  126. void
  127. sarray_at_put_safe(struct sarray* array, sidx index, void* element)
  128. {
  129.   if(soffset_decode(index) >= array->capacity)
  130.     sarray_realloc(array, soffset_decode(index)+1);
  131.   sarray_at_put(array, index, element);
  132. }
  133.  
  134. struct sarray* 
  135. sarray_new (int size, void* default_element)
  136. {
  137. #ifdef OBJC_SPARSE3
  138.   size_t num_indices = ((size-1)/(INDEX_CAPACITY))+1;
  139. #else /* OBJC_SPARSE2 */
  140.   size_t num_indices = ((size-1)/BUCKET_SIZE)+1;
  141. #endif
  142.   int counter;
  143.   struct sarray* arr;
  144.  
  145.   assert(size > 0);
  146.  
  147.   /* Allocate core array */
  148.   arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
  149.   arr->version = 0;
  150.   narrays  += 1;
  151.   
  152.   /* Initialize members */
  153. #ifdef OBJC_SPARSE3
  154.   arr->capacity = num_indices*INDEX_CAPACITY;
  155.   arr->indices = (struct sindex**) 
  156.     __objc_xmalloc(sizeof(struct sindex*)*num_indices);
  157.   idxsize  += num_indices;
  158.  
  159.   arr->empty_index = (struct sindex*) __objc_xmalloc(sizeof(struct sindex));
  160.   arr->empty_index->version = 0;
  161.   nindices += 1;
  162.  
  163. #else /* OBJC_SPARSE2 */
  164.   arr->capacity = num_indices*BUCKET_SIZE;
  165.   arr->buckets = (struct sbucket**) 
  166.     __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
  167.   idxsize  += num_indices;
  168.  
  169. #endif
  170.  
  171.   arr->empty_bucket = (struct sbucket*) __objc_xmalloc(sizeof(struct sbucket));
  172.   arr->empty_bucket->version = 0;
  173.   nbuckets += 1;
  174.  
  175.   arr->ref_count = 1;
  176.   arr->is_copy_of = (struct sarray*)0;
  177.   
  178.   for (counter=0; counter<BUCKET_SIZE; counter++)
  179.     arr->empty_bucket->elems[counter] = default_element;
  180.  
  181. #ifdef OBJC_SPARSE3
  182.   for (counter=0; counter<INDEX_SIZE; counter++)
  183.     arr->empty_index->buckets[counter] = arr->empty_bucket;
  184.  
  185.   for (counter=0; counter<num_indices; counter++)
  186.     arr->indices[counter] = arr->empty_index;
  187.  
  188. #else /* OBJC_SPARSE2 */
  189.  
  190.   for (counter=0; counter<num_indices; counter++)
  191.     arr->buckets[counter] = arr->empty_bucket;
  192.  
  193. #endif
  194.  
  195.   return arr;
  196. }
  197.  
  198.  
  199.  
  200. /* Reallocate the sparse array to hold `newsize' entries */
  201.  
  202. void 
  203. sarray_realloc(struct sarray* array, int newsize)
  204. {
  205. #ifdef OBJC_SPARSE3
  206.   int old_max_index = (array->capacity-1)/INDEX_CAPACITY;
  207.   int new_max_index = ((newsize-1)/INDEX_CAPACITY);
  208.   int rounded_size = (new_max_index+1)*INDEX_CAPACITY;
  209.  
  210. #else /* OBJC_SPARSE2 */
  211.   int old_max_index = (array->capacity-1)/BUCKET_SIZE;
  212.   int new_max_index = ((newsize-1)/BUCKET_SIZE);
  213.   int rounded_size = (new_max_index+1)*BUCKET_SIZE;
  214.  
  215. #endif
  216.  
  217.   int counter;
  218.  
  219.   assert(newsize > 0);
  220.  
  221.   /* The size is the same, just ignore the request */
  222.   if(rounded_size == array->capacity)
  223.     return;
  224.  
  225.   assert(array->ref_count == 1);    /* stop if lazy copied... */
  226.  
  227.   if(rounded_size < array->capacity) 
  228.     {
  229.       /* update capacity */
  230.       array->capacity = rounded_size;
  231.  
  232.       /* free buckets above new_max_index */
  233.       for(counter = old_max_index; counter > new_max_index; counter-- ) {
  234. #ifdef OBJC_SPARSE3
  235.     struct sindex* idx = array->indices[counter];
  236.     if((idx != array->empty_index) && (idx->version == array->version)) {
  237.       int c2; 
  238.       for(c2=0; c2<INDEX_SIZE; c2++) {
  239.         struct sbucket* bkt = idx->buckets[c2];
  240.         if((bkt != array->empty_bucket) && (bkt->version == array->version))
  241.           {
  242.         __objc_xfree(bkt);
  243.         nbuckets -= 1;
  244.           }
  245.       }
  246.       __objc_xfree(idx);
  247.       nindices -= 1;
  248.     }
  249. #else /* OBJC_SPARSE2 */
  250.     struct sbucket* bkt = array->buckets[counter];
  251.     if ((bkt != array->empty_bucket) && (bkt->version == array->version))
  252.       {
  253.         __objc_xfree(bkt);
  254.         nbuckets -= 1;
  255.       }
  256. #endif
  257.       }
  258.       
  259. #ifdef OBJC_SPARSE3
  260.       /* realloc to free the space above new_max_index */
  261.       array->indices = (struct sindex**)
  262.     __objc_xrealloc(array->indices, 
  263.             (new_max_index+1)*sizeof(struct sindex*));
  264. #else /* OBJC_SPARSE2 */
  265.       array->buckets = (struct sbucket**)
  266.     __objc_xrealloc(array->buckets, 
  267.             (new_max_index+1)*sizeof(struct sbucket*));
  268. #endif      
  269.       idxsize -= (old_max_index-new_max_index);
  270.  
  271.       return;
  272.     }
  273.  
  274.   /* We are asked to extend the array -- reallocate the bucket table, */
  275.   /* and insert empty_bucket in newly allocated places. */
  276.   if(rounded_size > array->capacity) 
  277.     {
  278.       /* update capacity */
  279.       array->capacity = rounded_size;
  280.  
  281. #ifdef OBJC_SPARSE3
  282.       /* realloc to make room in table above old_max_index */
  283.       array->indices = (struct sindex**)
  284.     __objc_xrealloc(array->indices, 
  285.             (new_max_index+1)*sizeof(struct sindex*));
  286.  
  287.       /* reset entries above old_max_index to empty_bucket */
  288.       for(counter = old_max_index+1; counter <= new_max_index; counter++)
  289.     array->indices[counter] = array->empty_index;
  290.  
  291. #else /* OBJC_SPARSE2 */
  292.  
  293.       /* realloc to make room in table above old_max_index */
  294.       array->buckets = (struct sbucket**)
  295.     __objc_xrealloc(array->buckets, 
  296.             (new_max_index+1)*sizeof(struct sbucket*));
  297.  
  298.       /* reset entries above old_max_index to empty_bucket */
  299.       for(counter = old_max_index+1; counter <= new_max_index; counter++)
  300.     array->buckets[counter] = array->empty_bucket;
  301.  
  302. #endif
  303.       idxsize += (new_max_index-old_max_index);
  304.       return;
  305.     }
  306. }
  307.  
  308.  
  309.  
  310. /* Free a sparse array allocated with sarray_new */
  311.  
  312. void 
  313. sarray_free(struct sarray* array) {
  314. #ifdef OBJC_SPARSE3
  315.   size_t old_max_index = (array->capacity-1)/INDEX_CAPACITY;
  316. #else
  317.   size_t old_max_index = (array->capacity-1)/BUCKET_SIZE;
  318. #endif
  319.   int counter = 0;
  320.  
  321.   assert(array->ref_count != 0);    /* Freed multiple times!!! */
  322.  
  323.   if(--(array->ref_count) != 0)    /* There exists copies of me */
  324.     return;
  325.  
  326.   if((array->is_copy_of) && ((array->is_copy_of->ref_count - 1) == 0))
  327.     sarray_free(array->is_copy_of);
  328.  
  329.   /* Free all entries that do not point to empty_bucket */
  330.   for(counter = 0; counter <= old_max_index; counter++ ) {
  331. #ifdef OBJC_SPARSE3
  332.     struct sindex* idx = array->indices[counter];
  333.     if((idx != array->empty_index) && (idx->version == array->version)) {
  334.       int c2; 
  335.       for(c2=0; c2<INDEX_SIZE; c2++) {
  336.     struct sbucket* bkt = idx->buckets[c2];
  337.     if((bkt != array->empty_bucket) && (bkt->version == array->version))
  338.       {
  339.         __objc_xfree(bkt);
  340.         nbuckets -= 1;
  341.       }
  342.       }
  343.       __objc_xfree(idx);
  344.       nindices -= 1;
  345.     }
  346. #else /* OBJC_SPARSE2 */
  347.     struct sbucket* bkt = array->buckets[counter];
  348.     if ((bkt != array->empty_bucket) && (bkt->version == array->version))
  349.       {
  350.     __objc_xfree(bkt);
  351.     nbuckets -= 1;
  352.       }
  353. #endif
  354.   }
  355.     
  356. #ifdef OBJC_SPARSE3  
  357.   /* free empty_index */
  358.   if(array->empty_index->version == array->version) {
  359.     __objc_xfree(array->empty_index);
  360.     nindices -= 1;
  361.   }
  362. #endif
  363.  
  364.   /* free empty_bucket */
  365.   if(array->empty_bucket->version == array->version) {
  366.     __objc_xfree(array->empty_bucket);
  367.     nbuckets -= 1;
  368.   }
  369.  
  370. #ifdef OBJC_SPARSE3
  371.   /* free bucket table */
  372.   __objc_xfree(array->indices);
  373.   idxsize -= (old_max_index+1);
  374.  
  375. #else
  376.   /* free bucket table */
  377.   __objc_xfree(array->buckets);
  378.   idxsize -= (old_max_index+1);
  379.  
  380. #endif
  381.  
  382.   /* free array */
  383.   __objc_xfree(array);
  384.   narrays -= 1;
  385. }
  386.  
  387. /* This is a lazy copy.  Only the core of the structure is actually */
  388. /* copied.   */
  389.  
  390. struct sarray* 
  391. sarray_lazy_copy(struct sarray* oarr)
  392. {
  393. #ifdef OBJC_SPARSE3
  394.   size_t num_indices = ((oarr->capacity-1)/INDEX_CAPACITY)+1;
  395. #else /* OBJC_SPARSE2 */
  396.   size_t num_indices = ((oarr->capacity-1)/BUCKET_SIZE)+1;
  397. #endif
  398.   struct sarray* arr;
  399.  
  400.   /* Allocate core array */
  401.   arr = (struct sarray*) __objc_xmalloc(sizeof(struct sarray));
  402.   memcpy( arr,oarr, sizeof(struct sarray));
  403.   arr->version = oarr->version + 1;
  404.   arr->is_copy_of = oarr;
  405.   oarr->ref_count += 1;
  406.   arr->ref_count = 1;
  407.   
  408. #ifdef OBJC_SPARSE3
  409.   /* Copy bucket table */
  410.   arr->indices = (struct sindex**) 
  411.     __objc_xmalloc(sizeof(struct sindex*)*num_indices);
  412.   memcpy( arr->indices,oarr->indices, 
  413.     sizeof(struct sindex*)*num_indices);
  414. #else 
  415.   /* Copy bucket table */
  416.   arr->buckets = (struct sbucket**) 
  417.     __objc_xmalloc(sizeof(struct sbucket*)*num_indices);
  418.   memcpy( arr->buckets,oarr->buckets, 
  419.     sizeof(struct sbucket*)*num_indices);
  420. #endif
  421.  
  422.   idxsize += num_indices;
  423.   narrays += 1;
  424.  
  425.   return arr;
  426. }
  427.  
  428.  
  429. void __objc_print_dtable_stats(void)
  430. {
  431.   int total = 0;
  432.   printf("memory usage: (%s)\n",
  433. #ifdef OBJC_SPARSE2
  434.      "2-level sparse arrays"
  435. #else
  436.      "3-level sparse arrays"
  437. #endif
  438.      );
  439.  
  440.   printf("arrays: %d = %d bytes\n", narrays, narrays*sizeof(struct sarray));
  441.   total += narrays*sizeof(struct sarray);
  442.   printf("buckets: %d = %d bytes\n", nbuckets, nbuckets*sizeof(struct sbucket));
  443.   total += nbuckets*sizeof(struct sbucket);
  444.  
  445.   printf("idxtables: %d = %d bytes\n", idxsize, idxsize*sizeof(void*));
  446.   total += idxsize*sizeof(void*);
  447.   printf("-----------------------------------\n");
  448.   printf("total: %d bytes\n", total);
  449.   printf("===================================\n");
  450. }
  451.