Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 2732c94 in mainline


Ignore:
Timestamp:
2012-07-21T13:37:09Z (9 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master
Children:
a2348a9
Parents:
0ca7286
Message:

Replaced separate uspace hash_set implementation with uspace's hash_table.

Location:
uspace/lib
Files:
2 deleted
5 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/c/generic/adt/hash_table.c

    r0ca7286 r2732c94  
    219219 *
    220220 */
    221 link_t *hash_table_find(hash_table_t *h, unsigned long key[])
     221link_t *hash_table_find(const hash_table_t *h, unsigned long key[])
    222222{
    223223        assert(h && h->bucket);
  • uspace/lib/c/include/adt/hash_table.h

    r0ca7286 r2732c94  
    9191extern void hash_table_insert(hash_table_t *, link_t *);
    9292extern bool hash_table_insert_unique(hash_table_t *, link_t *);
    93 extern link_t *hash_table_find(hash_table_t *, unsigned long []);
     93extern link_t *hash_table_find(const hash_table_t *, unsigned long []);
    9494extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
    9595extern void hash_table_remove_item(hash_table_t *, link_t *);
     
    9898        void *);
    9999
     100
    100101#endif
    101102
  • uspace/lib/c/include/adt/list.h

    r0ca7286 r2732c94  
    102102                iterator = next_iter, next_iter = iterator->next)
    103103
     104#ifndef member_to_inst
     105#define member_to_inst(ptr_member, type, member_identif) \
     106        ((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif))))
     107#endif
     108
    104109
    105110#define assert_link_not_used(link) \
  • uspace/lib/nic/include/nic_addr_db.h

    r0ca7286 r2732c94  
    4343#endif
    4444
    45 #include <adt/hash_set.h>
    46 
    47 /**
    48  * Initial size of DB's hash set
    49  */
    50 #define NIC_ADDR_DB_INIT_SIZE   8
    51 /**
    52  * Maximal length of addresses in the DB (in bytes).
    53  */
    54 #define NIC_ADDR_MAX_LENGTH             16
     45#include <adt/hash_table.h>
    5546
    5647/**
     
    5849 */
    5950typedef struct nic_addr_db {
    60         hash_set_t set;
     51        hash_table_t set;
    6152        size_t addr_len;
    6253} nic_addr_db_t;
    6354
    64 /**
    65  * Helper structure for keeping the address in the hash set.
    66  */
    67 typedef struct nic_addr_entry {
    68         link_t item;
    69         size_t addr_len;
    70         uint8_t addr[NIC_ADDR_MAX_LENGTH];
    71 } nic_addr_entry_t;
    7255
    7356extern int nic_addr_db_init(nic_addr_db_t *db, size_t addr_len);
    7457extern void nic_addr_db_clear(nic_addr_db_t *db);
    7558extern void nic_addr_db_destroy(nic_addr_db_t *db);
    76 extern size_t nic_addr_db_count(const nic_addr_db_t *db);
    7759extern int nic_addr_db_insert(nic_addr_db_t *db, const uint8_t *addr);
    7860extern int nic_addr_db_remove(nic_addr_db_t *db, const uint8_t *addr);
    79 extern void nic_addr_db_remove_selected(nic_addr_db_t *db,
    80         int (*func)(const uint8_t *, void *), void *arg);
    8161extern int nic_addr_db_contains(const nic_addr_db_t *db, const uint8_t *addr);
    8262extern void nic_addr_db_foreach(const nic_addr_db_t *db,
  • uspace/lib/nic/src/nic_addr_db.c

    r0ca7286 r2732c94  
    4242
    4343#include "nic_addr_db.h"
    44 
    45 /**
    46  * Hash set helper function
    47  */
    48 static int nic_addr_equals(const link_t *item1, const link_t *item2)
    49 {
    50         assert(item1 && item2);
    51         size_t addr_len = ((const nic_addr_entry_t *) item1)->addr_len;
    52 
    53         assert(addr_len == ((const nic_addr_entry_t *) item2)->addr_len);
    54 
    55         size_t i;
    56         for (i = 0; i < addr_len; ++i) {
    57                 if (((nic_addr_entry_t *) item1)->addr[i] !=
    58                         ((nic_addr_entry_t *) item2)->addr[i])
    59                         return false;
     44#include "adt/hash_table.h"
     45//#include "string.h"
     46
     47
     48/* Couple address bytes into KEY_CNT key fields. Align up to fit all bytes. */
     49//#define KEY_CNT ((NIC_ADDR_MAX_LENGTH + sizeof(unsigned long) - 1) / sizeof(unsigned long))
     50#define KEY_CNT 1
     51
     52/**
     53 * Maximal length of addresses in the DB (in bytes).
     54 */
     55#define NIC_ADDR_MAX_LENGTH             16
     56
     57/**
     58 * Helper structure for keeping the address in the hash set.
     59 */
     60typedef struct nic_addr_entry {
     61        link_t link;
     62        uint8_t addr[NIC_ADDR_MAX_LENGTH];
     63} nic_addr_entry_t;
     64
     65
     66/*
     67 * Hash table helper functions
     68 */
     69
     70static bool nic_addr_match(unsigned long *key, size_t key_cnt,
     71        const link_t *item)
     72{
     73        /* Ugly type-punning hack. */
     74        uint8_t *addr = (uint8_t*)key;
     75        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     76
     77        return 0 == bcmp(entry->addr, addr, NIC_ADDR_MAX_LENGTH);
     78}
     79
     80static size_t nic_addr_key_hash(unsigned long *key)
     81{
     82        uint8_t *addr = (uint8_t*)key;
     83        size_t hash = 0;
     84
     85        for (int i = NIC_ADDR_MAX_LENGTH - 1; i >= 0; --i) {
     86                hash = (hash << 8) ^ (hash >> 24) ^ addr[i];
    6087        }
    61         return true;
    62 }
    63 
    64 /**
    65  * Hash set helper function
    66  */
    67 static unsigned long nic_addr_hash(const link_t *item)
    68 {
    69         assert(item);
    70         const nic_addr_entry_t *entry = (const nic_addr_entry_t *) item;
    71         unsigned long hash = 0;
    72 
    73         size_t i;
    74         for (i = 0; i < entry->addr_len; ++i) {
    75                 hash = (hash << 8) ^ (hash >> 24) ^ entry->addr[i];
    76         }
     88       
    7789        return hash;
    7890}
    7991
    80 /**
    81  * Helper wrapper
    82  */
    83 static void nic_addr_destroy(link_t *item, void *unused)
    84 {
    85         free(item);
    86 }
     92static size_t nic_addr_hash(const link_t *item)
     93{
     94        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     95       
     96        /* Ugly type-punning hack. */
     97        unsigned long *key = (unsigned long*)entry->addr;
     98        return nic_addr_key_hash(key);
     99}
     100
     101static void nic_addr_removed(link_t *item)
     102{
     103        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     104       
     105        free(entry);
     106}
     107
     108static hash_table_ops_t set_ops = {
     109        .hash = nic_addr_hash,
     110        .key_hash = nic_addr_key_hash,
     111        .match = nic_addr_match,
     112        .equal = 0,
     113        .remove_callback = nic_addr_removed
     114};
    87115
    88116/**
     
    102130                return EINVAL;
    103131        }
    104         if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals,
    105                 NIC_ADDR_DB_INIT_SIZE)) {
     132       
     133        if (!hash_table_create(&db->set, 0, KEY_CNT, &set_ops))
    106134                return ENOMEM;
    107         }
     135       
    108136        db->addr_len = addr_len;
    109137        return EOK;
     
    118146{
    119147        assert(db);
    120         hash_set_clear(&db->set, nic_addr_destroy, NULL);
     148        hash_table_clear(&db->set);
    121149}
    122150
     
    129157{
    130158        assert(db);
    131         hash_set_apply(&db->set, nic_addr_destroy, NULL);
    132         hash_set_destroy(&db->set);
    133 }
    134 
    135 /**
    136  * Get number of addresses in the db
    137  *
    138  * @param       db
    139  *
    140  * @return Number of adresses
    141  */
    142 size_t nic_addr_db_count(const nic_addr_db_t *db)
    143 {
    144         assert(db);
    145         return hash_set_count(&db->set);
    146 }
     159        nic_addr_db_clear(db);
     160        hash_table_destroy(&db->set);
     161}
     162
    147163
    148164/**
     
    160176{
    161177        assert(db && addr);
    162         nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t));
    163         if (entry == NULL) {
     178        /* Ugly type-punning hack. */
     179        unsigned long *key = (unsigned long*)addr;
     180       
     181        if (hash_table_find(&db->set, key))
     182                return EEXIST;
     183       
     184        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t));
     185        if (entry == NULL)
    164186                return ENOMEM;
    165         }
    166         entry->addr_len = db->addr_len;
     187       
     188        link_initialize(&entry->link);
     189       
     190        bzero(entry->addr, NIC_ADDR_MAX_LENGTH);
    167191        memcpy(entry->addr, addr, db->addr_len);
    168 
    169         return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST;
     192       
     193        hash_table_insert(&db->set, &entry->link);
     194        return EOK;
    170195}
    171196
     
    182207{
    183208        assert(db && addr);
    184         nic_addr_entry_t entry;
    185         entry.addr_len = db->addr_len;
    186         memcpy(entry.addr, addr, db->addr_len);
    187 
    188         link_t *removed = hash_set_remove(&db->set, &entry.item);
    189         free(removed);
    190         return removed != NULL ? EOK : ENOENT;
     209        unsigned long *key = (unsigned long*)addr;
     210       
     211        link_t *item = hash_table_find(&db->set, key);
     212       
     213        if (item) {
     214                hash_table_remove_item(&db->set, item);
     215                return EOK;
     216        } else {
     217                return ENOENT;
     218        }
    191219}
    192220
     
    202230{
    203231        assert(db && addr);
    204         nic_addr_entry_t entry;
    205         entry.addr_len = db->addr_len;
    206         memcpy(entry.addr, addr, db->addr_len);
    207 
    208         return hash_set_contains(&db->set, &entry.item);
     232        unsigned long *key = (unsigned long*)addr;
     233       
     234        return 0 != hash_table_find(&db->set, key);
    209235}
    210236
     
    220246 * Helper function for nic_addr_db_foreach
    221247 */
    222 static void nic_addr_db_fe_helper(link_t *item, void *arg) {
     248static bool nic_addr_db_fe_helper(link_t *item, void *arg)
     249{
    223250        nic_addr_db_fe_arg_t *hs = (nic_addr_db_fe_arg_t *) arg;
    224         hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
     251        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     252        hs->func(entry->addr, hs->arg);
     253        return true;
    225254}
    226255
     
    237266{
    238267        nic_addr_db_fe_arg_t hs = { .func = func, .arg = arg };
    239         hash_set_apply((hash_set_t *) &db->set, nic_addr_db_fe_helper, &hs);
    240 }
    241 
    242 /**
    243  * Helper structure for nic_addr_db_remove_selected
    244  */
    245 typedef struct {
    246         int (*func)(const uint8_t *, void *);
    247         void *arg;
    248 } nic_addr_db_rs_arg_t;
    249 
    250 /**
    251  * Helper function for nic_addr_db_foreach
    252  */
    253 static int nic_addr_db_rs_helper(link_t *item, void *arg) {
    254         nic_addr_db_rs_arg_t *hs = (nic_addr_db_rs_arg_t *) arg;
    255         int retval = hs->func(((nic_addr_entry_t *) item)->addr, hs->arg);
    256         if (retval) {
    257                 free(item);
    258         }
    259         return retval;
    260 }
    261 
    262 /**
    263  * Removes all addresses for which the function returns non-zero.
    264  *
    265  * @param       db
    266  * @param       func    User-defined function
    267  * @param       arg             Custom argument passed to the function
    268  */
    269 void nic_addr_db_remove_selected(nic_addr_db_t *db,
    270         int (*func)(const uint8_t *, void *), void *arg)
    271 {
    272         nic_addr_db_rs_arg_t hs = { .func = func, .arg = arg };
    273         hash_set_remove_selected(&db->set, nic_addr_db_rs_helper, &hs);
     268        hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs);
    274269}
    275270
Note: See TracChangeset for help on using the changeset viewer.