Skip to content

Instantly share code, notes, and snippets.

@zacharycarter
Forked from incrediblejr/ijss.h
Created June 13, 2020 13:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zacharycarter/7b0fdd01ca40f3cc709fb8a04f39a0ee to your computer and use it in GitHub Desktop.
Save zacharycarter/7b0fdd01ca40f3cc709fb8a04f39a0ee to your computer and use it in GitHub Desktop.
/* 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 */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment