yAllocator.cpp

#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <exception>
#include <assert.h>
#include "yAllocator.h"

#define min(a,b) a<b?a:b
#define BITSIZE(a) (sizeof(a)*8)
#define ISBITSET(x,k) (x & (1<<k))

using namespace std;

yBitmaskBase::yBitmaskBase(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last)
{
	last = _last;
	owner = _owner;
	level = _level;
	size = _size;
}

//benchmarks say that it is minimal faster than other more complicated
int yBitmaskBase::findZero32(uint32_t x)
{
	int n;
	x = x & (~x - 1);
	n = 0;
	while (x != 0)
	{
		n = n + 1;
		x = x >> 1;
	}
	return n;
}

int yBitmaskBase::findZero64(uint64_t x)
{
	if ((x | 0xffffffff00000000) != 0xffffffffffffffff)
		return findZero32((uint32_t)x); //this branch must be first
	else
		return findZero32((uint32_t)(x >> 32)) + 32;
}

unsigned char yBitmaskBase::findFreeBitTab(unsigned char size, uint64_t *tab)
{
	int numQuads = DIVPAD(size, BITSIZE(uint64_t));
	int foundQuad = -1;
	for (int i = 0; i < numQuads; i++)
		if (tab[i] != 0xffffffffffffffff)
		{
			foundQuad = i;
			break;
		}
	if (foundQuad<0)
		throw exception("getNumber: all numbers are busy");
	int foundBit = findZero64(tab[foundQuad]);
	assert(foundBit < 64);
	return foundBit;
}

bool yBitmaskBase::setBitTab(unsigned char n, uint64_t *tab, bool bThrow)
{
	unsigned char numQuad = n / BITSIZE(uint64_t);
	unsigned char bitInQuad = n % BITSIZE(uint64_t);
	bool test = (tab[numQuad] & (1LL << bitInQuad)) != 0;
	if (bThrow && test)
		throw exception("bit already is set");
	tab[numQuad] |= (1LL << bitInQuad);
	return !test;
}
bool yBitmaskBase::clearBitTab(unsigned char n, uint64_t *tab, bool bThrow)
{
	unsigned char numQuad = n / BITSIZE(uint64_t);
	unsigned char bitInQuad = n % BITSIZE(uint64_t);
	bool test = (tab[numQuad] & (1LL << bitInQuad)) != 0;
	if (bThrow && !test)
		throw exception("bit already is clear");
	tab[numQuad] &= ~(1LL << bitInQuad);
	return test;
}

unsigned char yBitmaskBase::testBitTab(unsigned char n, uint64_t *tab)
{
	unsigned char numQuad = n / BITSIZE(uint64_t);
	unsigned char bitInQuad = n % BITSIZE(uint64_t);
	return (tab[numQuad] & (1LL << bitInQuad)) != 0;
}

yBitmask0::yBitmask0(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last)
	: yBitmaskBase(_owner, _size, _level, _last)
{
	memset(mask, 0, sizeof(mask));
	count = 0;
};

void yBitmask0::setBit(unsigned char n)
{
	setBitTab(n, mask, true);
	count++;
};

void yBitmask0::clearBit(unsigned char n)
{
	clearBitTab(n, mask, true);
	count--;
};

unsigned char yBitmask0::findFreeBit()
{
	return findFreeBitTab(size, mask);
}

void yBitmask0::debugWriteMask()
{
	for (int i = 0; i < size; i++)
		printf("%d", testBitTab(i, mask));
}

void yBitmask0::fillWhole()
{
	memset(mask, 255, sizeof(mask));
	count = size;
}

