move hash table functions from Windows to core

5 files changed, 204 insertions, 204 deletions

diff --git a/libusb/core.c b/libusb/core.c
index 12c0c9c..cb0038d 100644
--- a/libusb/core.c
+++ b/libusb/core.c
@@ -1530,6 +1530,184 @@ void API_EXPORTED libusb_set_debug(libusb_context *ctx, int level)
 		ctx->debug = level;
 }
 
+/* Hash table functions - modified From glibc 2.3.2:
+   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
+   [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
+#define DEFAULT_HTAB_SIZE 1021
+
+/* For the used double hash method the table size has to be a prime. To
+   correct the user given table size we need a prime test.  This trivial
+   algorithm is adequate because the code is called only during init and
+   the number is likely to be small  */
+static int isprime(unsigned long number)
+{
+	// no even number will be passed
+	unsigned int divider = 3;
+
+	while((divider * divider < number) && (number % divider != 0))
+		divider += 2;
+
+	return (number % divider != 0);
+}
+
+/* Before using the hash table we must allocate memory for it.
+   We allocate one element more as the found prime number says.
+   This is done for more effective indexing as explained in the
+   comment for the hash function.  */
+static int usbi_htab_create(struct libusb_context *ctx, unsigned long nel)
+{
+	if (ctx == NULL) {
+		usbi_err(ctx, "null context");
+		return 0;
+	}
+
+	if (ctx->htab_table != NULL) {
+		usbi_err(ctx, "hash table already allocated");
+		return 0;
+	}
+
+	// Create a mutex
+	usbi_mutex_init(&ctx->htab_write_mutex, NULL);
+
+	// Change nel to the first prime number not smaller as nel.
+	nel |= 1;
+	while(!isprime(nel))
+		nel += 2;
+
+	ctx->htab_size = nel;
+	usbi_dbg("using %d entries hash table", nel);
+	ctx->htab_filled = 0;
+
+	// allocate memory and zero out.
+	ctx->htab_table = (struct htab_entry*)calloc(ctx->htab_size + 1, sizeof(struct htab_entry));
+	if (ctx->htab_table == NULL) {
+		usbi_err(ctx, "could not allocate space for hash table");
+		return 0;
+	}
+
+	return 1;
+}
+
+/* After using the hash table it has to be destroyed.  */
+static void usbi_htab_destroy(struct libusb_context *ctx)
+{
+	size_t i;
+	if ((ctx == NULL) || (ctx->htab_table == NULL)) {
+		return;
+	}
+
+	for (i=0; i<ctx->htab_size; i++) {
+		if (ctx->htab_table[i].used) {
+			free(ctx->htab_table[i].str);
+		}
+	}
+	usbi_mutex_destroy(&ctx->htab_write_mutex);
+	free(ctx->htab_table);
+}
+
+/* This is the search function. It uses double hashing with open addressing.
+   We use an trick to speed up the lookup. The table is created with one
+   more element available. This enables us to use the index zero special.
+   This index will never be used because we store the first hash index in
+   the field used where zero means not used. Every other value means used.
+   The used field can be used as a first fast comparison for equality of
+   the stored and the parameter value. This helps to prevent unnecessary
+   expensive calls of strcmp.  */
+unsigned long usbi_htab_hash(struct libusb_context *ctx, const char* str)
+{
+	unsigned long hval, hval2;
+	unsigned long idx;
+	unsigned long r = 5381;
+	int c;
+	char* sz = (char*) str;
+
+	if (ctx == NULL) {
+		usbi_err(ctx, "no context");
+		return 0;
+	}
+	if ((str == NULL) || (str[0] == 0)) {
+		usbi_err(ctx, "empty string");
+		return 0;
+	}
+
+	// Compute main hash value (djb2 algorithm)
+	while ((c = *sz++))
+		r = ((r << 5) + r) + c;
+	if (r == 0)
+		++r;
+
+	// compute table hash: simply take the modulus
+	hval = r % ctx->htab_size;
+	if (hval == 0)
+		++hval;
+
+	// Try the first index
+	idx = hval;
+
+	if (ctx->htab_table[idx].used) {
+		if ( (ctx->htab_table[idx].used == hval)
+		  && (strcmp(str, ctx->htab_table[idx].str) == 0) ) {
+			// existing hash
+			return idx;
+		}
+		usbi_dbg("hash collision ('%s' vs '%s')", str, ctx->htab_table[idx].str);
+
+		// Second hash function, as suggested in [Knuth]
+		hval2 = 1 + hval % (ctx->htab_size - 2);
+
+		do {
+			// Because size is prime this guarantees to step through all available indexes
+			if (idx <= hval2) {
+				idx = ctx->htab_size + idx - hval2;
+			} else {
+				idx -= hval2;
+			}
+
+			// If we visited all entries leave the loop unsuccessfully
+			if (idx == hval) {
+				break;
+			}
+
+			// If entry is found use it.
+			if ( (ctx->htab_table[idx].used == hval)
+			  && (strcmp(str, ctx->htab_table[idx].str) == 0) ) {
+				return idx;
+			}
+		}
+		while (ctx->htab_table[idx].used);
+	}
+
+	// Not found => New entry
+
+	// If the table is full return an error
+	if (ctx->htab_filled >= ctx->htab_size) {
+		usbi_err(ctx, "hash table is full (%d entries)", ctx->htab_size);
+		return 0;
+	}
+
+	// Concurrent threads might be storing the same entry at the same time
+	// (eg. "simultaneous" enums from different threads) => use a mutex
+	usbi_mutex_lock(&ctx->htab_write_mutex);
+	// Just free any previously allocated string (which should be the same as
+	// new one). The possibility of concurrent threads storing a collision
+	// string (same hash, different string) at the same time is extremely low
+	if (ctx->htab_table[idx].str != NULL) {
+		free(ctx->htab_table[idx].str);
+	}
+	ctx->htab_table[idx].used = hval;
+	ctx->htab_table[idx].str = malloc(strlen(str)+1);
+	if (ctx->htab_table[idx].str == NULL) {
+		usbi_err(ctx, "could not duplicate string for hash table");
+		usbi_mutex_unlock(&ctx->htab_write_mutex);
+		return 0;
+	}
+	memcpy(ctx->htab_table[idx].str, str, strlen(str)+1);
+	++ctx->htab_filled;
+	usbi_mutex_unlock(&ctx->htab_write_mutex);
+
+	return idx;
+}
+
 /** \ingroup lib
  * Initialize libusb. This function must be called before calling any other
  * libusb function.
@@ -1609,6 +1787,10 @@ int API_EXPORTED libusb_init(libusb_context **context)
 		usbi_default_context = ctx;
 		default_context_refcnt++;
 	}
+
+	// TODO: check return
+	usbi_htab_create(ctx, DEFAULT_HTAB_SIZE);
+
 	usbi_mutex_static_unlock(&default_context_lock);
 
 	return 0;
@@ -1649,6 +1831,8 @@ void API_EXPORTED libusb_exit(struct libusb_context *ctx)
 		usbi_mutex_static_unlock(&default_context_lock);
 	}
 
+	usbi_htab_destroy(ctx);
+
 	/* a little sanity check. doesn't bother with open_devs locking because
 	 * unless there is an application bug, nobody will be accessing this. */
 	if (!list_empty(&ctx->open_devs))
