ijss.h

/* clang-format off */
/*
ijss : IncredibleJunior SparseSet

sparse set [1] for bookkeeping of dense<->sparse index mapping or
a building block for a simple LIFO index/handle allocator

[1] https://research.swtch.com/sparse
*/

#ifndef IJSS_INCLUDED_H
#define IJSS_INCLUDED_H

#ifdef __cplusplus
   extern "C" {
#endif

#if defined(IJSS_STATIC)
   #define IJSS_API static
#else
   #define IJSS_API extern
#endif

struct ijss_pair8 {
   unsigned char dense_index;
   unsigned char sparse_index;
};

struct ijss_pair16 {
   unsigned short dense_index;
   unsigned short sparse_index;
};

struct ijss_pair32 {
   unsigned dense_index;
   unsigned sparse_index;
};

struct ijss {
   void *dense;
   void *sparse;
   unsigned dense_stride;
   unsigned sparse_stride;
   unsigned size;
   unsigned capacity;
   unsigned elementsize; /* size in bytes for _one_ dense/sparse index */
};

/* initialize sparse set with a pair (ex struct ijss_pair<NBITS>) size (size of the _pair_) */
#define ijss_init_from_pairtype_size(pairtype_size, self, pairs, stride, capacity) ijss_init((self), (unsigned char*)(pairs)+((pairtype_size)>>1), (stride), (unsigned char*)(pairs), (stride), (pairtype_size)>>1, capacity)
/* initialize sparse set with a 'struct ijss_pair<NBITS>' */
#define ijss_init_from_pairtype(pairtype, self, pairs, stride, capacity) ijss_init_from_pairtype_size(sizeof(pairtype), (self), (pairs), (stride), (capacity))
/*
 * elementsize:
 *    the size in bytes of _one_ sparse/dense index
 *    i.e. if using ijss_pairXX for bookkeeping use 'sizeof(struct ijss_pairXX)>>1'
 */
IJSS_API void ijss_init(struct ijss *self, void *dense, unsigned dense_stride, void *sparse, unsigned sparse_stride, unsigned elementsize, unsigned capacity);

IJSS_API void ijss_reset(struct ijss *self);
/* reset and sets to D[x] = x for x [0, capacity) */
IJSS_API void ijss_reset_identity(struct ijss *self);

/* returns the dense index */
IJSS_API unsigned ijss_add(struct ijss *self, unsigned sparse_index);

/* returns -1 on invalid sparse index else if a move of (external) data is needed (i.e. movedata if 'ijss_remove(self, idx) > 0') */
/* stores the indices which should be moved in the (external) dense array if move is needed */
IJSS_API int ijss_remove(struct ijss *self, unsigned sparse_index, unsigned *move_to_index, unsigned *move_from_index);

IJSS_API unsigned ijss_dense_index(struct ijss *self, unsigned sparse_index);
IJSS_API unsigned ijss_sparse_index(struct ijss *self, unsigned dense_index);
IJSS_API int ijss_has(struct ijss *self, unsigned sparse_index);

#ifdef __cplusplus
   }
#endif

#endif /* IJSS_INCLUDED_H */

#if defined(IJSS_IMPLEMENTATION)

#ifndef IJSS_assert
   #include <assert.h>
   #define IJSS_assert assert
#endif

static unsigned ijss__load(const void * const p, unsigned len)
{
   IJSS_assert(len >= 1 && len <= 4);
   switch (len) {
      case 1: return *(unsigned char*)p;
      case 2: return *(unsigned short*)p;
      case 4: return *(unsigned*)p;
      default: return 0;
   }
}

static void ijss__store(void *dst, unsigned len, unsigned value)
{
   IJSS_assert(len >= 1 && len <= 4);
   IJSS_assert((0xffffffffu >> (8 * (4 - len))) >= value);
   switch (len) {
      case 1: *(unsigned char*)dst = (unsigned char)value; break;
      case 2: *(unsigned short*)dst = (unsigned short)value; break;
      case 4: *(unsigned*)dst = (unsigned)value; break;
      default:break;
   }
}

IJSS_API void ijss_init(struct ijss *self, void *dense, unsigned dense_stride, void *sparse, unsigned sparse_stride, unsigned elementsize, unsigned capacity)
{
   IJSS_assert(elementsize >= 1 && elementsize <= 4);

   self->dense = dense;
   self->dense_stride = dense_stride;
   self->sparse = sparse;
   self->sparse_stride = sparse_stride;
   self->size = 0;
   self->capacity = capacity;
   self->elementsize = elementsize;
   ijss_reset(self);
}

#define ijss__pointer_add(type, p, bytes) ((type)((unsigned char *)(p) + (bytes)))

#define IJSS__STORE(p, stride, elementsize, idx, value) ijss__store(ijss__pointer_add(void*, (p), (stride)*(idx)), (elementsize), (value))
#define IJSS__STORE_DENSE(idx, value) IJSS__STORE(self->dense, self->dense_stride, self->elementsize, idx, value)
#define IJSS__STORE_SPARSE(idx, value) IJSS__STORE(self->sparse, self->sparse_stride, self->elementsize, idx, value)

#define IJSS__LOAD(p, stride, elementsize, idx) ijss__load(ijss__pointer_add(void*, (p), (stride)*(idx)), (elementsize))
#define IJSS__LOAD_DENSE(idx) IJSS__LOAD(self->dense, self->dense_stride, self->elementsize, idx)
#define IJSS__LOAD_SPARSE(idx) IJSS__LOAD(self->sparse, self->sparse_stride, self->elementsize, idx)

