skcblitz/table.h

void *itbl_push(itable_t *table) {
	table_e *elem = table->free;
	uint *block;
	int cid;
	int eid;
	if(elem == NULL) {
		return NULL;
	}
	table->free = table->free->f_next ? table->free->f_next : table->free->f_prev;
	if(elem->f_prev) {
		elem->f_prev->f_next = elem->f_next;
	}
	if(elem->f_next) {
		elem->f_next->f_prev = elem->f_prev;
	}
	elem->f_next = elem->f_prev = NULL;
	if(table->used && table->used->u_prev) {
		table->used->u_prev->u_next = elem;
	}
	elem->u_prev = table->used ? table->used->u_prev : NULL; // unused
	elem->u_next = table->used;
	if(table->used) {
		table->used->u_prev = elem;
	}
	table->used = elem;
	
	cid = elem->cid;
	eid = elem->eid;
	if(table->data[cid] == NULL) {
		table->data[cid] = mem_alloc((sizeof(uint) * 2 + table->stride) * table->load, table->cat);
		table->alloc += 1;
	}
	table->sizes[cid] += 1;
	block = (uint *)(&((byte *)(table->data[cid]))[eid * (sizeof(uint) * 2 + table->stride)]);
	block[0] = cid;
	block[1] = eid;
	block += 2;
	table->stored += 1;
	// elem->value = (void *)block;
	return (void *)block;
}

void itbl_init(itable_t *table, uint size, uint load, uint stride, byte cat);

void *tbl_push(table_t *table) {
	void *elem;
	for(int z = 0; z < table->size; z++) {
		if(elem = itbl_push(&table->nodes[z])) {
			table->stored += 1;
			return elem;
		}
	}
	table->nodes = mem_realloc(table->nodes, sizeof(itable_t) * (table->size + 1), table->cat);
	itbl_init(&table->nodes[table->size], table->block, table->load, table->stride, table->cat);
	elem = itbl_push(&table->nodes[table->size]);
	table->size += 1;
	table->stored += 1;
	return elem;
}

byte itbl_pop(itable_t *table, void *ptr) {
	uint *block = ((uint *)ptr) - 2;
	int cid = block[0];
	int eid = block[1];
	if(block != (uint *)(&((byte *)(table->data[cid]))[eid * (sizeof(uint) * 2 + table->stride)]))
		return 0;
	table_e *elem = &table->elems[cid * table->load + eid];
	if(elem == table->used) {
		table->used = table->used->u_next ? table->used->u_next : table->used->u_prev;
	}
	if(elem->u_prev) {
		elem->u_prev->u_next = elem->u_next;
	}
	if(elem->u_next) {
		elem->u_next->u_prev = elem->u_prev;
	}
	elem->u_next = elem->u_prev = NULL;
	if(table->free && table->free->f_prev) {
		table->free->f_prev->f_next = elem;
	}
	elem->f_prev = table->free ? table->free->f_prev : NULL;
	elem->f_next = table->free;
	if(table->free) {
		table->free->f_prev = elem;
	}
	table->free = elem;
	
	if((table->sizes[cid] -= 1) == 0) {
		mem_free(table->data[cid]);
		table->data[cid] = NULL;
		table->alloc -= 1;
	}
	table->stored -= 1;
	// elem->value = NULL;
	return 1;
}

void itbl_free(itable_t *table);

byte tbl_pop(table_t *table, void *ptr) {
	itable_t *itable;
	for(int z = 0; z < table->size; z++) {
		itable = &table->nodes[z];
		if(itbl_pop(itable, ptr)) {
			table->stored -= 1;
			if(!itable->stored) {
				itbl_free(&table->nodes[z]);
				itable = table->size == 1 ? NULL : mem_alloc(sizeof(itable_t) * (table->size - 1), table->cat);
				table->size -= 1;
				if(z)
					memcpy(itable, table->nodes, z * sizeof(itable_t));
				if(z < table->size)
					memcpy(&itable[z], &table->nodes[z+1], (table->size - z) * sizeof(itable_t));
				mem_free(table->nodes);
				table->nodes = itable;
			}
			return 1;
		}
	}
	return 0;
}

