Changeset 0ca7286 in mainline for uspace/srv/ns/task.c

Timestamp:

2012-07-21T11:19:27Z (12 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2732c94

Parents:

1c1da4b

Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

File:

• uspace/srv/ns/task.c (modified) (11 diffs)

uspace/srv/ns/task.c

@@ -43 +43 @@
 #include "ns.h"
 
-#define TASK_HASH_TABLE_CHAINS  256
-#define P2I_HASH_TABLE_CHAINS   256
 
 /* TODO:
@@ -71 +69 @@
  *
  */
-static hash_index_t task_hash(unsigned long key[])
-{
-        assert(key);
-        return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
+static size_t task_key_hash(unsigned long key[])
+{
+        size_t hash = 17;
+        hash = 37 * hash + key[1];
+        hash = 37 * hash + key[0];
+        return hash;
+}
+
+static size_t task_hash(const link_t *item)
+{
+        hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
+
+        unsigned long key[] = {
+                LOWER32(ht->id),
+                UPPER32(ht->id)
+        };
+        
+        return task_key_hash(key);
 }
 
@@ -86 +98 @@
  *
  */
-static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool task_match(unsigned long key[], size_t keys, const link_t *item)
 {
         assert(key);
-        assert(keys <= 2);
+        assert(keys == 2);
         assert(item);
         
         hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
         
-        if (keys == 2)
-                return ((LOWER32(key[1]) == UPPER32(ht->id))
-                    && (LOWER32(key[0]) == LOWER32(ht->id)));
-        else
-                return (LOWER32(key[0]) == LOWER32(ht->id));
+        return (key[0] == LOWER32(ht->id))
+                && (key[1] == UPPER32(ht->id));
 }
 
@@ -113 +122 @@
 
 /** Operations for task hash table. */
-static hash_table_operations_t task_hash_table_ops = {
+static hash_table_ops_t task_hash_table_ops = {
         .hash = task_hash,
-        .compare = task_compare,
+        .key_hash = task_key_hash,
+        .match = task_match,
+        .equal = 0,
         .remove_callback = task_remove
 };
@@ -135 +146 @@
  *
  */
-static hash_index_t p2i_hash(unsigned long key[])
+static size_t p2i_key_hash(unsigned long key[])
 {
         assert(key);
-        return (key[0] % TASK_HASH_TABLE_CHAINS);
+        return key[0];
+}
+
+static size_t p2i_hash(const link_t *item)
+{
+        p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
+        unsigned long key = entry->in_phone_hash;
+        return p2i_key_hash(&key);
 }
 
@@ -150 +168 @@
  *
  */
-static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool p2i_match(unsigned long key[], size_t keys, const link_t *item)
 {
         assert(key);
@@ -173 +191 @@
 
 /** Operations for task hash table. */
-static hash_table_operations_t p2i_ops = {
+static hash_table_ops_t p2i_ops = {
         .hash = p2i_hash,
-        .compare = p2i_compare,
+        .key_hash = p2i_key_hash,
+        .match = p2i_match,
+        .equal = 0,
         .remove_callback = p2i_remove
 };
@@ -193 +213 @@
 int task_init(void)
 {
-        if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
-            2, &task_hash_table_ops)) {
+        if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) {
                 printf(NAME ": No memory available for tasks\n");
                 return ENOMEM;
         }
         
-        if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
-            1, &p2i_ops)) {
+        if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) {
                 printf(NAME ": No memory available for tasks\n");
                 return ENOMEM;
@@ -293 +311 @@
 int ns_task_id_intro(ipc_call_t *call)
 {
-        unsigned long keys[2];
         
         task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
-        keys[0] = call->in_phone_hash;
+
+        unsigned long keys[] = { call->in_phone_hash };
         
         link_t *link = hash_table_find(&phone_to_id, keys);
@@ -317 +335 @@
         entry->in_phone_hash = call->in_phone_hash;
         entry->id = id;
-        hash_table_insert(&phone_to_id, keys, &entry->link);
+        hash_table_insert(&phone_to_id, &entry->link);
         
         /*
          * Insert into the main table.
          */
-        
-        keys[0] = LOWER32(id);
-        keys[1] = UPPER32(id);
         
         link_initialize(&ht->link);
@@ -331 +346 @@
         ht->have_rval = false;
         ht->retval = -1;
-        hash_table_insert(&task_hash_table, keys, &ht->link);
+        hash_table_insert(&task_hash_table, &ht->link);
         
         return EOK;