1 /* Directory hashing for GNU Make.
2 Copyright (C) 1988, 1989, 1991, 1992, 1993 Free Software Foundation, Inc.
3 This file is part of GNU Make.
5 GNU Make is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 GNU Make is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNU Make; see the file COPYING. If not, write to
17 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21 #if defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__)
23 #ifndef __GNU_LIBRARY__
24 #define D_NAMLEN(d) strlen((d)->d_name)
25 #else /* GNU C library. */
26 #define D_NAMLEN(d) ((d)->d_namlen)
27 #endif /* Not GNU C library. */
28 #else /* Not POSIX or DIRENT. */
30 #define D_NAMLEN(d) ((d)->d_namlen)
40 #endif /* POSIX or DIRENT or __GNU_LIBRARY__. */
42 #if defined (POSIX) && !defined (__GNU_LIBRARY__)
43 /* Posix does not require that the d_ino field be present, and some
44 systems do not provide it. */
45 #define REAL_DIR_ENTRY(dp) 1
47 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
50 /* Hash table of directories. */
52 #ifndef DIRECTORY_BUCKETS
53 #define DIRECTORY_BUCKETS 199
56 struct directory_contents
58 struct directory_contents
*next
;
60 int dev
, ino
; /* Device and inode numbers of this dir. */
62 struct dirfile
**files
; /* Files in this directory. */
63 DIR *dirstream
; /* Stream reading this directory. */
66 /* Table of directory contents hashed by device and inode number. */
67 static struct directory_contents
*directories_contents
[DIRECTORY_BUCKETS
];
71 struct directory
*next
;
73 char *name
; /* Name of the directory. */
75 /* The directory's contents. This data may be shared by several
76 entries in the hash table, which refer to the same directory
77 (identified uniquely by `dev' and `ino') under different names. */
78 struct directory_contents
*contents
;
81 /* Table of directories hashed by name. */
82 static struct directory
*directories
[DIRECTORY_BUCKETS
];
85 /* Never have more than this many directories open at once. */
87 #define MAX_OPEN_DIRECTORIES 10
89 static unsigned int open_directories
= 0;
92 /* Hash table of files in each directory. */
97 char *name
; /* Name of the file. */
98 char impossible
; /* This file is impossible. */
101 #ifndef DIRFILE_BUCKETS
102 #define DIRFILE_BUCKETS 107
105 static int dir_contents_file_exists_p ();
107 /* Find the directory named NAME and return its `struct directory'. */
109 static struct directory
*
110 find_directory (name
)
113 register unsigned int hash
= 0;
115 register struct directory
*dir
;
117 for (p
= name
; *p
!= '\0'; ++p
)
119 hash
%= DIRECTORY_BUCKETS
;
121 for (dir
= directories
[hash
]; dir
!= 0; dir
= dir
->next
)
122 if (streq (dir
->name
, name
))
129 /* The directory was not found. Create a new entry for it. */
131 dir
= (struct directory
*) xmalloc (sizeof (struct directory
));
132 dir
->next
= directories
[hash
];
133 directories
[hash
] = dir
;
134 dir
->name
= savestring (name
, p
- name
);
136 /* The directory is not in the name hash table.
137 Find its device and inode numbers, and look it up by them. */
139 if (stat (name
, &st
) < 0)
140 /* Couldn't stat the directory. Mark this by
141 setting the `contents' member to a nil pointer. */
145 /* Search the contents hash table; device and inode are the key. */
147 struct directory_contents
*dc
;
149 hash
= ((unsigned int) st
.st_dev
<< 16) | (unsigned int) st
.st_ino
;
150 hash
%= DIRECTORY_BUCKETS
;
152 for (dc
= directories_contents
[hash
]; dc
!= 0; dc
= dc
->next
)
153 if (dc
->dev
== st
.st_dev
&& dc
->ino
== st
.st_ino
)
158 /* Nope; this really is a directory we haven't seen before. */
160 dc
= (struct directory_contents
*)
161 xmalloc (sizeof (struct directory_contents
));
163 /* Enter it in the contents hash table. */
166 dc
->next
= directories_contents
[hash
];
167 directories_contents
[hash
] = dc
;
169 dc
->dirstream
= opendir (name
);
170 if (dc
->dirstream
== 0)
171 /* Couldn't open the directory. Mark this by
172 setting the `files' member to a nil pointer. */
176 /* Allocate an array of buckets for files and zero it. */
177 dc
->files
= (struct dirfile
**)
178 xmalloc (sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
179 bzero ((char *) dc
->files
,
180 sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
182 /* Keep track of how many directories are open. */
184 if (open_directories
== MAX_OPEN_DIRECTORIES
)
185 /* We have too many directories open already.
186 Read the entire directory and then close it. */
187 (void) dir_contents_file_exists_p (dc
, (char *) 0);
191 /* Point the name-hashed entry for DIR at its contents data. */
199 /* Return 1 if the name FILENAME is entered in DIR's hash table.
200 FILENAME must contain no slashes. */
203 dir_contents_file_exists_p (dir
, filename
)
204 register struct directory_contents
*dir
;
205 register char *filename
;
207 register unsigned int hash
;
209 register struct dirfile
*df
;
210 register struct dirent
*d
;
212 if (dir
== 0 || dir
->files
== 0)
213 /* The directory could not be stat'd or opened. */
219 if (*filename
== '\0')
220 /* Checking if the directory exists. */
223 for (p
= filename
; *p
!= '\0'; ++p
)
225 hash
%= DIRFILE_BUCKETS
;
227 /* Search the list of hashed files. */
229 for (df
= dir
->files
[hash
]; df
!= 0; df
= df
->next
)
230 if (streq (df
->name
, filename
))
231 return !df
->impossible
;
234 /* The file was not found in the hashed list.
235 Try to read the directory further. */
237 if (dir
->dirstream
== 0)
238 /* The directory has been all read in. */
241 while ((d
= readdir (dir
->dirstream
)) != 0)
243 /* Enter the file in the hash table. */
244 register unsigned int newhash
= 0;
246 register unsigned int i
;
248 if (!REAL_DIR_ENTRY (d
))
252 while (d
->d_name
[len
- 1] == '\0')
255 for (i
= 0; i
< len
; ++i
)
256 HASH (newhash
, d
->d_name
[i
]);
257 newhash
%= DIRFILE_BUCKETS
;
259 df
= (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
260 df
->next
= dir
->files
[newhash
];
261 dir
->files
[newhash
] = df
;
262 df
->name
= savestring (d
->d_name
, len
);
265 /* Check if the name matches the one we're searching for. */
267 && newhash
== hash
&& streq (d
->d_name
, filename
))
271 /* If the directory has been completely read in,
272 close the stream and reset the pointer to nil. */
276 closedir (dir
->dirstream
);
283 /* Return 1 if the name FILENAME in directory DIRNAME
284 is entered in the dir hash table.
285 FILENAME must contain no slashes. */
288 dir_file_exists_p (dirname
, filename
)
289 register char *dirname
;
290 register char *filename
;
292 return dir_contents_file_exists_p (find_directory (dirname
)->contents
,
296 /* Return 1 if the file named NAME exists. */
307 return ar_member_date (name
) != (time_t) -1;
310 dirend
= rindex (name
, '/');
312 return dir_file_exists_p (".", name
);
314 dirname
= (char *) alloca (dirend
- name
+ 1);
315 bcopy (name
, dirname
, dirend
- name
);
316 dirname
[dirend
- name
] = '\0';
317 return dir_file_exists_p (dirname
, dirend
+ 1);
320 /* Mark FILENAME as `impossible' for `file_impossible_p'.
321 This means an attempt has been made to search for FILENAME
322 as an intermediate file, and it has failed. */
325 file_impossible (filename
)
326 register char *filename
;
329 register char *p
= filename
;
330 register unsigned int hash
;
331 register struct directory
*dir
;
332 register struct dirfile
*new;
334 dirend
= rindex (p
, '/');
336 dir
= find_directory (".");
339 char *dirname
= (char *) alloca (dirend
- p
+ 1);
340 bcopy (p
, dirname
, dirend
- p
);
341 dirname
[dirend
- p
] = '\0';
342 dir
= find_directory (dirname
);
343 filename
= p
= dirend
+ 1;
346 for (hash
= 0; *p
!= '\0'; ++p
)
348 hash
%= DIRFILE_BUCKETS
;
350 if (dir
->contents
== 0)
352 /* The directory could not be stat'd. We allocate a contents
353 structure for it, but leave it out of the contents hash table. */
354 dir
->contents
= (struct directory_contents
*)
355 xmalloc (sizeof (struct directory_contents
));
356 dir
->contents
->dev
= dir
->contents
->ino
= 0;
357 dir
->contents
->files
= 0;
358 dir
->contents
->dirstream
= 0;
361 if (dir
->contents
->files
== 0)
363 /* The directory was not opened; we must allocate the hash buckets. */
364 dir
->contents
->files
= (struct dirfile
**)
365 xmalloc (sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
366 bzero ((char *) dir
->contents
->files
,
367 sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
370 /* Make a new entry and put it in the table. */
372 new = (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
373 new->next
= dir
->contents
->files
[hash
];
374 dir
->contents
->files
[hash
] = new;
375 new->name
= savestring (filename
, strlen (filename
));
379 /* Return nonzero if FILENAME has been marked impossible. */
382 file_impossible_p (filename
)
386 register char *p
= filename
;
387 register unsigned int hash
;
388 register struct directory_contents
*dir
;
389 register struct dirfile
*next
;
391 dirend
= rindex (filename
, '/');
393 dir
= find_directory (".")->contents
;
396 char *dirname
= (char *) alloca (dirend
- filename
+ 1);
397 bcopy (p
, dirname
, dirend
- p
);
398 dirname
[dirend
- p
] = '\0';
399 dir
= find_directory (dirname
)->contents
;
403 if (dir
== 0 || dir
->files
== 0)
404 /* There are no files entered for this directory. */
407 for (hash
= 0; *p
!= '\0'; ++p
)
409 hash
%= DIRFILE_BUCKETS
;
411 for (next
= dir
->files
[hash
]; next
!= 0; next
= next
->next
)
412 if (streq (filename
, next
->name
))
413 return next
->impossible
;
418 /* Return the already allocated name in the
419 directory hash table that matches DIR. */
425 return find_directory (dir
)->name
;
428 /* Print the data base of directories. */
431 print_dir_data_base ()
433 register unsigned int i
, dirs
, files
, impossible
;
434 register struct directory
*dir
;
436 puts ("\n# Directories\n");
438 dirs
= files
= impossible
= 0;
439 for (i
= 0; i
< DIRECTORY_BUCKETS
; ++i
)
440 for (dir
= directories
[i
]; dir
!= 0; dir
= dir
->next
)
443 if (dir
->contents
== 0)
444 printf ("# %s: could not be stat'd.\n", dir
->name
);
445 else if (dir
->contents
->files
== 0)
446 printf ("# %s (device %d, inode %d): could not be opened.\n",
447 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
450 register unsigned int f
= 0, im
= 0;
451 register unsigned int j
;
452 register struct dirfile
*df
;
453 for (j
= 0; j
< DIRFILE_BUCKETS
; ++j
)
454 for (df
= dir
->contents
->files
[j
]; df
!= 0; df
= df
->next
)
459 printf ("# %s (device %d, inode %d): ",
460 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
462 fputs ("No", stdout
);
465 fputs (" files, ", stdout
);
467 fputs ("no", stdout
);
470 fputs (" impossibilities", stdout
);
471 if (dir
->contents
->dirstream
== 0)
480 fputs ("\n# ", stdout
);
482 fputs ("No", stdout
);
484 printf ("%u", files
);
485 fputs (" files, ", stdout
);
487 fputs ("no", stdout
);
489 printf ("%u", impossible
);
490 printf (" impossibilities in %u directories.\n", dirs
);
493 /* Hooks for globbing. */
497 /* Structure describing state of iterating through a directory hash table. */
501 struct directory_contents
*contents
; /* The directory being read. */
503 unsigned int bucket
; /* Current hash bucket. */
504 struct dirfile
*elt
; /* Current elt in bucket. */
507 /* Forward declarations. */
508 static __ptr_t open_dirstream
__P ((const char *));
509 static const char *read_dirstream
__P ((__ptr_t
));
512 open_dirstream (directory
)
513 const char *directory
;
515 struct dirstream
*new;
516 struct directory
*dir
= find_directory (directory
);
518 if (dir
->contents
== 0 || dir
->contents
->files
== 0)
519 /* DIR->contents is nil if the directory could not be stat'd.
520 DIR->contents->files is nil if it could not be opened. */
523 /* Read all the contents of the directory now. There is no benefit
524 in being lazy, since glob will want to see every file anyway. */
526 (void) dir_contents_file_exists_p (dir
->contents
, (char *) 0);
528 new = (struct dirstream
*) xmalloc (sizeof (struct dirstream
));
529 new->contents
= dir
->contents
;
531 new->elt
= new->contents
->files
[0];
533 return (__ptr_t
) new;
537 read_dirstream (stream
)
540 struct dirstream
*const ds
= (struct dirstream
*) stream
;
541 register struct dirfile
*df
;
543 while (ds
->bucket
< DIRFILE_BUCKETS
)
545 while ((df
= ds
->elt
) != 0)
551 if (++ds
->bucket
== DIRFILE_BUCKETS
)
553 ds
->elt
= ds
->contents
->files
[ds
->bucket
];
562 __glob_opendir_hook
= open_dirstream
;
563 __glob_readdir_hook
= read_dirstream
;
564 __glob_closedir_hook
= (void (*) __P ((__ptr_t stream
))) free
;