Changeset 9f4067b6 in mainline for uspace/lib/nic/src/nic_addr_db.c


Ignore:
Timestamp:
2012-10-09T21:16:13Z (12 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6659037, 7d248e3
Parents:
d1ef4a1 (diff), 97b199b1 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge from lp:~jakub/helenos/gsoc2012-uspace-hash-table-from-adam.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/nic/src/nic_addr_db.c

    rd1ef4a1 r9f4067b6  
    3535 * @brief Generic hash-set based database of addresses
    3636 */
     37#include "nic_addr_db.h"
     38#include "libarch/common.h"
    3739#include <assert.h>
    3840#include <stdlib.h>
    … …  
    4042#include <errno.h>
    4143#include <mem.h>
    42 
    43 #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 <macros.h>
     46#include <stdint.h>
     47
     48
     49/**
     50 * Helper structure for keeping the address in the hash set.
     51 */
     52typedef struct nic_addr_entry {
     53        ht_link_t link;
     54        uint8_t len;
     55        uint8_t addr[1];
     56} nic_addr_entry_t;
     57
     58
     59/*
     60 * Hash table helper functions
     61 */
     62typedef struct {
     63        size_t len;
     64        const uint8_t *addr;
     65} addr_key_t;
     66
     67static bool nic_addr_key_equal(void *key_arg, const ht_link_t *item)
     68{
     69        addr_key_t *key = (addr_key_t*)key_arg;
     70        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     71       
     72        return 0 == bcmp(entry->addr, key->addr, entry->len);
     73}
     74
     75static size_t addr_hash(size_t len, const uint8_t *addr)
     76{
     77        size_t hash = 0;
     78       
     79        for (size_t i = 0; i < len; ++i) {
     80                hash = (hash << 5) ^ addr[i];
    6081        }
    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         }
     82       
    7783        return hash;
    7884}
    7985
    80 /**
    81  * Helper wrapper
    82  */
    83 static void nic_addr_destroy(link_t *item, void *unused)
    84 {
    85         free(item);
    86 }
     86static size_t nic_addr_key_hash(void *k)
     87{
     88        addr_key_t *key = (addr_key_t*)k;
     89        return addr_hash(key->len, key->addr);
     90}
     91
     92static size_t nic_addr_hash(const ht_link_t *item)
     93{
     94        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     95        return addr_hash(entry->len, entry->addr);
     96}
     97
     98static void nic_addr_removed(ht_link_t *item)
     99{
     100        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     101       
     102        free(entry);
     103}
     104
     105static hash_table_ops_t set_ops = {
     106        .hash = nic_addr_hash,
     107        .key_hash = nic_addr_key_hash,
     108        .key_equal = nic_addr_key_equal,
     109        .equal = NULL,
     110        .remove_callback = nic_addr_removed
     111};
    87112
    88113/**
    … …  
    99124{
    100125        assert(db);
    101         if (addr_len > NIC_ADDR_MAX_LENGTH) {
     126       
     127        if (addr_len > UCHAR_MAX)
    102128                return EINVAL;
    103         }
    104         if (!hash_set_init(&db->set, nic_addr_hash, nic_addr_equals,
    105                 NIC_ADDR_DB_INIT_SIZE)) {
     129       
     130        if (!hash_table_create(&db->set, 0, 0, &set_ops))
    106131                return ENOMEM;
    107         }
     132       
    108133        db->addr_len = addr_len;
    109134        return EOK;
    … …  
    118143{
    119144        assert(db);
    120         hash_set_clear(&db->set, nic_addr_destroy, NULL);
     145        hash_table_clear(&db->set);
    121146}
    122147
    … …  
    129154{
    130155        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 }
     156        hash_table_destroy(&db->set);
     157}
     158
    147159
    148160/**
    … …  
    160172{
    161173        assert(db && addr);
    162         nic_addr_entry_t *entry = malloc(sizeof (nic_addr_entry_t));
    163         if (entry == NULL) {
     174
     175        addr_key_t key = {
     176                .len = db->addr_len,
     177                .addr = addr
     178        };
     179       
     180        if (hash_table_find(&db->set, &key))
     181                return EEXIST;
     182       
     183        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
     184        if (entry == NULL)
    164185                return ENOMEM;
    165         }
    166         entry->addr_len = db->addr_len;
     186
     187        entry->len = (uint8_t) db->addr_len;
    167188        memcpy(entry->addr, addr, db->addr_len);
    168 
    169         return hash_set_insert(&db->set, &entry->item) ? EOK : EEXIST;
     189       
     190        hash_table_insert(&db->set, &entry->link);
     191        return EOK;
    170192}
    171193
    … …  
    182204{
    183205        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;
     206       
     207        addr_key_t key = {
     208                .len = db->addr_len,
     209                .addr = addr
     210        };
     211       
     212        if (hash_table_remove(&db->set, &key))
     213                return EOK;
     214        else
     215                return ENOENT;
    191216}
    192217
    … …  
    202227{
    203228        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);
     229       
     230        addr_key_t key = {
     231                .len = db->addr_len,
     232                .addr = addr
     233        };
     234       
     235        return 0 != hash_table_find(&db->set, &key);
    209236}
    210237
    … …  
    220247 * Helper function for nic_addr_db_foreach
    221248 */
    222 static void nic_addr_db_fe_helper(link_t *item, void *arg) {
     249static bool nic_addr_db_fe_helper(ht_link_t *item, void *arg)
     250{
    223251        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);
     252        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
     253        hs->func(entry->addr, hs->arg);
     254        return true;
    225255}
    226256
    … …  
    237267{
    238268        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);
     269        hash_table_apply((hash_table_t*)&db->set, nic_addr_db_fe_helper, &hs);
    274270}
    275271
Note: See TracChangeset for help on using the changeset viewer.