yIndexRec* yBitmaskHi::getRecAlloc()
{
	if (indexCount > 0)
	{
		yIndexRec* rec = &indices[0];
		int n = indices[0].index;
		assert(testBitTab(n, maskOR) == 1);
		return rec;
	}
	else
	{
		unsigned char n = findFreeBitTab(size, maskAND);
		yIndexRec* rec = insertIndex(n);
		assert(level == 2 || level == 1);
		size_t sizeLowerAll;
		if (level == 2)
			sizeLowerAll = DIVPAD(owner->getCount(), BitsToBit);
		else
			sizeLowerAll = owner->getCount();
		assert(n < size);
		unsigned char sizeLower;
		bool lowerlast;
		if (last && n == size - 1)
		{
			lowerlast = true;
			sizeLower = sizeLowerAll % BitsToBit; //przetestować dla <64
		}
		else
		{
			lowerlast = false;
			sizeLower = BitsToBit;
		}
		if (level == 2)
			rec->lowerLevel = new yBitmaskHi(owner, sizeLower, level - 1, lowerlast);
		else
			rec->lowerLevel = new yBitmask0(owner, sizeLower, level - 1, lowerlast);
		return rec;
	}
}

void yBitmaskHi::fillWhole()
{
	memset(maskAND, 255, sizeof(maskAND));
	memset(maskOR, 255, sizeof(maskOR));
	countAND = size;
	countOR = size;
}

yIndexRec *yBitmaskHi::findRecRelease(unsigned char n)
{
	if (testBitTab(n, maskAND) == 0)
	{
		unsigned char position;
		bool found = binaryFind(n, position);
		if (!found)
			throw exception("releaseNumber: number not found");
		assert(indices);
		return &indices[position];
	}
	else
	{
		assert(level == 2 || level == 1);
		size_t sizeLowerAll;
		if (level == 2)
			sizeLowerAll = DIVPAD(owner->getCount(), BitsToBit);
		else
			sizeLowerAll = owner->getCount();
		assert(n < size);
		yBitmaskBase *lowerLevel;
		unsigned char sizeLower;
		bool lowerlast;
		if (last && n == size - 1)
		{
			lowerlast = true;
			sizeLower = sizeLowerAll % BitsToBit; //przetestować dla <64
		}
		else
		{
			lowerlast = false;
			sizeLower = BitsToBit;
		}
		if (level == 2)
			lowerLevel = new yBitmaskHi(owner, sizeLower, level - 1, lowerlast);
		else
			lowerLevel = new yBitmask0(owner, sizeLower, level - 1, lowerlast);
		lowerLevel->fillWhole();
		yIndexRec* rec = insertIndex(n);
		rec->lowerLevel = lowerLevel;
		return rec;
	}
}

unsigned char yBitmaskHi::setMasks(yIndexRec *rec)
{
	unsigned char n = rec->index;
	if (setBitTab(n, maskOR, false))
		countOR++;
	if (rec->lowerLevel->isFullAND())
	{
		if (setBitTab(n, maskAND, false))
			countAND++;
	}
	return n;
}

void yBitmaskHi::clearMasks(yIndexRec *rec)
{
	unsigned char n = rec->index;
	if (clearBitTab(n, maskAND, false))
		countAND--;
	if (rec->lowerLevel->isEmptyOR())
		clearBitTab(n, maskOR, false);
}

void yBitmaskHi::releaseIfFull(yIndexRec *rec)
{
	unsigned char n = rec->index;
	if (testBitTab(n, maskAND))
		releaseIndexByValue(rec->index);
}

void yBitmaskHi::releaseIfEmpty(yIndexRec *rec)
{
	unsigned char n = rec->index;
	if (!testBitTab(n, maskOR))
		releaseIndexByValue(rec->index);
}

void yBitmaskHi::setUnusedBits(uint64_t* tab)
{
	size_t fromQuad = size / BITSIZE(uint64_t);
	assert(fromQuad >= 0 && fromQuad < SIZEINQUADS);
	int fromBitOnQuad = size - (fromQuad*BITSIZE(uint64_t));
	assert(fromBitOnQuad >= 0 && fromBitOnQuad < 64);
	uint64_t mask = ~((1LL << fromBitOnQuad) - 1);
	tab[fromQuad] |= mask;
	for (int i = fromQuad + 1; i < SIZEINQUADS; i++)
		tab[i] = 0xffffffffffffffff;
}

