src/du.c

   1 /* du -- summarize disk usage
   2    Copyright (C) 88, 89, 90, 91, 95, 1996 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 Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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   -D, --dereference-args  dereference PATHs when symbolic link\n\
 227   -h, --human-readable  print sizes in human readable format (e.g., 1K 234M 2G)\n\
 228   -k, --kilobytes       use 1024-byte blocks, not 512 despite POSIXLY_CORRECT\n\
 229   -l, --count-links     count sizes many times if hard linked\n\
 230   -L, --dereference     dereference all symbolic links\n\
 231   -m, --megabytes       use 1024K-byte blocks, not 512 despite POSIXLY_CORRECT\n\
 232   -S, --separate-dirs   do not include size of subdirectories\n\
 233   -s, --summarize       display only a total for each argument\n\
 234   -x, --one-file-system  skip directories on different filesystems\n\
 235       --help            display this help and exit\n\
 236       --version         output version information and exit\n\
 237 "));
 238       puts (_("\nReport bugs to fileutils-bugs@gnu.ai.mit.edu"));
 239     }
 240   exit (status);
 241 }
 242
 243 int
 244 main (int argc, char **argv)
 245 {
 246   int c;
 247   char *cwd_only[2];
 248   char *bs;
 249
 250   cwd_only[0] = ".";
 251   cwd_only[1] = NULL;
 252
 253   program_name = argv[0];
 254   setlocale (LC_ALL, "");
 255   bindtextdomain (PACKAGE, LOCALEDIR);
 256   textdomain (PACKAGE);
 257
 258   xstat = lstat;
 259
 260   if (getenv ("POSIXLY_CORRECT"))
 261     output_size = size_blocks;
 262   else if ((bs = getenv ("BLOCKSIZE"))
 263            && strncmp (bs, "HUMAN", sizeof ("HUMAN") - 1) == 0)
 264     {
 265       opt_human_readable = 1;
 266       output_size = size_bytes;
 267     }
 268   else
 269     output_size = size_kilobytes;
 270
 271   while ((c = getopt_long (argc, argv, "abchklmsxDLS", long_options, NULL))
 272          != -1)
 273     {
 274       switch (c)
 275         {
 276         case 0:                 /* Long option. */
 277           break;
 278
 279         case 'a':
 280           opt_all = 1;
 281           break;
 282
 283         case 'b':
 284           output_size = size_bytes;
 285           opt_human_readable = 0;
 286           break;
 287
 288         case 'c':
 289           opt_combined_arguments = 1;
 290           break;
 291
 292         case 'h':
 293           output_size = size_bytes;
 294           opt_human_readable = 1;
 295           break;
 296
 297         case 'k':
 298           output_size = size_kilobytes;
 299           opt_human_readable = 0;
 300           break;
 301
 302         case 'm':
 303           output_size = size_megabytes;
 304           opt_human_readable = 0;
 305           break;
 306
 307         case 'l':
 308           opt_count_all = 1;
 309           break;
 310
 311         case 's':
 312           opt_summarize_only = 1;
 313           break;
 314
 315         case 'x':
 316           opt_one_file_system = 1;
 317           break;
 318
 319         case 'D':
 320           opt_dereference_arguments = 1;
 321           break;
 322
 323         case 'L':
 324           xstat = stat;
 325           break;
 326
 327         case 'S':
 328           opt_separate_dirs = 1;
 329           break;
 330
 331         default:
 332           usage (2, (char *) 0);
 333         }
 334     }
 335
 336   if (show_version)
 337     {
 338       printf ("du (%s) %s\n", GNU_PACKAGE, VERSION);
 339       exit (0);
 340     }
 341
 342   if (show_help)
 343     usage (0, NULL);
 344
 345   if (opt_all && opt_summarize_only)
 346     usage (2, _("cannot both summarize and show all entries"));
 347
 348   /* Initialize the hash structure for inode numbers.  */
 349   hash_init (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE);
 350
 351   str_init (&path, INITIAL_PATH_SIZE);
 352
 353   du_files (optind == argc ? cwd_only : argv + optind);
 354
 355   exit (exit_status);
 356 }
 357
 358 /* Convert N_BYTES to a more readable string than %d would.
 359    Most people visually process strings of 3-4 digits effectively,
 360    but longer strings of digits are more prone to misinterpretation.
 361    Hence, converting to an abbreviated form usually improves readability.
 362    Use a suffix indicating multiples of 1024 (K), 1024*1024 (M), and
 363    1024*1024*1024 (G).  For example, 8500 would be converted to 8.3K,
 364    133456345 to 127M, 56990456345 to 53G, and so on.  Numbers smaller
 365    than 1024 aren't modified.  */
 366
 367 static char *
 368 human_readable (int n_bytes, char *buf, int buf_len)
 369 {
 370   const char *suffix;
 371   double amt;
 372   char *p;
 373
 374   assert (buf_len > LONGEST_HUMAN_READABLE);
 375
 376   p = buf;
 377   amt = n_bytes;
 378
 379   if (amt >= 1024 * 1024 * 1024)
 380     {
 381       amt /= (1024 * 1024 * 1024);
 382       suffix = "G";
 383     }
 384   else if (amt >= 1024 * 1024)
 385     {
 386       amt /= (1024 * 1024);
 387       suffix = "M";
 388     }
 389   else if (amt >= 1024)
 390     {
 391       amt /= 1024;
 392       suffix = "K";
 393     }
 394   else
 395     {
 396       suffix = "";
 397     }
 398
 399   if (amt >= 10)
 400     {
 401       sprintf (p, "%.0f%s", amt, suffix);
 402     }
 403   else if (amt == 0)
 404     {
 405       strcpy (p, "0");
 406     }
 407   else
 408     {
 409       sprintf (p, "%.1f%s", amt, suffix);
 410     }
 411   return (p);
 412 }
 413
 414 /* Recursively print the sizes of the directories (and, if selected, files)
 415    named in FILES, the last entry of which is NULL.  */
 416
 417 static void
 418 du_files (char **files)
 419 {
 420   struct saved_cwd cwd;
 421   ino_t initial_ino;            /* Initial directory's inode. */
 422   dev_t initial_dev;            /* Initial directory's device. */
 423   int i;                        /* Index in FILES. */
 424
 425   if (save_cwd (&cwd))
 426     exit (1);
 427
 428   /* Remember the inode and device number of the current directory.  */
 429   if (stat (".", &stat_buf))
 430     error (1, errno, _("current directory"));
 431   initial_ino = stat_buf.st_ino;
 432   initial_dev = stat_buf.st_dev;
 433
 434   for (i = 0; files[i]; i++)
 435     {
 436       char *arg;
 437       int s;
 438
 439       arg = files[i];
 440
 441       /* Delete final slash in the argument, unless the slash is alone.  */
 442       s = strlen (arg) - 1;
 443       if (s != 0)
 444         {
 445           if (arg[s] == '/')
 446             arg[s] = 0;
 447
 448           str_copyc (path, arg);
 449         }
 450       else if (arg[0] == '/')
 451         str_trunc (path, 0);    /* Null path for root directory.  */
 452       else
 453         str_copyc (path, arg);
 454
 455       if (!opt_combined_arguments)
 456         hash_reset ();
 457
 458       count_entry (arg, 1, 0);
 459
 460       /* chdir if `count_entry' has changed the working directory.  */
 461       if (stat (".", &stat_buf))
 462         error (1, errno, ".");
 463       if (stat_buf.st_ino != initial_ino || stat_buf.st_dev != initial_dev)
 464         {
 465           if (restore_cwd (&cwd, _("starting directory"), NULL))
 466             exit (1);
 467         }
 468     }
 469
 470   if (opt_combined_arguments)
 471     {
 472       if (opt_human_readable)
 473         {
 474           char buf[LONGEST_HUMAN_READABLE + 1];
 475           printf("%s\ttotal\n", human_readable (tot_size, buf,
 476                                                 LONGEST_HUMAN_READABLE + 1));
 477         }
 478       else
 479         {
 480           printf (_("%ld\ttotal\n"), output_size == size_bytes ? tot_size
 481                   : convert_blocks (tot_size, output_size == size_kilobytes));
 482         }
 483       fflush (stdout);
 484     }
 485
 486   free_cwd (&cwd);
 487 }
 488
 489 /* Print (if appropriate) and return the size
 490    (in units determined by `output_size') of file or directory ENT.
 491    TOP is one for external calls, zero for recursive calls.
 492    LAST_DEV is the device that the parent directory of ENT is on.  */
 493
 494 static long
 495 count_entry (char *ent, int top, dev_t last_dev)
 496 {
 497   long size;
 498
 499   if (((top && opt_dereference_arguments)
 500        ? stat (ent, &stat_buf)
 501        : (*xstat) (ent, &stat_buf)) < 0)
 502     {
 503       error (0, errno, "%s", path->text);
 504       exit_status = 1;
 505       return 0;
 506     }
 507
 508   if (!opt_count_all
 509       && stat_buf.st_nlink > 1
 510       && hash_insert (stat_buf.st_ino, stat_buf.st_dev))
 511     return 0;                   /* Have counted this already.  */
 512
 513   if (output_size == size_bytes)
 514     size = stat_buf.st_size;
 515   else
 516     size = ST_NBLOCKS (stat_buf);
 517
 518   tot_size += size;
 519
 520   if (S_ISDIR (stat_buf.st_mode))
 521     {
 522       unsigned pathlen;
 523       dev_t dir_dev;
 524       char *name_space;
 525       char *namep;
 526       struct saved_cwd cwd;
 527       int through_symlink;
 528       struct stat e_buf;
 529
 530       dir_dev = stat_buf.st_dev;
 531
 532       if (opt_one_file_system && !top && last_dev != dir_dev)
 533         return 0;               /* Don't enter a new file system.  */
 534
 535 #ifndef S_ISDIR
 536 # define S_ISDIR(s) 0
 537 #endif
 538       /* If we're dereferencing symlinks and we're about to chdir through
 539          a symlink, remember the current directory so we can return to it
 540          later.  In other cases, chdir ("..") works fine.  */
 541       through_symlink = (xstat == stat
 542                          && lstat (ent, &e_buf) == 0
 543                          && S_ISLNK (e_buf.st_mode));
 544       if (through_symlink)
 545         if (save_cwd (&cwd))
 546           exit (1);
 547
 548       if (chdir (ent) < 0)
 549         {
 550           error (0, errno, _("cannot change to directory %s"), path->text);
 551           exit_status = 1;
 552           return 0;
 553         }
 554
 555       errno = 0;
 556       name_space = savedir (".", stat_buf.st_size);
 557       if (name_space == NULL)
 558         {
 559           if (errno)
 560             {
 561               error (0, errno, "%s", path->text);
 562               if (through_symlink)
 563                 {
 564                   if (restore_cwd (&cwd, "..", path->text))
 565                     exit (1);
 566                   free_cwd (&cwd);
 567                 }
 568               else if (chdir ("..") < 0)
 569                   error (1, errno, _("cannot change to `..' from directory %s"),
 570                          path->text);
 571               exit_status = 1;
 572               return 0;
 573             }
 574           else
 575             error (1, 0, _("virtual memory exhausted"));
 576         }
 577
 578       /* Remember the current path.  */
 579
 580       str_concatc (path, "/");
 581       pathlen = path->length;
 582
 583       namep = name_space;
 584       while (*namep != 0)
 585         {
 586           str_concatc (path, namep);
 587
 588           size += count_entry (namep, 0, dir_dev);
 589
 590           str_trunc (path, pathlen);
 591           namep += strlen (namep) + 1;
 592         }
 593       free (name_space);
 594       if (through_symlink)
 595         {
 596           restore_cwd (&cwd, "..", path->text);
 597           free_cwd (&cwd);
 598         }
 599       else if (chdir ("..") < 0)
 600         error (1, errno,
 601                _("cannot change to `..' from directory %s"), path->text);
 602
 603       str_trunc (path, pathlen - 1); /* Remove the "/" we added.  */
 604       if (!opt_summarize_only || top)
 605         {
 606           if (opt_human_readable)
 607             {
 608               char buf[LONGEST_HUMAN_READABLE + 1];
 609               printf("%s\t%s\n",
 610                      human_readable (size, buf, LONGEST_HUMAN_READABLE + 1),
 611                      path->length > 0 ? path->text : "/");
 612             }
 613           else
 614             {
 615               printf ("%ld\t%s\n", (output_size == size_bytes
 616                                     ? size
 617                                     : convert_blocks (size, output_size)),
 618                       path->length > 0 ? path->text : "/");
 619             }
 620           fflush (stdout);
 621         }
 622       return opt_separate_dirs ? 0 : size;
 623     }
 624   else if (opt_all || top)
 625     {
 626       /* FIXME: make this an option.  */
 627       int print_only_dir_size = 0;
 628       if (!print_only_dir_size)
 629         {
 630           if (opt_human_readable)
 631             {
 632               char buf[LONGEST_HUMAN_READABLE + 1];
 633               printf("%s\t%s\n",
 634                      human_readable (size, buf, LONGEST_HUMAN_READABLE + 1),
 635                      path->length > 0 ? path->text : "/");
 636             }
 637           else
 638             {
 639               printf ("%ld\t%s\n", output_size == size_bytes ? size
 640                       : convert_blocks (size, output_size),
 641                       path->text);
 642             }
 643           fflush (stdout);
 644         }
 645     }
 646
 647   return size;
 648 }
 649
 650 /* Allocate space for the hash structures, and set the global
 651    variable `htab' to point to it.  The initial hash module is specified in
 652    MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE.  (The
 653    hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been
 654    inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be
 655    doubled.)  */
 656
 657 static void
 658 hash_init (unsigned int modulus, unsigned int entry_tab_size)
 659 {
 660   struct htab *htab_r;
 661
 662   htab_r = (struct htab *)
 663     xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus);
 664
 665   htab_r->entry_tab = (struct entry *)
 666     xmalloc (sizeof (struct entry) * entry_tab_size);
 667
 668   htab_r->modulus = modulus;
 669   htab_r->entry_tab_size = entry_tab_size;
 670   htab = htab_r;
 671
 672   hash_reset ();
 673 }
 674
 675 /* Reset the hash structure in the global variable `htab' to
 676    contain no entries.  */
 677
 678 static void
 679 hash_reset (void)
 680 {
 681   int i;
 682   struct entry **p;
 683
 684   htab->first_free_entry = 0;
 685
 686   p = htab->hash;
 687   for (i = htab->modulus; i > 0; i--)
 688     *p++ = NULL;
 689 }
 690
 691 /* Insert an item (inode INO and device DEV) in the hash
 692    structure in the global variable `htab', if an entry with the same data
 693    was not found already.  Return zero if the item was inserted and nonzero
 694    if it wasn't.  */
 695
 696 static int
 697 hash_insert (ino_t ino, dev_t dev)
 698 {
 699   struct htab *htab_r = htab;   /* Initially a copy of the global `htab'.  */
 700
 701   if (htab_r->first_free_entry >= htab_r->entry_tab_size)
 702     {
 703       int i;
 704       struct entry *ep;
 705       unsigned modulus;
 706       unsigned entry_tab_size;
 707
 708       /* Increase the number of hash entries, and re-hash the data.
 709          The method of shrimping and increasing is made to compactify
 710          the heap.  If twice as much data would be allocated
 711          straightforwardly, we would never re-use a byte of memory.  */
 712
 713       /* Let `htab' shrimp.  Keep only the header, not the pointer vector.  */
 714
 715       htab_r = (struct htab *)
 716         xrealloc ((char *) htab_r, sizeof (struct htab));
 717
 718       modulus = 2 * htab_r->modulus;
 719       entry_tab_size = 2 * htab_r->entry_tab_size;
 720
 721       /* Increase the number of possible entries.  */
 722
 723       htab_r->entry_tab = (struct entry *)
 724         xrealloc ((char *) htab_r->entry_tab,
 725                  sizeof (struct entry) * entry_tab_size);
 726
 727       /* Increase the size of htab again.  */
 728
 729       htab_r = (struct htab *)
 730         xrealloc ((char *) htab_r,
 731                  sizeof (struct htab) + sizeof (struct entry *) * modulus);
 732
 733       htab_r->modulus = modulus;
 734       htab_r->entry_tab_size = entry_tab_size;
 735       htab = htab_r;
 736
 737       i = htab_r->first_free_entry;
 738
 739       /* Make the increased hash table empty.  The entries are still
 740          available in htab->entry_tab.  */
 741
 742       hash_reset ();
 743
 744       /* Go through the entries and install them in the pointer vector
 745          htab->hash.  The items are actually inserted in htab->entry_tab at
 746          the position where they already are.  The htab->coll_link need
 747          however be updated.  Could be made a little more efficient.  */
 748
 749       for (ep = htab_r->entry_tab; i > 0; i--)
 750         {
 751           hash_insert2 (htab_r, ep->ino, ep->dev);
 752           ep++;
 753         }
 754     }
 755
 756   return hash_insert2 (htab_r, ino, dev);
 757 }
 758
 759 /* Insert INO and DEV in the hash structure HTAB, if not
 760    already present.  Return zero if inserted and nonzero if it
 761    already existed.  */
 762
 763 static int
 764 hash_insert2 (struct htab *htab, ino_t ino, dev_t dev)
 765 {
 766   struct entry **hp, *ep2, *ep;
 767   hp = &htab->hash[ino % htab->modulus];
 768   ep2 = *hp;
 769
 770   /* Collision?  */
 771
 772   if (ep2 != NULL)
 773     {
 774       ep = ep2;
 775
 776       /* Search for an entry with the same data.  */
 777
 778       do
 779         {
 780           if (ep->ino == ino && ep->dev == dev)
 781             return 1;           /* Found an entry with the same data.  */
 782           ep = ep->coll_link;
 783         }
 784       while (ep != NULL);
 785
 786       /* Did not find it.  */
 787
 788     }
 789
 790   ep = *hp = &htab->entry_tab[htab->first_free_entry++];
 791   ep->ino = ino;
 792   ep->dev = dev;
 793   ep->coll_link = ep2;          /* `ep2' is NULL if no collision.  */
 794
 795   return 0;
 796 }
 797
 798 /* Initialize the struct string S1 for holding SIZE characters.  */
 799
 800 static void
 801 str_init (string *s1, unsigned int size)
 802 {
 803   string s;
 804
 805   s = (string) xmalloc (sizeof (stringstruct));
 806   s->text = xmalloc (size + 1);
 807
 808   s->alloc = size;
 809   *s1 = s;
 810 }
 811
 812 static void
 813 ensure_space (string s, unsigned int size)
 814 {
 815   if (s->alloc < size)
 816     {
 817       s->text = xrealloc (s->text, size + 1);
 818       s->alloc = size;
 819     }
 820 }
 821
 822 /* Assign the null-terminated C-string CSTR to S1.  */
 823
 824 static void
 825 str_copyc (string s1, char *cstr)
 826 {
 827   unsigned l = strlen (cstr);
 828   ensure_space (s1, l);
 829   strcpy (s1->text, cstr);
 830   s1->length = l;
 831 }
 832
 833 static void
 834 str_concatc (string s1, char *cstr)
 835 {
 836   unsigned l1 = s1->length;
 837   unsigned l2 = strlen (cstr);
 838   unsigned l = l1 + l2;
 839
 840   ensure_space (s1, l);
 841   strcpy (s1->text + l1, cstr);
 842   s1->length = l;
 843 }
 844
 845 /* Truncate the string S1 to have length LENGTH.  */
 846
 847 static void
 848 str_trunc (string s1, unsigned int length)
 849 {
 850   if (s1->length > length)
 851     {
 852       s1->text[length] = 0;
 853       s1->length = length;
 854     }
 855 }