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