/*
 * Example implementation of the routing table in an iceberg hash table.
 * The routing table maps key fingerprints to array indices.
 *
 * In this example:
 *  - the "bin" has a fixed size of six
 *  - fingerprints and indices are 4 bits wide
 *  - an uint32_t is used to store the 6*(4+1)=29 bits
 *  - the hash function generates fingerprints in range 1-13
 *  - fingerprint 0 denotes an empty field in the table
 */

#include <cstdint>
#include <iostream>


/* word with all 6 test bits set to 1 */
#define testbits ((1<<29) | (1<<24) | (1<<19) | (1<<14) | (1<<9) | (1<<4))

/* pack 6 copies of f (with padding bits) into a word; f is 4 bits wide */
#define pack_word(f) ((f<<25) | (f<<20) | (f<<15) | (f<<10) | (f<<5) | f)

/* find first set bit in w. rightmost bit (lsb) has position 1. */
#define ffs(w) (__builtin_ffs(w))

/* extract one of the six 4-bit fields from w.
 * k is the test bit left to the field (5,10,15,20,25,30) */
#define extract_field(w,k) (((w)>>((k)-5)) & 0x0f)

/* write one field in w. v is the 4-bit value to write.
 * k is the test bit left to the field (5,10,15,20,25,30) */
#define write_field(w,v,k) ( ((w)&~(0x0f<<((k)-5))) | ((v)<<((k)-5)) )


struct RoutingTable
{
	uint32_t fingerprints = 0;
	uint32_t indices = 0;

	/* get the index to which the fingerprint 'fp' points, or -1 if 'fp' is not in table */
	int query(unsigned fp) {

		// concat 6 copies of 'fp' (with one bit padding)
		uint32_t testword = pack_word(fp);

		// test bits are 1 if the field in 'fingerprints' is greater-equal 'fp'
		uint32_t X = (fingerprints | testbits) - testword;
		// test bits are 1 if 'fp' is greater-equal the field in 'fingerprints'
		uint32_t Y = (testword | testbits) - fingerprints;

		// test bits are 1 if 'fp' equals a field in 'fingerprints'
		int res = ffs(X & Y & testbits); // 0, 5, 10, 15, 20, 25, 30

		if (res)
			// get the value in 'indices' that correspondents to the fingerprint
			return extract_field(indices, res);

		return -1; // 'fp' not in table
	}

	/* add (fp,index) pair to the table. does not check if 'fp' is already in the table */
	int add(unsigned fp, unsigned index) {

		// look for field with value zero
		uint32_t testword = pack_word(0);

		uint32_t X = (fingerprints | testbits) - testword;
		uint32_t Y = (testword | testbits) - fingerprints;

		int res = ffs(X & Y & testbits);

		if (res) {
			// write 'fp' to field in 'fingerprints'
			fingerprints = write_field(fingerprints, fp, res);
			// write 'index' to field in 'indices'
			indices = write_field(indices, index, res);

			return 0;
		}

		return -1; // no free field
	}

	/* remove a fingerprint from the table */
	int remove(unsigned fp) {

		// search like in query()
		uint32_t testword = pack_word(fp);

		uint32_t X = (fingerprints | testbits) - testword;
		uint32_t Y = (testword | testbits) - fingerprints;

		int res = ffs(X & Y & testbits);

		if (res) {
			// zero out the field
			fingerprints = write_field(fingerprints, 0, res);

			return 0;
		}

		return -1; // 'fp' not in table
	}
};

/* a bin of the frontyard */
struct Bin
{
	uint8_t vacancy_map = 0x3f;
	RoutingTable rt;
	unsigned slots[6];

	/* calc the fingerprint of a key.
	 * fingerprints are 4 bits wide and have values from 1 to 13. */
	unsigned fp(unsigned key) {
		return (key % 13) + 1;
	}

	/* insert key into bin */
	int insert(unsigned key) {

		int slot = rt.query(fp(key));
		if (slot >= 0) {
			if (slots[slot] == key)
				return -1; // key already in the bin
			else
				return -2; // different key with same fingerprint present
		}

		// query vacancy map for an available slot
		int vacant_slot = ffs(vacancy_map) - 1;
		if (vacant_slot == -1)
			return -3; // no space left

		rt.add(fp(key), vacant_slot);
		vacancy_map &= ~(1<<vacant_slot); // mark slot occupied
		slots[vacant_slot] = key;

		return 0; // ok
	}

	/* remove key from bin */
	int remove(unsigned key) {

		int idx = rt.query(fp(key));
		if (idx >= 0 && slots[idx] == key) {
			rt.remove(fp(key));
			vacancy_map |= (1<<idx); // mark slot vacant

			return 0; // ok
		}

		return -1; // key not found
	}

	int contains(unsigned key) {

		int idx = rt.query(fp(key));
		if (idx >= 0 && slots[idx] == key)
			return true;

		return false;
	}
};

void printbits(uint64_t bits, int fields=6, int width=5) {
	unsigned lsb, pos;

	while (fields--) {
		lsb = fields*width;
		pos = width;
		while (pos--)
			std::cout << ((bits & (1<<(lsb+pos))) ? '1' : '0');
		std::cout << ' ';
	}
	std::cout << std::endl;
}

int main()
{
	Bin bin;

	std::cout << bin.insert(7) << " ";
	std::cout << bin.insert(8) << " ";
	std::cout << bin.insert(9) << " ";
	std::cout << bin.insert(10) << " ";
	std::cout << bin.insert(20) << " ";

	std::cout << std::endl;

	std::cout << bin.remove(9) << " ";
	std::cout << bin.remove(7) << " ";
	std::cout << bin.remove(5) << " ";

	std::cout << std::endl;

	std::cout << bin.contains(9) << " ";
	std::cout << bin.contains(7) << " ";
	std::cout << bin.contains(5) << " ";
	std::cout << bin.contains(8) << " ";
	std::cout << bin.contains(10) << " ";

	std::cout << std::endl;

	std::cout << bin.insert(6) << " ";
	std::cout << bin.insert(5) << " ";
	std::cout << bin.insert(4) << " ";
	std::cout << bin.insert(3) << " ";
	std::cout << bin.insert(2) << " ";

	std::cout << std::endl;

	printbits(bin.rt.fingerprints);
	printbits(bin.rt.indices);
}