Subversion Repositories HelenOS

Rev

Rev 2479 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2479 Rev 2759
Line 1... Line 1...
1 
/*
 1 
/*
2 
 * Copyright (c) 2006 Jakub Jermar
 2 
 * Copyright (c) 2008 Jakub Jermar
3 
 * All rights reserved.
 3 
 * All rights reserved.
4 
 *
 4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
 5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
 6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
 7 
 * are met:
Line 44... Line 44...
44 
#include <stdio.h>
 44 
#include <stdio.h>
45 
#include <string.h>
 45 
#include <string.h>
46 
 
 46 
 
47 
/** Create chained hash table.
 47 
/** Create chained hash table.
48 
 *
 48 
 *
49 
 * @param h Hash table structure. Will be initialized by this call.
 49 
 * @param h     Hash table structure. Will be initialized by this call.
50 
 * @param m Number of slots in the hash table.
 50 
 * @param m     Number of hash table buckets.
51 
 * @param max_keys Maximal number of keys needed to identify an item.
 51 
 * @param max_keys  Maximal number of keys needed to identify an item.
52 
 * @param op Hash table operations structure.
 52 
 * @param op        Hash table operations structure.
53 
 * @return true on success
 53 
 * @return      True on success
54 
 */
 54 
 */
55 
int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op)
 55 
int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
- 
 
 56 
    hash_table_operations_t *op)
56 
{
 57 
{
57 
    hash_count_t i;
 58 
    hash_count_t i;
58 
 
 59 
 
59 
    assert(h);
 60 
    assert(h);
60 
    assert(op && op->hash && op->compare);
 61 
    assert(op && op->hash && op->compare);
Line 74... Line 75...
74 
    h->max_keys = max_keys;
 75 
    h->max_keys = max_keys;
75 
    h->op = op;
 76 
    h->op = op;
76 
    return true;
 77 
    return true;
77 
}
 78 
}
78 
 
 79 
 
79 
/** Insert item into hash table.
 80 
/** Destroy a hash table instance.
80 
 *
 81 
 *
- 
 
 82 
 * @param h     Hash table to be destroyed.
- 
 
 83 
 */
- 
 
 84 
void hash_table_destroy(hash_table_t *h)
- 
 
 85 
{
- 
 
 86 
    assert(h);
- 
 
 87 
    assert(h->entry);
- 
 
 88 
    free(h->entry);
- 
 
 89 
}
- 
 
 90 
 
- 
 
 91 
/** Insert item into a hash table.
- 
 
 92 
 *
81 
 * @param h Hash table.
 93 
 * @param h     Hash table.
82 
 * @param key Array of all keys necessary to compute hash index.
 94 
 * @param key       Array of all keys necessary to compute hash index.
83 
 * @param item Item to be inserted into the hash table.
 95 
 * @param item      Item to be inserted into the hash table.
84 
 */
 96 
 */
85 
void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
 97 
void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
86 
{
 98 
{
87 
    hash_index_t chain;
 99 
    hash_index_t chain;
88 
 
 100 
 
Line 95... Line 107...
95 
    list_append(item, &h->entry[chain]);
 107 
    list_append(item, &h->entry[chain]);
96 
}
 108 
}
97 
 
 109 
 
98 
/** Search hash table for an item matching keys.
 110 
/** Search hash table for an item matching keys.
99 
 *
 111 
 *
100 
 * @param h Hash table.
 112 
 * @param h     Hash table.
101 
 * @param key Array of all keys needed to compute hash index.
 113 
 * @param key       Array of all keys needed to compute hash index.
102 
 *
 114 
 *
103 
 * @return Matching item on success, NULL if there is no such item.
 115 
 * @return      Matching item on success, NULL if there is no such item.
104 
 */
 116 
 */
105 
link_t *hash_table_find(hash_table_t *h, unsigned long key[])
 117 
link_t *hash_table_find(hash_table_t *h, unsigned long key[])
106 
{
 118 
{
107 
    link_t *cur;
 119 
    link_t *cur;
108 
    hash_index_t chain;
 120 
    hash_index_t chain;
Line 110... Line 122...
110 
    assert(h && h->op && h->op->hash && h->op->compare);
 122 
    assert(h && h->op && h->op->hash && h->op->compare);
111 
 
 123 
 
112 
    chain = h->op->hash(key);
 124 
    chain = h->op->hash(key);
113 
    assert(chain < h->entries);
 125 
    assert(chain < h->entries);
114 
   
 126 
   
115 
    for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
 127 
    for (cur = h->entry[chain].next; cur != &h->entry[chain];
- 
 
 128 
        cur = cur->next) {
116 
        if (h->op->compare(key, h->max_keys, cur)) {
 129 
        if (h->op->compare(key, h->max_keys, cur)) {
117 
            /*
 130 
            /*
118 
             * The entry is there.
 131 
             * The entry is there.
119 
             */
 132 
             */
120 
            return cur;
 133 
            return cur;
Line 126... Line 139...
126 
 
 139 
 
127 
/** Remove all matching items from hash table.
 140 
/** Remove all matching items from hash table.
128 
 *
 141 
 *
129 
 * For each removed item, h->remove_callback() is called.
 142 
 * For each removed item, h->remove_callback() is called.
130 
 *
 143 
 *
131 
 * @param h Hash table.
 144 
 * @param h     Hash table.
132 
 * @param key Array of keys that will be compared against items of the hash table.
 145 
 * @param key       Array of keys that will be compared against items of
- 
 
 146 
 *          the hash table.
133 
 * @param keys Number of keys in the 'key' array.
 147 
 * @param keys      Number of keys in the 'key' array.
134 
 */
 148 
 */
135 
void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
 149 
void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
136 
{
 150 
{
137 
    hash_index_t chain;
 151 
    hash_index_t chain;
138 
    link_t *cur;
 152 
    link_t *cur;
139 
 
 153 
 
140 
    assert(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
 154 
    assert(h && h->op && h->op->hash && h->op->compare &&
- 
 
 155 
        h->op->remove_callback);
141 
    assert(keys <= h->max_keys);
 156 
    assert(keys <= h->max_keys);
142 
   
 157 
   
143 
    if (keys == h->max_keys) {
 158 
    if (keys == h->max_keys) {
144 
 
 159 
 
145 
        /*
 160 
        /*
146 
         * All keys are known, hash_table_find() can be used to find the entry.
 161 
         * All keys are known, hash_table_find() can be used to find the
- 
 
 162 
         * entry.
147 
         */
 163 
         */
148 
   
 164 
   
149 
        cur = hash_table_find(h, key);
 165 
        cur = hash_table_find(h, key);
150 
        if (cur) {
 166 
        if (cur) {
151 
            list_remove(cur);
 167 
            list_remove(cur);
Line 157... Line 173...
157 
    /*
 173 
    /*
158 
     * Fewer keys were passed.
 174 
     * Fewer keys were passed.
159 
     * Any partially matching entries are to be removed.
 175 
     * Any partially matching entries are to be removed.
160 
     */
 176 
     */
161 
    for (chain = 0; chain < h->entries; chain++) {
 177 
    for (chain = 0; chain < h->entries; chain++) {
162 
        for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
 178 
        for (cur = h->entry[chain].next; cur != &h->entry[chain];
- 
 
 179 
            cur = cur->next) {
163 
            if (h->op->compare(key, keys, cur)) {
 180 
            if (h->op->compare(key, keys, cur)) {
164 
                link_t *hlp;
 181 
                link_t *hlp;
165 
               
 182 
               
166 
                hlp = cur;
 183 
                hlp = cur;
167 
                cur = cur->prev;
 184 
                cur = cur->prev;