From ccdb1b02159b155b71e561a0bc5b14656e1a7d4d Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Sat, 6 Oct 2001 21:29:19 +0000 Subject: Convert du.c to use the functions in lib/hash.c, not private, slightly-modified copies of those that used to be in cp-hash.c. (struct entry) [coll_link]: Remove member. (struct htab): Remove. (hash_reset, hash_init, hash_insert2, hash_insert): Remove functions. Include hash.h and same.h. (htab): Change type of global to `struct hash'; (entry_hash, entry_compare, hash_ins): New functions. (count_entry): Use hash_ins instead of hash_insert. --- src/du.c | 247 +++++++++++++++++++-------------------------------------------- 1 file changed, 74 insertions(+), 173 deletions(-) (limited to 'src') diff --git a/src/du.c b/src/du.c index 1143ae079..39a015268 100644 --- a/src/du.c +++ b/src/du.c @@ -54,8 +54,10 @@ #include "system.h" #include "error.h" #include "exclude.h" +#include "hash.h" #include "human.h" #include "quote.h" +#include "same.h" #include "save-cwd.h" #include "savedir.h" #include "xstrtol.h" @@ -66,11 +68,8 @@ #define AUTHORS \ "Torbjorn Granlund, David MacKenzie, Larry McVoy, and Paul Eggert" -/* Initial number of entries in each hash table entry's table of inodes. */ -#define INITIAL_HASH_MODULE 100 - -/* Initial number of entries in the inode hash table. */ -#define INITIAL_ENTRY_TAB_SIZE 70 +/* Initial size of the hash table. */ +#define INITIAL_TABLE_SIZE 103 /* Initial size to allocate for `path'. */ #define INITIAL_PATH_SIZE 100 @@ -80,22 +79,12 @@ struct entry { - ino_t ino; - dev_t dev; - struct entry *coll_link; -}; - -/* Structure for a hash table for inode numbers. */ - -struct htab -{ - unsigned modulus; /* Size of the `hash' pointer vector. */ - struct entry *entry_tab; /* Pointer to dynamically growing vector. */ - unsigned entry_tab_size; /* Size of current `entry_tab' allocation. */ - unsigned first_free_entry; /* Index in `entry_tab'. */ - struct entry *hash[1]; /* Vector of pointers in `entry_tab'. */ + ino_t st_ino; + dev_t st_dev; }; +/* A set of dev/ino pairs. */ +static struct hash_table *htab; /* Structure for dynamically resizable strings. */ @@ -143,9 +132,6 @@ static int output_block_size; /* Accumulated path for file or directory being processed. */ static String *path; -/* Pointer to hash structure, used by the hash routines. */ -static struct htab *htab; - /* A pointer to either lstat or stat, depending on whether dereferencing of all symbolic links is to be done. */ static int (*xstat) (); @@ -232,6 +218,69 @@ Summarize disk usage of each FILE, recursively for directories.\n\ exit (status); } +static unsigned int +entry_hash (void const *x, unsigned int table_size) +{ + struct entry const *p = x; + + /* Ignoring the device number here should be fine. */ + /* The cast to uintmax_t prevents negative remainders + if st_ino is negative. */ + return (uintmax_t) p->st_ino % table_size; +} + +/* Compare two dev/ino pairs. Return true if they are the same. */ +static bool +entry_compare (void const *x, void const *y) +{ + struct entry const *a = x; + struct entry const *b = y; + return SAME_INODE (*a, *b) ? true : false; +} + +/* Try to insert the INO/DEV pair into the global table, HTAB. + If the pair is successfully inserted, return zero. + Upon failed memory allocation exit nonzero. + If the pair is already in the table, return nonzero. */ +static int +hash_ins (ino_t ino, dev_t dev) +{ + struct entry *ent; + struct entry *ent_from_table; + + ent = (struct entry *) xmalloc (sizeof *ent); + ent->st_ino = ino; + ent->st_dev = dev; + + ent_from_table = hash_insert (htab, ent); + if (ent_from_table == NULL) + { + /* Insertion failed due to lack of memory. */ + xalloc_die (); + } + + if (ent_from_table == ent) + { + /* Insertion succeeded. */ + return 0; + } + + /* That pair is already in the table, so ENT was not inserted. Free it. */ + free (ent); + + return 1; +} + +/* Initialize the hash table. */ +static void +hash_init (void) +{ + htab = hash_initialize (INITIAL_TABLE_SIZE, NULL, + entry_hash, entry_compare, free); + if (htab == NULL) + xalloc_die (); +} + /* Initialize string S1 to hold SIZE characters. */ static void @@ -307,154 +356,6 @@ print_size (uintmax_t n_blocks, const char *string) fflush (stdout); } -/* Reset the hash structure in the global variable `htab' to - contain no entries. */ - -static void -hash_reset (void) -{ - int i; - struct entry **p; - - htab->first_free_entry = 0; - - p = htab->hash; - for (i = htab->modulus; i > 0; i--) - *p++ = NULL; -} - -/* Allocate space for the hash structures, and set the global - variable `htab' to point to it. The initial hash module is specified in - MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE. (The - hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been - inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be - doubled.) */ - -static void -hash_init (unsigned int modulus, unsigned int entry_tab_size) -{ - struct htab *htab_r; - - htab_r = (struct htab *) - xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus); - - htab_r->entry_tab = (struct entry *) - xmalloc (sizeof (struct entry) * entry_tab_size); - - htab_r->modulus = modulus; - htab_r->entry_tab_size = entry_tab_size; - htab = htab_r; - - hash_reset (); -} - -/* Insert INO and DEV in the hash structure HTAB, if not - already present. Return zero if inserted and nonzero if it - already existed. */ - -static int -hash_insert2 (struct htab *ht, ino_t ino, dev_t dev) -{ - struct entry **hp, *ep2, *ep; - hp = &ht->hash[ino % ht->modulus]; - ep2 = *hp; - - /* Collision? */ - - if (ep2 != NULL) - { - ep = ep2; - - /* Search for an entry with the same data. */ - - do - { - if (ep->ino == ino && ep->dev == dev) - return 1; /* Found an entry with the same data. */ - ep = ep->coll_link; - } - while (ep != NULL); - - /* Did not find it. */ - - } - - ep = *hp = &ht->entry_tab[ht->first_free_entry++]; - ep->ino = ino; - ep->dev = dev; - ep->coll_link = ep2; /* `ep2' is NULL if no collision. */ - - return 0; -} - -/* Insert an item (inode INO and device DEV) in the hash - structure in the global variable `htab', if an entry with the same data - was not found already. Return zero if the item was inserted and nonzero - if it wasn't. */ - -static int -hash_insert (ino_t ino, dev_t dev) -{ - struct htab *htab_r = htab; /* Initially a copy of the global `htab'. */ - - if (htab_r->first_free_entry >= htab_r->entry_tab_size) - { - int i; - struct entry *ep; - unsigned modulus; - unsigned entry_tab_size; - - /* Increase the number of hash entries, and re-hash the data. - The method of shrimping and increasing is made to compactify - the heap. If twice as much data would be allocated - straightforwardly, we would never re-use a byte of memory. */ - - /* Let `htab' shrimp. Keep only the header, not the pointer vector. */ - - htab_r = (struct htab *) - xrealloc ((char *) htab_r, sizeof (struct htab)); - - modulus = 2 * htab_r->modulus; - entry_tab_size = 2 * htab_r->entry_tab_size; - - /* Increase the number of possible entries. */ - - htab_r->entry_tab = (struct entry *) - xrealloc ((char *) htab_r->entry_tab, - sizeof (struct entry) * entry_tab_size); - - /* Increase the size of htab again. */ - - htab_r = (struct htab *) - xrealloc ((char *) htab_r, - sizeof (struct htab) + sizeof (struct entry *) * modulus); - - htab_r->modulus = modulus; - htab_r->entry_tab_size = entry_tab_size; - htab = htab_r; - - i = htab_r->first_free_entry; - - /* Make the increased hash table empty. The entries are still - available in htab->entry_tab. */ - - hash_reset (); - - /* Go through the entries and install them in the pointer vector - htab->hash. The items are actually inserted in htab->entry_tab at - the position where they already are. The htab->coll_link need - however be updated. Could be made a little more efficient. */ - - for (ep = htab_r->entry_tab; i > 0; i--) - { - hash_insert2 (htab_r, ep->ino, ep->dev); - ep++; - } - } - - return hash_insert2 (htab_r, ino, dev); -} - /* Restore the previous working directory or exit. If CWD is null, simply call `chdir ("..")'. Otherwise, use CWD and free it. CURR_DIR_NAME is the name of the current directory @@ -502,7 +403,7 @@ count_entry (const char *ent, int top, dev_t last_dev, int depth) if (!opt_count_all && stat_buf.st_nlink > 1 - && hash_insert (stat_buf.st_ino, stat_buf.st_dev)) + && hash_ins (stat_buf.st_ino, stat_buf.st_dev)) return 0; /* Have counted this already. */ size = ST_NBLOCKS (stat_buf); @@ -634,7 +535,7 @@ du_files (char **files) str_copyc (path, arg); if (!print_totals) - hash_reset (); + hash_clear (htab); count_entry (arg, 1, 0, 0); } @@ -785,7 +686,7 @@ main (int argc, char **argv) max_depth = 0; /* Initialize the hash structure for inode numbers. */ - hash_init (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE); + hash_init (); str_init (&path, INITIAL_PATH_SIZE); -- cgit v1.2.3-54-g00ecf