Changeset 0ca7286 in mainline for uspace/lib/c/include/adt


Ignore:
Timestamp:
2012-07-21T11:19:27Z (13 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.

Location:
uspace/lib/c/include/adt
Files:
2 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

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

    r1c1da4b r0ca7286  
    7171            iterator != &(list).head; iterator = iterator->next)
    7272
     73/** Unlike list_foreach(), allows removing items while traversing a list.
     74 *
     75 * @code
     76 * list_t mylist;
     77 * typedef struct item {
     78 *     int value;
     79 *     link_t item_link;
     80 * } item_t;
     81 *
     82 * //..
     83 *
     84 * // Print each list element's value and remove the element from the list.
     85 * list_foreach_safe(mylist, cur_link, next_link) {
     86 *     item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
     87 *     printf("%d\n", cur_item->value);
     88 *     list_remove(cur_link);
     89 * }
     90 * @endcode
     91 *
     92 * @param list List to traverse.
     93 * @param iterator Iterator to the current element of the list.
     94 *             The item this iterator points may be safely removed
     95 *             from the list.
     96 * @param next_iter Iterator to the next element of the list.
     97 */
     98#define list_foreach_safe(list, iterator, next_iter) \
     99        for (link_t *iterator = (list).head.next, \
     100                *next_iter = iterator->next; \
     101                iterator != &(list).head; \
     102                iterator = next_iter, next_iter = iterator->next)
     103
     104
    73105#define assert_link_not_used(link) \
    74106        assert(((link)->prev == NULL) && ((link)->next == NULL))
Note: See TracChangeset for help on using the changeset viewer.