Changeset bc216a0 in mainline for uspace/lib/c/include/adt


Ignore:
Timestamp:
2012-08-07T22:13:44Z (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:
da68871a
Parents:
b17518e
Message:

Refactored any users of hash_table to use opaque void* keys instead of the cumbersome unsigned long[] keys. Switched from the ad hoc computations of hashes of multiple values to hash_combine().

Location:
uspace/lib/c/include/adt
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed

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

    rb17518e rbc216a0  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    3941#include <unistd.h>
    4042#include <bool.h>
     43#include <macros.h>
    4144
     45/** Opaque hash table link type. */
     46typedef struct ht_link {
     47        link_t link;
     48} ht_link_t;
    4249
    4350/** Set of operations for hash table. */
    4451typedef struct {
    45         /** Returns the hash of the key stored in the item.
    46          */
    47         size_t (*hash)(const link_t *item);
     52        /** Returns the hash of the key stored in the item (ie its lookup key). */
     53        size_t (*hash)(const ht_link_t *item);
    4854       
    49         /** Returns the hash of the key.
    50          */
    51         size_t (*key_hash)(unsigned long key[]);
     55        /** Returns the hash of the key. */
     56        size_t (*key_hash)(void *key);
    5257       
    53         /** Hash table item match function.
    54          *
    55          * @param key Array of keys that will be compared with item. It is
    56          *            not necessary to pass all keys.
    57          *
    58          * @return True if the keys match, false otherwise.
    59          *
    60          */
    61         bool (*match)(unsigned long key[], size_t keys, const link_t *item);
     58        /** True if the items are equal (have the same lookup keys). */
     59        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
    6260
    63         /**
    64          */
    65         bool (*equal)(const link_t *item1, const link_t *item2);
    66        
     61        /** Returns true if the key is equal to the item's lookup key. */
     62        bool (*key_equal)(void *key, const ht_link_t *item);
     63
    6764        /** Hash table item removal callback.
    6865         *
    … …  
    7168         * @param item Item that was removed from the hash table.
    7269         */
    73         void (*remove_callback)(link_t *item);
     70        void (*remove_callback)(ht_link_t *item);
    7471} hash_table_ops_t;
    7572
    7673/** Hash table structure. */
    7774typedef struct {
     75        hash_table_ops_t *op;
    7876        list_t *bucket;
    7977        size_t bucket_cnt;
    80         size_t max_keys;
    81         size_t items;
    82         hash_table_ops_t *op;
     78        size_t full_item_cnt;
     79        size_t item_cnt;
     80        size_t max_load;
     81        bool apply_ongoing;
    8382} hash_table_t;
    8483
    85 #define hash_table_get_instance(item, type, member) \
    86     list_get_instance((item), type, member)
     84#define hash_table_get_inst(item, type, member) \
     85        member_to_inst((item), type, member)
    8786
    8887extern bool hash_table_create(hash_table_t *, size_t, size_t,
    8988        hash_table_ops_t *);
     89extern void hash_table_destroy(hash_table_t *);
     90
     91extern bool hash_table_empty(hash_table_t *);
     92extern size_t hash_table_size(hash_table_t *);
     93
    9094extern void hash_table_clear(hash_table_t *);
    91 extern void hash_table_insert(hash_table_t *, link_t *);
    92 extern bool hash_table_insert_unique(hash_table_t *, link_t *);
    93 extern link_t *hash_table_find(const hash_table_t *, unsigned long []);
    94 extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
    95 extern void hash_table_remove_item(hash_table_t *, link_t *);
    96 extern void hash_table_destroy(hash_table_t *);
    97 extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *),
     95extern void hash_table_insert(hash_table_t *, ht_link_t *);
     96extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
     97extern ht_link_t *hash_table_find(const hash_table_t *, void *);
     98extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
     99extern size_t hash_table_remove(hash_table_t *, void *);
     100extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
     101extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *),
    98102        void *);
    99103

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

    rb17518e rbc216a0  
    105105        assert(((link)->prev == NULL) && ((link)->next == NULL))
    106106
     107/** Returns true if the link is definitely part of a list. False if not sure. */
     108static inline int link_in_use(link_t *link)
     109{
     110        return link->prev != NULL && link->next != NULL;
     111}
     112
    107113/** Initialize doubly-linked circular list link
    108114 *
Note: See TracChangeset for help on using the changeset viewer.