diff options
author | Pete Batard <pbatard@gmail.com> | 2010-10-12 19:21:29 +0100 |
---|---|---|
committer | Pete Batard <pbatard@gmail.com> | 2010-10-12 19:21:29 +0100 |
commit | c6a552ee3cd7255e4045402be71f022d2aec32ef (patch) | |
tree | e18fe8025c27bbb55d0360d6dddb11caf82e077a | |
parent | f7b57e0b199a0f623930000266ed401abf9e22ca (diff) | |
download | libusb-c6a552ee3cd7255e4045402be71f022d2aec32ef.tar.gz |
hash function for session id now uses a proper hash table
* hash table functions modified from glibc (LGPL)
-rw-r--r-- | libusb/os/windows_usb.c | 178 |
1 files changed, 169 insertions, 9 deletions
diff --git a/libusb/os/windows_usb.c b/libusb/os/windows_usb.c index a61176f..5281e31 100644 --- a/libusb/os/windows_usb.c +++ b/libusb/os/windows_usb.c @@ -4,6 +4,7 @@ * With contributions from Michael Plante, Orin Eman et al. * Parts of this code adapted from libusb-win32-v1 by Stephan Meyer * HID Reports IOCTLs inspired from HIDAPI by Alan Ott, Signal 11 Software + * Hash table functions adapted from glibc, by Ulrich Drepper et al. * Major code testing contribution by Xiaofan Chen * * This library is free software; you can redistribute it and/or @@ -385,16 +386,170 @@ err_exit: return NULL; } -/* - * Hash a string (Nokia suggestion) - * TODO: add collision detection (also flag 0x00000000 as reserved) - */ -static inline unsigned long hash(const char* sz) +/* 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 elements 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. */ + +/* NB: the only way we would ever need a mutex here is if 2 colliding + hashes were to be stored concurrently from 2 different threads. */ + +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; /* r * 33 + c */ + 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 r; + } + 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 r; + } + } + 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); + memcpy(htab_table[idx].str, str, safe_strlen(str)+1); + ++htab_filled; + usbi_mutex_unlock(&htab_write_mutex); + return r; } @@ -418,7 +573,7 @@ static unsigned long get_parent_session_id(DWORD devinst) if (sanitized_path == NULL) { return 0; } - session_id = hash(sanitized_path); + session_id = htab_hash(sanitized_path); safe_free(sanitized_path); return session_id; } @@ -454,7 +609,7 @@ static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp) if (sanitized_path == NULL) { return 0; } - session_id = hash(sanitized_path); + session_id = htab_hash(sanitized_path); safe_free(sanitized_path); return session_id; } @@ -703,6 +858,9 @@ static int windows_init(struct libusb_context *ctx) } SetThreadAffinityMask(timer_thread, 0); + // Create a hash table to store session ids (769 is prime) + htab_create(ctx, 769); + r = LIBUSB_SUCCESS; } @@ -732,6 +890,7 @@ init_exit: // Holds semaphore here. CloseHandle(timer_mutex); timer_mutex = NULL; } + htab_destroy(); } if (r != LIBUSB_SUCCESS) @@ -1294,7 +1453,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 = hash(dev_id_path); + session_id = htab_hash(dev_id_path); dev = usbi_get_device_by_session_id(ctx, session_id); if (dev != NULL) { // No need to re-process hubs @@ -1470,6 +1629,7 @@ static void windows_exit(void) CloseHandle(timer_mutex); timer_mutex = NULL; } + htab_destroy(); } ReleaseSemaphore(semaphore, 1, NULL); // increase count back to 1 |