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