[haiku-commits] haiku: hrev48640 - in src: add-ons/kernel/network/stack system/kernel add-ons/kernel/file_cache add-ons/kernel/network/datalink_protocols/arp system/kernel/device_manager
- From: pulkomandy@xxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Fri, 9 Jan 2015 18:08:47 +0100 (CET)
hrev48640 adds 8 changesets to branch 'master'
old head: ce39d3a366f7d7b5c8055aa594f33668cd8724d8
new head: a2c274e70e7af2cc8cf79a31aa8a41b041067ad2
overview: http://cgit.haiku-os.org/haiku/log/?qt=range&q=a2c274e+%5Ece39d3a
----------------------------------------------------------------------------
69ff01c: Migrate image hash table to BOpenHashTable.
For #9552.
f5acc80: ipv6 datagram: migrate to BOpenHashTable.
6f05b19: ARP: convert to BOpenHashTable
* Replaced the hash function as it wasn't really useful. It seems better
to use the full in_addr_t as a hash as it is a 32bit value. Shuffling it
like the previous hash function did can only increase the number of
collisions.
* BOpenHashTable lacks the "range" parameter to the hash function, so we
can't know which bits from the hash are actually going to be used.
6a89f80: devfs: migrate to BOpenHashTable
For #9552.
d4aabe7: Network stack: migrate to BOpenHashTable
955d525: Rewrite sample HashTable description to use the typedefs
This makes the code more readable (as KeyType and ValueType are clearer
than int and Foo) and easier to copypaste and edit.
271ac91: Remove useless includes of khash.h
* These files were already converted to BOpenHashTable.
* For #9552.
a2c274e: rule based prefetcher: migrate to BOpenHashTable.
For #9552.
[ Adrien Destugues <pulkomandy@xxxxxxxxx> ]
----------------------------------------------------------------------------
15 files changed, 372 insertions(+), 415 deletions(-)
headers/private/kernel/util/OpenHashTable.h | 8 +-
.../kernel/file_cache/rule_based_prefetcher.cpp | 140 +++++------
.../network/datalink_protocols/arp/arp.cpp | 100 ++++----
.../ipv6_datagram/ipv6_datagram.cpp | 84 +++----
.../kernel/network/protocols/ipv6/ipv6.cpp | 1 -
src/add-ons/kernel/network/stack/stack.cpp | 236 +++++++++----------
.../kernel/device_manager/IOSchedulerSimple.cpp | 1 -
src/system/kernel/device_manager/devfs.cpp | 86 ++++---
src/system/kernel/elf.cpp | 124 +++++-----
src/system/kernel/module.cpp | 1 -
src/system/kernel/posix/realtime_sem.cpp | 2 +-
.../kernel/scheduler/scheduling_analysis.cpp | 1 -
src/system/kernel/slab/Slab.cpp | 1 -
src/system/kernel/vm/VMCache.cpp | 1 -
src/system/kernel/vm/vm.cpp | 1 -
############################################################################
Commit: 69ff01cb9ea7aacb1ac487b6a309f4bd192b5755
URL: http://cgit.haiku-os.org/haiku/commit/?id=69ff01c
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 11:01:59 2015 UTC
Ticket: https://dev.haiku-os.org/ticket/9552
Migrate image hash table to BOpenHashTable.
For #9552.
----------------------------------------------------------------------------
diff --git a/src/system/kernel/elf.cpp b/src/system/kernel/elf.cpp
index 4d18448..e501ede 100644
--- a/src/system/kernel/elf.cpp
+++ b/src/system/kernel/elf.cpp
@@ -34,7 +34,6 @@
#include <thread.h>
#include <runtime_loader.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <vfs.h>
#include <vm/vm.h>
#include <vm/vm_types.h>
@@ -56,7 +55,29 @@
#define IMAGE_HASH_SIZE 16
-static hash_table *sImagesHash;
+struct ImageHashDefinition {
+ typedef struct elf_image_info ValueType;
+ typedef image_id KeyType;
+
+ size_t Hash(ValueType* entry) const
+ { return HashKey(entry->id); }
+ ValueType*& GetLink(ValueType* entry) const
+ { return entry->next; }
+
+ size_t HashKey(KeyType key) const
+ {
+ return (size_t)key;
+ }
+
+ bool Compare(KeyType key, ValueType* entry) const
+ {
+ return key - entry->id;
+ }
+};
+
+typedef BOpenHashTable<ImageHashDefinition> ImageHash;
+
+static ImageHash *sImagesHash;
static struct elf_image_info *sKernelImage = NULL;
static mutex sImageMutex = MUTEX_INITIALIZER("kimages_lock");
@@ -71,36 +92,11 @@ static elf_sym *elf_find_symbol(struct elf_image_info
*image, const char *name,
const elf_version_info *version, bool lookupDefault);
-/*! Calculates hash for an image using its ID */
-static uint32
-image_hash(void *_image, const void *_key, uint32 range)
-{
- struct elf_image_info *image = (struct elf_image_info *)_image;
- image_id id = (image_id)(addr_t)_key;
-
- if (image != NULL)
- return image->id % range;
-
- return (uint32)id % range;
-}
-
-
-/*! Compares an image to a given ID */
-static int
-image_compare(void *_image, const void *_key)
-{
- struct elf_image_info *image = (struct elf_image_info *)_image;
- image_id id = (image_id)(addr_t)_key;
-
- return id - image->id;
-}
-
-
static void
unregister_elf_image(struct elf_image_info *image)
{
unregister_image(team_get_kernel_team(), image->id);
- hash_remove(sImagesHash, image);
+ sImagesHash->Remove(image);
}
@@ -161,7 +157,7 @@ register_elf_image(struct elf_image_info *image)
image->id = register_image(team_get_kernel_team(), &imageInfo,
sizeof(image_info));
- hash_insert(sImagesHash, image);
+ sImagesHash->Insert(image);
}
@@ -169,20 +165,19 @@ register_elf_image(struct elf_image_info *image)
static struct elf_image_info *
find_image_at_address(addr_t address)
{
- struct hash_iterator iterator;
- struct elf_image_info *image;
+ struct elf_image_info *image = NULL;
#if KDEBUG
if (!debug_debugger_running())
ASSERT_LOCKED_MUTEX(&sImageMutex);
#endif
- hash_open(sImagesHash, &iterator);
+ ImageHash::Iterator iterator(sImagesHash);
// get image that may contain the address
- while ((image = (elf_image_info *)hash_next(sImagesHash, &iterator))
- != NULL) {
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if ((address >= image->text_region.start && address
<= (image->text_region.start +
image->text_region.size))
|| (address >= image->data_region.start
@@ -191,7 +186,6 @@ find_image_at_address(addr_t address)
break;
}
- hash_close(sImagesHash, &iterator, false);
return image;
}
@@ -234,26 +228,24 @@ dump_address_info(int argc, char **argv)
static struct elf_image_info *
find_image(image_id id)
{
- return (elf_image_info *)hash_lookup(sImagesHash, (void *)(addr_t)id);
+ return sImagesHash->Lookup(id);
}
static struct elf_image_info *
find_image_by_vnode(void *vnode)
{
- struct hash_iterator iterator;
- struct elf_image_info *image;
+ struct elf_image_info *image = NULL;
mutex_lock(&sImageMutex);
- hash_open(sImagesHash, &iterator);
+ ImageHash::Iterator iterator(sImagesHash);
- while ((image = (elf_image_info *)hash_next(sImagesHash, &iterator))
- != NULL) {
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if (image->vnode == vnode)
break;
}
- hash_close(sImagesHash, &iterator, false);
mutex_unlock(&sImageMutex);
return image;
@@ -357,14 +349,13 @@ dump_symbol(int argc, char **argv)
}
struct elf_image_info *image = NULL;
- struct hash_iterator iterator;
const char *pattern = argv[1];
void* symbolAddress = NULL;
- hash_open(sImagesHash, &iterator);
- while ((image = (elf_image_info *)hash_next(sImagesHash, &iterator))
- != NULL) {
+ ImageHash::Iterator iterator(sImagesHash);
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if (image->num_debug_symbols > 0) {
// search extended debug symbol table (contains static
symbols)
for (uint32 i = 0; i < image->num_debug_symbols; i++) {
@@ -396,7 +387,6 @@ dump_symbol(int argc, char **argv)
}
}
}
- hash_close(sImagesHash, &iterator, false);
if (symbolAddress != NULL)
set_debug_variable("_", (addr_t)symbolAddress);
@@ -409,7 +399,6 @@ static int
dump_symbols(int argc, char **argv)
{
struct elf_image_info *image = NULL;
- struct hash_iterator iterator;
uint32 i;
// if the argument looks like a hex number, treat it as such
@@ -420,22 +409,21 @@ dump_symbols(int argc, char **argv)
if (IS_KERNEL_ADDRESS(num)) {
// find image at address
- hash_open(sImagesHash, &iterator);
- while ((image = (elf_image_info
*)hash_next(sImagesHash,
- &iterator)) != NULL) {
+ ImageHash::Iterator iterator(sImagesHash);
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if (image->text_region.start <= num
&& image->text_region.start +
image->text_region.size
>= num)
break;
}
- hash_close(sImagesHash, &iterator, false);
if (image == NULL) {
kprintf("No image covers %#" B_PRIxADDR
" in the kernel!\n",
num);
}
} else {
- image = (elf_image_info
*)hash_lookup(sImagesHash, (void *)num);
+ image = sImagesHash->Lookup(num);
if (image == NULL) {
kprintf("image %#" B_PRIxADDR " doesn't
exist in the "
"kernel!\n", num);
@@ -443,13 +431,12 @@ dump_symbols(int argc, char **argv)
}
} else {
// look for image by name
- hash_open(sImagesHash, &iterator);
- while ((image = (elf_image_info *)hash_next(sImagesHash,
- &iterator)) != NULL) {
+ ImageHash::Iterator iterator(sImagesHash);
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if (!strcmp(image->name, argv[1]))
break;
}
- hash_close(sImagesHash, &iterator, false);
if (image == NULL)
kprintf("No image \"%s\" found in kernel!\n",
argv[1]);
@@ -545,7 +532,6 @@ dump_image_info(struct elf_image_info *image)
static int
dump_image(int argc, char **argv)
{
- struct hash_iterator iterator;
struct elf_image_info *image;
// if the argument looks like a hex number, treat it as such
@@ -556,7 +542,7 @@ dump_image(int argc, char **argv)
// semi-hack
dump_image_info((struct elf_image_info *)num);
} else {
- image = (elf_image_info *)hash_lookup(sImagesHash,
(void *)num);
+ image = sImagesHash->Lookup(num);
if (image == NULL) {
kprintf("image %#" B_PRIxADDR " doesn't exist
in the kernel!\n",
num);
@@ -568,14 +554,13 @@ dump_image(int argc, char **argv)
kprintf("loaded kernel images:\n");
- hash_open(sImagesHash, &iterator);
+ ImageHash::Iterator iterator(sImagesHash);
- while ((image = (elf_image_info *)hash_next(sImagesHash, &iterator))
- != NULL) {
+ while (iterator.HasNext()) {
+ image = iterator.Next();
kprintf("%p (%" B_PRId32 ") %s\n", image, image->id,
image->name);
}
- hash_close(sImagesHash, &iterator, false);
return 0;
}
@@ -1767,11 +1752,10 @@ addr_t
elf_debug_lookup_symbol(const char* searchName)
{
struct elf_image_info *image = NULL;
- struct hash_iterator iterator;
- hash_open(sImagesHash, &iterator);
- while ((image = (elf_image_info *)hash_next(sImagesHash, &iterator))
- != NULL) {
+ ImageHash::Iterator iterator(sImagesHash);
+ while (iterator.HasNext()) {
+ image = iterator.Next();
if (image->num_debug_symbols > 0) {
// search extended debug symbol table (contains static
symbols)
for (uint32 i = 0; i < image->num_debug_symbols; i++) {
@@ -1795,7 +1779,6 @@ elf_debug_lookup_symbol(const char* searchName)
}
}
}
- hash_close(sImagesHash, &iterator, false);
return 0;
}
@@ -2572,9 +2555,12 @@ elf_init(kernel_args *args)
image_init();
- sImagesHash = hash_init(IMAGE_HASH_SIZE, 0, image_compare, image_hash);
+ sImagesHash = new ImageHash();
if (sImagesHash == NULL)
return B_NO_MEMORY;
+ status_t init = sImagesHash->Init(IMAGE_HASH_SIZE);
+ if (init != B_OK)
+ return init;
// Build a image structure for the kernel, which has already been
loaded.
// The preloaded_images were already prepared by the VM.
############################################################################
Commit: f5acc807f82189e0321ff57ebf840e531ac196aa
URL: http://cgit.haiku-os.org/haiku/commit/?id=f5acc80
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 13:26:02 2015 UTC
ipv6 datagram: migrate to BOpenHashTable.
----------------------------------------------------------------------------
diff --git
a/src/add-ons/kernel/network/datalink_protocols/ipv6_datagram/ipv6_datagram.cpp
b/src/add-ons/kernel/network/datalink_protocols/ipv6_datagram/ipv6_datagram.cpp
index 9d19e8f..65564a4 100644
---
a/src/add-ons/kernel/network/datalink_protocols/ipv6_datagram/ipv6_datagram.cpp
+++
b/src/add-ons/kernel/network/datalink_protocols/ipv6_datagram/ipv6_datagram.cpp
@@ -18,7 +18,6 @@
#include <util/atomic.h>
#include <util/AutoLock.h>
#include <util/DoublyLinkedList.h>
-#include <util/khash.h>
#include <KernelExport.h>
#include <netinet/in.h>
@@ -58,14 +57,12 @@ static net_stack_module_info* sStackModule;
static net_datalink_module_info* sDatalinkModule;
static net_protocol_module_info* sIPv6Module;
static net_protocol* sIPv6Protocol;
-static hash_table* sCache;
static mutex sCacheLock;
static const net_buffer* kDeletedBuffer = (net_buffer*)~0;
// needed for IN6_IS_ADDR_UNSPECIFIED() macro
const struct in6_addr in6addr_any = IN6ADDR_ANY_INIT;
-
// #pragma mark -
@@ -112,8 +109,6 @@ struct ndp_entry {
BufferList queue;
- static int Compare(void* _entry, const void* _key);
- static uint32 Hash(void* _entry, const void* _key, uint32 range);
static ndp_entry* Lookup(const in6_addr& protocolAddress);
static ndp_entry* Add(const in6_addr& protocolAddress,
sockaddr_dl* hardwareAddress, uint32 flags);
@@ -126,6 +121,38 @@ struct ndp_entry {
void ScheduleRemoval();
};
+
+struct ndpHash {
+ typedef in6_addr KeyType;
+ typedef ndp_entry ValueType;
+
+ size_t HashKey(in6_addr key) const
+ {
+ return jenkins_hashword((const uint32*)&(key),
+ sizeof(in6_addr) / sizeof(uint32), 0);
+ }
+
+ size_t Hash(ndp_entry* value) const
+ {
+ return HashKey(value->protocol_address);
+ }
+
+ bool Compare(in6_addr key, ndp_entry* value) const
+ {
+ return value->protocol_address == key;
+ }
+
+ ndp_entry*& GetLink(ndp_entry* value) const
+ {
+ return value->next;
+ }
+};
+
+
+typedef BOpenHashTable<ndpHash> AddressCache;
+static AddressCache* sCache;
+
+
#define NDP_FLAG_LOCAL 0x01
#define NDP_FLAG_REJECT 0x02
#define NDP_FLAG_PERMANENT 0x04
@@ -209,14 +236,6 @@ ipv6_to_solicited_multicast(sockaddr_in6* target, const
in6_addr& address)
}
-static inline uint32
-hash_ipv6_address(const in6_addr& address, uint32 range)
-{
- return jenkins_hashword((const uint32*)&address,
- sizeof(in6_addr) / sizeof(uint32), 0) % range;
-}
-
-
// #pragma mark -
@@ -258,36 +277,10 @@ delete_request_buffer(ndp_entry* entry)
}
-int
-ndp_entry::Compare(void* _entry, const void* _key)
-{
- ndp_entry* entry = (ndp_entry*)_entry;
- in6_addr* key = (in6_addr*)_key;
-
- if (entry->protocol_address == *key)
- return 0;
-
- return 1;
-}
-
-
-uint32
-ndp_entry::Hash(void* _entry, const void* _key, uint32 range)
-{
- ndp_entry* entry = (ndp_entry*)_entry;
- const in6_addr* key = (const in6_addr*)_key;
-
- if (entry != NULL)
- return hash_ipv6_address(entry->protocol_address, range);
-
- return hash_ipv6_address(*key, range);
-}
-
-
ndp_entry*
ndp_entry::Lookup(const in6_addr& address)
{
- return (ndp_entry*)hash_lookup(sCache, &address);
+ return sCache->Lookup(address);
}
@@ -322,7 +315,7 @@ ndp_entry::Add(const in6_addr& protocolAddress,
sockaddr_dl* hardwareAddress,
entry->hardware_address.sdl_len = sizeof(sockaddr_dl);
}
- if (hash_insert(sCache, entry) != B_OK) {
+ if (sCache->Insert(entry) != B_OK) {
// We can delete the entry here with the sCacheLock held, since
it's
// guaranteed there are no timers pending.
delete entry;
@@ -414,9 +407,8 @@ ndp_init()
mutex_init(&sCacheLock, "ndp cache");
- sCache = hash_init(64, offsetof(struct ndp_entry, next),
- &ndp_entry::Compare, &ndp_entry::Hash);
- if (sCache == NULL) {
+ sCache = new AddressCache();
+ if (sCache == NULL || sCache->Init(64) != B_OK) {
mutex_destroy(&sCacheLock);
return B_NO_MEMORY;
}
@@ -534,7 +526,7 @@ ndp_remove_local_entry(ipv6_datalink_protocol* protocol,
const sockaddr* local,
ndp_entry* entry = ndp_entry::Lookup(inetAddress);
if (entry != NULL) {
- hash_remove(sCache, entry);
+ sCache->Remove(entry);
entry->flags |= NDP_FLAG_REMOVED;
}
@@ -851,7 +843,7 @@ ndp_timer(struct net_timer* timer, void* data)
break;
}
- hash_remove(sCache, entry);
+ sCache->Remove(entry);
mutex_unlock(&sCacheLock);
delete entry;
############################################################################
Commit: 6f05b191d7c50bcff58abe869caaec656f2ccec7
URL: http://cgit.haiku-os.org/haiku/commit/?id=6f05b19
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 14:08:51 2015 UTC
ARP: convert to BOpenHashTable
* Replaced the hash function as it wasn't really useful. It seems better
to use the full in_addr_t as a hash as it is a 32bit value. Shuffling it
like the previous hash function did can only increase the number of
collisions.
* BOpenHashTable lacks the "range" parameter to the hash function, so we
can't know which bits from the hash are actually going to be used.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/network/datalink_protocols/arp/arp.cpp
b/src/add-ons/kernel/network/datalink_protocols/arp/arp.cpp
index d2ee6eb..fac074f 100644
--- a/src/add-ons/kernel/network/datalink_protocols/arp/arp.cpp
+++ b/src/add-ons/kernel/network/datalink_protocols/arp/arp.cpp
@@ -22,7 +22,6 @@
#include <util/atomic.h>
#include <util/AutoLock.h>
#include <util/DoublyLinkedList.h>
-#include <util/khash.h>
#include <ByteOrder.h>
#include <KernelExport.h>
@@ -80,8 +79,6 @@ struct arp_entry {
BufferList queue;
- static int Compare(void *_entry, const void *_key);
- static uint32 Hash(void *_entry, const void *_key, uint32 range);
static arp_entry *Lookup(in_addr_t protocolAddress);
static arp_entry *Add(in_addr_t protocolAddress,
sockaddr_dl *hardwareAddress, uint32 flags);
@@ -122,11 +119,40 @@ static void arp_timer(struct net_timer *timer, void
*data);
net_buffer_module_info* gBufferModule;
static net_stack_module_info* sStackModule;
static net_datalink_module_info* sDatalinkModule;
-static hash_table* sCache;
static mutex sCacheLock;
static bool sIgnoreReplies;
+struct arpHash {
+ typedef in_addr_t KeyType;
+ typedef arp_entry ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return HashKey(value->protocol_address);
+ }
+
+ bool Compare(KeyType key, ValueType* value) const
+ {
+ return value->protocol_address == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->next;
+ }
+};
+
+
+typedef BOpenHashTable<arpHash> AddressCache;
+static AddressCache* sCache;
+
+
#ifdef TRACE_ARP
@@ -221,46 +247,10 @@ ipv4_to_ether_multicast(sockaddr_dl *destination, const
sockaddr_in *source)
// #pragma mark -
-/*static*/ int
-arp_entry::Compare(void *_entry, const void *_key)
-{
- arp_entry *entry = (arp_entry *)_entry;
- in_addr_t *key = (in_addr_t *)_key;
-
- if (entry->protocol_address == *key)
- return 0;
-
- return 1;
-}
-
-
-/*static*/ uint32
-arp_entry::Hash(void *_entry, const void *_key, uint32 range)
-{
- arp_entry *entry = (arp_entry *)_entry;
- const in_addr_t *key = (const in_addr_t *)_key;
-
-// TODO: check if this makes a good hash...
-#define HASH(o) ((((o) >> 24) ^ ((o) >> 16) ^ ((o) >> 8) ^ (o)) % range)
-
-#if 0
- in_addr_t a = entry ? entry->protocol_address : *key;
- dprintf("%ld.%ld.%ld.%ld: Hash: %lu\n", a >> 24, (a >> 16) & 0xff,
- (a >> 8) & 0xff, a & 0xff, HASH(a));
-#endif
-
- if (entry != NULL)
- return HASH(entry->protocol_address);
-
- return HASH(*key);
-#undef HASH
-}
-
-
/*static*/ arp_entry *
arp_entry::Lookup(in_addr_t address)
{
- return (arp_entry *)hash_lookup(sCache, &address);
+ return sCache->Lookup(address);
}
@@ -295,7 +285,7 @@ arp_entry::Add(in_addr_t protocolAddress, sockaddr_dl
*hardwareAddress,
entry->hardware_address.sdl_len = sizeof(sockaddr_dl);
}
- if (hash_insert(sCache, entry) != B_OK) {
+ if (sCache->Insert(entry) != B_OK) {
// We can delete the entry here with the sCacheLock held, since
it's
// guaranteed there are no timers pending.
delete entry;
@@ -496,7 +486,7 @@ arp_remove_local_entry(arp_protocol* protocol, const
sockaddr* local,
arp_entry* entry = arp_entry::Lookup(inetAddress);
if (entry != NULL) {
- hash_remove(sCache, entry);
+ sCache->Remove(entry);
entry->flags |= ARP_FLAG_REMOVED;
}
@@ -722,7 +712,7 @@ arp_timer(struct net_timer *timer, void *data)
break;
}
- hash_remove(sCache, entry);
+ sCache->Remove(entry);
locker.Unlock();
delete entry;
@@ -891,16 +881,14 @@ arp_control(const char *subsystem, uint32 function, void
*buffer,
case ARP_GET_ENTRIES:
{
- hash_iterator iterator;
- hash_open(sCache, &iterator);
+ AddressCache::Iterator iterator(sCache);
- arp_entry *entry;
+ arp_entry *entry = NULL;
uint32 i = 0;
- while ((entry = (arp_entry *)hash_next(sCache,
&iterator)) != NULL
- && i < control.cookie) {
+ while (iterator.HasNext() && i < control.cookie) {
+ entry = iterator.Next();
i++;
}
- hash_close(sCache, &iterator, false);
if (entry == NULL)
return B_ENTRY_NOT_FOUND;
@@ -931,18 +919,17 @@ arp_control(const char *subsystem, uint32 function, void
*buffer,
case ARP_FLUSH_ENTRIES:
{
- hash_iterator iterator;
- hash_open(sCache, &iterator);
+ AddressCache::Iterator iterator(sCache);
arp_entry *entry;
- while ((entry = (arp_entry *)hash_next(sCache,
&iterator)) != NULL) {
+ while (iterator.HasNext()) {
+ entry = iterator.Next();
// we never flush local ARP entries
if ((entry->flags & ARP_FLAG_LOCAL) != 0)
continue;
entry->ScheduleRemoval();
}
- hash_close(sCache, &iterator, false);
return B_OK;
}
@@ -960,9 +947,8 @@ arp_init()
{
mutex_init(&sCacheLock, "arp cache");
- sCache = hash_init(64, offsetof(struct arp_entry, next),
- &arp_entry::Compare, &arp_entry::Hash);
- if (sCache == NULL) {
+ sCache = new AddressCache();
+ if (sCache == NULL || sCache->Init(64) != B_OK) {
mutex_destroy(&sCacheLock);
return B_NO_MEMORY;
}
############################################################################
Commit: 6a89f8040fbc385a9298e5afd4ae33a4dbc5b734
URL: http://cgit.haiku-os.org/haiku/commit/?id=6a89f80
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 15:22:15 2015 UTC
Ticket: https://dev.haiku-os.org/ticket/9552
devfs: migrate to BOpenHashTable
For #9552.
----------------------------------------------------------------------------
diff --git a/src/system/kernel/device_manager/devfs.cpp
b/src/system/kernel/device_manager/devfs.cpp
index 88564a9..1b6f6e5 100644
--- a/src/system/kernel/device_manager/devfs.cpp
+++ b/src/system/kernel/device_manager/devfs.cpp
@@ -33,7 +33,6 @@
#include <lock.h>
#include <Notifications.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <vfs.h>
#include <vm/vm.h>
@@ -99,12 +98,40 @@ struct devfs_vnode {
#define DEVFS_HASH_SIZE 16
+
+struct NodeHash {
+ typedef ino_t KeyType;
+ typedef devfs_vnode ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key ^ (key >> 32);
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return HashKey(value->id);
+ }
+
+ bool Compare(KeyType key, ValueType* value) const
+ {
+ return value->id == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->all_next;
+ }
+};
+
+typedef BOpenHashTable<NodeHash> NodeTable;
+
struct devfs {
dev_t id;
fs_volume* volume;
recursive_lock lock;
- int32 next_vnode_id;
- hash_table* vnode_hash;
+ int32 next_vnode_id;
+ NodeTable* vnode_hash;
struct devfs_vnode* root_vnode;
};
@@ -208,32 +235,6 @@ scan_for_drivers_if_needed(devfs_vnode* dir)
}
-static uint32
-devfs_vnode_hash(void* _vnode, const void* _key, uint32 range)
-{
- struct devfs_vnode* vnode = (struct devfs_vnode*)_vnode;
- const ino_t* key = (const ino_t*)_key;
-
- if (vnode != NULL)
- return vnode->id % range;
-
- return (uint64)*key % range;
-}
-
-
-static int
-devfs_vnode_compare(void* _vnode, const void* _key)
-{
- struct devfs_vnode* vnode = (struct devfs_vnode*)_vnode;
- const ino_t* key = (const ino_t*)_key;
-
- if (vnode->id == *key)
- return 0;
-
- return -1;
-}
-
-
static void
init_directory_vnode(struct devfs_vnode* vnode, int permissions)
{
@@ -283,7 +284,7 @@ devfs_delete_vnode(struct devfs* fs, struct devfs_vnode*
vnode,
return B_NOT_ALLOWED;
// remove it from the global hash table
- hash_remove(fs->vnode_hash, vnode);
+ fs->vnode_hash->Remove(vnode);
if (S_ISCHR(vnode->stream.type)) {
if (vnode->stream.u.dev.partition == NULL) {
@@ -465,7 +466,7 @@ add_partition(struct devfs* fs, struct devfs_vnode* device,
const char* name,
partitionNode->stream.u.dev.device = device->stream.u.dev.device;
partitionNode->stream.u.dev.partition = partition;
- hash_insert(fs->vnode_hash, partitionNode);
+ fs->vnode_hash->Insert(partitionNode);
devfs_insert_in_dir(device->parent, partitionNode);
TRACE(("add_partition(name = %s, offset = %Ld, size = %Ld)\n",
@@ -536,7 +537,7 @@ out:
static void
publish_node(devfs* fs, devfs_vnode* dirNode, struct devfs_vnode* node)
{
- hash_insert(fs->vnode_hash, node);
+ fs->vnode_hash->Insert(node);
devfs_insert_in_dir(dirNode, node);
}
@@ -896,10 +897,8 @@ devfs_mount(fs_volume* volume, const char* devfs, uint32
flags,
recursive_lock_init(&fs->lock, "devfs lock");
- fs->vnode_hash = hash_init(DEVFS_HASH_SIZE, offsetof(devfs_vnode,
all_next),
- //(addr_t)&vnode->all_next - (addr_t)vnode,
- &devfs_vnode_compare, &devfs_vnode_hash);
- if (fs->vnode_hash == NULL) {
+ fs->vnode_hash = new NodeTable();
+ if (fs->vnode_hash == NULL || fs->vnode_hash->Init(DEVFS_HASH_SIZE) !=
B_OK) {
err = B_NO_MEMORY;
goto err2;
}
@@ -918,7 +917,7 @@ devfs_mount(fs_volume* volume, const char* devfs, uint32
flags,
init_directory_vnode(vnode, 0755);
fs->root_vnode = vnode;
- hash_insert(fs->vnode_hash, vnode);
+ fs->vnode_hash->Insert(vnode);
publish_vnode(volume, vnode->id, vnode, &kVnodeOps, vnode->stream.type,
0);
*_rootNodeID = vnode->id;
@@ -926,7 +925,7 @@ devfs_mount(fs_volume* volume, const char* devfs, uint32
flags,
return B_OK;
err3:
- hash_uninit(fs->vnode_hash);
+ delete fs->vnode_hash;
err2:
recursive_lock_destroy(&fs->lock);
free(fs);
@@ -940,7 +939,6 @@ devfs_unmount(fs_volume* _volume)
{
struct devfs* fs = (struct devfs*)_volume->private_volume;
struct devfs_vnode* vnode;
- struct hash_iterator i;
TRACE(("devfs_unmount: entry fs = %p\n", fs));
@@ -950,12 +948,12 @@ devfs_unmount(fs_volume* _volume)
put_vnode(fs->volume, fs->root_vnode->id);
// delete all of the vnodes
- hash_open(fs->vnode_hash, &i);
- while ((vnode = (devfs_vnode*)hash_next(fs->vnode_hash, &i)) != NULL) {
+ NodeTable::Iterator i(fs->vnode_hash);
+ while (i.HasNext()) {
+ vnode = i.Next();
devfs_delete_vnode(fs, vnode, true);
}
- hash_close(fs->vnode_hash, &i, false);
- hash_uninit(fs->vnode_hash);
+ delete fs->vnode_hash;
recursive_lock_destroy(&fs->lock);
free(fs);
@@ -1032,7 +1030,7 @@ devfs_get_vnode(fs_volume* _volume, ino_t id, fs_vnode*
_vnode, int* _type,
RecursiveLocker _(fs->lock);
- struct devfs_vnode* vnode = (devfs_vnode*)hash_lookup(fs->vnode_hash,
&id);
+ struct devfs_vnode* vnode = fs->vnode_hash->Lookup(id);
if (vnode == NULL)
return B_ENTRY_NOT_FOUND;
############################################################################
Commit: d4aabe75c3fc1cdf93871ab15c12e02eb6761200
URL: http://cgit.haiku-os.org/haiku/commit/?id=d4aabe7
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 16:28:07 2015 UTC
Network stack: migrate to BOpenHashTable
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/network/stack/stack.cpp
b/src/add-ons/kernel/network/stack/stack.cpp
index 9ca32c0..f935bcc 100644
--- a/src/add-ons/kernel/network/stack/stack.cpp
+++ b/src/add-ons/kernel/network/stack/stack.cpp
@@ -22,7 +22,6 @@
#include <lock.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <KernelExport.h>
@@ -68,6 +67,8 @@ struct family {
ChainList chains;
};
+struct ChainHash;
+
struct chain : DoublyLinkedListLinkImpl<chain> {
chain(int family, int type, int protocol);
~chain();
@@ -76,15 +77,13 @@ struct chain : DoublyLinkedListLinkImpl<chain> {
void Release();
void Uninitialize();
- static int Compare(void* _chain, const void* _key);
- static uint32 Hash(void* _chain, const void* _key, uint32 range);
- static struct chain* Lookup(hash_table* chains, int family, int type,
- int protocol);
- static struct chain* Add(hash_table* chains, int family, int type,
- int protocol, va_list modules);
- static struct chain* Add(hash_table* chains, int family, int type,
- int protocol, ...);
- static void DeleteChains(hash_table* chains);
+ static struct chain* Lookup(BOpenHashTable<ChainHash>* chains,
+ int family, int type, int protocol);
+ static struct chain* Add(BOpenHashTable<ChainHash>* chains,
+ int family, int type, int protocol, va_list modules);
+ static struct chain* Add(BOpenHashTable<ChainHash>* chains,
+ int family, int type, int protocol, ...);
+ static void DeleteChains(BOpenHashTable<ChainHash>* chains);
chain* next;
struct family* parent;
@@ -99,15 +98,78 @@ struct chain : DoublyLinkedListLinkImpl<chain> {
module_info* infos[MAX_CHAIN_MODULES + 1];
};
+struct ChainHash {
+ typedef chain_key KeyType;
+ typedef chain ValueType;
+
+// TODO: check if this makes a good hash...
+#define HASH(o) ((uint32)(((o)->family) ^ ((o)->type) ^ ((o)->protocol)))
+
+ size_t HashKey(KeyType key) const
+ {
+ return HASH(&key);
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return HASH(value);
+ }
+
+#undef HASH
+
+ bool Compare(KeyType key, ValueType* chain) const
+ {
+ if (chain->family == key.family
+ && chain->type == key.type
+ && chain->protocol == key.protocol)
+ return true;
+
+ return false;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->next;
+ }
+};
+
+struct FamilyHash {
+ typedef int KeyType;
+ typedef family ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return value->type;
+ }
+
+ bool Compare(KeyType key, ValueType* family) const
+ {
+ return family->type == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->next;
+ }
+};
+
+typedef BOpenHashTable<ChainHash> ChainTable;
+typedef BOpenHashTable<FamilyHash> FamilyTable;
+
#define CHAIN_MISSING_MODULE 0x02
#define CHAIN_INITIALIZED 0x01
static mutex sChainLock;
static mutex sInitializeChainLock;
-static hash_table* sProtocolChains;
-static hash_table* sDatalinkProtocolChains;
-static hash_table* sReceivingProtocolChains;
-static hash_table* sFamilies;
+static ChainTable* sProtocolChains;
+static ChainTable* sDatalinkProtocolChains;
+static ChainTable* sReceivingProtocolChains;
+static FamilyTable* sFamilies;
static bool sInitialized;
@@ -142,36 +204,10 @@ family::Release()
}
-/*static*/ int
-family::Compare(void* _family, const void* _key)
-{
- struct family* family = (struct family*)_family;
- int key = (addr_t)_key;
-
- if (family->type == key)
- return 0;
-
- return 1;
-}
-
-
-/*static*/ uint32
-family::Hash(void* _family, const void* _key, uint32 range)
-{
- struct family* family = (struct family*)_family;
- int key = (addr_t)_key;
-
- if (family != NULL)
- return family->type % range;
-
- return key % range;
-}
-
-
/*static*/ struct family*
family::Lookup(int type)
{
- return (struct family*)hash_lookup(sFamilies, (void*)(addr_t)type);
+ return sFamilies->Lookup(type);
}
@@ -182,7 +218,7 @@ family::Add(int type)
if (family == NULL)
return NULL;
- if (hash_insert(sFamilies, family) != B_OK) {
+ if (sFamilies->Insert(family) != B_OK) {
delete family;
return NULL;
}
@@ -294,60 +330,23 @@ chain::Uninitialize()
}
-/*static*/ int
-chain::Compare(void* _chain, const void* _key)
-{
- const chain_key* key = (const chain_key*)_key;
- struct chain* chain = (struct chain*)_chain;
-
- if (chain->family == key->family
- && chain->type == key->type
- && chain->protocol == key->protocol)
- return 0;
-
- return 1;
-}
-
-
-/*static*/ uint32
-chain::Hash(void* _chain, const void* _key, uint32 range)
-{
- const chain_key* key = (const chain_key*)_key;
- struct chain* chain = (struct chain*)_chain;
-
-// TODO: check if this makes a good hash...
-#define HASH(o) ((uint32)(((o)->family) ^ ((o)->type) ^ ((o)->protocol)) %
range)
-#if 0
- TRACE(("%d.%d.%d: Hash: %lu\n", chain ? chain->family : key->family,
- chain ? chain->type : key->type, chain ? chain->protocol :
key->protocol,
- chain ? HASH(chain) : HASH(key)));
-#endif
-
- if (chain != NULL)
- return HASH(chain);
-
- return HASH(key);
-#undef HASH
-}
-
-
/*static*/ struct chain*
-chain::Lookup(hash_table* chains, int family, int type, int protocol)
+chain::Lookup(ChainTable* chains, int family, int type, int protocol)
{
struct chain_key key = { family, type, protocol };
- return (struct chain*)hash_lookup(chains, &key);
+ return chains->Lookup(key);
}
/*static*/ struct chain*
-chain::Add(hash_table* chains, int family, int type, int protocol,
+chain::Add(ChainTable* chains, int family, int type, int protocol,
va_list modules)
{
struct chain* chain = new (std::nothrow) ::chain(family, type,
protocol);
if (chain == NULL)
return NULL;
- if (chain->parent == NULL || hash_insert(chains, chain) != B_OK) {
+ if (chain->parent == NULL || chains->Insert(chain) != B_OK) {
delete chain;
return NULL;
}
@@ -365,14 +364,14 @@ chain::Add(hash_table* chains, int family, int type, int
protocol,
chain->modules[count] = strdup(module);
if (chain->modules[count] == NULL
|| ++count >= MAX_CHAIN_MODULES) {
- hash_remove(chains, chain);
+ chains->Remove(chain);
delete chain;
return NULL;
}
}
if (chains == sProtocolChains && count == 0) {
- hash_remove(chains, chain);
+ chains->Remove(chain);
delete chain;
return NULL;
}
@@ -382,7 +381,7 @@ chain::Add(hash_table* chains, int family, int type, int
protocol,
/*static*/ struct chain*
-chain::Add(hash_table* chains, int family, int type, int protocol, ...)
+chain::Add(ChainTable* chains, int family, int type, int protocol, ...)
{
va_list modules;
va_start(modules, protocol);
@@ -395,16 +394,16 @@ chain::Add(hash_table* chains, int family, int type, int
protocol, ...)
/*static*/ void
-chain::DeleteChains(hash_table* chains)
+chain::DeleteChains(ChainTable* chains)
{
- uint32 cookie = 0;
- while (true) {
- struct chain* chain = (struct chain*)hash_remove_first(chains,
&cookie);
- if (chain == NULL)
- break;
+ struct chain* current;
+ current = chains->Clear(true);
+ while (current) {
+ struct chain* next = current->next;
- chain->Uninitialize();
- delete chain;
+ current->Uninitialize();
+ delete current;
+ current = next;
}
}
@@ -799,30 +798,28 @@ init_stack()
mutex_init(&sChainLock, "net chains");
mutex_init(&sInitializeChainLock, "net intialize chains");
- sFamilies = hash_init(10, offsetof(struct family, next),
- &family::Compare, &family::Hash);
- if (sFamilies == NULL) {
+ sFamilies = new FamilyTable();
+ if (sFamilies == NULL || sFamilies->Init(10) != B_OK) {
status = B_NO_MEMORY;
goto err5;
}
- sProtocolChains = hash_init(10, offsetof(struct chain, next),
- &chain::Compare, &chain::Hash);
- if (sProtocolChains == NULL) {
+ sProtocolChains = new ChainTable();
+ if (sProtocolChains == NULL || sProtocolChains->Init(10) != B_OK) {
status = B_NO_MEMORY;
goto err6;
}
- sDatalinkProtocolChains = hash_init(10, offsetof(struct chain, next),
- &chain::Compare, &chain::Hash);
- if (sDatalinkProtocolChains == NULL) {
+ sDatalinkProtocolChains = new ChainTable();
+ if (sDatalinkProtocolChains == NULL
+ || sDatalinkProtocolChains->Init(10) != B_OK) {
status = B_NO_MEMORY;
goto err7;
}
- sReceivingProtocolChains = hash_init(10, offsetof(struct chain, next),
- &chain::Compare, &chain::Hash);
- if (sReceivingProtocolChains == NULL) {
+ sReceivingProtocolChains = new ChainTable();
+ if (sReceivingProtocolChains == NULL
+ || sReceivingProtocolChains->Init(10) != B_OK) {
status = B_NO_MEMORY;
goto err8;
}
@@ -850,11 +847,11 @@ init_stack()
return B_OK;
err8:
- hash_uninit(sDatalinkProtocolChains);
+ delete sDatalinkProtocolChains;
err7:
- hash_uninit(sProtocolChains);
+ delete sProtocolChains;
err6:
- hash_uninit(sFamilies);
+ delete sFamilies;
err5:
mutex_destroy(&sInitializeChainLock);
mutex_destroy(&sChainLock);
@@ -891,20 +888,19 @@ uninit_stack()
chain::DeleteChains(sDatalinkProtocolChains);
chain::DeleteChains(sReceivingProtocolChains);
- uint32 cookie = 0;
- while (true) {
- struct family* family = (struct
family*)hash_remove_first(sFamilies,
- &cookie);
- if (family == NULL)
- break;
+ struct family* current;
+ current = sFamilies->Clear(true);
+ while (current) {
+ struct family* next = current->next;
- delete family;
+ delete current;
+ current = next;
}
- hash_uninit(sProtocolChains);
- hash_uninit(sDatalinkProtocolChains);
- hash_uninit(sReceivingProtocolChains);
- hash_uninit(sFamilies);
+ delete sProtocolChains;
+ delete sDatalinkProtocolChains;
+ delete sReceivingProtocolChains;
+ delete sFamilies;
return B_OK;
}
############################################################################
Commit: 955d5259d0d83f8ffbf221dcea3cea5e6764199b
URL: http://cgit.haiku-os.org/haiku/commit/?id=955d525
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 16:28:40 2015 UTC
Rewrite sample HashTable description to use the typedefs
This makes the code more readable (as KeyType and ValueType are clearer
than int and Foo) and easier to copypaste and edit.
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/OpenHashTable.h
b/headers/private/kernel/util/OpenHashTable.h
index c58fba5..1baea62 100644
--- a/headers/private/kernel/util/OpenHashTable.h
+++ b/headers/private/kernel/util/OpenHashTable.h
@@ -34,22 +34,22 @@
typedef int KeyType;
typedef Foo ValueType;
- size_t HashKey(int key) const
+ size_t HashKey(KeyType key) const
{
return key >> 1;
}
- size_t Hash(Foo* value) const
+ size_t Hash(ValueType* value) const
{
return HashKey(value->bar);
}
- bool Compare(int key, Foo* value) const
+ bool Compare(KeyType key, ValueType* value) const
{
return value->bar == key;
}
- Foo*& GetLink(Foo* value) const
+ ValueType*& GetLink(ValueType* value) const
{
return value->fNext;
}
############################################################################
Commit: 271ac910a4cfdefa6393c1e7cb5e3a665404757d
URL: http://cgit.haiku-os.org/haiku/commit/?id=271ac91
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 10:12:20 2015 UTC
Ticket: https://dev.haiku-os.org/ticket/9552
Remove useless includes of khash.h
* These files were already converted to BOpenHashTable.
* For #9552.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/network/protocols/ipv6/ipv6.cpp
b/src/add-ons/kernel/network/protocols/ipv6/ipv6.cpp
index 76a5ec5..16e8482 100644
--- a/src/add-ons/kernel/network/protocols/ipv6/ipv6.cpp
+++ b/src/add-ons/kernel/network/protocols/ipv6/ipv6.cpp
@@ -24,7 +24,6 @@
#include <KernelExport.h>
#include <util/AutoLock.h>
#include <util/list.h>
-#include <util/khash.h>
#include <util/DoublyLinkedList.h>
#include <util/MultiHashTable.h>
diff --git a/src/system/kernel/device_manager/IOSchedulerSimple.cpp
b/src/system/kernel/device_manager/IOSchedulerSimple.cpp
index 34e62ba..1edaf5e 100644
--- a/src/system/kernel/device_manager/IOSchedulerSimple.cpp
+++ b/src/system/kernel/device_manager/IOSchedulerSimple.cpp
@@ -14,7 +14,6 @@
#include <algorithm>
-#include <khash.h>
#include <lock.h>
#include <thread_types.h>
#include <thread.h>
diff --git a/src/system/kernel/module.cpp b/src/system/kernel/module.cpp
index 13c4ac2..d5cabc9 100644
--- a/src/system/kernel/module.cpp
+++ b/src/system/kernel/module.cpp
@@ -32,7 +32,6 @@
#include <safemode.h>
#include <syscalls.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <util/Stack.h>
#include <vfs.h>
diff --git a/src/system/kernel/posix/realtime_sem.cpp
b/src/system/kernel/posix/realtime_sem.cpp
index 7c51e80..41766f8 100644
--- a/src/system/kernel/posix/realtime_sem.cpp
+++ b/src/system/kernel/posix/realtime_sem.cpp
@@ -20,8 +20,8 @@
#include <thread.h>
#include <util/atomic.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <util/OpenHashTable.h>
+#include <util/StringHash.h>
class SemInfo {
diff --git a/src/system/kernel/scheduler/scheduling_analysis.cpp
b/src/system/kernel/scheduler/scheduling_analysis.cpp
index 7c5e86e..68a3a44 100644
--- a/src/system/kernel/scheduler/scheduling_analysis.cpp
+++ b/src/system/kernel/scheduler/scheduling_analysis.cpp
@@ -10,7 +10,6 @@
#include <scheduler_defs.h>
#include <tracing.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include "scheduler_tracing.h"
diff --git a/src/system/kernel/slab/Slab.cpp b/src/system/kernel/slab/Slab.cpp
index 81a8cdd..01695bc 100644
--- a/src/system/kernel/slab/Slab.cpp
+++ b/src/system/kernel/slab/Slab.cpp
@@ -25,7 +25,6 @@
#include <tracing.h>
#include <util/AutoLock.h>
#include <util/DoublyLinkedList.h>
-#include <util/khash.h>
#include <vm/vm.h>
#include <vm/VMAddressSpace.h>
diff --git a/src/system/kernel/vm/VMCache.cpp b/src/system/kernel/vm/VMCache.cpp
index 688f5cb..ce6bcb6 100644
--- a/src/system/kernel/vm/VMCache.cpp
+++ b/src/system/kernel/vm/VMCache.cpp
@@ -23,7 +23,6 @@
#include <slab/Slab.h>
#include <smp.h>
#include <tracing.h>
-#include <util/khash.h>
#include <util/AutoLock.h>
#include <vfs.h>
#include <vm/vm.h>
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index c67acd8..569b62d 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -47,7 +47,6 @@
#include <team.h>
#include <tracing.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <vm/vm_page.h>
#include <vm/vm_priv.h>
#include <vm/VMAddressSpace.h>
############################################################################
Revision: hrev48640
Commit: a2c274e70e7af2cc8cf79a31aa8a41b041067ad2
URL: http://cgit.haiku-os.org/haiku/commit/?id=a2c274e
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Fri Jan 9 17:08:03 2015 UTC
Ticket: https://dev.haiku-os.org/ticket/9552
rule based prefetcher: migrate to BOpenHashTable.
For #9552.
----------------------------------------------------------------------------
diff --git a/src/add-ons/kernel/file_cache/rule_based_prefetcher.cpp
b/src/add-ons/kernel/file_cache/rule_based_prefetcher.cpp
index 4c7adc4..5a7523e 100644
--- a/src/add-ons/kernel/file_cache/rule_based_prefetcher.cpp
+++ b/src/add-ons/kernel/file_cache/rule_based_prefetcher.cpp
@@ -15,7 +15,6 @@
#include <Node.h>
#include <util/kernel_cpp.h>
-#include <util/khash.h>
#include <util/AutoLock.h>
#include <thread.h>
#include <team.h>
@@ -51,7 +50,7 @@ enum match_type {
enum rule_type {
LAUNCH_TYPE = 0x1,
OPEN_FILE_TYPE = 0x2,
- ARGUMENTS_TYPE = 0x4,
+ ARGUMENTS_TYPE = 0x4,
ALL_TYPES = 0xff,
};
@@ -84,7 +83,8 @@ class Rule {
void AddBody(struct body *body);
struct head *FindHead(mount_id device, vnode_id node);
- match_type Match(int32 state, mount_id device, vnode_id parent,
const char *name);
+ match_type Match(int32 state, mount_id device, vnode_id parent,
+ const char *name);
void Apply();
void KnownFileOpened() { fKnownFileOpened++; }
@@ -143,67 +143,69 @@ class RuleMatcher {
private:
void _CollectRules(const char *name);
void _MatchFile(mount_id device, vnode_id parent, const char
*name);
- void _MatchArguments(int32 argCount, char * const *args);
+ void _MatchArguments(int32 argCount, char * const *args);
team_rules *fRules;
};
-static hash_table *sRulesHash;
-static hash_table *sTeamHash;
-static recursive_lock sLock;
-int32 sMinConfidence = 5000;
-
-
-static int
-rules_compare(void *_rules, const void *_key)
-{
- struct rules *rules = (struct rules *)_rules;
- const char *key = (const char *)_key;
-
- return strcmp(rules->name, key);
-}
-
+struct RuleHash {
+ typedef char* KeyType;
+ typedef rules ValueType;
-static uint32
-rules_hash(void *_rules, const void *_key, uint32 range)
-{
- struct rules *rules = (struct rules *)_rules;
- const char *key = (const char *)_key;
-
- if (rules != NULL)
- return hash_hash_string(rules->name) % range;
+ size_t HashKey(KeyType key) const
+ {
+ return key >> 1;
+ }
- return hash_hash_string(key) % range;
-}
+ size_t Hash(ValueType* value) const
+ {
+ return HashKey(value->bar);
+ }
+ bool Compare(KeyType key, ValueType* rules) const
+ {
+ return strcmp(rules->name, key) == 0;
+ }
-// #pragma mark -
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->fNext;
+ }
+};
+struct TeamHash {
+ typedef team_id KeyType;
+ typedef team_rules ValueType;
-static int
-team_compare(void *_rules, const void *_key)
-{
- team_rules *rules = (team_rules *)_rules;
- const team_id *team = (const team_id *)_key;
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
- if (rules->team == *team)
- return 0;
+ size_t Hash(ValueType* value) const
+ {
+ return value->team;
+ }
- return -1;
-}
+ bool Compare(KeyType key, ValueType* value) const
+ {
+ return value->team == key;
+ }
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->fNext;
+ }
+};
-static uint32
-team_hash(void *_rules, const void *_key, uint32 range)
-{
- team_rules *rules = (team_rules *)_rules;
- const team_id *team = (const team_id *)_key;
- if (rules != NULL)
- return rules->team % range;
+typedef BOpenHashTable<RuleHash> RuleTable;
+typedef BOpenHashTable<TeamHash> TeamTable;
- return *team % range;
-}
+static RuleTable *sRulesHash;
+static TeamTable *sTeamHash;
+static recursive_lock sLock;
+int32 sMinConfidence = 5000;
static void
@@ -212,7 +214,7 @@ team_gone(team_id team, void *_rules)
team_rules *rules = (team_rules *)_rules;
recursive_lock_lock(&sLock);
- hash_remove(sTeamHash, rules);
+ sTeamHash->Remove(rules);
recursive_lock_unlock(&sLock);
delete rules;
@@ -253,7 +255,7 @@ head::head()
static inline rules *
find_rules(const char *name)
{
- return (rules *)hash_lookup(sRulesHash, name);
+ return sRulesHash->Lookup(name);
}
@@ -274,7 +276,7 @@ get_rule(const char *name, rule_type type)
strlcpy(rules->name, name, B_FILE_NAME_LENGTH);
rules->first = NULL;
- hash_insert(sRulesHash, rules);
+ sRulesHash->Insert(rules);
}
// search for matching rule type
@@ -561,7 +563,7 @@ RuleMatcher::RuleMatcher(team_id team, const char *name)
if (name == NULL)
return;
- fRules = (team_rules *)hash_lookup(sTeamHash, &team);
+ fRules = sTeamHash->Lookup(team);
if (fRules != NULL)
return;
@@ -576,7 +578,7 @@ RuleMatcher::RuleMatcher(team_id team, const char *name)
dprintf("new rules for \"%s\"\n", name);
_CollectRules(name);
- hash_insert(sTeamHash, fRules);
+ sTeamHash->Insert(fRules);
start_watching_team(team, team_gone, fRules);
fRules->timestamp = system_time();
@@ -592,7 +594,7 @@ RuleMatcher::~RuleMatcher()
void
RuleMatcher::_CollectRules(const char *name)
{
- struct rules *rules = (struct rules *)hash_lookup(sRulesHash, name);
+ struct rules *rules = sRulesHash->Lookup(name);
if (rules == NULL) {
// there are no rules for this command
return;
@@ -715,14 +717,15 @@ uninit()
// free all sessions from the hashes
- uint32 cookie = 0;
- team_rules *teamRules;
- while ((teamRules = (team_rules *)hash_remove_first(sTeamHash,
&cookie)) != NULL) {
+ team_rules *teamRules = sTeamHash->Clear(true);
+ while ((teamRules != NULL) {
+ team_rules *next = teamRules->next;
delete teamRules;
+ teamRules = next;
}
- struct rules *rules;
- cookie = 0;
- while ((rules = (struct rules *)hash_remove_first(sRulesHash, &cookie))
!= NULL) {
+
+ struct rules *rules = sRulesHash->Clear(true);
+ while ((rules != NULL) {
Rule *rule = rules->first;
while (rule) {
Rule *next = rule->Next();
@@ -733,11 +736,14 @@ uninit()
delete rule;
rule = next;
}
+
+ struct rules *next = rules->next;
delete rules;
+ rules = next;
}
- hash_uninit(sTeamHash);
- hash_uninit(sRulesHash);
+ delete sTeamHash;
+ delete sRulesHash;
recursive_lock_destroy(&sLock);
}
@@ -745,15 +751,15 @@ uninit()
static status_t
init()
{
- sTeamHash = hash_init(64, 0, &team_compare, &team_hash);
- if (sTeamHash == NULL)
+ sTeamHash = new TeamTable();
+ if (sTeamHash == NULL || sTeamHash->Init(64) != B_OK)
return B_NO_MEMORY;
status_t status;
- sRulesHash = hash_init(64, 0, &rules_compare, &rules_hash);
- if (sRulesHash == NULL) {
- hash_uninit(sTeamHash);
+ sRulesHash = new RuleTable();
+ if (sRulesHash == NULL || sRulesHash->Init(64) != B_OK) {
+ delete sTeamHash;
return B_NO_MEMORY;
}
Other related posts:
