Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/config Make hash capable of taking two key strings.
details: https://anonhg.NetBSD.org/src/rev/b7c8b4db0e96
branches: trunk
changeset: 803069:b7c8b4db0e96
user: uebayasi <uebayasi%NetBSD.org@localhost>
date: Sun Oct 12 05:20:54 2014 +0000
description:
Make hash capable of taking two key strings.
diffstat:
usr.bin/config/defs.h | 8 +++-
usr.bin/config/hash.c | 103 ++++++++++++++++++++++++++++++++++++++++---------
2 files changed, 90 insertions(+), 21 deletions(-)
diffs (247 lines):
diff -r 941a4367a26c -r b7c8b4db0e96 usr.bin/config/defs.h
--- a/usr.bin/config/defs.h Sun Oct 12 04:38:28 2014 +0000
+++ b/usr.bin/config/defs.h Sun Oct 12 05:20:54 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: defs.h,v 1.56 2014/10/11 03:17:40 uebayasi Exp $ */
+/* $NetBSD: defs.h,v 1.57 2014/10/12 05:20:54 uebayasi Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -536,14 +536,20 @@
/* hash.c */
struct hashtab *ht_new(void);
void ht_free(struct hashtab *);
+int ht_insrep2(struct hashtab *, const char *, const char *, void *, int);
int ht_insrep(struct hashtab *, const char *, void *, int);
+#define ht_insert2(ht, nam1, nam2, val) ht_insrep2(ht, nam1, nam2, val, 0)
#define ht_insert(ht, nam, val) ht_insrep(ht, nam, val, 0)
#define ht_replace(ht, nam, val) ht_insrep(ht, nam, val, 1)
+int ht_remove2(struct hashtab *, const char *, const char *);
int ht_remove(struct hashtab *, const char *);
+void *ht_lookup2(struct hashtab *, const char *, const char *);
void *ht_lookup(struct hashtab *, const char *);
void initintern(void);
const char *intern(const char *);
+typedef int (*ht_callback2)(const char *, const char *, void *, void *);
typedef int (*ht_callback)(const char *, void *, void *);
+int ht_enumerate2(struct hashtab *, ht_callback2, void *);
int ht_enumerate(struct hashtab *, ht_callback, void *);
/* typed hash, named struct HT, whose type is string -> struct VT */
diff -r 941a4367a26c -r b7c8b4db0e96 usr.bin/config/hash.c
--- a/usr.bin/config/hash.c Sun Oct 12 04:38:28 2014 +0000
+++ b/usr.bin/config/hash.c Sun Oct 12 05:20:54 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.8 2012/03/12 02:58:55 dholland Exp $ */
+/* $NetBSD: hash.c,v 1.9 2014/10/12 05:20:54 uebayasi Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -58,7 +58,10 @@
struct hashent {
// XXXLUKEM: a SIMPLEQ might be more appropriate
TAILQ_ENTRY(hashent) h_next;
- const char *h_name; /* the string */
+ const char *h_names[2]; /* the string */
+#define h_name1 h_names[0]
+#define h_name2 h_names[1]
+#define h_name h_name1
u_int h_hash; /* its hash value */
void *h_value; /* other values (for name=value) */
};
@@ -81,7 +84,8 @@
static void ht_expand(struct hashtab *);
static void ht_init(struct hashtab *, size_t);
-static inline u_int hash(const char *);
+static inline u_int hash(u_int, const char *);
+static inline u_int hash2(u_int, const char *, const char *);
static inline struct hashent *newhashent(const char *, u_int);
/*
@@ -137,27 +141,51 @@
* otherwise allocate a new entry.
*/
static inline struct hashent *
-newhashent(const char *name, u_int h)
+newhashent2(const char *name1, const char *name2, u_int h)
{
struct hashent *hp;
hp = ecalloc(1, sizeof(*hp));
- hp->h_name = name;
+ hp->h_name1 = name1;
+ hp->h_name2 = name2;
hp->h_hash = h;
return (hp);
}
+static inline struct hashent *
+newhashent(const char *name, u_int h)
+{
+ return newhashent2(name, NULL, h);
+}
+
+static inline u_int
+hv(u_int h, char c)
+{
+ return (h << 5) + h + c;
+}
+
/*
* Hash a string.
*/
static inline u_int
-hash(const char *str)
+hash(u_int h, const char *str)
{
- u_int h;
+
+ while (str && *str)
+ h = hv(h, *str++);
+ return (h);
+}
+
+#define HASH2DELIM ' '
- for (h = 0; *str;)
- h = (h << 5) + h + *str++;
+static inline u_int
+hash2(u_int h, const char *str1, const char *str2)
+{
+
+ h = hash(h, str1);
+ h = hv(h, HASH2DELIM);
+ h = hash(h, str2);
return (h);
}
@@ -182,7 +210,7 @@
char *p;
ht = &strings;
- h = hash(s);
+ h = hash2(0, s, NULL);
hpp = &ht->ht_tab[h & ht->ht_mask];
TAILQ_FOREACH(hp, hpp, h_next) {
if (hp->h_hash == h && strcmp(hp->h_name, s) == 0)
@@ -231,22 +259,23 @@
* Insert and/or replace.
*/
int
-ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
+ht_insrep2(struct hashtab *ht, const char *nam1, const char *nam2, void *val, int replace)
{
struct hashent *hp;
struct hashenthead *hpp;
u_int h;
- h = hash(nam);
+ h = hash2(0, nam1, NULL);
hpp = &ht->ht_tab[h & ht->ht_mask];
TAILQ_FOREACH(hp, hpp, h_next) {
- if (hp->h_name == nam) {
+ if (hp->h_name1 == nam1 &&
+ hp->h_name2 == nam2) {
if (replace)
hp->h_value = val;
return (1);
}
}
- hp = newhashent(nam, h);
+ hp = newhashent2(nam1, nam2, h);
TAILQ_INSERT_TAIL(hpp, hp, h_next);
hp->h_value = val;
if (++ht->ht_used > ht->ht_lim)
@@ -254,21 +283,27 @@
return (0);
}
+int
+ht_insrep(struct hashtab *ht, const char *nam, void *val, int replace)
+{
+ return ht_insrep2(ht, nam, NULL, val, replace);
+}
+
/*
* Remove.
*/
int
-ht_remove(struct hashtab *ht, const char *name)
+ht_remove2(struct hashtab *ht, const char *name1, const char *name2)
{
struct hashent *hp;
struct hashenthead *hpp;
u_int h;
- h = hash(name);
+ h = hash2(0, name1, name2);
hpp = &ht->ht_tab[h & ht->ht_mask];
TAILQ_FOREACH(hp, hpp, h_next) {
- if (hp->h_name != name)
+ if (hp->h_name1 != name1 || hp->h_name2 != name2)
continue;
TAILQ_REMOVE(hpp, hp, h_next);
@@ -279,21 +314,33 @@
return (1);
}
+int
+ht_remove(struct hashtab *ht, const char *name)
+{
+ return ht_remove2(ht, name, NULL);
+}
+
void *
-ht_lookup(struct hashtab *ht, const char *nam)
+ht_lookup2(struct hashtab *ht, const char *nam1, const char *nam2)
{
struct hashent *hp;
struct hashenthead *hpp;
u_int h;
- h = hash(nam);
+ h = hash2(0, nam1, NULL);
hpp = &ht->ht_tab[h & ht->ht_mask];
TAILQ_FOREACH(hp, hpp, h_next)
- if (hp->h_name == nam)
+ if (hp->h_name == nam1)
return (hp->h_value);
return (NULL);
}
+void *
+ht_lookup(struct hashtab *ht, const char *nam)
+{
+ return ht_lookup2(ht, nam, NULL);
+}
+
/*
* first parameter to callback is the entry name from the hash table
* second parameter is the value from the hash table
@@ -301,6 +348,22 @@
*/
int
+ht_enumerate2(struct hashtab *ht, ht_callback2 cbfunc2, void *arg)
+{
+ struct hashent *hp;
+ struct hashenthead *hpp;
+ size_t i;
+ int rval = 0;
+
+ for (i = 0; i < ht->ht_size; i++) {
+ hpp = &ht->ht_tab[i];
+ TAILQ_FOREACH(hp, hpp, h_next)
+ rval += (*cbfunc2)(hp->h_name1, hp->h_name2, hp->h_value, arg);
+ }
+ return rval;
+}
+
+int
ht_enumerate(struct hashtab *ht, ht_callback cbfunc, void *arg)
{
struct hashent *hp;
Home |
Main Index |
Thread Index |
Old Index