155682Smarkm/* 2233294Sstas * Copyright (c) 1997 Kungliga Tekniska H��gskolan 3233294Sstas * (Royal Institute of Technology, Stockholm, Sweden). 4233294Sstas * All rights reserved. 555682Smarkm * 6233294Sstas * Redistribution and use in source and binary forms, with or without 7233294Sstas * modification, are permitted provided that the following conditions 8233294Sstas * are met: 955682Smarkm * 10233294Sstas * 1. Redistributions of source code must retain the above copyright 11233294Sstas * notice, this list of conditions and the following disclaimer. 1255682Smarkm * 13233294Sstas * 2. Redistributions in binary form must reproduce the above copyright 14233294Sstas * notice, this list of conditions and the following disclaimer in the 15233294Sstas * documentation and/or other materials provided with the distribution. 1655682Smarkm * 17233294Sstas * 3. Neither the name of the Institute nor the names of its contributors 18233294Sstas * may be used to endorse or promote products derived from this software 19233294Sstas * without specific prior written permission. 2055682Smarkm * 21233294Sstas * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 22233294Sstas * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23233294Sstas * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24233294Sstas * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 25233294Sstas * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26233294Sstas * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27233294Sstas * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28233294Sstas * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29233294Sstas * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30233294Sstas * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31233294Sstas * SUCH DAMAGE. 3255682Smarkm */ 3355682Smarkm 3455682Smarkm/* 3555682Smarkm * hash.h. Header file for hash table functions 3655682Smarkm */ 3755682Smarkm 38233294Sstas/* $Id$ */ 3955682Smarkm 4055682Smarkmstruct hashentry { /* Entry in bucket */ 4155682Smarkm struct hashentry **prev; 4255682Smarkm struct hashentry *next; 4355682Smarkm void *ptr; 4455682Smarkm}; 4555682Smarkm 4655682Smarkmtypedef struct hashentry Hashentry; 4755682Smarkm 4855682Smarkmstruct hashtab { /* Hash table */ 4955682Smarkm int (*cmp)(void *, void *); /* Compare function */ 5055682Smarkm unsigned (*hash)(void *); /* hash function */ 5155682Smarkm int sz; /* Size */ 5255682Smarkm Hashentry *tab[1]; /* The table */ 5355682Smarkm}; 5455682Smarkm 5555682Smarkmtypedef struct hashtab Hashtab; 5655682Smarkm 5755682Smarkm/* prototypes */ 5855682Smarkm 59233294SstasHashtab *hashtabnew(int sz, 6055682Smarkm int (*cmp)(void *, void *), 6155682Smarkm unsigned (*hash)(void *)); /* Make new hash table */ 6255682Smarkm 6355682Smarkmvoid *hashtabsearch(Hashtab *htab, /* The hash table */ 6455682Smarkm void *ptr); /* The key */ 6555682Smarkm 6655682Smarkm 6755682Smarkmvoid *hashtabadd(Hashtab *htab, /* The hash table */ 6855682Smarkm void *ptr); /* The element */ 6955682Smarkm 7055682Smarkmint _hashtabdel(Hashtab *htab, /* The table */ 7155682Smarkm void *ptr, /* Key */ 7255682Smarkm int freep); /* Free data part? */ 7355682Smarkm 7455682Smarkmvoid hashtabforeach(Hashtab *htab, 7555682Smarkm int (*func)(void *ptr, void *arg), 7655682Smarkm void *arg); 7755682Smarkm 7855682Smarkmunsigned hashadd(const char *s); /* Standard hash function */ 7955682Smarkmunsigned hashcaseadd(const char *s); /* Standard hash function */ 8055682Smarkmunsigned hashjpw(const char *s); /* another hash function */ 8155682Smarkm 8255682Smarkm/* macros */ 8355682Smarkm 8455682Smarkm /* Don't free space */ 8555682Smarkm#define hashtabdel(htab,key) _hashtabdel(htab,key,FALSE) 8655682Smarkm 8755682Smarkm#define hashtabfree(htab,key) _hashtabdel(htab,key,TRUE) /* Do! */ 88