mailund/cuckoo

Implementation of cuckoo hashing

cuckoo's Issues

this is a mock hash function

---

opened via imdone.io from a code comment on d3c54cc14da4e500ffbdeb1a79bd199ca079ab11 by Thomas Mailund [email protected]

---

cuckoo/libcuckoo/cuckoo.c

Lines 33 to 38 in d3c54cc

	// FIXME: this is a mock hash function
	static hash_index_type mock_new_hash_index(hash_index_type old)
	{
	return old;
	}
	static void mock_free_hash_index(hash_index_type index)

I don't actually test how it deals with

collisions on the second hash function...

---

opened via imdone.io from a code comment on 9ef3abfdf3a491fd04289ccb219c0a7a3808b003 by Thomas Mailund [email protected]

---

cuckoo/tests/insertion_test.c

Lines 26 to 32 in 28eae17

	// FIXME: I don't actually test how it deals with
	// collisions on the second hash function...
	static void initialise_hash_keys()
	{
	for (int i = 0; i < NO_KEYS; ++i) {
	keys[i] = hash_keys[i] = i;

This is passed like: "a b c", not "a;b;c"

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/cmake/Coveralls.cmake

Lines 75 to 80 in 28eae17

	-DCOVERAGE_SRCS="${COVERAGE_SRCS}" # TODO: This is passed like: "a b c", not "a;b;c"
	-DCOVERALLS_OUTPUT_FILE="${COVERALLS_FILE}"
	-DCOV_PATH="${PROJECT_BINARY_DIR}"
	-DPROJECT_ROOT="${PROJECT_SOURCE_DIR}"
	-P "${_CMAKE_SCRIPT_PATH}/CoverallsGenerateGcov.cmake"

replace modulus with bit operations

---

opened via imdone.io from a code comment on 9ef3abfdf3a491fd04289ccb219c0a7a3808b003 by Thomas Mailund [email protected]

---

cuckoo/libcuckoo/cuckoo_internal.h

Lines 15 to 20 in 28eae17

	// TODO: replace modulus with bit operations
	#define HASH0(table, key) \
	(size_t)(((table->a0 * key + table->b0) % LARGE_PRIME) & (table->table_size - 1))
	#define HASH1(table, key) \
	(size_t)(((table->a1 * key + table->b1) % LARGE_PRIME) & (table->table_size - 1))

, not this much

---

opened via imdone.io from a code comment on 28eae17

---

cuckoo/libcuckoo/cuckoo.c

Lines 172 to 177 in 28eae17

	int attempt_threshold = map->table_size; // FIXME, not this much
	for (int i = 0; i < attempt_threshold; ++i) {
	// I'm using the last bit of i to pick the table.
	// This is so I can simply increment i to pick the other table.

Enable setting these

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/cmake/CoverallsGenerateGcov.cmake

Lines 275 to 280 in 28eae17

	# TODO: Enable setting these
	set(JSON_SERVICE_NAME "travis-ci")
	set(JSON_SERVICE_JOB_ID $ENV{TRAVIS_JOB_ID})
	set(JSON_REPO_TOKEN $ENV{COVERALLS_REPO_TOKEN})
	set(JSON_TEMPLATE

There must be a better way to set these files

set(COVERAGE_SRCS 
	libcuckoo/cuckoo.h 
	libcuckoo/cuckoo_internal.h 
	libcuckoo/cuckoo.c)
coveralls_setup("${COVERAGE_SRCS}" ON) # ON / OFF upload

endif()

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/CMakeLists.txt

Lines 11 to 22 in 28eae17

	#FIXME: There must be a better way to set these files
	set(COVERAGE_SRCS
	libcuckoo/cuckoo.h
	libcuckoo/cuckoo_internal.h
	libcuckoo/cuckoo.c)
	coveralls_setup("${COVERAGE_SRCS}" ON) # ON / OFF upload
	endif()
	# Make sure we use C99 with gcc
	if (CMAKE_COMPILER_IS_GNUCC)
	set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -std=c99")
	endif()

what should the threshold be?

---

opened via imdone.io from a code comment on d3c54cc14da4e500ffbdeb1a79bd199ca079ab11 by Thomas Mailund [email protected]

---

cuckoo/libcuckoo/cuckoo.c

Lines 161 to 166 in d3c54cc

	// FIXME: what should the threshold be?
	int attempt_threshold = set->table_size;
	struct table_bin *bin;
	for (int i = 0; i < attempt_threshold; ++i) {
	bin = &(set->table1[x.hash_key1]);

Make these be absolute path

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/cmake/CoverallsGenerateGcov.cmake

Lines 212 to 217 in 28eae17

	# TODO: Make these be absolute path
	file(GLOB ALL_GCOV_FILES ${COV_PATH}/*.gcov)
	# Get only the filenames to use for filtering.
	#set(COVERAGE_SRCS_NAMES "")
	#foreach (COVSRC ${COVERAGE_SRCS})

Fill in git remote data

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/cmake/CoverallsGenerateGcov.cmake

Lines 108 to 113 in 28eae17

	# TODO: Fill in git remote data
	if (GIT_FOUND)
	# Branch.
	execute_process(
	COMMAND ${GIT_EXECUTABLE} rev-parse --abbrev-ref HEAD
	WORKING_DIRECTORY ${CMAKE_SOURCE_DIR}

Uploading to coveralls doesn't work

It looks like it really needs the repo token. I need to find out how to upload that without putting it in the source...

We want to match against relative path filenames from the source file root...

---

opened via imdone.io from a code comment on d86e4e870efc42f5c79eb5c4ba11b243b5320802 by Thomas Mailund [email protected]

---

cuckoo/cmake/CoverallsGenerateGcov.cmake

Lines 259 to 264 in 28eae17

	# TODO: We want to match against relative path filenames from the source file root...
	list(FIND COVERAGE_SRCS ${GCOV_SRC_PATH} WAS_FOUND)
	if (NOT WAS_FOUND EQUAL -1)
	message("YES: ${GCOV_FILE}")
	list(APPEND GCOV_FILES ${GCOV_FILE})

mock up a hash function

---

opened via imdone.io from a code comment on d3c54cc14da4e500ffbdeb1a79bd199ca079ab11 by Thomas Mailund [email protected]

---

cuckoo/tests/insertion_test.c

Lines 11 to 16 in d3c54cc

	// FIXME: mock up a hash function
	hash_key_type keys1[] = { 5, 1, 5, 1, 5 };
	hash_key_type keys2[] = { 2, 2, 4, 6, 6 };
	static int hack = 0;
	static hash_index_type mock_new_hash_index(hash_index_type old)
	{

, not this much

---

opened via imdone.io from a code comment on 28eae17

---

cuckoo/libcuckoo/cuckoo.c

Lines 84 to 89 in 28eae17

	int attempt_threshold = set->table_size; // FIXME, not this much
	for (int i = 0; i < attempt_threshold; ++i) {
	// I'm using the last bit of i to pick the table.
	// This is so I can simply increment i to pick the other table.

Setup CI

• Setup travis
• Setup coveralls

The cmake module I have included should handle coveralls if I get it configured to run on Travis.