yBitmaskHi::yBitmaskHi(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last)
	: yBitmaskBase(_owner, _size, _level, _last)
{
	indexCount = 0;
	indexCapacity = 0;
	indices = NULL;
	memset(maskAND, 0, sizeof(maskAND));
	memset(maskOR, 0, sizeof(maskOR));
	setUnusedBits(maskAND);
	setUnusedBits(maskOR);
}

yBitmaskHi::~yBitmaskHi()
{
	releaseAllIndices();
	free(indices);
}

//if not found - return index next element
bool yBitmaskHi::binaryFind(unsigned char n, unsigned char &index)
{
	int L, R;
	index = 0;
	if (indexCount<1) return false;
	L = 0;
	R = indexCount - 1;
	while (L <= R)
	{
		index = (L + R) >> 1;
		unsigned char val = indices[index].index;
		if (val < n)
			L = index + 1;
		else if (val > n)
			R = index - 1;
		else return true;
	}
	index = L;
	return false;
}

yIndexRec * yBitmaskHi::insertIndex(unsigned char n)//jako drugi parametr link do bitmaski?
{
	unsigned char index;
	const int initCap = 4;
	if (!indices)
	{
		indices = (yIndexRec *)malloc(initCap*sizeof(yIndexRec));
		indexCapacity = initCap;
		indexCount = 1;
		indices[0].lowerLevel = NULL;
		indices[0].index = n;
		index = 0;
	}
	else
	{
		assert(indexCount <= indexCapacity);
		if (indexCount == indexCapacity) //grows
		{
			indexCapacity *= 2;
			indices = (yIndexRec *)realloc(indices, indexCapacity*sizeof(yIndexRec));
		}
		//find place to insert
		bool found = binaryFind(n, index);
		assert(found == false);
		assert(index >= 0 && index <= indexCount);
		//move
		memmove(&indices[index + 1], &indices[index], (indexCount - index)*sizeof(yIndexRec));
		indices[index].lowerLevel = NULL;
		indices[index].index = n;
		indexCount++;
	}
	return &indices[index];
}

void yBitmaskHi::releaseAllIndices()
{
	for (int i = 0; i < indexCount; i++)
		delete indices[i].lowerLevel;
	indexCount = 0;
}

void yBitmaskHi::releaseIndexbyPosition(unsigned char position)
{
	assert(position >= 0 && position < indexCount);
	delete indices[position].lowerLevel;
	memmove(&indices[position], &indices[position + 1], (indexCount - position - 1)*sizeof(yIndexRec));
	indexCount--;
}


void yBitmaskHi::releaseIndexByValue(unsigned char value)
{
	unsigned char position;
	bool found = binaryFind(value, position);
	assert(found == true);
	releaseIndexbyPosition(position);
}

void yBitmaskHi::debugWriteAND()
{
	for (int i = 0; i < size; i++)
		printf("%d", testBitTab(i, maskAND));
}

void yBitmaskHi::debugWriteOR()
{
	for (int i = 0; i < size; i++)
		printf("%d", testBitTab(i, maskOR));
}

void yBitmaskHi::debugWrite()
{
	if (level != 2) return;
	printf("AND:");
	debugWriteAND();
	printf("\n");
	printf("OR: ");
	debugWriteOR();
	printf("\n\n");
	printf("AND:");
	for (int i = 0; i < indexCount; i++)
	{
		yBitmaskHi *level1 = (yBitmaskHi *)indices[i].lowerLevel;
		level1->debugWriteAND();
		printf("|");
	}
	printf("\n");
	printf("OR: ");
	for (int i = 0; i < indexCount; i++)
	{
		yBitmaskHi *level1 = (yBitmaskHi *)indices[i].lowerLevel;
		level1->debugWriteOR();
		printf("|");
	}
	printf("\n\n");
	for (int i = 0; i < indexCount; i++)
	{
		yBitmaskHi *level1 = (yBitmaskHi *)indices[i].lowerLevel;
		for (int i = 0; i < level1->indexCount; i++)
		{
			yBitmask0 *level0 = (yBitmask0 *)level1->indices[i].lowerLevel;
			printf("[");
			level0->debugWriteMask();
			printf("]");
		}
		printf("|");
	}
	printf("\n----------------------------------\n");
}

