Return to hash.c CVS log

Up to [local] / src / usr.sbin / config

remove sys/param.h includes by stopping use of NODEV, ALIGNED and ALIGN().
The latter two exposed a large block allocator on top of malloc() which
doesn't really make sense in this decade (the objects are never freed, so
not quite like the famous openssl allocator)
ok millert jsg

/*	$OpenBSD: hash.c,v 1.19 2021/11/28 19:26:03 deraadt Exp $	*/
/*	$NetBSD: hash.c,v 1.4 1996/11/07 22:59:43 gwr Exp $	*/

/*
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This software was developed by the Computer Systems Engineering group
 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
 * contributed to Berkeley.
 *
 * All advertising materials mentioning features or use of this software
 * must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Lawrence Berkeley Laboratories.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	from: @(#)hash.c	8.1 (Berkeley) 6/6/93
 */

#include <sys/types.h>

#include <stdlib.h>
#include <string.h>

#include "config.h"

/*
 * Interned strings are kept in a hash table.  By making each string
 * unique, the program can compare strings by comparing pointers.
 */
struct hashent {
	struct	hashent *h_next;	/* hash buckets are chained */
	const char *h_name;		/* the string */
	u_int	h_hash;			/* its hash value */
	void	*h_value;		/* other values (for name=value) */
};
struct hashtab {
	size_t	ht_size;		/* size (power of 2) */
	u_int	ht_mask;		/* == ht_size - 1 */
	u_int	ht_used;		/* number of entries used */
	u_int	ht_lim;			/* when to expand */
	struct	hashent **ht_tab;	/* base of table */
};
static struct hashtab strings;

/*
 * HASHFRACTION controls ht_lim, which in turn controls the average chain
 * length.  We allow a few entries, on average, as comparing them is usually
 * cheap (the h_hash values prevent a strcmp).
 */
#define	HASHFRACTION(sz) ((sz) * 3 / 2)

/* round up to next multiple of y, where y is a power of 2 */
#define	ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1))

static void ht_init(struct hashtab *, size_t);
static void ht_expand(struct hashtab *);

/*
 * Initialize a new hash table.  The size must be a power of 2.
 */
static void
ht_init(struct hashtab *ht, size_t sz)
{
	struct hashent **h;
	u_int n;

	h = ereallocarray(NULL, sz, sizeof *h);
	ht->ht_tab = h;
	ht->ht_size = sz;
	ht->ht_mask = sz - 1;
	for (n = 0; n < sz; n++)
		*h++ = NULL;
	ht->ht_used = 0;
	ht->ht_lim = HASHFRACTION(sz);
}

/*
 * Expand an existing hash table.
 */
static void
ht_expand(struct hashtab *ht)
{
	struct hashent *p, **h, **oldh, *q;
	u_int n, i;

	n = ht->ht_size * 2;
	h = ecalloc(n, sizeof *h);
	oldh = ht->ht_tab;
	n--;
	for (i = ht->ht_size; i != 0; i--) {
		for (p = *oldh++; p != NULL; p = q) {
			q = p->h_next;
			p->h_next = h[p->h_hash & n];
			h[p->h_hash & n] = p;
		}
	}
	free(ht->ht_tab);
	ht->ht_tab = h;
	ht->ht_mask = n;
	ht->ht_size = ++n;
	ht->ht_lim = HASHFRACTION(n);
}

/*
 * Make a new hash entry, setting its h_next to NULL.
 */
static __inline struct hashent *
newhashent(const char *name, u_int h)
{
	struct	hashent *hp;

	hp = emalloc(sizeof(*hp));
	hp->h_name = name;
	hp->h_hash = h;
	hp->h_next = NULL;
	return (hp);
}

/*
 * Hash a string.
 */
static __inline u_int
hash(const char *str)
{
	u_int h;

	for (h = 0; *str;)
		h = (h << 5) + h + *str++;
	return (h);
}

void
initintern(void)
{

	ht_init(&strings, 128);
}

/*
 * Generate a single unique copy of the given string.  We expect this
 * function to be used frequently, so it should be fast.
 */
const char *
intern(const char *s)
{
	struct hashtab *ht;
	struct hashent *hp, **hpp;
	u_int h;
	char *p;
	size_t l;

	ht = &strings;
	h = hash(s);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
		if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
			return (hp->h_name);
	l = strlen(s) + 1;
	p = malloc(l);
	bcopy(s, p, l);
	*hpp = newhashent(p, h);
	if (++ht->ht_used > ht->ht_lim)
		ht_expand(ht);
	return (p);
}

struct hashtab *
ht_new(void)
{
	struct hashtab *ht;

	ht = emalloc(sizeof *ht);
	ht_init(ht, 8);
	return (ht);
}

/*
 * Remove.
 */
int
ht_remove(struct hashtab *ht, const char *nam)
{
	struct hashent *hp, *thp;
	u_int h;

	h = hash(nam);
	hp = ht->ht_tab[h & ht->ht_mask];
	while (hp && hp->h_name == nam)	{
		ht->ht_tab[h & ht->ht_mask] = hp->h_next;
		/* XXX free hp ? */
		hp = ht->ht_tab[h & ht->ht_mask];
	}

	if ((hp = ht->ht_tab[h & ht->ht_mask]) == NULL)
		return (0);

	for (thp = hp->h_next; thp != NULL; thp = hp->h_next) {
		if (thp->h_name == nam) {
			hp->h_next = thp->h_next;
			/* XXX free thp ? */
		} else
			hp = thp;
	}

	return (0);
}

/*
 * Insert and/or replace.
 */
int
ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
{
	struct hashent *hp, **hpp;
	u_int h;

	h = hash(nam);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next) {
		if (hp->h_name == nam) {
			if (replace)
				hp->h_value = val;
			return (1);
		}
	}
	*hpp = hp = newhashent(nam, h);
	hp->h_value = val;
	if (++ht->ht_used > ht->ht_lim)
		ht_expand(ht);
	return (0);
}

void *
ht_lookup(struct hashtab *ht, const char *nam)
{
	struct hashent *hp, **hpp;
	u_int h;

	h = hash(nam);
	hpp = &ht->ht_tab[h & ht->ht_mask];
	for (; (hp = *hpp) != NULL; hpp = &hp->h_next)
		if (hp->h_name == nam)
			return (hp->h_value);
	return (NULL);
}