src/du.c

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