Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/include/adt/hash_table.h

    r1c1da4b r0ca7286  
    4040#include <bool.h>
    4141
    42 typedef unsigned long hash_count_t;
    43 typedef unsigned long hash_index_t;
    4442
    4543/** Set of operations for hash table. */
    4644typedef struct {
    47         /** Hash function.
    48          *
    49          * @param key Array of keys needed to compute hash index.
    50          *            All keys must be passed.
    51          *
    52          * @return Index into hash table.
    53          *
     45        /** Returns the hash of the key stored in the item.
    5446         */
    55         hash_index_t (*hash)(unsigned long key[]);
     47        size_t (*hash)(const link_t *item);
    5648       
    57         /** Hash table item comparison function.
     49        /** Returns the hash of the key.
     50         */
     51        size_t (*key_hash)(unsigned long key[]);
     52       
     53        /** Hash table item match function.
    5854         *
    5955         * @param key Array of keys that will be compared with item. It is
    … …  
    6359         *
    6460         */
    65         int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
     61        bool (*match)(unsigned long key[], size_t keys, const link_t *item);
     62
     63        /**
     64         */
     65        bool (*equal)(const link_t *item1, const link_t *item2);
    6666       
    6767        /** Hash table item removal callback.
     68         *
     69         * Must not invoke any mutating functions of the hash table.
    6870         *
    6971         * @param item Item that was removed from the hash table.
    70          *
    7172         */
    7273        void (*remove_callback)(link_t *item);
    73 } hash_table_operations_t;
     74} hash_table_ops_t;
    7475
    7576/** Hash table structure. */
    7677typedef struct {
    77         list_t *entry;
    78         hash_count_t entries;
    79         hash_count_t max_keys;
    80         hash_table_operations_t *op;
     78        list_t *bucket;
     79        size_t bucket_cnt;
     80        size_t max_keys;
     81        size_t items;
     82        hash_table_ops_t *op;
    8183} hash_table_t;
    8284
    … …  
    8486    list_get_instance((item), type, member)
    8587
    86 extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
    87     hash_table_operations_t *);
     88extern bool hash_table_create(hash_table_t *, size_t, size_t,
     89        hash_table_ops_t *);
    8890extern void hash_table_clear(hash_table_t *);
    89 extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *);
     91extern void hash_table_insert(hash_table_t *, link_t *);
     92extern bool hash_table_insert_unique(hash_table_t *, link_t *);
    9093extern link_t *hash_table_find(hash_table_t *, unsigned long []);
    91 extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
     94extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
     95extern void hash_table_remove_item(hash_table_t *, link_t *);
    9296extern void hash_table_destroy(hash_table_t *);
    93 extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
    94     void *);
     97extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *),
     98        void *);
    9599
    96100#endif
Note: See TracChangeset for help on using the changeset viewer.