WebSVN – HelenOS – Blame – /branches/dd/kernel/generic/src/adt/hash_table.c

Rev	Author	Line No.	Line
790	jermar	1	/*
2071	jermar	2	* Copyright (c) 2006 Jakub Jermar
790	jermar	3	* All rights reserved.
		4	*
		5	* Redistribution and use in source and binary forms, with or without
		6	* modification, are permitted provided that the following conditions
		7	* are met:
		8	*
		9	* - Redistributions of source code must retain the above copyright
		10	* notice, this list of conditions and the following disclaimer.
		11	* - Redistributions in binary form must reproduce the above copyright
		12	* notice, this list of conditions and the following disclaimer in the
		13	* documentation and/or other materials provided with the distribution.
		14	* - The name of the author may not be used to endorse or promote products
		15	* derived from this software without specific prior written permission.
		16	*
		17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
		18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
		19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
		20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
		21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
		22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
		23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
		24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
		26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		27	*/
		28
1757	jermar	29	/** @addtogroup genericadt
1702	cejka	30	* @{
		31	*/
		32
1248	jermar	33	/**
1704	cejka	34	* @file
1248	jermar	35	* @brief Implementation of generic chained hash table.
		36	*
		37	* This file contains implementation of generic chained hash table.
790	jermar	38	*/
		39
		40	#include <adt/hash_table.h>
		41	#include <adt/list.h>
		42	#include <arch/types.h>
		43	#include <debug.h>
814	palkovsky	44	#include <mm/slab.h>
790	jermar	45	#include <memstr.h>
		46
		47	/** Create chained hash table.
		48	*
		49	* @param h Hash table structure. Will be initialized by this call.
		50	* @param m Number of slots in the hash table.
		51	* @param max_keys Maximal number of keys needed to identify an item.
		52	* @param op Hash table operations structure.
		53	*/
		54	void hash_table_create(hash_table_t h, count_t m, count_t max_keys, hash_table_operations_t op)
		55	{
2112	decky	56	index_t i;
902	jermar	57
790	jermar	58	ASSERT(h);
		59	ASSERT(op && op->hash && op->compare);
		60	ASSERT(max_keys > 0);
		61
2112	decky	62	h->entry = (link_t ) malloc(m sizeof(link_t), 0);
790	jermar	63	if (!h->entry) {
		64	panic("cannot allocate memory for hash table\n");
		65	}
1780	jermar	66	memsetb((uintptr_t) h->entry, m * sizeof(link_t), 0);
790	jermar	67
902	jermar	68	for (i = 0; i < m; i++)
		69	list_initialize(&h->entry[i]);
		70
790	jermar	71	h->entries = m;
		72	h->max_keys = max_keys;
		73	h->op = op;
		74	}
		75
		76	/** Insert item into hash table.
		77	*
		78	* @param h Hash table.
1708	jermar	79	* @param key Array of all keys necessary to compute hash index.
790	jermar	80	* @param item Item to be inserted into the hash table.
		81	*/
1780	jermar	82	void hash_table_insert(hash_table_t h, unative_t key[], link_t item)
790	jermar	83	{
		84	index_t chain;
		85
		86	ASSERT(item);
		87	ASSERT(h && h->op && h->op->hash && h->op->compare);
		88
		89	chain = h->op->hash(key);
		90	ASSERT(chain < h->entries);
		91
		92	list_append(item, &h->entry[chain]);
		93	}
		94
		95	/** Search hash table for an item matching keys.
		96	*
		97	* @param h Hash table.
		98	* @param key Array of all keys needed to compute hash index.
		99	*
		100	* @return Matching item on success, NULL if there is no such item.
		101	*/
1780	jermar	102	link_t hash_table_find(hash_table_t h, unative_t key[])
790	jermar	103	{
		104	link_t *cur;
		105	index_t chain;
		106
		107	ASSERT(h && h->op && h->op->hash && h->op->compare);
		108
		109	chain = h->op->hash(key);
		110	ASSERT(chain < h->entries);
		111
		112	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		113	if (h->op->compare(key, h->max_keys, cur)) {
		114	/*
		115	* The entry is there.
		116	*/
		117	return cur;
		118	}
		119	}
		120
		121	return NULL;
		122	}
		123
		124	/** Remove all matching items from hash table.
		125	*
		126	* For each removed item, h->remove_callback() is called.
		127	*
		128	* @param h Hash table.
		129	* @param key Array of keys that will be compared against items of the hash table.
1248	jermar	130	* @param keys Number of keys in the key array.
790	jermar	131	*/
1780	jermar	132	void hash_table_remove(hash_table_t *h, unative_t key[], count_t keys)
790	jermar	133	{
		134	index_t chain;
		135	link_t *cur;
		136
		137	ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
		138	ASSERT(keys <= h->max_keys);
		139
		140	if (keys == h->max_keys) {
		141
		142	/*
		143	* All keys are known, hash_table_find() can be used to find the entry.
		144	*/
		145
		146	cur = hash_table_find(h, key);
		147	if (cur) {
		148	list_remove(cur);
		149	h->op->remove_callback(cur);
		150	}
		151	return;
		152	}
		153
		154	/*
		155	* Fewer keys were passed.
		156	* Any partially matching entries are to be removed.
		157	*/
		158	for (chain = 0; chain < h->entries; chain++) {
		159	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		160	if (h->op->compare(key, keys, cur)) {
		161	link_t *hlp;
		162
		163	hlp = cur;
		164	cur = cur->prev;
		165
		166	list_remove(hlp);
		167	h->op->remove_callback(hlp);
		168
		169	continue;
		170	}
		171	}
		172	}
		173	}
1702	cejka	174
1757	jermar	175	/** @}
1702	cejka	176	*/

Subversion Repositories HelenOS

(root)/branches/dd/kernel/generic/src/adt/hash_table.c – Rev 3022