1/* 2 * Copyright (c) 1989, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Chris Newcomb. 7 * 8 * Redistribution and use in source and binary forms, with or without --- 32 unchanged lines hidden (view full) --- 41#endif /* not lint */ 42 43#ifndef lint 44#if 0 45static const char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95"; 46#endif 47#endif /* not lint */ 48#include <sys/cdefs.h> |
49__FBSDID("$FreeBSD: head/usr.bin/du/du.c 128806 2004-05-01 21:47:31Z kientzle $"); |
50 51#include <sys/param.h> 52#include <sys/queue.h> 53#include <sys/stat.h> 54 55#include <err.h> 56#include <errno.h> 57#include <fnmatch.h> --- 247 unchanged lines hidden (view full) --- 305 306 ignoreclean(); 307 exit(rval); 308} 309 310static int 311linkchk(FTSENT *p) 312{ |
313 struct links_entry { |
314 struct links_entry *next; 315 struct links_entry *previous; 316 int links; 317 dev_t dev; 318 ino_t ino; |
319 }; |
320 static const size_t links_hash_initial_size = 8192; 321 static struct links_entry **buckets; 322 static struct links_entry *free_list; 323 static size_t number_buckets; 324 static unsigned long number_entries; 325 static char stop_allocating; 326 struct links_entry *le, **new_buckets; 327 struct stat *st; 328 size_t i, new_size; 329 int count; 330 int hash; |
331 |
332 st = p->fts_statp; 333 334 /* If necessary, initialize the hash table. */ 335 if (buckets == NULL) { 336 number_buckets = links_hash_initial_size; 337 buckets = malloc(number_buckets * sizeof(buckets[0])); 338 if (buckets == NULL) |
339 errx(1, "No memory for hardlink detection."); |
340 for (i = 0; i < number_buckets; i++) 341 buckets[i] = NULL; 342 } 343 344 /* If the hash table is getting too full, enlarge it. */ 345 if (number_entries > number_buckets * 10 && !stop_allocating) { |
346 347 new_size = number_buckets * 2; 348 new_buckets = malloc(new_size * sizeof(struct links_entry *)); 349 count = 0; 350 351 /* Try releasing the free list to see if that helps. */ 352 if (new_buckets == NULL && free_list != NULL) { 353 while (free_list != NULL) { 354 le = free_list; 355 free_list = le->next; 356 free(le); 357 } 358 new_buckets = malloc(new_size * sizeof(new_buckets[0])); 359 } 360 361 if (new_buckets == NULL) { 362 stop_allocating = 1; |
363 warnx("No more memory for tracking hard links."); |
364 } else { 365 memset(new_buckets, 0, 366 new_size * sizeof(struct links_entry *)); 367 for (i = 0; i < number_buckets; i++) { 368 while (buckets[i] != NULL) { 369 /* Remove entry from old bucket. */ 370 le = buckets[i]; 371 buckets[i] = le->next; --- 51 unchanged lines hidden (view full) --- 423 /* Pull a node from the free list if we can. */ 424 le = free_list; 425 free_list = le->next; 426 } else 427 /* Malloc one if we have to. */ 428 le = malloc(sizeof(struct links_entry)); 429 if (le == NULL) { 430 stop_allocating = 1; |
431 warnx("No more memory for tracking hard links."); |
432 return (0); 433 } 434 le->dev = st->st_dev; 435 le->ino = st->st_ino; 436 le->links = st->st_nlink - 1; 437 number_entries++; 438 le->next = buckets[hash]; 439 le->previous = NULL; --- 94 unchanged lines hidden --- |