/*
  this structure limit is 16M = 256*256*256
  for example X11 ridmask was 2097151 = 0x1FFFFF, (rid base was 62914560 = 0x3C00000)
  How it works:
  in level 0 we have: (for simplicity - 4 instead of 256 bits)
  [1111] [1011] [0011] [0000] | [0100] [1111] [1000] [0000] | [0000] [0000] [0000] [0000] | [1111] [1111] [1111] [1111]
  at level 1 mask AND:
  1000 | 0100 | 0000 | 1111
  at level 1 mask OR:
  1110 | 1110 | 0000 | 1111
  on level 1 indices from range(16) only for this: not all 0, not all 1
  1,2,4,6
  just indices is for set bits od XOR mask:
  0110 | 1010 | 0000 | 0000
*/
yAllocator::yAllocator(const uint32_t base, const uint32_t count)
{
	this->alloc_base = base;
	this->alloc_count = min(count, BitsToBit *BitsToBit *BitsToBit);
	bitmask2 = new yBitmaskHi(this, DIVPAD(this->alloc_count, BitsToBit * BitsToBit),2, true);
}
yAllocator::~yAllocator()
{
	delete bitmask2;
}

uint32_t yAllocator::makeFullNumber(unsigned char n2, unsigned char n1, unsigned char n0)
{
	return n2*BitsToBit*BitsToBit + n1*BitsToBit + n0;
}

uint32_t yAllocator::getNumber()
{
	yIndexRec *rec2, *rec1;
	yBitmaskHi *bitmask1;
	yBitmask0 *bitmask0;

	rec2 = bitmask2->getRecAlloc();
	bitmask1 = (yBitmaskHi *)rec2->lowerLevel;
	rec1 = bitmask1->getRecAlloc();
	bitmask0 = (yBitmask0 *)rec1->lowerLevel;
	int n0 = bitmask0->findFreeBit();
	bitmask0->setBit(n0);
	int n1 = bitmask1->setMasks(rec1);
	bitmask1->releaseIfFull(rec1);
	int n2 = bitmask2->setMasks(rec2);
	bitmask2->releaseIfFull(rec2);
	return makeFullNumber(n2, n2, n0) + alloc_base;
}

void yAllocator::releaseNumber(uint32_t number)
{
	if (number < alloc_base)
		throw exception("releaseNumber: bad number, too small");
	uint32_t n = number - alloc_base;
	if (n >= alloc_count)
		throw exception("releaseNumber: bad number, too big");
	// find bit n on level2, level1 and level0
	// release level0 if needs, release level1 if needs
	yIndexRec *rec2, *rec1;
	yBitmaskHi *bitmask1;
	yBitmask0 *bitmask0;

	rec2 = bitmask2->findRecRelease(n / (BitsToBit*BitsToBit));
	bitmask1 = (yBitmaskHi *)rec2->lowerLevel;
	rec1 = bitmask1->findRecRelease((n / BitsToBit) % BitsToBit);
	bitmask0 = (yBitmask0 *)rec1->lowerLevel;
	bitmask0->clearBit(n % BitsToBit);
	bitmask1->clearMasks(rec1);
	bitmask1->releaseIfEmpty(rec1);
	bitmask2->clearMasks(rec2);
	bitmask2->releaseIfEmpty(rec2);
}

void yAllocator::debugWrite()
{
	bitmask2->debugWrite();
}

