/*
    HashList.c, Copyright  (c) by George Fankhauser,
    Swiss Federal Institute of Technology,
    Computer Engineering and Networks Laboratory.

    TOPSY -- A Teachable Operating System.
             Implementation of a tiny and simple
             micro kernel for teaching purposes.

    For further information, please visit http://www.tik.ee.ethz.ch/~topsy

    This software is provided under the terms of the GNU General Public Licence.

    A full copy of the GNU GPL is provided in the file COPYING found in the 
    development root of Topsy.
*/
/*
	
	File:                  $Source: /usr/drwho/vault/cvs/topsy/Topsy/Topsy/HashList.c,v $
 	Author(s):             George Fankhauser
 	Affiliation:           ETH Zuerich, TIK
 	Version:               $Revision: 1.15 $
 	Creation Date:         
 	Last Date of Change:   $Date: 1999/12/13 21:48:36 $      by: $Author: ruf $
	
	
	$Log: HashList.c,v $
	Revision 1.15  1999/12/13 21:48:36  ruf
	GNU General Public Licence Update
	
	Revision 1.14  1999/10/19 14:59:21  gfa
	*** empty log message ***
	
	Revision 1.13  1997/04/25 18:36:44  gfa
	hash function runs on unsigned keys...

 * Revision 1.12  1997/04/23  11:56:34  gfa
 * *** empty log message ***
 *
 * Revision 1.11  1997/04/06  18:57:18  gfa
 * changed hashFunction to be static
 *
 * Revision 1.10  1997/03/24  20:33:31  gfa
 * uses only dynamic memory from now on...
 *
 * Revision 1.9  1997/03/13  23:57:50  gfa
 * no changes
 *
 * Revision 1.8  97/03/11  20:08:40  conrad
 * new HashFunction
 * 
 * Revision 1.7  1997/03/11  08:18:29  gfa
 * changed kmAlloc to hmAlloc
 *
 * Revision 1.6  1997/03/09  20:52:40  gfa
 * added GET_STATIC... macro
 *
 * Revision 1.5  1997/03/06  16:14:17  gfa
 * changed constants from OK to HASHOK etc.
 *
 * Revision 1.4  1997/02/22  19:36:14  gfa
 * *** empty log message ***
 *
 * Revision 1.3  1997/02/22  19:21:23  gfa
 * purify'ed and tested version
 * supports now the mixed use of static and dynamic memory
 * to allow kernel data structures to be accessed on startup
 * and grow dynamically later
 *
 * Revision 1.2  1997/02/13  15:49:14  conrad
 * First compilation/linking of complete environment (all modules)
 *
 * Revision 1.1  1997/02/04  11:46:04  topsy
 * Initial revision
 *
*/

#include "HashList.h"


static unsigned long int hashFunction(unsigned long int key) {
    return( key % HASHLISTSIZE);       /* modulo array size */
}


HashList hashListNew() {
    Error error;
    int i;
    HashList list;

    error = hmAlloc((Address*)&list, sizeof(HashListDesc));
    if (error != HM_ALLOCOK) return NULL;
    for (i = 0; i < HASHLISTSIZE; i++) {
	list->table[i] = NULL;
    }
    return list;
}


Error hashListFree(HashList list) {
    int i;
    HashListElement toBeFreed, toBeFreedNext;
    
    for (i = 0; i < HASHLISTSIZE; i++) {
	toBeFreed = list->table[i];
	while (toBeFreed != NULL) {
	    toBeFreedNext = toBeFreed->next;
	    hmFree(toBeFreed);
	    toBeFreed = toBeFreedNext;
	}
    }
    hmFree(list);
    return HASHOK;
}


Error hashListAdd(HashList list, void* data, unsigned long int key) {
    Address address;
    Error error;
    HashListElement element;

    address = NULL;
    error = hmAlloc(&address, sizeof(HashListElementDesc));   
    if (error != HM_ALLOCOK) return HASHERROR;

    if (list->table[hashFunction(key)] == NULL) {
	list->table[hashFunction(key)] = (HashListElement)address;
	element = (HashListElement)address;
    }
    else {
	element = list->table[hashFunction(key)];
	if (element->key == key) { 
	    hmFree(address); return HASHDUPLICATEKEY; 
	}
	while (element->next != NULL) {
	    element = element->next;
	    if (element->key == key) { 
		hmFree(address); return HASHDUPLICATEKEY; 
	    }
	}
	element->next = (HashListElement)address;
	element = element->next;
    }
    element->item = data;
    element->key = key;
    element->next = NULL;
    return HASHOK;
}


Error hashListGet(HashList list, void** data, unsigned long int key) {
    HashListElement element = list->table[hashFunction(key)];

    while (element != NULL) {
	if (element->key == key) {
	    *data = element->item;
	    return HASHOK;
	}
	element = element->next;
    }
    *data = NULL;
    return HASHNOTFOUND;
}


Error hashListRemove(HashList list, unsigned long int key) {
    HashListElement previous = NULL;
    HashListElement element = list->table[hashFunction(key)];

    if (element != NULL) {
	if (element->key == key) {
	    list->table[hashFunction(key)] = element->next;
	    hmFree(element);
	    return HASHOK;
	}
	else {
	    previous = element;
	    element = element->next;
	    while (element != NULL) {
		if (element->key == key) {
		    previous->next = element->next;
		    hmFree(element);
		    return HASHOK;
		}
		previous = element;
		element = element->next;
	    }
	}
    }
    return HASHNOTFOUND;
}