Ignore:
Timestamp:
2012-10-09T11:49:43Z (12 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
4e00f87
Parents:
87e9392
git-author:
Adam Hraska <adam.hraska+hos@…> (2012-10-09 11:49:43)
git-committer:
Jakub Jermar <jakub@…> (2012-10-09 11:49:43)
Message:

Cherrypick userspace hash table changes from lp:~adam-hraska+lp/helenos/rcu/.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r87e9392 r062d900  
    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
    42 typedef unsigned long hash_count_t;
    43 typedef unsigned long hash_index_t;
     45/** Opaque hash table link type. */
     46typedef struct ht_link {
     47        link_t link;
     48} ht_link_t;
    4449
    4550/** Set of operations for hash table. */
    4651typedef 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          *
    54          */
    55         hash_index_t (*hash)(unsigned long key[]);
     52        /** Returns the hash of the key stored in the item (ie its lookup key). */
     53        size_t (*hash)(const ht_link_t *item);
    5654       
    57         /** Hash table item comparison function.
    58          *
    59          * @param key Array of keys that will be compared with item. It is
    60          *            not necessary to pass all keys.
    61          *
    62          * @return True if the keys match, false otherwise.
    63          *
    64          */
    65         int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
     55        /** Returns the hash of the key. */
     56        size_t (*key_hash)(void *key);
    6657       
     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);
     60
     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.
     65         *
     66         * Must not invoke any mutating functions of the hash table.
    6867         *
    6968         * @param item Item that was removed from the hash table.
    70          *
    7169         */
    72         void (*remove_callback)(link_t *item);
    73 } hash_table_operations_t;
     70        void (*remove_callback)(ht_link_t *item);
     71} hash_table_ops_t;
    7472
    7573/** Hash table structure. */
    7674typedef struct {
    77         list_t *entry;
    78         hash_count_t entries;
    79         hash_count_t max_keys;
    80         hash_table_operations_t *op;
     75        hash_table_ops_t *op;
     76        list_t *bucket;
     77        size_t bucket_cnt;
     78        size_t full_item_cnt;
     79        size_t item_cnt;
     80        size_t max_load;
     81        bool apply_ongoing;
    8182} hash_table_t;
    8283
    83 #define hash_table_get_instance(item, type, member) \
    84     list_get_instance((item), type, member)
     84#define hash_table_get_inst(item, type, member) \
     85        member_to_inst((item), type, member)
    8586
    86 extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
    87     hash_table_operations_t *);
     87extern bool hash_table_create(hash_table_t *, size_t, size_t,
     88        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
    8894extern void hash_table_clear(hash_table_t *);
    89 extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *);
    90 extern link_t *hash_table_find(hash_table_t *, unsigned long []);
    91 extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
    92 extern void hash_table_destroy(hash_table_t *);
    93 extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
    94     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 *),
     102        void *);
     103
    95104
    96105#endif
Note: See TracChangeset for help on using the changeset viewer.