File: [local] / src / usr.bin / cvs / Attic / strtab.c (download)
Revision 1.7, Fri Jul 29 17:04:42 2005 UTC (18 years, 10 months ago) by xsa
Branch: MAIN
CVS Tags: OPENBSD_3_8_BASE, OPENBSD_3_8 Changes since 1.6: +3 -3 lines
minor KNF;
|
/* $OpenBSD: strtab.c,v 1.7 2005/07/29 17:04:42 xsa Exp $ */
/*
* Copyright (c) 2005 Jean-Francois Brousseau <jfb@openbsd.org>
* All rights reserved.
*
* 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. The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED ``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 AUTHOR 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.
*/
/*
* The hash table code uses the 32-bit Fowler/Noll/Vo (FNV-1) hash algorithm
* for indexing.
* http://www.isthe.com/chongo/tech/comp/fnv/
*/
#include <sys/types.h>
#include <sys/queue.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "cvs.h"
#include "log.h"
#include "strtab.h"
#define CVS_STRTAB_HASHBITS 8
#define CVS_STRTAB_NBUCKETS (1 << CVS_STRTAB_HASHBITS)
#define CVS_STRTAB_FNVPRIME 0x01000193
#define CVS_STRTAB_FNVINIT 0x811c9dc5
struct cvs_str {
char *cs_str;
int cs_ref;
SLIST_ENTRY(cvs_str) cs_link;
};
SLIST_HEAD(cvs_slist, cvs_str);
static struct cvs_slist cvs_strtab[CVS_STRTAB_NBUCKETS];
static struct cvs_str *cvs_strtab_insert(const char *);
static struct cvs_str *cvs_strtab_lookup(const char *);
static u_int32_t cvs_strtab_hash(const char *);
static void cvs_strtab_free(const char *);
/*
* cvs_strdup()
*
* Simple interface to the string table.
*/
char *
cvs_strdup(const char *s)
{
struct cvs_str *csp;
if ((csp = cvs_strtab_lookup(s)) == NULL) {
if ((csp = cvs_strtab_insert(s)) == NULL)
return (NULL);
} else {
csp->cs_ref++;
}
return (csp->cs_str);
}
/*
* cvs_strfree()
*/
void
cvs_strfree(const char *s)
{
cvs_strtab_free(s);
}
/*
*
*/
void
cvs_strtab_init(void)
{
int i;
for (i = 0; i < CVS_STRTAB_NBUCKETS; i++)
SLIST_INIT(&cvs_strtab[i]);
}
/*
* cvs_strtab_cleanup()
*
*/
void
cvs_strtab_cleanup(void)
{
int i, unfreed;
struct cvs_str *sp;
unfreed = 0;
for (i = 0; i < CVS_STRTAB_NBUCKETS; i++) {
SLIST_FOREACH(sp, &cvs_strtab[i], cs_link) {
cvs_log(LP_DEBUG, "string '%s' not freed", sp->cs_str);
unfreed++;
}
}
if (unfreed > 0)
cvs_log(LP_WARN, "%d unfreed string references in string table",
unfreed);
}
/*
* cvs_strtab_insert()
*
* Insert the string <str> in the string table.
*/
static struct cvs_str *
cvs_strtab_insert(const char *str)
{
u_int32_t h;
struct cvs_str *sp;
if ((sp = (struct cvs_str *)malloc(sizeof(*sp))) == NULL) {
cvs_log(LP_ERRNO, "failed to insert string `%s'", str);
return (NULL);
}
if ((sp->cs_str = strdup(str)) == NULL) {
free(sp);
return (NULL);
}
h = cvs_strtab_hash(str);
SLIST_INSERT_HEAD(&cvs_strtab[h], sp, cs_link);
sp->cs_ref = 1;
return (sp);
}
/*
* cvs_strtab_hash()
*
* Generate a hash value from the string <str>.
* The resulting hash value is bitwise AND'ed with the appropriate mask so
* the returned index does not go out of the boundaries of the hash table.
*/
static u_int32_t
cvs_strtab_hash(const char *str)
{
const char *np;
u_int32_t h;
h = CVS_STRTAB_FNVINIT;
for (np = str; *np != '\0'; np++) {
h *= CVS_STRTAB_FNVPRIME;
h ^= (u_int32_t)*np;
}
return (h & (CVS_STRTAB_NBUCKETS - 1));
}
/*
* cvs_strtab_lookup()
*
* Lookup the string <str> in the string table. If the corresponding entry
* is found, a pointer to the string is returned and the entry's reference
* count is increased.
*/
static struct cvs_str *
cvs_strtab_lookup(const char *str)
{
u_int32_t h;
struct cvs_str *sp;
h = cvs_strtab_hash(str);
SLIST_FOREACH(sp, &(cvs_strtab[h]), cs_link)
if (strcmp(str, sp->cs_str) == 0) {
break;
}
return (sp);
}
/*
* cvs_strtab_free()
*
* Release a reference to the string <str>. If the reference count reaches 0,
* the string is removed from the table and freed.
*/
static void
cvs_strtab_free(const char *str)
{
u_int32_t h;
struct cvs_str *sp;
if ((sp = cvs_strtab_lookup(str)) == NULL) {
cvs_log(LP_WARN, "attempt to free unregistered string `%s'",
str);
return;
}
sp->cs_ref--;
if (sp->cs_ref == 0) {
/* no more references, free the file */
h = cvs_strtab_hash(sp->cs_str);
SLIST_REMOVE(&(cvs_strtab[h]), sp, cvs_str, cs_link);
free(sp->cs_str);
free(sp);
}
}