err.no Git - sope/blob - gnustep-objc/sarray.h

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
   3    Contributed by Kresten Krab Thorup.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* As a special exception, if you link this library with files
  23    compiled with GCC to produce an executable, this does not cause
  24    the resulting executable to be covered by the GNU General Public License.
  25    This exception does not however invalidate any other reasons why
  26    the executable file might be covered by the GNU General Public License.  */
  27
  28 #ifndef __sarray_INCLUDE_GNU
  29 #define __sarray_INCLUDE_GNU
  30
  31 #include "objc/objc-decls.h"
  32
  33 objc_EXPORT const char* __objc_sparse2_id;
  34
  35 #include <stddef.h>
  36 #include "objc/thr.h"
  37
  38 objc_EXPORT int nbuckets;            /* for stats */
  39 objc_EXPORT int nindices;
  40 objc_EXPORT int narrays;
  41 objc_EXPORT int idxsize;
  42
  43 #include <assert.h>
  44
  45 /* Buckets are 32 words each */
  46 #define BUCKET_SIZE (1 << 6)
  47
  48 typedef size_t sidx;
  49
  50 union sversion {
  51   int   version;
  52   void *next_free;
  53 };
  54
  55 struct sbucket {
  56   void* elems[BUCKET_SIZE];     /* elements stored in array */
  57   union sversion        version;                /* used for copy-on-write */
  58 };
  59
  60 struct sarray {
  61   struct sbucket** buckets;
  62   struct sbucket*  empty_bucket;
  63   union sversion   version;        /* used for copy-on-write */
  64   short            ref_count;
  65   struct sarray    *is_copy_of;
  66   size_t           capacity;
  67 };
  68
  69 struct sarray* sarray_new        (int size);
  70 void           sarray_free       (struct sarray *array);
  71 struct sarray* sarray_lazy_copy  (struct sarray *array);
  72 void           sarray_realloc    (struct sarray *array, int new_size);
  73 void           sarray_at_put_safe(struct sarray *array, sidx index, void* elem);
  74
  75 void sarray_remove_garbage(void);
  76
  77 /* implementation */
  78
  79 /* Get element from the Sparse array `array' at offset `index' */
  80
  81 static inline void* sarray_get_safe(struct sarray* array, sidx index)
  82 {
  83   return (index < array->capacity)
  84     ? array->buckets[index / BUCKET_SIZE]->elems[index % BUCKET_SIZE]
  85     : array->empty_bucket->elems[0];
  86 }
  87
  88 #endif /* __sarray_INCLUDE_GNU */