WebSVN – HelenOS-historic – Blame – /uspace/trunk/libc/generic/libadt/hash_table.c

Rev	Author	Line No.	Line
996	cejka	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
1653	cejka	29	/** @addtogroup libc
		30	* @{
		31	*/
		32	/** @file
		33	*/
		34
996	cejka	35	/*
		36	* This is an implementation of generic chained hash table.
		37	*/
		38
1392	palkovsky	39	#include <libadt/hash_table.h>
		40	#include <libadt/list.h>
996	cejka	41	#include <unistd.h>
		42	#include <malloc.h>
		43	#include <assert.h>
997	cejka	44	#include <stdio.h>
		45	#include <string.h>
996	cejka	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.
997	cejka	53	* @return true on success
996	cejka	54	*/
997	cejka	55	int hash_table_create(hash_table_t h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t op)
996	cejka	56	{
997	cejka	57	hash_count_t i;
996	cejka	58
997	cejka	59	assert(h);
		60	assert(op && op->hash && op->compare);
		61	assert(max_keys > 0);
996	cejka	62
1202	jermar	63	h->entry = malloc(m * sizeof(link_t));
996	cejka	64	if (!h->entry) {
997	cejka	65	printf("cannot allocate memory for hash table\n");
		66	return false;
996	cejka	67	}
1202	jermar	68	memset((void ) h->entry, 0, m sizeof(link_t));
996	cejka	69
		70	for (i = 0; i < m; i++)
		71	list_initialize(&h->entry[i]);
		72
		73	h->entries = m;
		74	h->max_keys = max_keys;
		75	h->op = op;
997	cejka	76	return true;
996	cejka	77	}
		78
		79	/** Insert item into hash table.
		80	*
		81	* @param h Hash table.
1709	jermar	82	* @param key Array of all keys necessary to compute hash index.
996	cejka	83	* @param item Item to be inserted into the hash table.
		84	*/
997	cejka	85	void hash_table_insert(hash_table_t h, unsigned long key[], link_t item)
996	cejka	86	{
		87	hash_index_t chain;
		88
997	cejka	89	assert(item);
		90	assert(h && h->op && h->op->hash && h->op->compare);
996	cejka	91
		92	chain = h->op->hash(key);
997	cejka	93	assert(chain < h->entries);
996	cejka	94
		95	list_append(item, &h->entry[chain]);
		96	}
		97
		98	/** Search hash table for an item matching keys.
		99	*
		100	* @param h Hash table.
		101	* @param key Array of all keys needed to compute hash index.
		102	*
		103	* @return Matching item on success, NULL if there is no such item.
		104	*/
997	cejka	105	link_t hash_table_find(hash_table_t h, unsigned long key[])
996	cejka	106	{
		107	link_t *cur;
		108	hash_index_t chain;
		109
997	cejka	110	assert(h && h->op && h->op->hash && h->op->compare);
996	cejka	111
		112	chain = h->op->hash(key);
997	cejka	113	assert(chain < h->entries);
996	cejka	114
		115	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		116	if (h->op->compare(key, h->max_keys, cur)) {
		117	/*
		118	* The entry is there.
		119	*/
		120	return cur;
		121	}
		122	}
		123
		124	return NULL;
		125	}
		126
		127	/** Remove all matching items from hash table.
		128	*
		129	* For each removed item, h->remove_callback() is called.
		130	*
		131	* @param h Hash table.
		132	* @param key Array of keys that will be compared against items of the hash table.
		133	* @param keys Number of keys in the 'key' array.
		134	*/
997	cejka	135	void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
996	cejka	136	{
		137	hash_index_t chain;
		138	link_t *cur;
		139
997	cejka	140	assert(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback);
		141	assert(keys <= h->max_keys);
996	cejka	142
		143	if (keys == h->max_keys) {
		144
		145	/*
		146	* All keys are known, hash_table_find() can be used to find the entry.
		147	*/
		148
		149	cur = hash_table_find(h, key);
		150	if (cur) {
		151	list_remove(cur);
		152	h->op->remove_callback(cur);
		153	}
		154	return;
		155	}
		156
		157	/*
		158	* Fewer keys were passed.
		159	* Any partially matching entries are to be removed.
		160	*/
		161	for (chain = 0; chain < h->entries; chain++) {
		162	for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) {
		163	if (h->op->compare(key, keys, cur)) {
		164	link_t *hlp;
		165
		166	hlp = cur;
		167	cur = cur->prev;
		168
		169	list_remove(hlp);
		170	h->op->remove_callback(hlp);
		171
		172	continue;
		173	}
		174	}
		175	}
		176	}
1653	cejka	177
		178
		179	/** @}
		180	*/
		181
		182

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/libc/generic/libadt/hash_table.c – Rev 1709