src/du.c

   1 /* du -- summarize disk usage
   2    Copyright (C) 1988, 1989, 1990, 1991, 1995 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Differences from the Unix du:
  19    * Doesn't simply ignore the names of regular files given as arguments
  20      when -a is given.
  21    * Additional options:
  22    -l           Count the size of all files, even if they have appeared
  23                 already in another hard link.
  24    -x           Do not cross file-system boundaries during the recursion.
  25    -c           Write a grand total of all of the arguments after all
  26                 arguments have been processed.  This can be used to find
  27                 out the disk usage of a directory, with some files excluded.
  28    -h           Print sizes in human readable format (1k 234M 2G, etc).
  29    -k           Print sizes in kilobytes instead of 512 byte blocks
  30                 (the default required by POSIX).
  31    -m           Print sizes in megabytes instead of 512 byte blocks
  32    -b           Print sizes in bytes.
  33    -S           Count the size of each directory separately, not including
  34                 the sizes of subdirectories.
  35    -D           Dereference only symbolic links given on the command line.
  36    -L           Dereference all symbolic links.
  37
  38    By tege@sics.se, Torbjorn Granlund,
  39    and djm@ai.mit.edu, David MacKenzie.
  40    Variable blocks added by lm@sgi.com.
  41 */
  42
  43 #ifdef _AIX
  44  #pragma alloca
  45 #endif
  46
  47 #include <config.h>
  48 #include <stdio.h>
  49 #include <getopt.h>
  50 #include <sys/types.h>
  51 #include <assert.h>
  52
  53 #include "system.h"
  54 #include "save-cwd.h"
  55 #include "error.h"
  56
  57 #undef  convert_blocks
  58 #define convert_blocks(b, size) (size == size_kilobytes ? ((b) + 1) / 2 : \
  59     size == size_megabytes ? ((b) + 1024) / 2048 : (b))
  60
  61 /* Initial number of entries in each hash table entry's table of inodes.  */
  62 #define INITIAL_HASH_MODULE 100
  63
  64 /* Initial number of entries in the inode hash table.  */
  65 #define INITIAL_ENTRY_TAB_SIZE 70
  66
  67 /* Initial size to allocate for `path'.  */
  68 #define INITIAL_PATH_SIZE 100
  69
  70 /* The maximum length of a human-readable string.  Be pessimistic
  71    and assume `int' is 64-bits wide.  Converting 2^63 - 1 gives the
  72    11-character string, 8589934592G.  */
  73 #define LONGEST_HUMAN_READABLE 11
  74
  75 /* Hash structure for inode and device numbers.  The separate entry
  76    structure makes it easier to rehash "in place".  */
  77
  78 struct entry
  79 {
  80   ino_t ino;
  81   dev_t dev;
  82   struct entry *coll_link;
  83 };
  84
  85 /* Structure for a hash table for inode numbers. */
  86
  87 struct htab
  88 {
  89   unsigned modulus;             /* Size of the `hash' pointer vector.  */
  90   struct entry *entry_tab;      /* Pointer to dynamically growing vector.  */
  91   unsigned entry_tab_size;      /* Size of current `entry_tab' allocation.  */
  92   unsigned first_free_entry;    /* Index in `entry_tab'.  */
  93   struct entry *hash[1];        /* Vector of pointers in `entry_tab'.  */
  94 };
  95
  96
  97 /* Structure for dynamically resizable strings. */
  98
  99 typedef struct
 100 {
 101   unsigned alloc;               /* Size of allocation for the text.  */
 102   unsigned length;              /* Length of the text currently.  */
 103   char *text;                   /* Pointer to the text.  */
 104 } *string, stringstruct;
 105
 106 int stat ();
 107 int lstat ();
 108
 109 char *savedir ();
 110 char *xmalloc ();
 111 char *xrealloc ();
 112
 113 static int hash_insert __P ((ino_t ino, dev_t dev));
 114 static int hash_insert2 __P ((struct htab *htab, ino_t ino, dev_t dev));
 115 static long count_entry __P ((char *ent, int top, dev_t last_dev));
 116 static void du_files __P ((char **files));
 117 static void hash_init __P ((unsigned int modulus,
 118                             unsigned int entry_tab_size));
 119 static void hash_reset __P ((void));
 120 static void str_concatc __P ((string s1, char *cstr));
 121 static void str_copyc __P ((string s1, char *cstr));
 122 static void str_init __P ((string *s1, unsigned int size));
 123 static void str_trunc __P ((string s1, unsigned int length));
 124
 125 /* Name under which this program was invoked.  */
 126 char *program_name;
 127
 128 /* If nonzero, display only a total for each argument. */
 129 static int opt_summarize_only = 0;
 130
 131 /* If nonzero, display counts for all files, not just directories. */
 132 static int opt_all = 0;
 133
 134 /* If nonzero, count each hard link of files with multiple links. */
 135 static int opt_count_all = 0;
 136
 137 /* If nonzero, do not cross file-system boundaries. */
 138 static int opt_one_file_system = 0;
 139
 140 /* If nonzero, print a grand total at the end. */
 141 static int opt_combined_arguments = 0;
 142
 143 /* If nonzero, do not add sizes of subdirectories. */
 144 static int opt_separate_dirs = 0;
 145
 146 /* If nonzero, dereference symlinks that are command line arguments. */
 147 static int opt_dereference_arguments = 0;
 148
 149 enum output_size
 150 {
 151   size_blocks,                  /* 512-byte blocks. */
 152   size_kilobytes,               /* 1K blocks. */
 153   size_megabytes,               /* 1024K blocks. */
 154   size_bytes                    /* 1-byte blocks. */
 155 };
 156
 157 /* human style output */
 158 static int opt_human_readable;
 159
 160 /* The units to count in. */
 161 static enum output_size output_size;
 162
 163 /* Accumulated path for file or directory being processed.  */
 164 static string path;
 165
 166 /* Pointer to hash structure, used by the hash routines.  */
 167 static struct htab *htab;
 168
 169 /* Globally used stat buffer.  */
 170 static struct stat stat_buf;
 171
 172 /* A pointer to either lstat or stat, depending on whether
 173    dereferencing of all symbolic links is to be done. */
 174 static int (*xstat) ();
 175
 176 /* The exit status to use if we don't get any fatal errors. */
 177 static int exit_status;
 178
 179 /* If nonzero, display usage information and exit.  */
 180 static int show_help;
 181
 182 /* If nonzero, print the version on standard output and exit.  */
 183 static int show_version;
 184
 185 /* Grand total size of all args. */
 186 static long tot_size = 0L;
 187
 188 static struct option const long_options[] =
 189 {
 190   {"all", no_argument, &opt_all, 1},
 191   {"bytes", no_argument, NULL, 'b'},
 192   {"count-links", no_argument, &opt_count_all, 1},
 193   {"dereference", no_argument, NULL, 'L'},
 194   {"dereference-args", no_argument, &opt_dereference_arguments, 1},
 195   {"human-readable", no_argument, NULL, 'h'},
 196   {"kilobytes", no_argument, NULL, 'k'},
 197   {"megabytes", no_argument, NULL, 'm'},
 198   {"one-file-system", no_argument, &opt_one_file_system, 1},
 199   {"separate-dirs", no_argument, &opt_separate_dirs, 1},
 200   {"summarize", no_argument, &opt_summarize_only, 1},
 201   {"total", no_argument, &opt_combined_arguments, 1},
 202   {"help", no_argument, &show_help, 1},
 203   {"version", no_argument, &show_version, 1},
 204   {NULL, 0, NULL, 0}
 205 };
 206
 207 static void
 208 usage (int status, char *reason)
 209 {
 210   if (reason != NULL)
 211     fprintf (status == 0 ? stdout : stderr, "%s: %s\n",
 212              program_name, reason);
 213
 214   if (status != 0)
 215     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 216              program_name);
 217   else
 218     {
 219       printf (_("Usage: %s [OPTION]... [FILE]...\n"), program_name);
 220       printf (_("\
 221 Summarize disk usage of each FILE, recursively for directories.\n\
 222 \n\
 223   -a, --all             write counts for all files, not just directories\n\
 224   -b, --bytes           print size in bytes\n\
 225   -c, --total           produce a grand total\n\
 226   -h, --human           print sizes in human readable format (e.g. 1K 234M 2G)\n\
 227   -k, --kilobytes       use 1024-byte blocks, not 512 despite POSIXLY_CORRECT\n\
 228   -l, --count-links     count sizes many times if hard linked\n\
 229   -m, --megabytes       use 1024K-byte blocks, not 512 despite POSIXLY_CORRECT\n\
 230   -s, --summarize       display only a total for each argument\n\
 231   -x, --one-file-system  skip directories on different filesystems\n\
 232   -D, --dereference-args  dereference PATHs when symbolic link\n\
 233   -L, --dereference     dereference all symbolic links\n\
 234   -S, --separate-dirs   do not include size of subdirectories\n\
 235       --help            display this help and exit\n\
 236       --version         output version information and exit\n"));
 237     }
 238   exit (status);
 239 }
 240
 241 void
 242 main (int argc, char **argv)
 243 {
 244   int c;
 245   char *cwd_only[2];
 246   char *bs;
 247
 248   cwd_only[0] = ".";
 249   cwd_only[1] = NULL;
 250
 251   program_name = argv[0];
 252   setlocale (LC_ALL, "");
 253   bindtextdomain (PACKAGE, LOCALEDIR);
 254   textdomain (PACKAGE);
 255
 256   xstat = lstat;
 257
 258   if (getenv ("POSIXLY_CORRECT"))
 259     output_size = size_blocks;
 260   else if ((bs = getenv ("BLOCKSIZE"))
 261            && strncmp (bs, "HUMAN", sizeof ("HUMAN") - 1) == 0)
 262     {
 263       opt_human_readable = 1;
 264       output_size = size_bytes;
 265     }
 266   else
 267     output_size = size_kilobytes;
 268
 269   while ((c = getopt_long (argc, argv, "abchklmsxDLS", long_options,
 270                            (int *) 0))
 271          != EOF)
 272     {
 273       switch (c)
 274         {
 275         case 0:                 /* Long option. */
 276           break;
 277
 278         case 'a':
 279           opt_all = 1;
 280           break;
 281
 282         case 'b':
 283           output_size = size_bytes;
 284           opt_human_readable = 0;
 285           break;
 286
 287         case 'c':
 288           opt_combined_arguments = 1;
 289           break;
 290
 291         case 'h':
 292           output_size = size_bytes;
 293           opt_human_readable = 1;
 294           break;
 295
 296         case 'k':
 297           output_size = size_kilobytes;
 298           opt_human_readable = 0;
 299           break;
 300
 301         case 'm':
 302           output_size = size_megabytes;
 303           opt_human_readable = 0;
 304           break;
 305
 306         case 'l':
 307           opt_count_all = 1;
 308           break;
 309
 310         case 's':
 311           opt_summarize_only = 1;
 312           break;
 313
 314         case 'x':
 315           opt_one_file_system = 1;
 316           break;
 317
 318         case 'D':
 319           opt_dereference_arguments = 1;
 320           break;
 321
 322         case 'L':
 323           xstat = stat;
 324           break;
 325
 326         case 'S':
 327           opt_separate_dirs = 1;
 328           break;
 329
 330         default:
 331           usage (2, (char *) 0);
 332         }
 333     }
 334
 335   if (show_version)
 336     {
 337       printf ("du - %s\n", PACKAGE_VERSION);
 338       exit (0);
 339     }
 340
 341   if (show_help)
 342     usage (0, NULL);
 343
 344   if (opt_all && opt_summarize_only)
 345     usage (2, _("cannot both summarize and show all entries"));
 346
 347   /* Initialize the hash structure for inode numbers.  */
 348   hash_init (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE);
 349
 350   str_init (&path, INITIAL_PATH_SIZE);
 351
 352   du_files (optind == argc ? cwd_only : argv + optind);
 353
 354   exit (exit_status);
 355 }
 356
 357 /* Convert N_BYTES to a more readable string than %d would.
 358    Most people visually process strings of 3-4 digits effectively,
 359    but longer strings of digits are more prone to misinterpretation.
 360    Hence, converting to an abbreviated form usually improves readability.
 361    Use a suffix indicating multiples of 1024 (K), 1024*1024 (M), and
 362    1024*1024*1024 (G).  For example, 8500 would be converted to 8.3K,
 363    133456345 to 127M, 56990456345 to 53G, and so on.  Numbers smaller
 364    than 1024 aren't modified.  */
 365
 366 static char *
 367 human_readable (int n_bytes, char *buf, int buf_len)
 368 {
 369   const char *suffix;
 370   double amt;
 371   char *p;
 372
 373   assert (buf_len > LONGEST_HUMAN_READABLE);
 374
 375   p = buf;
 376   amt = n_bytes;
 377
 378   if (amt >= 1024 * 1024 * 1024)
 379     {
 380       amt /= (1024 * 1024 * 1024);
 381       suffix = "G";
 382     }
 383   else if (amt >= 1024 * 1024)
 384     {
 385       amt /= (1024 * 1024);
 386       suffix = "M";
 387     }
 388   else if (amt >= 1024)
 389     {
 390       amt /= 1024;
 391       suffix = "K";
 392     }
 393   else
 394     {
 395       suffix = "";
 396     }
 397
 398   if (amt >= 10)
 399     {
 400       sprintf (p, "%.0f%s", amt, suffix);
 401     }
 402   else if (amt == 0)
 403     {
 404       strcpy (p, "0");
 405     }
 406   else
 407     {
 408       sprintf (p, "%.1f%s", amt, suffix);
 409     }
 410   return (p);
 411 }
 412
 413 /* Recursively print the sizes of the directories (and, if selected, files)
 414    named in FILES, the last entry of which is NULL.  */
 415
 416 static void
 417 du_files (char **files)
 418 {
 419   struct saved_cwd cwd;
 420   ino_t initial_ino;            /* Initial directory's inode. */
 421   dev_t initial_dev;            /* Initial directory's device. */
 422   int i;                        /* Index in FILES. */
 423
 424   if (save_cwd (&cwd))
 425     exit (1);
 426
 427   /* Remember the inode and device number of the current directory.  */
 428   if (stat (".", &stat_buf))
 429     error (1, errno, _("current directory"));
 430   initial_ino = stat_buf.st_ino;
 431   initial_dev = stat_buf.st_dev;
 432
 433   for (i = 0; files[i]; i++)
 434     {
 435       char *arg;
 436       int s;
 437
 438       arg = files[i];
 439
 440       /* Delete final slash in the argument, unless the slash is alone.  */
 441       s = strlen (arg) - 1;
 442       if (s != 0)
 443         {
 444           if (arg[s] == '/')
 445             arg[s] = 0;
 446
 447           str_copyc (path, arg);
 448         }
 449       else if (arg[0] == '/')
 450         str_trunc (path, 0);    /* Null path for root directory.  */
 451       else
 452         str_copyc (path, arg);
 453
 454       if (!opt_combined_arguments)
 455         hash_reset ();
 456
 457       count_entry (arg, 1, 0);
 458
 459       /* chdir if `count_entry' has changed the working directory.  */
 460       if (stat (".", &stat_buf))
 461         error (1, errno, ".");
 462       if (stat_buf.st_ino != initial_ino || stat_buf.st_dev != initial_dev)
 463         {
 464           if (restore_cwd (&cwd, _("starting directory"), NULL))
 465             exit (1);
 466         }
 467     }
 468
 469   if (opt_combined_arguments)
 470     {
 471       if (opt_human_readable)
 472         {
 473           char buf[LONGEST_HUMAN_READABLE + 1];
 474           printf("%s\ttotal\n", human_readable (tot_size, buf,
 475                                                 LONGEST_HUMAN_READABLE + 1));
 476         }
 477       else
 478         {
 479           printf (_("%ld\ttotal\n"), output_size == size_bytes ? tot_size
 480                   : convert_blocks (tot_size, output_size == size_kilobytes));
 481         }
 482       fflush (stdout);
 483     }
 484
 485   free_cwd (&cwd);
 486 }
 487
 488 /* Print (if appropriate) and return the size
 489    (in units determined by `output_size') of file or directory ENT.
 490    TOP is one for external calls, zero for recursive calls.
 491    LAST_DEV is the device that the parent directory of ENT is on.  */
 492
 493 static long
 494 count_entry (char *ent, int top, dev_t last_dev)
 495 {
 496   long size;
 497
 498   if (((top && opt_dereference_arguments)
 499        ? stat (ent, &stat_buf)
 500        : (*xstat) (ent, &stat_buf)) < 0)
 501     {
 502       error (0, errno, "%s", path->text);
 503       exit_status = 1;
 504       return 0;
 505     }
 506
 507   if (!opt_count_all
 508       && stat_buf.st_nlink > 1
 509       && hash_insert (stat_buf.st_ino, stat_buf.st_dev))
 510     return 0;                   /* Have counted this already.  */
 511
 512   if (output_size == size_bytes)
 513     size = stat_buf.st_size;
 514   else
 515     size = ST_NBLOCKS (stat_buf);
 516
 517   tot_size += size;
 518
 519   if (S_ISDIR (stat_buf.st_mode))
 520     {
 521       unsigned pathlen;
 522       dev_t dir_dev;
 523       char *name_space;
 524       char *namep;
 525       struct saved_cwd cwd;
 526       int through_symlink;
 527       struct stat e_buf;
 528
 529       dir_dev = stat_buf.st_dev;
 530
 531       if (opt_one_file_system && !top && last_dev != dir_dev)
 532         return 0;               /* Don't enter a new file system.  */
 533
 534 #ifndef S_ISDIR
 535 # define S_ISDIR(s) 0
 536 #endif
 537       /* If we're dereferencing symlinks and we're about to chdir through
 538          a symlink, remember the current directory so we can return to it
 539          later.  In other cases, chdir ("..") works fine.  */
 540       through_symlink = (xstat == stat
 541                          && lstat (ent, &e_buf) == 0
 542                          && S_ISLNK (e_buf.st_mode));
 543       if (through_symlink)
 544         if (save_cwd (&cwd))
 545           exit (1);
 546
 547       if (chdir (ent) < 0)
 548         {
 549           error (0, errno, _("cannot change to directory %s"), path->text);
 550           exit_status = 1;
 551           return 0;
 552         }
 553
 554       errno = 0;
 555       name_space = savedir (".", stat_buf.st_size);
 556       if (name_space == NULL)
 557         {
 558           if (errno)
 559             {
 560               error (0, errno, "%s", path->text);
 561               if (through_symlink)
 562                 {
 563                   if (restore_cwd (&cwd, "..", path->text))
 564                     exit (1);
 565                   free_cwd (&cwd);
 566                 }
 567               else if (chdir ("..") < 0)
 568                   error (1, errno, _("cannot change to `..' from directory %s"),
 569                          path->text);
 570               exit_status = 1;
 571               return 0;
 572             }
 573           else
 574             error (1, 0, _("virtual memory exhausted"));
 575         }
 576
 577       /* Remember the current path.  */
 578
 579       str_concatc (path, "/");
 580       pathlen = path->length;
 581
 582       namep = name_space;
 583       while (*namep != 0)
 584         {
 585           str_concatc (path, namep);
 586
 587           size += count_entry (namep, 0, dir_dev);
 588
 589           str_trunc (path, pathlen);
 590           namep += strlen (namep) + 1;
 591         }
 592       free (name_space);
 593       if (through_symlink)
 594         {
 595           restore_cwd (&cwd, "..", path->text);
 596           free_cwd (&cwd);
 597         }
 598       else if (chdir ("..") < 0)
 599         error (1, errno,
 600                _("cannot change to `..' from directory %s"), path->text);
 601
 602       str_trunc (path, pathlen - 1); /* Remove the "/" we added.  */
 603       if (!opt_summarize_only || top)
 604         {
 605           if (opt_human_readable)
 606             {
 607               char buf[LONGEST_HUMAN_READABLE + 1];
 608               printf("%s\t%s\n",
 609                      human_readable (size, buf, LONGEST_HUMAN_READABLE + 1),
 610                      path->length > 0 ? path->text : "/");
 611             }
 612           else
 613             {
 614               printf ("%ld\t%s\n", (output_size == size_bytes
 615                                     ? size
 616                                     : convert_blocks (size, output_size)),
 617                       path->length > 0 ? path->text : "/");
 618             }
 619           fflush (stdout);
 620         }
 621       return opt_separate_dirs ? 0 : size;
 622     }
 623   else if (opt_all || top)
 624     {
 625       /* FIXME: make this an option.  */
 626       int print_only_dir_size = 0;
 627       if (!print_only_dir_size)
 628         {
 629           if (opt_human_readable)
 630             {
 631               char buf[LONGEST_HUMAN_READABLE + 1];
 632               printf("%s\t%s\n",
 633                      human_readable (size, buf, LONGEST_HUMAN_READABLE + 1),
 634                      path->length > 0 ? path->text : "/");
 635             }
 636           else
 637             {
 638               printf ("%ld\t%s\n", output_size == size_bytes ? size
 639                       : convert_blocks (size, output_size == size_kilobytes),
 640                       path->text);
 641             }
 642           fflush (stdout);
 643         }
 644     }
 645
 646   return size;
 647 }
 648
 649 /* Allocate space for the hash structures, and set the global
 650    variable `htab' to point to it.  The initial hash module is specified in
 651    MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE.  (The
 652    hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been
 653    inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be
 654    doubled.)  */
 655
 656 static void
 657 hash_init (unsigned int modulus, unsigned int entry_tab_size)
 658 {
 659   struct htab *htab_r;
 660
 661   htab_r = (struct htab *)
 662     xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus);
 663
 664   htab_r->entry_tab = (struct entry *)
 665     xmalloc (sizeof (struct entry) * entry_tab_size);
 666
 667   htab_r->modulus = modulus;
 668   htab_r->entry_tab_size = entry_tab_size;
 669   htab = htab_r;
 670
 671   hash_reset ();
 672 }
 673
 674 /* Reset the hash structure in the global variable `htab' to
 675    contain no entries.  */
 676
 677 static void
 678 hash_reset (void)
 679 {
 680   int i;
 681   struct entry **p;
 682
 683   htab->first_free_entry = 0;
 684
 685   p = htab->hash;
 686   for (i = htab->modulus; i > 0; i--)
 687     *p++ = NULL;
 688 }
 689
 690 /* Insert an item (inode INO and device DEV) in the hash
 691    structure in the global variable `htab', if an entry with the same data
 692    was not found already.  Return zero if the item was inserted and nonzero
 693    if it wasn't.  */
 694
 695 static int
 696 hash_insert (ino_t ino, dev_t dev)
 697 {
 698   struct htab *htab_r = htab;   /* Initially a copy of the global `htab'.  */
 699
 700   if (htab_r->first_free_entry >= htab_r->entry_tab_size)
 701     {
 702       int i;
 703       struct entry *ep;
 704       unsigned modulus;
 705       unsigned entry_tab_size;
 706
 707       /* Increase the number of hash entries, and re-hash the data.
 708          The method of shrimping and increasing is made to compactify
 709          the heap.  If twice as much data would be allocated
 710          straightforwardly, we would never re-use a byte of memory.  */
 711
 712       /* Let `htab' shrimp.  Keep only the header, not the pointer vector.  */
 713
 714       htab_r = (struct htab *)
 715         xrealloc ((char *) htab_r, sizeof (struct htab));
 716
 717       modulus = 2 * htab_r->modulus;
 718       entry_tab_size = 2 * htab_r->entry_tab_size;
 719
 720       /* Increase the number of possible entries.  */
 721
 722       htab_r->entry_tab = (struct entry *)
 723         xrealloc ((char *) htab_r->entry_tab,
 724                  sizeof (struct entry) * entry_tab_size);
 725
 726       /* Increase the size of htab again.  */
 727
 728       htab_r = (struct htab *)
 729         xrealloc ((char *) htab_r,
 730                  sizeof (struct htab) + sizeof (struct entry *) * modulus);
 731
 732       htab_r->modulus = modulus;
 733       htab_r->entry_tab_size = entry_tab_size;
 734       htab = htab_r;
 735
 736       i = htab_r->first_free_entry;
 737
 738       /* Make the increased hash table empty.  The entries are still
 739          available in htab->entry_tab.  */
 740
 741       hash_reset ();
 742
 743       /* Go through the entries and install them in the pointer vector
 744          htab->hash.  The items are actually inserted in htab->entry_tab at
 745          the position where they already are.  The htab->coll_link need
 746          however be updated.  Could be made a little more efficient.  */
 747
 748       for (ep = htab_r->entry_tab; i > 0; i--)
 749         {
 750           hash_insert2 (htab_r, ep->ino, ep->dev);
 751           ep++;
 752         }
 753     }
 754
 755   return hash_insert2 (htab_r, ino, dev);
 756 }
 757
 758 /* Insert INO and DEV in the hash structure HTAB, if not
 759    already present.  Return zero if inserted and nonzero if it
 760    already existed.  */
 761
 762 static int
 763 hash_insert2 (struct htab *htab, ino_t ino, dev_t dev)
 764 {
 765   struct entry **hp, *ep2, *ep;
 766   hp = &htab->hash[ino % htab->modulus];
 767   ep2 = *hp;
 768
 769   /* Collision?  */
 770
 771   if (ep2 != NULL)
 772     {
 773       ep = ep2;
 774
 775       /* Search for an entry with the same data.  */
 776
 777       do
 778         {
 779           if (ep->ino == ino && ep->dev == dev)
 780             return 1;           /* Found an entry with the same data.  */
 781           ep = ep->coll_link;
 782         }
 783       while (ep != NULL);
 784
 785       /* Did not find it.  */
 786
 787     }
 788
 789   ep = *hp = &htab->entry_tab[htab->first_free_entry++];
 790   ep->ino = ino;
 791   ep->dev = dev;
 792   ep->coll_link = ep2;          /* `ep2' is NULL if no collision.  */
 793
 794   return 0;
 795 }
 796
 797 /* Initialize the struct string S1 for holding SIZE characters.  */
 798
 799 static void
 800 str_init (string *s1, unsigned int size)
 801 {
 802   string s;
 803
 804   s = (string) xmalloc (sizeof (stringstruct));
 805   s->text = xmalloc (size + 1);
 806
 807   s->alloc = size;
 808   *s1 = s;
 809 }
 810
 811 static void
 812 ensure_space (string s, unsigned int size)
 813 {
 814   if (s->alloc < size)
 815     {
 816       s->text = xrealloc (s->text, size + 1);
 817       s->alloc = size;
 818     }
 819 }
 820
 821 /* Assign the null-terminated C-string CSTR to S1.  */
 822
 823 static void
 824 str_copyc (string s1, char *cstr)
 825 {
 826   unsigned l = strlen (cstr);
 827   ensure_space (s1, l);
 828   strcpy (s1->text, cstr);
 829   s1->length = l;
 830 }
 831
 832 static void
 833 str_concatc (string s1, char *cstr)
 834 {
 835   unsigned l1 = s1->length;
 836   unsigned l2 = strlen (cstr);
 837   unsigned l = l1 + l2;
 838
 839   ensure_space (s1, l);
 840   strcpy (s1->text + l1, cstr);
 841   s1->length = l;
 842 }
 843
 844 /* Truncate the string S1 to have length LENGTH.  */
 845
 846 static void
 847 str_trunc (string s1, unsigned int length)
 848 {
 849   if (s1->length > length)
 850     {
 851       s1->text[length] = 0;
 852       s1->length = length;
 853     }
 854 }