Changeset 82cbf8c6 in mainline for kernel/generic/include


Ignore:
Timestamp:
2017-10-08T19:37:24Z (8 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2fd26bb
Parents:
81b9d3e
Message:

Replace the old hash table implementation in the kernel with the newer one

This replaces the original hash table implementation with the resizable one
already used in uspace. Along the way, the IRQ hash table code was streamlined
and cleaned up.

Location:
kernel/generic/include
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/hash.h

    r81b9d3e r82cbf8c6  
    4545         * Public domain.
    4646         */
    47         hash = ~hash + (hash << 15); 
     47        hash = ~hash + (hash << 15);
    4848        hash = hash ^ (hash >> 12);
    4949        hash = hash + (hash << 2);
    5050        hash = hash ^ (hash >> 4);
    51         hash = hash * 2057; 
     51        hash = hash * 2057;
    5252        hash = hash ^ (hash >> 16);
    53         return hash;   
     53        return hash;
    5454}
    5555
    … …  
    6565        hash = hash ^ (hash >> 4);
    6666        hash = hash * 0x27d4eb2d;
    67         hash = hash ^ (hash >> 15);     
    68         /* 
     67        hash = hash ^ (hash >> 15);
     68        /*
    6969         * Lower order bits are mixed more thoroughly. Swap them with
    7070         * the higher order bits and make the resulting higher order bits
    … …  
    105105         * http://burtleburtle.net/bob/c/lookup3.c
    106106         */
    107         seed ^= hash + 0x9e3779b9 
     107        seed ^= hash + 0x9e3779b9
    108108                + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5)));
    109         return seed;   
     109        return seed;
    110110}
    111111

  • kernel/generic/include/adt/hash_table.h

    r81b9d3e r82cbf8c6  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    2729 */
    2830
    29 /** @addtogroup genericadt
     31/** @addtogroup libc
    3032 * @{
    3133 */
    … …  
    3335 */
    3436
    35 #ifndef KERN_HASH_TABLE_H_
    36 #define KERN_HASH_TABLE_H_
     37#ifndef LIBC_HASH_TABLE_H_
     38#define LIBC_HASH_TABLE_H_
    3739
    3840#include <adt/list.h>
    39 #include <typedefs.h>
     41#include <stdbool.h>
     42#include <macros.h>
     43
     44/** Opaque hash table link type. */
     45typedef struct ht_link {
     46        link_t link;
     47} ht_link_t;
    4048
    4149/** Set of operations for hash table. */
    4250typedef struct {
    43         /** Hash function.
    44          *
    45          * @param key   Array of keys needed to compute hash index. All keys must
    46          *              be passed.
    47          *
    48          * @return Index into hash table.
    49          */
    50         size_t (* hash)(sysarg_t key[]);
     51        /** Returns the hash of the key stored in the item (ie its lookup key). */
     52        size_t (*hash)(const ht_link_t *item);
    5153       
    52         /** Hash table item comparison function.
    53          *
    54          * @param key   Array of keys that will be compared with item. It is not
    55          *              necessary to pass all keys.
    56          *
    57          * @return true if the keys match, false otherwise.
    58         */
    59         bool (*compare)(sysarg_t key[], size_t keys, link_t *item);
     54        /** Returns the hash of the key. */
     55        size_t (*key_hash)(void *key);
     56       
     57        /** True if the items are equal (have the same lookup keys). */
     58        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
     59
     60        /** Returns true if the key is equal to the item's lookup key. */
     61        bool (*key_equal)(void *key, const ht_link_t *item);
    6062
    6163        /** Hash table item removal callback.
     64         *
     65         * Must not invoke any mutating functions of the hash table.
    6266         *
    6367         * @param item Item that was removed from the hash table.
    6468         */
    65         void (*remove_callback)(link_t *item);
    66 } hash_table_operations_t;
     69        void (*remove_callback)(ht_link_t *item);
     70} hash_table_ops_t;
    6771
    6872/** Hash table structure. */
    6973typedef struct {
    70         list_t *entry;
    71         size_t entries;
    72         size_t max_keys;
    73         hash_table_operations_t *op;
     74        hash_table_ops_t *op;
     75        list_t *bucket;
     76        size_t bucket_cnt;
     77        size_t full_item_cnt;
     78        size_t item_cnt;
     79        size_t max_load;
     80        bool apply_ongoing;
    7481} hash_table_t;
    7582
    76 #define hash_table_get_instance(item, type, member) \
    77         list_get_instance((item), type, member)
     83#define hash_table_get_inst(item, type, member) \
     84        member_to_inst((item), type, member)
    7885
    79 extern void hash_table_create(hash_table_t *h, size_t m, size_t max_keys,
    80     hash_table_operations_t *op);
    81 extern void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item);
    82 extern link_t *hash_table_find(hash_table_t *h, sysarg_t key[]);
    83 extern void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys);
    84 extern void hash_table_remove_item(hash_table_t *h, link_t *item);
     86extern bool hash_table_create(hash_table_t *, size_t, size_t,
     87        hash_table_ops_t *);
     88extern void hash_table_destroy(hash_table_t *);
     89
     90extern bool hash_table_empty(hash_table_t *);
     91extern size_t hash_table_size(hash_table_t *);
     92
     93extern void hash_table_clear(hash_table_t *);
     94extern void hash_table_insert(hash_table_t *, ht_link_t *);
     95extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
     96extern ht_link_t *hash_table_find(const hash_table_t *, void *);
     97extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
     98extern size_t hash_table_remove(hash_table_t *, void *);
     99extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
     100extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *),
     101        void *);
     102
    85103
    86104#endif

  • kernel/generic/include/ddi/irq.h

    r81b9d3e r82cbf8c6  
    102102typedef struct irq {
    103103        /** Hash table link. */
    104         link_t link;
     104        ht_link_t link;
    105105       
    106106        /** Lock protecting everything in this structure

  • kernel/generic/include/lib/ra.h

    r81b9d3e r82cbf8c6  
    7171typedef struct {
    7272        link_t segment_link;    /**< Span's segment list link. */
    73         link_t fu_link;         /**< Span's free list or used hash link. */
     73
     74        /*
     75         * A segment cannot be both on the free list and in the used hash.
     76         * Their respective links can therefore occupy the same space.
     77         */
     78        union {
     79                link_t fl_link;         /**< Span's free list link. */
     80                ht_link_t uh_link;      /**< Span's used hash link. */
     81        };
    7482
    7583        uintptr_t base;         /**< Segment base. */

  • kernel/generic/include/synch/futex.h

    r81b9d3e r82cbf8c6  
    3838#include <typedefs.h>
    3939#include <synch/waitq.h>
     40#include <adt/hash_table.h>
    4041
    4142/** Kernel-side futex structure. */
    … …  
    4647        waitq_t wq;
    4748        /** Futex hash table link. */
    48         link_t ht_link;
     49        ht_link_t ht_link;
    4950        /** Number of tasks that reference this futex. */
    5051        size_t refcount;
Note: See TracChangeset for help on using the changeset viewer.