diff options
| -rw-r--r-- | bootstrap.conf | 4 | ||||
| -rw-r--r-- | lib/Makefile.am | 2 | ||||
| -rw-r--r-- | lib/README | 1 | ||||
| -rw-r--r-- | lib/glcontainers.h | 11 | ||||
| -rw-r--r-- | lib/hashtable.c | 232 | ||||
| -rw-r--r-- | lib/hashtable.h | 61 | ||||
| -rw-r--r-- | lib/orderfiles.c | 25 | ||||
| -rw-r--r-- | libdb/db_btree.c | 26 | ||||
| -rw-r--r-- | libdb/db_gdbm.c | 177 | ||||
| -rw-r--r-- | src/check_mandirs.c | 37 | ||||
| -rw-r--r-- | src/globbing.c | 39 | ||||
| -rw-r--r-- | src/man.c | 49 | ||||
| -rw-r--r-- | src/mandb.c | 46 | ||||
| -rw-r--r-- | src/whatis.c | 14 |
14 files changed, 220 insertions, 504 deletions
diff --git a/bootstrap.conf b/bootstrap.conf index 27747b55..a86cb762 100644 --- a/bootstrap.conf +++ b/bootstrap.conf @@ -38,7 +38,9 @@ gnulib_modules=" gitlog-to-changelog glob gnupload + hash-map hash-pjw-bare + hash-set idpriv-drop idpriv-droptemp lchown @@ -74,6 +76,8 @@ gnulib_modules=" xalloc xgetcwd xlist + xmap + xset xstdopen xstrndup xvasprintf diff --git a/lib/Makefile.am b/lib/Makefile.am index d8be3716..731bd331 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -43,8 +43,6 @@ libman_la_SOURCES = \ encodings.h \ glcontainers.c \ glcontainers.h \ - hashtable.c \ - hashtable.h \ linelength.c \ linelength.h \ lower.c \ @@ -10,7 +10,6 @@ cleanup.* author - Markus Armbruster, Colin Watson debug.c author - Colin Watson decompress.* author - Colin Watson encodings.* author - Colin Watson -hashtable.* author - Wilf., Colin Watson linelength.* author - Martin Schulze, Jon Tombs, Colin Watson lower.* author - Wilf., Colin Watson pathsearch.* author - Colin Watson diff --git a/lib/glcontainers.h b/lib/glcontainers.h index 482a99d3..3e2917fa 100644 --- a/lib/glcontainers.h +++ b/lib/glcontainers.h @@ -44,4 +44,15 @@ void plain_free (const void *s); gl_list_iterator_free (&list##_iter); \ } while (0) +#define GL_MAP_FOREACH_START(map, key, value) \ + do { \ + gl_map_iterator_t map##_iter = gl_map_iterator (map); \ + while (gl_map_iterator_next (&map##_iter, \ + (const void **) &key, \ + (const void **) &value)) + +#define GL_MAP_FOREACH_END(map) \ + gl_map_iterator_free (&map##_iter); \ + } while (0) + #endif /* MAN_GLCONTAINERS_H */ diff --git a/lib/hashtable.c b/lib/hashtable.c deleted file mode 100644 index 85fbb04d..00000000 --- a/lib/hashtable.c +++ /dev/null @@ -1,232 +0,0 @@ -/* - * hashtable.c: in core hash table routines. - * - * Copyright (C) 1994, 1995 Graeme W. Wilford. (Wilf.) - * Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009 Colin Watson. - * - * This file is part of man-db. - * - * man-db is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * man-db is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with man-db; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - * All of these routines except hashtable_free() can be found in K&R II. - * - * Sat Aug 20 15:01:02 BST 1994 Wilf. (G.Wilford@ee.surrey.ac.uk) - */ - -/* which hash function do we want ? */ -/* #define PROLOGUE */ -#define KRII - -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif /* HAVE_CONFIG_H */ - -#include <string.h> -#include <stdlib.h> - -#include "manconfig.h" -#include "hashtable.h" - -#if defined(PROLOGUE) -#define HASHSIZE 2048 -#elif defined(KRII) -#define HASHSIZE 2001 -#else -#error hash function not defined -#endif - -/* Return hash value for string. */ -static unsigned int hash (const char *s, size_t len) -{ - unsigned int hashval = 0; - size_t i; - - for (i = 0; i < len && s[i]; ++i) -#if defined(KRII) - hashval = s[i] + 31 * hashval; - return hashval % HASHSIZE; -#elif defined(PROLOGUE) - hashval = (hashval << 1) + s[i]; - return hashval & (HASHSIZE - 1); -#endif -} - -void null_hashtable_free (void *defn ATTRIBUTE_UNUSED) -{ -} - -/* Create a hashtable. */ -struct hashtable *hashtable_create (hashtable_free_ptr free_defn) -{ - struct hashtable *ht = XMALLOC (struct hashtable); - ht->hashtab = XCALLOC (HASHSIZE, struct nlist *); - ht->unique = 0; - ht->identical = 0; - ht->free_defn = free_defn; - return ht; -} - -/* Return pointer to hash entry structure containing s, or NULL if it - * doesn't exist. - */ -struct nlist *hashtable_lookup_structure (const struct hashtable *ht, - const char *s, size_t len) -{ - struct nlist *np; - - for (np = ht->hashtab[hash (s, len)]; np; np = np->next) { - if (strncmp (s, np->name, len) == 0) - return np; - } - return NULL; -} - -/* Return pointer to definition of s, or NULL if it doesn't exist. */ -void *hashtable_lookup (const struct hashtable *ht, const char *s, size_t len) -{ - struct nlist *np = hashtable_lookup_structure (ht, s, len); - if (np) - return np->defn; - else - return NULL; -} - -/* Return structure containing definition (never NULL). */ -struct nlist *hashtable_install (struct hashtable *ht, - const char *name, size_t len, void *defn) -{ - struct nlist *np; - - np = hashtable_lookup_structure (ht, name, len); - if (np) { - if (np->defn) - ht->free_defn (np->defn); - } else { - unsigned int hashval; - - np = XMALLOC (struct nlist); - np->name = xstrndup (name, len); - hashval = hash (name, len); - - /* record uniqueness if debugging */ - if (debug_level) { - if (ht->hashtab[hashval]) - ht->identical++; - else - ht->unique++; - } - - /* point to last entry with this hash */ - np->next = ht->hashtab[hashval]; - - /* attach to hashtab array */ - ht->hashtab[hashval] = np; - } - - np->defn = defn; - - return np; -} - -/* Remove structure containing name from the hash tree. */ -void hashtable_remove (struct hashtable *ht, const char *name, size_t len) -{ - struct nlist *np, *prev; - unsigned int hashval = hash (name, len); - - for (np = ht->hashtab[hashval], prev = NULL; np; - prev = np, np = np->next) { - if (strncmp (name, np->name, len) == 0) { - if (prev) - prev->next = np->next; - else - ht->hashtab[hashval] = np->next; - if (np->defn) - ht->free_defn (np->defn); - free (np->name); - free (np); - return; - } - } -} - -struct hashtable_iter { - struct nlist **bucket; - struct nlist *np; -}; - -/* Iterate over hash. Do not modify hash while iterating. */ -struct nlist *hashtable_iterate (const struct hashtable *ht, - struct hashtable_iter **iterp) -{ - struct hashtable_iter *iter = *iterp; - - if (!iter) - *iterp = iter = XZALLOC (struct hashtable_iter); - - if (iter->np && iter->np->next) - return iter->np = iter->np->next; - - if (iter->bucket) - ++iter->bucket; - else - iter->bucket = ht->hashtab; - - while (iter->bucket < ht->hashtab + HASHSIZE) { - if (*iter->bucket) - return iter->np = *iter->bucket; - ++iter->bucket; - } - - free (iter); - *iterp = NULL; - return NULL; -} - -/* Free up the hash tree (garbage collection). Also call the free_defn() - * hook to free up values if necessary. - */ -void hashtable_free (struct hashtable *ht) -{ - int i; - - if (!ht) - return; - - debug ("hashtable_free: %d entries, %d (%d%%) unique\n", - ht->unique + ht->identical, - ht->unique, - ht->unique ? (ht->unique * 100) / (ht->unique + ht->identical) - : 0); - - for (i = 0; i < HASHSIZE; i++) { - struct nlist *np; - - np = ht->hashtab[i]; - while (np) { - struct nlist *next; - - if (np->defn) - ht->free_defn (np->defn); - free (np->name); - next = np->next; - free (np); - np = next; - } - } - - free (ht->hashtab); - free (ht); -} diff --git a/lib/hashtable.h b/lib/hashtable.h deleted file mode 100644 index 3924518c..00000000 --- a/lib/hashtable.h +++ /dev/null @@ -1,61 +0,0 @@ -/* - * hashtable.h: contains struct nlist - * - * Copyright (C) 1994, 1995 Graeme W. Wilford. (Wilf.) - * Copyright (C) 2002, 2003, 2004, 2005, 2007, 2009 Colin Watson. - * - * This file is part of man-db. - * - * man-db is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * man-db is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with man-db; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - * Sat Aug 20 15:01:02 BST 1994 Wilf. (G.Wilford@ee.surrey.ac.uk) - */ - -#ifndef _HASHTABLE_H -#define _HASHTABLE_H - -typedef void (*hashtable_free_ptr) (void *defn); - -struct hashtable { - struct nlist **hashtab; /* the storage array */ - int unique; /* unique hash values */ - int identical; /* identical hash values */ - hashtable_free_ptr free_defn; /* function to free a hash entry */ -}; - -struct nlist { - struct nlist *next; /* next in the chain */ - char *name; /* the _name_ */ - void *defn; /* the _definition_ */ -}; - -struct hashtable_iter; - -extern void null_hashtable_free (void *defn); - -extern struct hashtable *hashtable_create (hashtable_free_ptr free_defn); -extern struct nlist *hashtable_lookup_structure (const struct hashtable *ht, - const char *s, size_t len); -extern void *hashtable_lookup (const struct hashtable *ht, - const char *s, size_t len); -extern struct nlist *hashtable_install (struct hashtable *ht, - const char *name, size_t len, - void *defn); -extern struct nlist *hashtable_iterate (const struct hashtable *ht, - struct hashtable_iter **iterp); -extern void hashtable_remove (struct hashtable *ht, const char *s, size_t len); -extern void hashtable_free (struct hashtable *ht); - -#endif /* _HASHTABLE_H */ diff --git a/lib/orderfiles.c b/lib/orderfiles.c index a7c84ac5..e51a1dca 100644 --- a/lib/orderfiles.c +++ b/lib/orderfiles.c @@ -44,25 +44,24 @@ #include <string.h> #include <unistd.h> +#include "gl_hash_map.h" #include "gl_rbtree_list.h" #include "gl_xlist.h" +#include "gl_xmap.h" #include "manconfig.h" #include "glcontainers.h" -#include "hashtable.h" - -struct hashtable *physical_offsets = NULL; #if defined(HAVE_LINUX_FIEMAP_H) +gl_map_t physical_offsets = NULL; + int compare_physical_offsets (const void *a, const void *b) { const char *left = (const char *) a; const char *right = (const char *) b; - uint64_t *left_offset_p = hashtable_lookup (physical_offsets, - left, strlen (left)); - uint64_t *right_offset_p = hashtable_lookup (physical_offsets, - right, strlen (right)); + const uint64_t *left_offset_p = gl_map_get (physical_offsets, left); + const uint64_t *right_offset_p = gl_map_get (physical_offsets, right); uint64_t left_offset = left_offset_p ? *left_offset_p : UINT64_MAX; uint64_t right_offset = right_offset_p ? *right_offset_p : UINT64_MAX; @@ -101,7 +100,8 @@ void order_files (const char *dir, gl_list_t *basenamesp) * a small number of contiguous blocks, which seems a reasonable * assumption for manual pages. */ - physical_offsets = hashtable_create (&free); + physical_offsets = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, NULL, plain_free); sorted_basenames = gl_list_create_empty (GL_RBTREE_LIST, string_equals, string_hash, plain_free, false); @@ -125,15 +125,18 @@ void order_files (const char *dir, gl_list_t *basenamesp) if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) &fm) == 0) { uint64_t *offset = XMALLOC (uint64_t); *offset = fm.fiemap.fm_extents[0].fe_physical; - hashtable_install (physical_offsets, name, - strlen (name), offset); + /* Borrow the key from basenames; since + * physical_offsets has a shorter lifetime, we don't + * need to duplicate it. + */ + gl_map_put (physical_offsets, name, offset); } close (fd); gl_sortedlist_add (sorted_basenames, compare_physical_offsets, xstrdup (name)); } GL_LIST_FOREACH_END (basenames); - hashtable_free (physical_offsets); + gl_map_free (physical_offsets); physical_offsets = NULL; close (dir_fd); gl_list_free (basenames); diff --git a/libdb/db_btree.c b/libdb/db_btree.c index f1de4078..c72c7b4d 100644 --- a/libdb/db_btree.c +++ b/libdb/db_btree.c @@ -39,18 +39,20 @@ #include <sys/types.h> /* for open() */ #include <sys/stat.h> +#include "gl_hash_set.h" +#include "gl_xset.h" #include "stat-time.h" #include "timespec.h" #include "manconfig.h" #include "error.h" -#include "hashtable.h" +#include "glcontainers.h" #include "mydbm.h" #include "db_storage.h" -struct hashtable *loop_check_hash; +gl_set_t loop_check; /* the Berkeley database libraries do nothing to arbitrate between concurrent database accesses, so we do a simple flock(). If the db is opened in @@ -178,26 +180,28 @@ int btree_exists (DB *db, datum key) static datum btree_findkey (DB *db, u_int flags) { datum key, data; + char *loop_check_key; memset (&key, 0, sizeof key); memset (&data, 0, sizeof data); if (flags == R_FIRST) { - if (loop_check_hash) { - hashtable_free (loop_check_hash); - loop_check_hash = NULL; + if (loop_check) { + gl_set_free (loop_check); + loop_check = NULL; } } - if (!loop_check_hash) - loop_check_hash = hashtable_create (&free); + if (!loop_check) + loop_check = gl_set_create_empty (GL_HASH_SET, string_equals, + string_hash, plain_free); if (((db->seq) (db, (DBT *) &key, (DBT *) &data, flags))) { memset (&key, 0, sizeof key); return key; } - if (hashtable_lookup (loop_check_hash, - MYDBM_DPTR (key), MYDBM_DSIZE (key))) { + loop_check_key = xstrndup (MYDBM_DPTR (key), MYDBM_DSIZE (key)); + if (gl_set_search (loop_check, loop_check_key)) { /* We've seen this key already, which is broken. Return NULL * so the caller doesn't go round in circles. */ @@ -205,11 +209,11 @@ static datum btree_findkey (DB *db, u_int flags) "Attempting to recover ...\n", (int) MYDBM_DSIZE (key), MYDBM_DPTR (key)); memset (&key, 0, sizeof key); + free (loop_check_key); return key; } - hashtable_install (loop_check_hash, - MYDBM_DPTR (key), MYDBM_DSIZE (key), NULL); + gl_set_add (loop_check, loop_check_key); return copy_datum (key); } diff --git a/libdb/db_gdbm.c b/libdb/db_gdbm.c index f3aaa94e..650f16f4 100644 --- a/libdb/db_gdbm.c +++ b/libdb/db_gdbm.c @@ -34,22 +34,22 @@ #include <sys/stat.h> #include <unistd.h> +#include "gl_hash_map.h" +#include "gl_rbtree_list.h" +#include "gl_xlist.h" +#include "gl_xmap.h" +#include "hash-pjw-bare.h" #include "stat-time.h" #include "timespec.h" #include "manconfig.h" -#include "hashtable.h" #include "cleanup.h" +#include "glcontainers.h" #include "mydbm.h" -static struct hashtable *parent_sortkey_hash; - -struct sortkey { - datum key; - struct sortkey *next; -}; +static gl_map_t parent_keys; /* setjmp/longjmp handling to defend against _gdbm_fatal exiting under our * feet. Not thread-safe, but there is no plan for man-db to ever use @@ -103,129 +103,112 @@ man_gdbm_wrapper man_gdbm_open_wrapper (const char *name, int flags) return wrap; } -static void parent_sortkey_hashtable_free (void *defn) -{ - /* Automatically free child hashtables on removal. */ - hashtable_free ((struct hashtable *) defn); -} - -static void sortkey_hashtable_free (void *defn) +static int datum_compare (const void *a, const void *b) { - struct sortkey *key = (struct sortkey *) defn; - MYDBM_FREE_DPTR (key->key); - free (key); -} - -static int sortkey_compare (const void *a, const void *b) -{ - const struct sortkey **left = (const struct sortkey **) a; - const struct sortkey **right = (const struct sortkey **) b; + const datum *left = (const datum *) a; + const datum *right = (const datum *) b; int cmp; size_t minsize; /* Sentinel NULL elements sort to the end. */ - if (!MYDBM_DPTR ((*left)->key)) + if (!MYDBM_DPTR (*left)) return 1; - else if (!MYDBM_DPTR ((*right)->key)) + else if (!MYDBM_DPTR (*right)) return -1; - if (MYDBM_DSIZE ((*left)->key) < MYDBM_DSIZE ((*right)->key)) - minsize = MYDBM_DSIZE ((*left)->key); + if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right)) + minsize = MYDBM_DSIZE (*left); else - minsize = MYDBM_DSIZE ((*right)->key); - cmp = strncmp (MYDBM_DPTR ((*left)->key), MYDBM_DPTR ((*right)->key), - minsize); + minsize = MYDBM_DSIZE (*right); + cmp = strncmp (MYDBM_DPTR (*left), MYDBM_DPTR (*right), minsize); if (cmp) return cmp; - else if (MYDBM_DSIZE ((*left)->key) < MYDBM_DSIZE ((*right)->key)) + else if (MYDBM_DSIZE (*left) < MYDBM_DSIZE (*right)) return 1; - else if (MYDBM_DSIZE ((*left)->key) > MYDBM_DSIZE ((*right)->key)) + else if (MYDBM_DSIZE (*left) > MYDBM_DSIZE (*right)) return -1; else return 0; } +static bool datum_equals (const void *a, const void *b) +{ + return datum_compare (a, b) == 0; +} + +static size_t datum_hash (const void *value) +{ + const datum *d = value; + return hash_pjw_bare (MYDBM_DPTR (*d), MYDBM_DSIZE (*d)); +} + +static void datum_free (const void *value) +{ + MYDBM_FREE_DPTR (*(datum *) value); +} + static datum empty_datum = { NULL, 0 }; -/* We keep a hashtable of filenames to sorted lists of keys. Each list is - * stored both with links from each element to the next and in a hashtable, - * so that both sequential access and random access are quick. This is - * necessary for a reasonable ordered implementation of nextkey. +/* We keep a map of filenames to sorted lists of keys. Each list is stored + * using a hash-based implementation that allows lookup by name and + * traversal to the next item in O(log n) time, which is necessary for a + * reasonable ordered implementation of nextkey. */ datum man_gdbm_firstkey (man_gdbm_wrapper wrap) { - struct hashtable *sortkey_hash; - struct sortkey **keys, *firstkey; - int numkeys = 0, maxkeys = 256; - int i; - - /* Build the raw list of keys and sort it. */ - keys = xnmalloc (maxkeys, sizeof *keys); - keys[0] = xmalloc (sizeof **keys); - keys[0]->key = gdbm_firstkey (wrap->file); - while (MYDBM_DPTR (keys[numkeys]->key)) { - if (++numkeys >= maxkeys) { - maxkeys *= 2; - keys = xnrealloc (keys, maxkeys, sizeof *keys); - } - keys[numkeys] = xmalloc (sizeof **keys); - keys[numkeys]->key = - gdbm_nextkey (wrap->file, keys[numkeys - 1]->key); + gl_list_t keys; + datum *key; + + /* Build the raw sorted list of keys. */ + keys = gl_list_create_empty (GL_RBTREE_LIST, datum_equals, datum_hash, + datum_free, false); + key = XMALLOC (datum); + *key = gdbm_firstkey (wrap->file); + while (MYDBM_DPTR (*key)) { + datum *next; + + gl_sortedlist_add (keys, datum_compare, key); + next = XMALLOC (datum); + *next = gdbm_nextkey (wrap->file, *key); + key = next; } - free (keys[numkeys]); - keys[numkeys] = NULL; /* simplifies the empty case */ - qsort (keys, numkeys, sizeof *keys, &sortkey_compare); - - /* Link the elements together and insert them into a hash. */ - sortkey_hash = hashtable_create (&sortkey_hashtable_free); - for (i = 0; i < numkeys; ++i) { - if (i < numkeys - 1) - keys[i]->next = keys[i + 1]; - else - keys[i]->next = NULL; - hashtable_install (sortkey_hash, - MYDBM_DPTR (keys[i]->key), - MYDBM_DSIZE (keys[i]->key), - keys[i]); - } - firstkey = keys[0]; - free (keys); /* element memory now owned by hashtable */ - - if (!parent_sortkey_hash) { - parent_sortkey_hash = hashtable_create - (&parent_sortkey_hashtable_free); - push_cleanup ((cleanup_fun) hashtable_free, - parent_sortkey_hash, 0); + + if (!parent_keys) { + parent_keys = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, plain_free, + (gl_listelement_dispose_fn) + gl_list_free); + push_cleanup ((cleanup_fun) gl_map_free, parent_keys, 0); } /* Remember this structure for use by nextkey. */ - hashtable_install (parent_sortkey_hash, - wrap->name, strlen (wrap->name), sortkey_hash); + gl_map_put (parent_keys, xstrdup (wrap->name), keys); - if (firstkey) - return copy_datum (firstkey->key); + if (gl_list_size (keys)) + return copy_datum (*(datum *) gl_list_get_at (keys, 0)); else - return empty_datum; /* dptr is NULL, so no copy needed */ + return empty_datum; } datum man_gdbm_nextkey (man_gdbm_wrapper wrap, datum key) { - struct hashtable *sortkey_hash; - struct sortkey *sortkey; + gl_list_t keys; + gl_list_node_t node, next_node; - if (!parent_sortkey_hash) + if (!parent_keys) return empty_datum; - sortkey_hash = hashtable_lookup (parent_sortkey_hash, - wrap->name, strlen (wrap->name)); - if (!sortkey_hash) + keys = (gl_list_t) gl_map_get (parent_keys, wrap->name); + if (!keys) return empty_datum; - sortkey = hashtable_lookup (sortkey_hash, - MYDBM_DPTR (key), MYDBM_DSIZE (key)); - if (!sortkey || !sortkey->next) + node = gl_sortedlist_search (keys, datum_compare, &key); + if (!node) + return empty_datum; + next_node = gl_list_next_node (keys, node); + if (!next_node) return empty_datum; - return copy_datum (sortkey->next->key); + return copy_datum (*(datum *) gl_list_node_value (keys, next_node)); } struct timespec man_gdbm_get_time (man_gdbm_wrapper wrap) @@ -255,14 +238,8 @@ void man_gdbm_close (man_gdbm_wrapper wrap) if (!wrap) return; - if (parent_sortkey_hash) { - struct hashtable *sortkey_hash = - hashtable_lookup (parent_sortkey_hash, - wrap->name, strlen (wrap->name)); - if (sortkey_hash) - hashtable_remove (parent_sortkey_hash, - wrap->name, strlen (wrap->name)); - } + if (parent_keys) + gl_map_remove (parent_keys, wrap->name); free (wrap->name); gdbm_close (wrap->file); diff --git a/src/check_mandirs.c b/src/check_mandirs.c index 58dc64cc..7c0708b1 100644 --- a/src/check_mandirs.c +++ b/src/check_mandirs.c @@ -45,7 +45,9 @@ #include "dirname.h" #include "gl_array_list.h" +#include "gl_hash_map.h" #include "gl_xlist.h" +#include "gl_xmap.h" #include "stat-time.h" #include "timespec.h" #include "xvasprintf.h" @@ -57,7 +59,6 @@ #include "error.h" #include "glcontainers.h" -#include "hashtable.h" #include "orderfiles.h" #include "security.h" @@ -75,20 +76,20 @@ int opt_test; /* don't update db */ int pages; int force_rescan = 0; -static struct hashtable *whatis_hash = NULL; +gl_map_t whatis_map = NULL; -struct whatis_hashent { +struct whatis { char *whatis; gl_list_t trace; }; -static void whatis_hashtable_free (void *defn) +static void whatis_free (const void *value) { - struct whatis_hashent *hashent = defn; + struct whatis *whatis = (struct whatis *) value; - free (hashent->whatis); - gl_list_free (hashent->trace); - free (hashent); + free (whatis->whatis); + gl_list_free (whatis->trace); + free (whatis); } static void gripe_multi_extensions (const char *path, const char *sec, @@ -131,7 +132,7 @@ void test_manfile (MYDBM_FILE dbf, const char *file, const char *path) struct stat buf; size_t len; gl_list_t ult_trace = NULL; - struct whatis_hashent *whatis; + const struct whatis *whatis; memset (&lg, 0, sizeof (struct lexgrog)); memset (&info, 0, sizeof (struct mandata)); @@ -217,10 +218,12 @@ void test_manfile (MYDBM_FILE dbf, const char *file, const char *path) return; } - if (!whatis_hash) - whatis_hash = hashtable_create (&whatis_hashtable_free); + if (!whatis_map) + whatis_map = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, plain_free, + whatis_free); - whatis = hashtable_lookup (whatis_hash, ult, strlen (ult)); + whatis = gl_map_get (whatis_map, ult); if (!whatis) { if (!STRNEQ (ult, file, len)) debug ("\ntest_manfile(): link not in cache:\n" @@ -266,6 +269,7 @@ void test_manfile (MYDBM_FILE dbf, const char *file, const char *path) else { /* Cache miss; go and get the whatis info in its raw state. */ char *file_base = base_name (file); + struct whatis *new_whatis; lg.type = MANPAGE; drop_effective_privs (); @@ -273,11 +277,12 @@ void test_manfile (MYDBM_FILE dbf, const char *file, const char *path) free (file_base); regain_effective_privs (); - whatis = XMALLOC (struct whatis_hashent); - whatis->whatis = lg.whatis ? xstrdup (lg.whatis) : NULL; + new_whatis = XMALLOC (struct whatis); + new_whatis->whatis = lg.whatis ? xstrdup (lg.whatis) : NULL; /* We filled out ult_trace above. */ - whatis->trace = ult_trace; - hashtable_install (whatis_hash, ult, strlen (ult), whatis); + new_whatis->trace = ult_trace; + gl_map_put (whatis_map, xstrdup (ult), new_whatis); + whatis = new_whatis; } debug ("\"%s\"\n", lg.whatis); diff --git a/src/globbing.c b/src/globbing.c index 0c9a9ced..93df7ca1 100644 --- a/src/globbing.c +++ b/src/globbing.c @@ -37,7 +37,9 @@ #include "fnmatch.h" #include "gl_array_list.h" +#include "gl_hash_map.h" #include "gl_xlist.h" +#include "gl_xmap.h" #include "regex.h" #include "xvasprintf.h" @@ -45,7 +47,6 @@ #include "error.h" #include "glcontainers.h" -#include "hashtable.h" #include "cleanup.h" #include "xregcomp.h" @@ -113,23 +114,23 @@ static int parse_layout (const char *layout) } } -struct dirent_hashent { +struct dirent_names { char **names; size_t names_len, names_max; }; -static void dirent_hashtable_free (void *defn) +static void dirent_names_free (const void *value) { - struct dirent_hashent *hashent = defn; + struct dirent_names *cache = (struct dirent_names *) value; size_t i; - for (i = 0; i < hashent->names_len; ++i) - free (hashent->names[i]); - free (hashent->names); - free (hashent); + for (i = 0; i < cache->names_len; ++i) + free (cache->names[i]); + free (cache->names); + free (cache); } -static struct hashtable *dirent_hash = NULL; +static gl_map_t dirent_map = NULL; static int cache_compare (const void *a, const void *b) { @@ -138,17 +139,19 @@ static int cache_compare (const void *a, const void *b) return strcasecmp (left, right); } -static struct dirent_hashent *update_directory_cache (const char *path) +static struct dirent_names *update_directory_cache (const char *path) { - struct dirent_hashent *cache; + struct dirent_names *cache; DIR *dir; struct dirent *entry; - if (!dirent_hash) { - dirent_hash = hashtable_create (&dirent_hashtable_free); - push_cleanup ((cleanup_fun) hashtable_free, dirent_hash, 0); + if (!dirent_map) { + dirent_map = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, plain_free, + dirent_names_free); + push_cleanup ((cleanup_fun) gl_map_free, dirent_map, 0); } - cache = hashtable_lookup (dirent_hash, path, strlen (path)); + cache = (struct dirent_names *) gl_map_get (dirent_map, path); /* Check whether we've got this one already. */ if (cache) { @@ -164,7 +167,7 @@ static struct dirent_hashent *update_directory_cache (const char *path) return NULL; } - cache = XMALLOC (struct dirent_hashent); + cache = XMALLOC (struct dirent_names); cache->names_len = 0; cache->names_max = 1024; cache->names = XNMALLOC (cache->names_max, char *); @@ -183,7 +186,7 @@ static struct dirent_hashent *update_directory_cache (const char *path) qsort (cache->names, cache->names_len, sizeof *cache->names, &cache_compare); - hashtable_install (dirent_hash, path, strlen (path), cache); + gl_map_put (dirent_map, xstrdup (path), cache); closedir (dir); return cache; @@ -204,7 +207,7 @@ static int pattern_compare (const void *a, const void *b) static void match_in_directory (const char *path, const char *pattern, int opts, gl_list_t matched) { - struct dirent_hashent *cache; + struct dirent_names *cache; int flags; regex_t preg; struct pattern_bsearch pattern_start = { NULL, -1 }; @@ -60,8 +60,10 @@ #include "argp.h" #include "dirname.h" #include "gl_array_list.h" +#include "gl_hash_map.h" #include "gl_list.h" #include "gl_xlist.h" +#include "gl_xmap.h" #include "minmax.h" #include "progname.h" #include "regex.h" @@ -81,7 +83,6 @@ #include "error.h" #include "cleanup.h" #include "glcontainers.h" -#include "hashtable.h" #include "pipeline.h" #include "pathsearch.h" #include "linelength.h" @@ -203,7 +204,7 @@ static char *less; static const char *std_sections[] = STD_SECTIONS; static char *manp; static const char *external; -static struct hashtable *db_hash = NULL; +static gl_map_t db_map = NULL; static int troff; static const char *roff_device = NULL; @@ -3314,11 +3315,6 @@ static int display_database_check (struct candidate *candp) return exists; } -static void db_hashtable_free (void *defn) -{ - free_mandata_struct (defn); -} - #ifdef MAN_DB_UPDATES static int maybe_update_file (const char *manpath, const char *name, struct mandata *info) @@ -3399,11 +3395,14 @@ static int try_db (const char *manpath, const char *sec, const char *name, } else database = mkdbname (manpath); - if (!db_hash) - db_hash = hashtable_create (&db_hashtable_free); + if (!db_map) + db_map = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, plain_free, + (gl_mapvalue_dispose_fn) + free_mandata_struct); /* Have we looked here already? */ - data = hashtable_lookup (db_hash, manpath, strlen (manpath)); + data = (struct mandata *) gl_map_get (db_map, manpath); if (!data) { MYDBM_FILE dbf; @@ -3425,8 +3424,7 @@ static int try_db (const char *manpath, const char *sec, const char *name, else data = dblookup_all (dbf, name, section, match_case); - hashtable_install (db_hash, manpath, strlen (manpath), - data); + gl_map_put (db_map, xstrdup (manpath), data); MYDBM_CLOSE (dbf); dbf = NULL; #ifdef MAN_DB_CREATES @@ -3437,9 +3435,7 @@ static int try_db (const char *manpath, const char *sec, const char *name, data = infoalloc (); data->next = NULL; data->addr = NULL; - hashtable_install (db_hash, - manpath, strlen (manpath), - data); + gl_map_put (db_map, xstrdup (manpath), data); return TRY_DATABASE_OPEN_FAILED; } return TRY_DATABASE_CREATED; @@ -3449,8 +3445,7 @@ static int try_db (const char *manpath, const char *sec, const char *name, data = infoalloc (); data->next = (struct mandata *) NULL; data->addr = NULL; - hashtable_install (db_hash, manpath, strlen (manpath), - data); + gl_map_put (db_map, xstrdup (manpath), data); return TRY_DATABASE_OPEN_FAILED; } } @@ -3475,7 +3470,7 @@ static int try_db (const char *manpath, const char *sec, const char *name, found_stale = 1; if (found_stale) { - hashtable_remove (db_hash, manpath, strlen (manpath)); + gl_map_remove (db_map, manpath); return TRY_DATABASE_UPDATED; } #endif /* MAN_DB_UPDATES */ @@ -4274,8 +4269,10 @@ int main (int argc, char *argv[]) } /* clean out the cache of database lookups for each man page */ - hashtable_free (db_hash); - db_hash = NULL; + if (db_map) { + gl_map_free (db_map); + db_map = NULL; + } if (section && maybe_section) { if (status != OK && !catman) { @@ -4299,8 +4296,10 @@ int main (int argc, char *argv[]) } if (!found_subpage) status = man (tmp, &found); - hashtable_free (db_hash); - db_hash = NULL; + if (db_map) { + gl_map_free (db_map); + db_map = NULL; + } /* ... but don't gripe about it if it doesn't * work! */ @@ -4345,8 +4344,10 @@ int main (int argc, char *argv[]) chkr_garbage_detector (); } - hashtable_free (db_hash); - db_hash = NULL; + if (db_map) { + gl_map_free (db_map); + db_map = NULL; + } drop_effective_privs (); diff --git a/src/mandb.c b/src/mandb.c index f4fc0652..a256ebae 100644 --- a/src/mandb.c +++ b/src/mandb.c @@ -49,7 +49,9 @@ #include "argp.h" #include "dirname.h" +#include "gl_hash_map.h" #include "gl_list.h" +#include "gl_xmap.h" #include "progname.h" #include "stat-time.h" #include "timespec.h" @@ -66,7 +68,6 @@ #include "error.h" #include "cleanup.h" #include "glcontainers.h" -#include "hashtable.h" #include "pipeline.h" #include "sandbox.h" #include "security.h" @@ -556,7 +557,7 @@ static int mandb (struct dbpaths *dbpaths, } static int process_manpath (const char *manpath, bool global_manpath, - struct hashtable *tried_catdirs) + gl_map_t tried_catdirs) { char *catpath; struct tried_catdirs_entry *tried; @@ -576,7 +577,7 @@ static int process_manpath (const char *manpath, bool global_manpath, tried = XMALLOC (struct tried_catdirs_entry); tried->manpath = xstrdup (manpath); tried->seen = 0; - hashtable_install (tried_catdirs, catpath, strlen (catpath), tried); + gl_map_put (tried_catdirs, xstrdup (catpath), tried); if (stat (manpath, &st) < 0 || !S_ISDIR (st.st_mode)) goto out; @@ -652,21 +653,21 @@ static int is_lang_dir (const char *base) (!base[2] || base[2] < 'a' || base[2] > 'z'); } -static void tried_catdirs_free (void *defn) +static void tried_catdirs_free (const void *value) { - struct tried_catdirs_entry *tried = defn; + struct tried_catdirs_entry *tried = + (struct tried_catdirs_entry *) value; free (tried->manpath); free (tried); } -static void purge_catdir (const struct hashtable *tried_catdirs, - const char *path) +static void purge_catdir (gl_map_t tried_catdirs, const char *path) { struct stat st; if (stat (path, &st) == 0 && S_ISDIR (st.st_mode) && - !hashtable_lookup (tried_catdirs, path, strlen (path))) { + !gl_map_get (tried_catdirs, path)) { if (!quiet) printf (_("Removing obsolete cat directory %s...\n"), path); @@ -718,14 +719,12 @@ static void purge_catsubdirs (const char *manpath, const char *catpath) * the usual NLS pattern (two lower-case letters followed by nothing or a * non-letter). */ -static void purge_catdirs (const struct hashtable *tried_catdirs) +static void purge_catdirs (gl_map_t tried_catdirs) { - struct hashtable_iter *iter = NULL; - const struct nlist *elt; + const char *path; + struct tried_catdirs_entry *tried; - while ((elt = hashtable_iterate (tried_catdirs, &iter)) != NULL) { - const char *path = elt->name; - struct tried_catdirs_entry *tried = elt->defn; + GL_MAP_FOREACH_START (tried_catdirs, path, tried) { char *base; DIR *dir; struct dirent *subdirent; @@ -745,6 +744,7 @@ static void purge_catdirs (const struct hashtable *tried_catdirs) continue; while ((subdirent = readdir (dir)) != NULL) { char *subdirpath; + const struct tried_catdirs_entry *subtried; if (STREQ (subdirent->d_name, ".") || STREQ (subdirent->d_name, "..")) @@ -757,22 +757,22 @@ static void purge_catdirs (const struct hashtable *tried_catdirs) subdirpath = xasprintf ("%s/%s", path, subdirent->d_name); - tried = hashtable_lookup (tried_catdirs, subdirpath, - strlen (subdirpath)); - if (tried && tried->seen) { + subtried = gl_map_get (tried_catdirs, subdirpath); + if (subtried && subtried->seen) { debug ("Seen mandir for %s; not deleting\n", subdirpath); /* However, we may still need to purge cat* * subdirectories. */ - purge_catsubdirs (tried->manpath, subdirpath); + purge_catsubdirs (subtried->manpath, + subdirpath); } else purge_catdir (tried_catdirs, subdirpath); free (subdirpath); } closedir (dir); - } + } GL_MAP_FOREACH_END (tried_catdirs); } int main (int argc, char *argv[]) @@ -780,7 +780,7 @@ int main (int argc, char *argv[]) char *sys_manp; int amount = 0; char *mp; - struct hashtable *tried_catdirs; + gl_map_t tried_catdirs; #ifdef SIGPIPE struct sigaction sa; #endif /* SIGPIPE */ @@ -858,7 +858,9 @@ int main (int argc, char *argv[]) /* finished manpath processing, regain privs */ regain_effective_privs (); - tried_catdirs = hashtable_create (tried_catdirs_free); + tried_catdirs = gl_map_create_empty (GL_HASH_MAP, string_equals, + string_hash, plain_free, + tried_catdirs_free); GL_LIST_FOREACH_START (manpathlist, mp) { bool global_manpath = is_global_mandir (mp); @@ -914,7 +916,7 @@ next_manpath: } GL_LIST_FOREACH_END (manpathlist); purge_catdirs (tried_catdirs); - hashtable_free (tried_catdirs); + gl_map_free (tried_catdirs); if (!quiet) { printf (ngettext ("%d man subdirectory contained newer " diff --git a/src/whatis.c b/src/whatis.c index 7c3bfb61..5d45ae46 100644 --- a/src/whatis.c +++ b/src/whatis.c @@ -57,7 +57,9 @@ #include "argp.h" #include "dirname.h" +#include "gl_hash_set.h" #include "gl_list.h" +#include "gl_xset.h" #include "fnmatch.h" #include "progname.h" #include "xvasprintf.h" @@ -70,7 +72,6 @@ #include "pipeline.h" #include "pathsearch.h" #include "linelength.h" -#include "hashtable.h" #include "lower.h" #include "wordfnmatch.h" #include "xregcomp.h" @@ -114,7 +115,7 @@ static const char *alt_systems = ""; static const char *locale = NULL; static char *multiple_locale = NULL, *internal_locale; -static struct hashtable *display_seen = NULL; +static gl_set_t display_seen = NULL; const char *argp_program_version; /* initialised in main */ const char *argp_program_bug_address = PACKAGE_BUGREPORT; @@ -454,9 +455,9 @@ static void display (MYDBM_FILE dbf, struct mandata *info, const char *page) page_name = page; key = xasprintf ("%s (%s)", page_name, newinfo->ext); - if (hashtable_lookup_structure (display_seen, key, strlen (key))) + if (gl_set_search (display_seen, key)) goto out; - hashtable_install (display_seen, key, strlen (key), NULL); + gl_set_add (display_seen, xstrdup (key)); line_len = get_line_length (); @@ -968,7 +969,8 @@ int main (int argc, char *argv[]) manpathlist = create_pathlist (manp); - display_seen = hashtable_create (&null_hashtable_free); + display_seen = gl_set_create_empty (GL_HASH_SET, string_equals, + string_hash, plain_free); #ifdef HAVE_ICONV locale_charset = xasprintf ("%s//IGNORE", get_locale_charset ()); @@ -998,7 +1000,7 @@ int main (int argc, char *argv[]) if (conv_to_locale != (iconv_t) -1) iconv_close (conv_to_locale); #endif /* HAVE_ICONV */ - hashtable_free (display_seen); + gl_set_free (display_seen); free_pathlist (manpathlist); free (manp); free (internal_locale); |