void *itbl_iter(itable_t *table, uint *ptr) {
	table_e *elem = ((*ptr) == 0xffffffff) ? NULL : (((*ptr) == 0) ? table->used : &table->elems[(*ptr)-1]);
	if(elem == NULL) {
		return NULL;
	}
	*ptr = elem->u_next ? ((elem->u_next->cid * table->load + elem->u_next->eid) + 1) : 0xffffffff;
	return ((uint *)(&((byte *)(table->data[elem->cid]))[elem->eid * (sizeof(uint) * 2 + table->stride)])) + 2;
}

void *tbl_iter(table_t *table, ulong *ptr) {
	uint tid = (uint)((*ptr) & 0xffffffff);
	uint nid = (uint)((*ptr) >> 32);
	void *elem;
	if(tid >= table->size) {
		return NULL;
	}
	elem = itbl_iter(&table->nodes[tid], &nid);
	while(!elem) {
		if(++tid >= table->size)
			return NULL;
		nid = 0;
		elem = itbl_iter(&table->nodes[tid], &nid);
	}
	*ptr = (ulong)tid | ((ulong)nid << 32);
	return elem;
}


void itbl_dealloc(itable_t *table) {
	for(int z = 0; z < table->chunks; z++) {
		if(table->data[z]) {
			mem_free(table->data[z]);
			table->data[z] = NULL;
			table->sizes[z] = 0;
		}
	}
}

void itbl_clear(itable_t *table) {
	table_e *elem;
	itbl_dealloc(table);
	table->stored = table->alloc = 0;
	table->used = NULL;
	table->free = table->elems;
	for(int z = 0; z < table->size; z++) {
		elem = &table->elems[z];
		elem->f_prev = (z == 0) ? NULL : &table->elems[z-1];
		elem->f_next = (z == (table->size - 1)) ? NULL : &table->elems[z+1];
		elem->u_prev = elem->u_next = NULL;
		// elem->value = NULL;
		elem->cid = z / table->load;
		elem->eid = z % table->load;
	}
}

void itbl_init(itable_t *table, uint size, uint load, uint stride, byte cat) {
	table->size = size * load;
	table->load = load;
	table->chunks = table->size / table->load;
	table->stride = stride;
	table->cat = cat;
	table->elems = mem_alloc(table->size * sizeof(table_e), cat);
	table->data = mem_alloc(table->chunks * sizeof(void *), cat);
	memset(table->data, 0, table->chunks * sizeof(void *));
	table->sizes = mem_alloc(table->chunks * sizeof(uint), cat);
	memset(table->sizes, 0, table->chunks * sizeof(uint));
	itbl_clear(table);
}

void tbl_init(table_t *table, uint block, uint load, uint stride, byte cat) {
	table->load = load;
	table->block = block;
	table->stride = stride;
	table->cat = cat;
	table->nodes = NULL;
	table->size = table->stored = 0;
}

void itbl_free(itable_t *table) {
	itbl_dealloc(table);
	mem_free(table->elems);
	mem_free(table->data);
	mem_free(table->sizes);
}

void tbl_clear(table_t *table) {
	for(int z = 0; z < table->size; z++) {
		itbl_free(&table->nodes[z]);
	}
	if(table->nodes) {
		mem_free(table->nodes);
		table->nodes = NULL;
	}
	table->size = table->stored = 0;
}

int tbl_clear_func(table_t *table, clear_func *func) {
	ulong iter = 0;
	int pos = 0;
	void *elem;
	while(elem = tbl_iter(table, &iter)) {
		func(elem);
		pos++;
	}
	tbl_clear(table);
	return pos;
}

int tbl_clear_func_sel(table_t *table, clear_sfunc *func, int count) {
	ulong iter = 0;
	int pos = 0;
	void *elem;
	void **clr = mem_alloc(sizeof(void*) * count, table->cat);
	while(elem = tbl_iter(table, &iter)) {
		if(func(elem))
			clr[pos++] = elem;
	}
	for(iter = 0; iter < pos; iter++) {
		tbl_pop(table, clr[iter]);
	}
	mem_free(clr);
	return pos;
}