diff --git a/libusb/libusbi.h b/libusb/libusbi.h
index 2963a9a..f829fa4 100644
--- a/libusb/libusbi.h
+++ b/libusb/libusbi.h
@@ -179,26 +179,6 @@ static inline void usbi_dbg(const char *format, ...)
 
 #endif /* !defined(_MSC_VER) || _MSC_VER > 1200 */
 
-/*
- * djb2
- *
- * This algorithm (k=33) was first reported by Dan Bernstein many years
- * ago in comp.lang.c.
- */
-// TODO: maintain a hash table and detect collisions
-static inline unsigned long usbi_hash(const char* sz)
-{
-	unsigned long r = 5381;
-	int c;
-	while ((c = *sz++)) {
-		r = ((r << 5) + r) + c; /* r * 33 + c */
-	}
-	if (r == 0) {
-		usbi_warn(NULL, "'%s''s hash is 0!", sz);
-	}
-	return r;
-}
-
 #define USBI_GET_CONTEXT(ctx) if (!(ctx)) (ctx) = usbi_default_context
 #define DEVICE_CTX(dev) ((dev)->ctx)
 #define HANDLE_CTX(handle) (DEVICE_CTX((handle)->dev))
@@ -275,6 +255,15 @@ struct libusb_context {
 	int timerfd;
 #endif
 
+	/* the following are used to maintain a hash table for session IDs */
+	usbi_mutex_t htab_write_mutex;
+	unsigned long htab_size;
+	unsigned long htab_filled;
+	struct htab_entry {
+		unsigned long used;
+		char* str;
+	}* htab_table;
+
 	libusb_hotplug_cb_fn hotplug_connected_listener;
 	libusb_hotplug_cb_fn hotplug_disconnected_listener;
 	void* hotplug_listener_user_data;
@@ -391,6 +380,7 @@ struct libusb_device *usbi_get_device_by_session_id(struct libusb_context *ctx,
 struct libusb_device *usbi_get_device_by_session_id_ref(struct libusb_context *ctx,
 	unsigned long session_id);
 int usbi_sanitize_device(struct libusb_device *dev);
+unsigned long usbi_htab_hash(struct libusb_context *ctx, const char* str);
 void usbi_handle_disconnect(struct libusb_device_handle *handle);
 
 int usbi_handle_transfer_completion(struct usbi_transfer *itransfer,
diff --git a/libusb/os/linux_usbfs.c b/libusb/os/linux_usbfs.c
index eed8a9c..f006fff 100644
--- a/libusb/os/linux_usbfs.c
+++ b/libusb/os/linux_usbfs.c
@@ -839,7 +839,7 @@ static int get_device(struct libusb_context* ctx,
 	unsigned long session_id;
 	int r = 0;
 
-	session_id = usbi_hash(sysfs_dir);
+	session_id = usbi_htab_hash(ctx, sysfs_dir);
 	usbi_dbg("busnum %d devaddr %d session_id %ld", busnum, devaddr,
 		session_id);
 
@@ -2227,7 +2227,7 @@ static void handle_hotplug_event(struct libusb_context *ctx)
 		}
 	}
 	else if (strncmp(udev_action, "remove", 6) == 0) {
-		dev = usbi_get_device_by_session_id_ref(ctx, usbi_hash(sys_name));
+		dev = usbi_get_device_by_session_id_ref(ctx, usbi_htab_hash(ctx, sys_name));
 		if (dev) {
 			pthread_mutex_lock(&dev->status_online_lock);
 			dev->status_online = 0;
diff --git a/libusb/os/windows_usb.c b/libusb/os/windows_usb.c
index 547d9c1..6019bbb 100644
--- a/libusb/os/windows_usb.c
+++ b/libusb/os/windows_usb.c
@@ -391,177 +391,10 @@ err_exit:
 	return NULL;
 }
 
-/* Hash table functions - modified From glibc 2.3.2:
-   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
-   [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
-typedef struct htab_entry {
-	unsigned long used;
-	char* str;
-} htab_entry;
-htab_entry* htab_table = NULL;
-usbi_mutex_t htab_write_mutex = NULL;
-unsigned long htab_size, htab_filled;
-
-/* For the used double hash method the table size has to be a prime. To
-   correct the user given table size we need a prime test.  This trivial
-   algorithm is adequate because the code is called only during init and
-   the number is likely to be small  */
-static int isprime(unsigned long number)
-{
-	// no even number will be passed
-	unsigned int divider = 3;
-
-	while((divider * divider < number) && (number % divider != 0))
-		divider += 2;
-
-	return (number % divider != 0);
-}
-
-/* Before using the hash table we must allocate memory for it.
-   We allocate one element more as the found prime number says.
-   This is done for more effective indexing as explained in the
-   comment for the hash function.  */
-int htab_create(struct libusb_context *ctx, unsigned long nel)
-{
-	if (htab_table != NULL) {
-		usbi_err(ctx, "hash table already allocated");
-	}
-
-	// Create a mutex
-	usbi_mutex_init(&htab_write_mutex, NULL);
-
-	// Change nel to the first prime number not smaller as nel.
-	nel |= 1;
-	while(!isprime(nel))
-		nel += 2;
-
-	htab_size = nel;
-	usbi_dbg("using %d entries hash table", nel);
-	htab_filled = 0;
-
-	// allocate memory and zero out.
-	htab_table = (htab_entry*)calloc(htab_size + 1, sizeof(htab_entry));
-	if (htab_table == NULL) {
-		usbi_err(ctx, "could not allocate space for hash table");
-		return 0;
-	}
-
-	return 1;
-}
-
-/* After using the hash table it has to be destroyed.  */
-void htab_destroy(void)
-{
-	size_t i;
-	if (htab_table == NULL) {
-		return;
-	}
-
-	for (i=0; i<htab_size; i++) {
-		if (htab_table[i].used) {
-			safe_free(htab_table[i].str);
-		}
-	}
-	usbi_mutex_destroy(&htab_write_mutex);
-	safe_free(htab_table);
-}
-
-/* This is the search function. It uses double hashing with open addressing.
-   We use an trick to speed up the lookup. The table is created with one
-   more element available. This enables us to use the index zero special.
-   This index will never be used because we store the first hash index in
-   the field used where zero means not used. Every other value means used.
-   The used field can be used as a first fast comparison for equality of
-   the stored and the parameter value. This helps to prevent unnecessary
-   expensive calls of strcmp.  */
-unsigned long htab_hash(char* str)
-{
-	unsigned long hval, hval2;
-	unsigned long idx;
-	unsigned long r = 5381;
-	int c;
-	char* sz = str;
-
-	// Compute main hash value (algorithm suggested by Nokia)
-	while ((c = *sz++))
-		r = ((r << 5) + r) + c;
-	if (r == 0)
-		++r;
-
-	// compute table hash: simply take the modulus
-	hval = r % htab_size;
-	if (hval == 0)
-		++hval;
-
-	// Try the first index
-	idx = hval;
-
-	if (htab_table[idx].used) {
-		if ( (htab_table[idx].used == hval)
-		  && (safe_strcmp(str, htab_table[idx].str) == 0) ) {
-			// existing hash
-			return idx;
-		}
-		usbi_dbg("hash collision ('%s' vs '%s')", str, htab_table[idx].str);
-
-		// Second hash function, as suggested in [Knuth]
-		hval2 = 1 + hval % (htab_size - 2);
-
-		do {
-			// Because size is prime this guarantees to step through all available indexes
-			if (idx <= hval2) {
-				idx = htab_size + idx - hval2;
-			} else {
-				idx -= hval2;
-			}
-
-			// If we visited all entries leave the loop unsuccessfully
-			if (idx == hval) {
-				break;
-			}
-
-			// If entry is found use it.
-			if ( (htab_table[idx].used == hval)
-			  && (safe_strcmp(str, htab_table[idx].str) == 0) ) {
-				return idx;
-			}
-		}
-		while (htab_table[idx].used);
-	}
-
-	// Not found => New entry
-
-	// If the table is full return an error
-	if (htab_filled >= htab_size) {
-		usbi_err(NULL, "hash table is full (%d entries)", htab_size);
-		return 0;
-	}
-
-	// Concurrent threads might be storing the same entry at the same time
-	// (eg. "simultaneous" enums from different threads) => use a mutex
-	usbi_mutex_lock(&htab_write_mutex);
-	// Just free any previously allocated string (which should be the same as
-	// new one). The possibility of concurrent threads storing a collision
-	// string (same hash, different string) at the same time is extremely low
-	safe_free(htab_table[idx].str);
-	htab_table[idx].used = hval;
-	htab_table[idx].str = malloc(safe_strlen(str)+1);
-	if (htab_table[idx].str == NULL) {
-		usbi_err(NULL, "could not duplicate string for hash table");
-		usbi_mutex_unlock(&htab_write_mutex);
-		return 0;
-	}
-	memcpy(htab_table[idx].str, str, safe_strlen(str)+1);
-	++htab_filled;
-	usbi_mutex_unlock(&htab_write_mutex);
-
-	return idx;
-}
-
 /*
  * Returns the Device ID path of a device's parent
  */
-static unsigned long get_parent_session_id(DWORD devinst)
+static unsigned long get_parent_session_id(struct libusb_context *ctx, DWORD devinst)
 {
 	DWORD parent_devinst;
 	unsigned long session_id = 0;
@@ -578,7 +411,7 @@ static unsigned long get_parent_session_id(DWORD devinst)
 	if (sanitized_path == NULL) {
 		return 0;
 	}
-	session_id = htab_hash(sanitized_path);
+	session_id = usbi_htab_hash(ctx, sanitized_path);
 	safe_free(sanitized_path);
 	return session_id;
 }
@@ -586,7 +419,7 @@ static unsigned long get_parent_session_id(DWORD devinst)
 /*
  * Returns the Device ID path of a device's grandparent
  */
-static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp)
+static unsigned long get_grandparent_session_id(struct libusb_context *ctx, DWORD devinst, bool* non_usb_gp)
 {
 	DWORD parent_devinst, grandparent_devinst;
 	unsigned long session_id = 0;
@@ -614,7 +447,7 @@ static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp)
 	if (sanitized_path == NULL) {
 		return 0;
 	}
-	session_id = htab_hash(sanitized_path);
+	session_id = usbi_htab_hash(ctx, sanitized_path);
 	safe_free(sanitized_path);
 	return session_id;
 }
@@ -813,7 +646,7 @@ LRESULT CALLBACK messaging_callback(HWND hWnd, UINT message, WPARAM wParam, LPAR
 					// If it's an insertion, update the list
 					libusb_get_device_list(ctx, &devs);
 				}
-				dev = usbi_get_device_by_session_id(ctx, usbi_hash(hotplug_path));
+				dev = usbi_get_device_by_session_id(ctx, usbi_htab_hash(ctx, hotplug_path));
 				if (dev == NULL) {
 					usbi_warn(ctx, "%s: '%s' (not active)", (online)?"INSERTION":"REMOVAL",
 						hotplug_path);
@@ -1003,9 +836,6 @@ static int windows_init(struct libusb_context *ctx)
 			goto init_exit;
 		}
 
-		// Create a hash table to store session ids Second parameter is better if prime
-		htab_create(ctx, HTAB_SIZE);
-
 		r = LIBUSB_SUCCESS;
 	}
 
