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