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

Rev	Author	Line No.	Line
790	jermar	1	/*
		2	* Copyright (C) 2006 Jakub 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
		29	/*
		30	* This is an implementation of generic chained hash table.
		31	*/
		32
		33	#include <adt/hash_table.h>
		34	#include <adt/list.h>
		35	#include <typedefs.h>
		36	#include <arch/types.h>
		37	#include <debug.h>
		38	#include <mm/heap.h>
		39	#include <memstr.h>
		40
		41	/** Create chained hash table.
		42	*
		43	* @param h Hash table structure. Will be initialized by this call.
		44	* @param m Number of slots in the hash table.
		45	* @param max_keys Maximal number of keys needed to identify an item.
		46	* @param op Hash table operations structure.
		47	*/
		48	void hash_table_create(hash_table_t h, count_t m, count_t max_keys, hash_table_operations_t op)
		49	{
		50	ASSERT(h);
		51	ASSERT(op && op->hash && op->compare);
		52	ASSERT(max_keys > 0);
		53
		54	h->entry = malloc(m * sizeof(link_t *));
		55	if (!h->entry) {
		56	panic("cannot allocate memory for hash table\n");
		57	}
		58	memsetb((__address) h->entry, m * sizeof(link_t *), 0);
		59
		60	h->entries = m;
		61	h->max_keys = max_keys;
		62	h->op = op;
		63	}
		64
		65	/** Insert item into hash table.
		66	*
		67	* @param h Hash table.
		68	* @param hey Array of all keys necessary to compute hash index.
		69	* @param item Item to be inserted into the hash table.
		70	*
		71	* @return true on success, false if the keys were already present in the hash table.
		72	*/
		73	bool hash_table_insert(hash_table_t h, __native key[], link_t item)
		74	{
		75	index_t chain;
		76
		77	ASSERT(item);
		78	ASSERT(h && h->op && h->op->hash && h->op->compare);
		79
		80	chain = h->op->hash(key);
		81	ASSERT(chain < h->entries);
		82
		83	if (hash_table_find(h, key)) {
		84	/*
		85	* The hash table is not redundant.
		86	* Signal failure on return.
		87	*/
		88	return false;
		89	}
		90
		91	list_append(item, &h->entry[chain]);
		92	return true;
		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	*/
		102	link_t hash_table_find(hash_table_t h, __native key[])
		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	/*
		113	* The hash table is not redundant.
		114	* Check if the keys are not in place already.
		115	*/
		116	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		117	if (h->op->compare(key, h->max_keys, cur)) {
		118	/*
		119	* The entry is there.
		120	*/
		121	return cur;
		122	}
		123	}
		124
		125	return NULL;
		126	}
		127
		128	/** Remove all matching items from hash table.
		129	*
		130	* For each removed item, h->remove_callback() is called.
		131	*
		132	* @param h Hash table.
		133	* @param key Array of keys that will be compared against items of the hash table.
		134	* @param keys Number of keys in the 'key' array.
		135	*/
		136	void hash_table_remove(hash_table_t *h, __native key[], count_t keys)
		137	{
		138	index_t chain;
		139	link_t *cur;
		140
		141	ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
		142	ASSERT(keys <= h->max_keys);
		143
		144	if (keys == h->max_keys) {
		145
		146	/*
		147	* All keys are known, hash_table_find() can be used to find the entry.
		148	*/
		149
		150	cur = hash_table_find(h, key);
		151	if (cur) {
		152	list_remove(cur);
		153	h->op->remove_callback(cur);
		154	}
		155	return;
		156	}
		157
		158	/*
		159	* Fewer keys were passed.
		160	* Any partially matching entries are to be removed.
		161	*/
		162	for (chain = 0; chain < h->entries; chain++) {
		163	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		164	if (h->op->compare(key, keys, cur)) {
		165	link_t *hlp;
		166
		167	hlp = cur;
		168	cur = cur->prev;
		169
		170	list_remove(hlp);
		171	h->op->remove_callback(hlp);
		172
		173	continue;
		174	}
		175	}
		176	}
		177	}

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/adt/hash_table.c @ 4153 – Rev 790