@@ -1035,7 +865,6 @@ init_exit: // Holds semaphore here.
 			CloseHandle(timer_mutex);
 			timer_mutex = NULL;
 		}
-		htab_destroy();
 	}
 
 	if (r != LIBUSB_SUCCESS)
@@ -1557,7 +1386,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered
 			case DEV_PASS:
 				break;
 			default:
-				session_id = get_parent_session_id(dev_info_data.DevInst);
+				session_id = get_parent_session_id(ctx, dev_info_data.DevInst);
 				if (session_id == 0) {
 					usbi_err(ctx, "program assertion failed: orphan device '%s'", dev_id_path);
 					LOOP_BREAK(LIBUSB_ERROR_NO_DEVICE);
@@ -1565,7 +1394,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered
 				parent_dev = usbi_get_device_by_session_id(ctx, session_id);
 				// Composite HID devices have double indirection => Check grandparent
 				if (pass == HID_PASS) {
-					session_id = get_grandparent_session_id(dev_info_data.DevInst, &non_usb_hid_parent);
+					session_id = get_grandparent_session_id(ctx, dev_info_data.DevInst, &non_usb_hid_parent);
 					if (session_id == 0) {
 						if (non_usb_hid_parent) {
 							usbi_dbg("skipping non USB HID interface '%s'", dev_id_path);
@@ -1598,7 +1427,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered
 			// Create new or match existing device, using the (hashed) device_id as session id
 			if (pass <= DEV_PASS) {	// For subsequent passes, we'll lookup the parent
 				// These are the passes that create "new" devices
-				session_id = usbi_hash(dev_id_path);
+				session_id = usbi_htab_hash(ctx, dev_id_path);
 				dev = usbi_get_device_by_session_id(ctx, session_id);
 				if (dev != NULL) {
 					// No need to re-process hubs
@@ -1783,8 +1612,6 @@ static void windows_exit(struct libusb_context *ctx)
 				TerminateThread(hotplug_thread, 1);
 			}
 		}
-
-		htab_destroy();
 	}
 
 	ReleaseSemaphore(semaphore, 1, NULL);	// increase count back to 1
diff --git a/libusb/os/windows_usb.h b/libusb/os/windows_usb.h
index 2138361..a1319ca 100644
--- a/libusb/os/windows_usb.h
+++ b/libusb/os/windows_usb.h
@@ -89,7 +89,6 @@ inline void upperize(char* str) {
 #define TIMER_REQUEST_RETRY_MS      100
 #define ERR_BUFFER_SIZE             256
 #define LIST_SEPARATOR              ';'
-#define HTAB_SIZE                   1021
 
 // Handle code for HID interface that have been claimed ("dibs")
 #define INTERFACE_CLAIMED           ((HANDLE)(intptr_t)0xD1B5)