sparse array

sarray.c

/*******************************************************************
 * Caribou Programming Language
 * Copyright (C) 2010, Jeremy Tregunna, All Rights Reserved.
 * Originally written by: David Chisnall
 *
 * This software project, which includes this module, is protected
 * under Canadian copyright legislation, as well as international
 * treaty. It may be used only as directed by the copyright holder.
 * The copyright holder hereby consents to usage and distribution
 * based on the terms and conditions of the MIT license, which may
 * be found in the LICENSE file included in this distribution.
 *******************************************************************
 * Project: Caribou Programming Language
 * File: sarray.c
 * Description: Sparse array
 ******************************************************************/

#include <stdint.h>
#include <stdlib.h>
#ifdef BUILD_TESTS
#include <stdio.h>
#endif
#include <caribou/sarray.h>
#include <caribou/lock.h>

DECLARE_STATIC_LOCK(sarray);
static SparseArray* EmptyArray = NULL;

static void init_pointers(SparseArray* sarray)
{
	sarray->data = calloc(256, sizeof(void*));
	if(sarray->shift != 0)
	{
		for(unsigned i=0 ; i<256 ; i++)
		{
			sarray->data[i] = EmptyArray;
		}
	}
}

void __attribute__((constructor)) sarray_init(void)
{
	LOCK(sarray)
	if(EmptyArray == NULL)
	{
		EmptyArray = calloc(1, sizeof(SparseArray));
		EmptyArray->shift = 0;
		EmptyArray->mask = 0xff;
		EmptyArray->data = calloc(256, sizeof(void*));
	}
	UNLOCK(sarray);
}

SparseArray* SparseArrayNew()
{
	SparseArray* sarray = calloc(1, sizeof(SparseArray));
	sarray->shift = 24;
	sarray->mask = 0xff000000;
	init_pointers(sarray);
	return sarray;
}


void* SparseArrayNext(SparseArray* sarray, uintptr_t* index)
{
	uintptr_t j = MASK_INDEX((*index));
	uintptr_t max = (sarray->mask >> sarray->shift) + 1;
	if(sarray->shift == 0)
	{
		while(j<max)
		{
			(*index)++;
			if(sarray->data[j] != SARRAY_EMPTY)
			{
				return sarray->data[j];
			}
			j++;
		}
	}
	else while(j<max)
	{
		uintptr_t zeromask = ~(sarray->mask >> 8);
		while(j<max)
		{
			//Look in child nodes
			if(sarray->data[j] != SARRAY_EMPTY)
			{
				void* ret = SparseArrayNext(sarray->data[j], index);
				if(ret != SARRAY_EMPTY)
				{
					return ret;
				}
			}
			//Go to the next child
			j++;
			//Add 2^n to index so j is still correct
			(*index) += 1<<sarray->shift;
			//Zero off the next component of the index so we don't miss any.
			*index &= zeromask;
		}
	}
	return SARRAY_EMPTY;
}

void SparseArrayInsert(SparseArray* sarray, uintptr_t index, void* value)
{
	while(sarray->shift > 0)
	{
		uintptr_t i = MASK_INDEX(index);
		if(sarray->data[i] == EmptyArray)
		{
			SparseArray* newsarray = calloc(1, sizeof(SparseArray));
			newsarray->shift = sarray->shift - 8;
			newsarray->mask = sarray->mask >> 8;
			init_pointers(newsarray);
			sarray->data[i] = newsarray;
		}
		sarray = sarray->data[i];
	}
	sarray->data[index & sarray->mask] = value;
}

void SparseArrayDestroy(SparseArray* sarray)
{
	if(sarray->shift > 0)
	{
		uintptr_t max = (sarray->mask >> sarray->shift) + 1;
		for(uintptr_t i=0 ; i<max ; i++)
		{
			SparseArrayDestroy((SparseArray*)sarray->data[i]);
		}
	}
	free(sarray->data);
	free(sarray);
}

sarray.h

/*******************************************************************
 * Caribou Programming Language
 * Copyright (C) 2010, Jeremy Tregunna, All Rights Reserved.
 * Originally written by: David Chisnall
 *
 * This software project, which includes this module, is protected
 * under Canadian copyright legislation, as well as international
 * treaty. It may be used only as directed by the copyright holder.
 * The copyright holder hereby consents to usage and distribution
 * based on the terms and conditions of the MIT license, which may
 * be found in the LICENSE file included in this distribution.
 *******************************************************************
 * Project: Caribou Programming Language
 * File: sarray.h
 * Description: Sparse array
 ******************************************************************/

#ifndef __CARIBOU__SARRAY_H__
#define __CARIBOU__SARRAY_H__

#include <stdint.h>
#include <stdlib.h>

/**
 * Sparse arrays, used to implement dispatch tables.  Current implementation is
 * quite RAM-intensive and could be optimised.  Maps 32-bit integers to pointers.
 *
 * Note that deletion from the array is not supported.  This allows accesses to
 * be done without locking; the worst that can happen is that the caller gets
 * an old value (and if this is important to you then you should be doing your
 * own locking).  For this reason, you should be very careful when deleting a
 * sparse array that there are no references to it held by other threads.
 */
typedef struct 
{
	uintptr_t mask;
	uintptr_t shift;
	void** data;
} SparseArray;

/**
 * Turn an index in the array into an index in the current depth.
 */
#define MASK_INDEX(index) \
	((index & sarray->mask) >> sarray->shift)

#define SARRAY_EMPTY ((void*)0)
/**
 * Look up the specified value in the sparse array.  This is used in message
 * dispatch and so has been put in the header to allow compilers to inline it,
 * even though this breaks the abstraction.
 */
static inline void* SparseArrayLookup(SparseArray* sarray, uintptr_t index)
{
	while(sarray->shift > 0)
	{
		uintptr_t i = MASK_INDEX(index);
		sarray = (SparseArray*) sarray->data[i];
	}
	uintptr_t i = index & sarray->mask;
	return sarray->data[i];
}
/**
 * Create a new sparse array.
 */
SparseArray* SparseArrayNew();
/**
 * Insert a value at the specified index.
 */
void SparseArrayInsert(SparseArray* sarray, uintptr_t index, void* value);
/**
 * Destroy the sparse array.  Note that calling this while other threads are
 * performing lookups is guaranteed to break.
 */
void SparseArrayDestroy(SparseArray* sarray);
/**
 * Iterate through the array.  Returns the next non-NULL value after index and
 * sets index to the following value.  For example, an array containing values
 * at 0 and 10 will, if called with index set to 0 first return the value at 0
 * and set index to 1.  A subsequent call with index set to 1 will return the
 * value at 10 and set index to 11.
 */
void* SparseArrayNext(SparseArray* sarray, uintptr_t* index);

#endif /* !__CARIBOU__SARRAY_H__ */