#ifndef __sarray_INCLUDE_GNU
#define __sarray_INCLUDE_GNU
#include "thr.h"
#define OBJC_SPARSE2
#ifdef OBJC_SPARSE2
extern const char* __objc_sparse2_id;
#endif
#ifdef OBJC_SPARSE3
extern const char* __objc_sparse3_id;
#endif
#include <stddef.h>
#include <assert.h>
#ifdef __cplusplus
extern "C" {
#endif
extern int nbuckets;
extern int nindices;
extern int narrays;
extern int idxsize;
#define SIZET_BITS (sizeof(size_t)*8)
#if defined(__sparc__) || defined(OBJC_SPARSE2)
#define PRECOMPUTE_SELECTORS
#endif
#ifdef OBJC_SPARSE3
#define BUCKET_BITS 3
#define BUCKET_SIZE (1<<BUCKET_BITS)
#define BUCKET_MASK (BUCKET_SIZE-1)
#define INDEX_BITS 4
#define INDEX_SIZE (1<<INDEX_BITS)
#define INDEX_MASK (INDEX_SIZE-1)
#define INDEX_CAPACITY (BUCKET_SIZE*INDEX_SIZE)
#else
#define BUCKET_BITS 5
#define BUCKET_SIZE (1<<BUCKET_BITS)
#define BUCKET_MASK (BUCKET_SIZE-1)
#endif
typedef size_t sidx;
#ifdef PRECOMPUTE_SELECTORS
struct soffset {
#ifdef OBJC_SPARSE3
unsigned int unused : SIZET_BITS/4;
unsigned int eoffset : SIZET_BITS/4;
unsigned int boffset : SIZET_BITS/4;
unsigned int ioffset : SIZET_BITS/4;
#else
#ifdef __sparc__
unsigned long boffset : (SIZET_BITS - 2) - BUCKET_BITS;
unsigned int eoffset : BUCKET_BITS;
unsigned int unused : 2;
#else
unsigned int boffset : SIZET_BITS/2;
unsigned int eoffset : SIZET_BITS/2;
#endif
#endif
};
union sofftype {
struct soffset off;
sidx idx;
};
#endif
union sversion {
int version;
void *next_free;
};
struct sbucket {
void* elems[BUCKET_SIZE];
union sversion version;
};
#ifdef OBJC_SPARSE3
struct sindex {
struct sbucket* buckets[INDEX_SIZE];
union sversion version;
};
#endif
struct sarray {
#ifdef OBJC_SPARSE3
struct sindex** indices;
struct sindex* empty_index;
#else
struct sbucket** buckets;
#endif
struct sbucket* empty_bucket;
union sversion version;
short ref_count;
struct sarray* is_copy_of;
size_t capacity;
};
struct sarray* sarray_new(int, void* default_element);
void sarray_free(struct sarray*);
struct sarray* sarray_lazy_copy(struct sarray*);
void sarray_realloc(struct sarray*, int new_size);
void sarray_at_put(struct sarray*, sidx indx, void* elem);
void sarray_at_put_safe(struct sarray*, sidx indx, void* elem);
struct sarray* sarray_hard_copy(struct sarray*);
void sarray_remove_garbage(void);
#ifdef PRECOMPUTE_SELECTORS
static inline unsigned int
soffset_decode(sidx indx)
{
union sofftype x;
x.idx = indx;
#ifdef OBJC_SPARSE3
return x.off.eoffset
+ (x.off.boffset*BUCKET_SIZE)
+ (x.off.ioffset*INDEX_CAPACITY);
#else
return x.off.eoffset + (x.off.boffset*BUCKET_SIZE);
#endif
}
static inline sidx
soffset_encode(size_t offset)
{
union sofftype x;
x.off.eoffset = offset%BUCKET_SIZE;
#ifdef OBJC_SPARSE3
x.off.boffset = (offset/BUCKET_SIZE)%INDEX_SIZE;
x.off.ioffset = offset/INDEX_CAPACITY;
#else
x.off.boffset = offset/BUCKET_SIZE;
#endif
return (sidx)x.idx;
}
#else
static inline size_t
soffset_decode(sidx indx)
{
return indx;
}
static inline sidx
soffset_encode(size_t offset)
{
return offset;
}
#endif
static inline void* sarray_get(struct sarray* array, sidx indx)
{
#ifdef PRECOMPUTE_SELECTORS
union sofftype x;
x.idx = indx;
#ifdef OBJC_SPARSE3
return
array->
indices[x.off.ioffset]->
buckets[x.off.boffset]->
elems[x.off.eoffset];
#else
return array->buckets[x.off.boffset]->elems[x.off.eoffset];
#endif
#else
#ifdef OBJC_SPARSE3
return array->
indices[indx/INDEX_CAPACITY]->
buckets[(indx/BUCKET_SIZE)%INDEX_SIZE]->
elems[indx%BUCKET_SIZE];
#else
return array->buckets[indx/BUCKET_SIZE]->elems[indx%BUCKET_SIZE];
#endif
#endif
}
static inline void* sarray_get_safe(struct sarray* array, sidx indx)
{
if(soffset_decode(indx) < array->capacity)
return sarray_get(array, indx);
else
return (array->empty_bucket->elems[0]);
}
#ifdef __cplusplus
}
#endif
#endif