IJSS_API void ijss_reset(struct ijss *self)
{
   self->size = 0;
}

IJSS_API void ijss_reset_identity(struct ijss *self)
{
   unsigned i;
   self->size = 0;
   for (i = 0; i != self->capacity; ++i)
      IJSS__STORE_DENSE(i, i);
}

IJSS_API unsigned ijss_add(struct ijss *self, unsigned sparse_index)
{
   unsigned dense_index = self->size++;
   IJSS_assert((0xffffffffu >> (8 * (4 - self->elementsize))) >= dense_index);
   IJSS_assert((0xffffffffu >> (8 * (4 - self->elementsize))) >= sparse_index);

   IJSS_assert(self->capacity > dense_index);
   IJSS_assert(self->capacity > sparse_index);

   IJSS__STORE_DENSE(dense_index, sparse_index);
   IJSS__STORE_SPARSE(sparse_index, dense_index);

   return dense_index;
}

IJSS_API int ijss_remove(struct ijss *self, unsigned sparse_index, unsigned *move_to_index, unsigned *move_from_index)
{
   if (!ijss_has(self, sparse_index))
      return -1;
   else {
      unsigned size_now = self->size-1;
      unsigned dense_index_of_removed, sparse_index_of_back;
      IJSS_assert(self->capacity > size_now);

      dense_index_of_removed = IJSS__LOAD_SPARSE(sparse_index);
      IJSS_assert(self->capacity > dense_index_of_removed);
      IJSS_assert(size_now >= dense_index_of_removed);
      sparse_index_of_back = IJSS__LOAD_DENSE(size_now);

      IJSS__STORE_DENSE(size_now, sparse_index); /* done as now we can (together with 'ijss_reset_identity') make a LIFO index/handle allocator */
      IJSS__STORE_DENSE(dense_index_of_removed, sparse_index_of_back);
      IJSS__STORE_SPARSE(sparse_index_of_back, dense_index_of_removed);

      *move_from_index = size_now;
      *move_to_index = dense_index_of_removed;
      --self->size;

      return dense_index_of_removed != size_now;
   }
}

IJSS_API int ijss_has(struct ijss *self, unsigned sparse_index)
{
   if (sparse_index >= self->capacity)
      return 0;
   else {
      unsigned dense_index = IJSS__LOAD_SPARSE(sparse_index);
      return self->size > dense_index && IJSS__LOAD_DENSE(dense_index) == sparse_index;
   }
}

IJSS_API unsigned ijss_dense_index(struct ijss *self, unsigned sparse_index)
{
   IJSS_assert(self->capacity > sparse_index);
   return IJSS__LOAD_SPARSE(sparse_index);
}

IJSS_API unsigned ijss_sparse_index(struct ijss *self, unsigned dense_index)
{
   IJSS_assert(self->capacity > dense_index);
   return IJSS__LOAD_DENSE(dense_index);
}

#if defined(IJSS_TEST) || defined(IJSS_TEST_MAIN)

#define SSHA_INVALID_HANDLE (unsigned)-1
static unsigned ijss_alloc_handle(struct ijss *self, unsigned *dense)
{
   unsigned h;
   if (self->capacity == self->size)
      return SSHA_INVALID_HANDLE;

   h = ijss_sparse_index(self, self->size);
   *dense = ijss_add(self, h);

   return h;
}

static void ijss_as_handlealloc_test_suite(void)
{
#define SSHA_NUM_OBJECTS (4)
   int r;
   unsigned i, h, dense, move_from, move_to;
   struct ijss_pair32 ssdata[SSHA_NUM_OBJECTS];
   unsigned handles[SSHA_NUM_OBJECTS];
   struct ijss ss, *self = &ss;
   ijss_init_from_pairtype_size(sizeof *ssdata, self, ssdata, sizeof *ssdata, SSHA_NUM_OBJECTS);
   ijss_reset_identity(self);

   for (i = 0; i != SSHA_NUM_OBJECTS; ++i) {
      h = ijss_alloc_handle(self, &dense);
      handles[i] = h;
      h = 0;
   }

   for (i = 0; i != SSHA_NUM_OBJECTS; ++i) {
      IJSS_assert(ijss_has(self, i));
      if (i % 2) {
         continue;
      }

      r = ijss_remove(self, i, &move_to, &move_from);
      handles[i] = SSHA_INVALID_HANDLE;
   }

   for (i = 0; i != SSHA_NUM_OBJECTS; ++i) {
      if (i % 2) {
         IJSS_assert(ijss_has(self, i));
      }
      else {
         IJSS_assert(!ijss_has(self, i));
      }
   }

   for (i = 0; i != 2; ++i) {
      h = ijss_alloc_handle(self, &dense);
      IJSS_assert(handles[h] == SSHA_INVALID_HANDLE);
      handles[h] = h;
      h = 0;
   }
}

#if defined(IJSS_TEST_MAIN)

int main(int args, char **argc)
{
   (void)args;
   (void)argc;
   ijss_as_handlealloc_test_suite();

   return 0;
}
#endif /* defined(IJSS_TEST_MAIN) */
#endif /* defined(IJSS_TEST) || defined(IJSS_TEST_MAIN) */

#endif /* IJSS_IMPLEMENTATION */

/* clang-format on */