int main()
{
	try
	{
		yAllocator alloc(0, 64/*9*//*11*1000000*/);
		uint32_t n = alloc.getNumber();
		n = alloc.getNumber();
		n = alloc.getNumber();
		n = alloc.getNumber();
		n = alloc.getNumber();
		alloc.releaseNumber(2);
		alloc.debugWrite();
		n = alloc.getNumber();
		alloc.debugWrite();
		printf("przydzielono %d\n", n);
	}
	catch (exception& e)
	{
		printf("ERROR %s\n", e.what());
	}
    return 0;
}

yAllocator.h

#pragma once
#include <stdint.h>
#define DIVPAD(a,div) ((a+div-1)/(div)) //round to ceil
#define BitsToBit 4
#define SIZEINQUADS DIVPAD(BitsToBit, 64)

class yBitmaskBase;
class yBitmaskHi;

class yAllocator
{
private:
	uint32_t alloc_base;
	uint32_t alloc_count;
	yBitmaskHi *bitmask2;
	uint32_t makeFullNumber(unsigned char n2, unsigned char n1, unsigned char n0);
public:
	yAllocator(const uint32_t base, const uint32_t count);
	virtual ~yAllocator();
	uint32_t getCount() { return alloc_count; }
	uint32_t getNumber();
	void releaseNumber(uint32_t number);
	void debugWrite();
};

struct yIndexRec {
	yBitmaskBase* lowerLevel; //size 4 or 8 bytes
	unsigned char index; //in this level
};//size 8 or (for 64bit) 16 bytes

class yBitmaskBase {
protected:
	yAllocator *owner;
	unsigned char level;
	unsigned char size; //ususally 256 but can be less
	bool last;
	static int findZero32(uint32_t x);
	static int findZero64(uint64_t x);
	static unsigned char findFreeBitTab(unsigned char size, uint64_t *tab);
	inline static bool setBitTab(unsigned char n, uint64_t *tab, bool bThrow);
	inline static bool clearBitTab(unsigned char n, uint64_t *tab, bool bThrow);
	inline static unsigned char testBitTab(unsigned char n, uint64_t *tab);
public:
	virtual bool isFullAND() = 0;
	virtual bool isEmptyOR() = 0;
	yBitmaskBase(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last);
	virtual ~yBitmaskBase() {};
	virtual void fillWhole() = 0;
};

//level 0
class yBitmask0 : public yBitmaskBase {
	uint64_t mask[SIZEINQUADS]; // 256 bits,32 bytes,4 uint64_t
	unsigned char count;
public:
	yBitmask0(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last);
	unsigned char findFreeBit();
	void setBit(unsigned char n);
	void clearBit(unsigned char n);
	void debugWriteMask();
	virtual void fillWhole();
	virtual bool isFullAND() { return count == size; };
	virtual bool isEmptyOR() { return count == 0; };
};

//1 and 2 level
class yBitmaskHi : public yBitmaskBase {
	uint64_t maskAND[SIZEINQUADS];
	uint64_t maskOR[SIZEINQUADS];
	unsigned char indexCount;
	unsigned char indexCapacity;
	yIndexRec *indices;
	void setUnusedBits(uint64_t* tab);
	bool binaryFind(unsigned char n, unsigned char &index);
	yIndexRec *insertIndex(unsigned char n);
	void releaseAllIndices();
	void releaseIndexbyPosition(unsigned char position);
	void releaseIndexByValue(unsigned char value);
	unsigned char countAND;
	unsigned char countOR;
public:
	yBitmaskHi(yAllocator *_owner, unsigned char _size, unsigned char _level, bool _last);
	virtual ~yBitmaskHi();
	yIndexRec *getRecAlloc();
	yIndexRec *findRecRelease(unsigned char n);
	virtual void fillWhole();
	virtual bool isFullAND() { return countAND == size; };
	virtual bool isEmptyOR() { return countOR == 0; };
	unsigned char setMasks(yIndexRec *rec);
	void clearMasks(yIndexRec *rec);
	void releaseIfFull(yIndexRec *rec);
	void releaseIfEmpty(yIndexRec *rec);
	void debugWriteAND();
	void debugWriteOR();
	void debugWrite();
};