1 /* Directory hashing for GNU Make.
2 Copyright (C) 1988, 89, 91, 92, 93, 94, 95, 96 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. */
23 # define NAMLEN(dirent) strlen((dirent)->d_name)
25 # define dirent direct
26 # define NAMLEN(dirent) (dirent)->d_namlen
27 # ifdef HAVE_SYS_NDIR_H
28 # include <sys/ndir.h>
30 # ifdef HAVE_SYS_DIR_H
38 /* In GNU systems, <dirent.h> defines this macro for us. */
41 #define NAMLEN(d) _D_NAMLEN(d)
44 #if defined (POSIX) && !defined (__GNU_LIBRARY__)
45 /* Posix does not require that the d_ino field be present, and some
46 systems do not provide it. */
47 #define REAL_DIR_ENTRY(dp) 1
48 #define FAKE_DIR_ENTRY(dp)
50 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
51 #define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
61 static char dos_filename
[14];
68 if (strpbrk (filename
, "\"*+,;<=>?[\\]|") != 0)
73 /* First, transform the name part. */
74 for (i
= 0; *filename
!= '\0' && i
< 8 && *filename
!= '.'; ++i
)
75 *df
++ = tolower (*filename
++);
77 /* Now skip to the next dot. */
78 while (*filename
!= '\0' && *filename
!= '.')
80 if (*filename
!= '\0')
83 for (i
= 0; *filename
!= '\0' && i
< 3 && *filename
!= '.'; ++i
)
84 *df
++ = tolower (*filename
++);
87 /* Look for more dots. */
88 while (*filename
!= '\0' && *filename
!= '.')
97 /* Hash table of directories. */
99 #ifndef DIRECTORY_BUCKETS
100 #define DIRECTORY_BUCKETS 199
103 struct directory_contents
105 struct directory_contents
*next
;
107 int dev
, ino
; /* Device and inode numbers of this dir. */
109 struct dirfile
**files
; /* Files in this directory. */
110 DIR *dirstream
; /* Stream reading this directory. */
113 /* Table of directory contents hashed by device and inode number. */
114 static struct directory_contents
*directories_contents
[DIRECTORY_BUCKETS
];
118 struct directory
*next
;
120 char *name
; /* Name of the directory. */
122 /* The directory's contents. This data may be shared by several
123 entries in the hash table, which refer to the same directory
124 (identified uniquely by `dev' and `ino') under different names. */
125 struct directory_contents
*contents
;
128 /* Table of directories hashed by name. */
129 static struct directory
*directories
[DIRECTORY_BUCKETS
];
132 /* Never have more than this many directories open at once. */
134 #define MAX_OPEN_DIRECTORIES 10
136 static unsigned int open_directories
= 0;
139 /* Hash table of files in each directory. */
143 struct dirfile
*next
;
144 char *name
; /* Name of the file. */
145 char impossible
; /* This file is impossible. */
148 #ifndef DIRFILE_BUCKETS
149 #define DIRFILE_BUCKETS 107
152 static int dir_contents_file_exists_p ();
154 /* Find the directory named NAME and return its `struct directory'. */
156 static struct directory
*
157 find_directory (name
)
160 register unsigned int hash
= 0;
162 register struct directory
*dir
;
164 for (p
= name
; *p
!= '\0'; ++p
)
166 hash
%= DIRECTORY_BUCKETS
;
168 for (dir
= directories
[hash
]; dir
!= 0; dir
= dir
->next
)
169 if (streq (dir
->name
, name
))
176 /* The directory was not found. Create a new entry for it. */
178 dir
= (struct directory
*) xmalloc (sizeof (struct directory
));
179 dir
->next
= directories
[hash
];
180 directories
[hash
] = dir
;
181 dir
->name
= savestring (name
, p
- name
);
183 /* The directory is not in the name hash table.
184 Find its device and inode numbers, and look it up by them. */
186 if (stat (name
, &st
) < 0)
187 /* Couldn't stat the directory. Mark this by
188 setting the `contents' member to a nil pointer. */
192 /* Search the contents hash table; device and inode are the key. */
194 struct directory_contents
*dc
;
196 hash
= ((unsigned int) st
.st_dev
<< 16) | (unsigned int) st
.st_ino
;
197 hash
%= DIRECTORY_BUCKETS
;
199 for (dc
= directories_contents
[hash
]; dc
!= 0; dc
= dc
->next
)
200 if (dc
->dev
== st
.st_dev
&& dc
->ino
== st
.st_ino
)
205 /* Nope; this really is a directory we haven't seen before. */
207 dc
= (struct directory_contents
*)
208 xmalloc (sizeof (struct directory_contents
));
210 /* Enter it in the contents hash table. */
213 dc
->next
= directories_contents
[hash
];
214 directories_contents
[hash
] = dc
;
216 dc
->dirstream
= opendir (name
);
217 if (dc
->dirstream
== 0)
218 /* Couldn't open the directory. Mark this by
219 setting the `files' member to a nil pointer. */
223 /* Allocate an array of buckets for files and zero it. */
224 dc
->files
= (struct dirfile
**)
225 xmalloc (sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
226 bzero ((char *) dc
->files
,
227 sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
229 /* Keep track of how many directories are open. */
231 if (open_directories
== MAX_OPEN_DIRECTORIES
)
232 /* We have too many directories open already.
233 Read the entire directory and then close it. */
234 (void) dir_contents_file_exists_p (dc
, (char *) 0);
238 /* Point the name-hashed entry for DIR at its contents data. */
246 /* Return 1 if the name FILENAME is entered in DIR's hash table.
247 FILENAME must contain no slashes. */
250 dir_contents_file_exists_p (dir
, filename
)
251 register struct directory_contents
*dir
;
252 register char *filename
;
254 register unsigned int hash
;
256 register struct dirfile
*df
;
257 register struct dirent
*d
;
259 if (dir
== 0 || dir
->files
== 0)
260 /* The directory could not be stat'd or opened. */
264 filename
= dosify (filename
);
270 if (*filename
== '\0')
271 /* Checking if the directory exists. */
274 for (p
= filename
; *p
!= '\0'; ++p
)
276 hash
%= DIRFILE_BUCKETS
;
278 /* Search the list of hashed files. */
280 for (df
= dir
->files
[hash
]; df
!= 0; df
= df
->next
)
281 if (streq (df
->name
, filename
))
282 return !df
->impossible
;
285 /* The file was not found in the hashed list.
286 Try to read the directory further. */
288 if (dir
->dirstream
== 0)
289 /* The directory has been all read in. */
292 while ((d
= readdir (dir
->dirstream
)) != 0)
294 /* Enter the file in the hash table. */
295 register unsigned int newhash
= 0;
297 register unsigned int i
;
299 if (!REAL_DIR_ENTRY (d
))
303 for (i
= 0; i
< len
; ++i
)
304 HASH (newhash
, d
->d_name
[i
]);
305 newhash
%= DIRFILE_BUCKETS
;
307 df
= (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
308 df
->next
= dir
->files
[newhash
];
309 dir
->files
[newhash
] = df
;
310 df
->name
= savestring (d
->d_name
, len
);
313 /* Check if the name matches the one we're searching for. */
315 && newhash
== hash
&& streq (d
->d_name
, filename
))
319 /* If the directory has been completely read in,
320 close the stream and reset the pointer to nil. */
324 closedir (dir
->dirstream
);
331 /* Return 1 if the name FILENAME in directory DIRNAME
332 is entered in the dir hash table.
333 FILENAME must contain no slashes. */
336 dir_file_exists_p (dirname
, filename
)
337 register char *dirname
;
338 register char *filename
;
340 return dir_contents_file_exists_p (find_directory (dirname
)->contents
,
344 /* Return 1 if the file named NAME exists. */
355 return ar_member_date (name
) != (time_t) -1;
358 dirend
= rindex (name
, '/');
360 return dir_file_exists_p (".", name
);
362 dirname
= (char *) alloca (dirend
- name
+ 1);
363 bcopy (name
, dirname
, dirend
- name
);
364 dirname
[dirend
- name
] = '\0';
365 return dir_file_exists_p (dirname
, dirend
+ 1);
368 /* Mark FILENAME as `impossible' for `file_impossible_p'.
369 This means an attempt has been made to search for FILENAME
370 as an intermediate file, and it has failed. */
373 file_impossible (filename
)
374 register char *filename
;
377 register char *p
= filename
;
378 register unsigned int hash
;
379 register struct directory
*dir
;
380 register struct dirfile
*new;
382 dirend
= rindex (p
, '/');
384 dir
= find_directory (".");
387 char *dirname
= (char *) alloca (dirend
- p
+ 1);
388 bcopy (p
, dirname
, dirend
- p
);
389 dirname
[dirend
- p
] = '\0';
390 dir
= find_directory (dirname
);
391 filename
= p
= dirend
+ 1;
394 for (hash
= 0; *p
!= '\0'; ++p
)
396 hash
%= DIRFILE_BUCKETS
;
398 if (dir
->contents
== 0)
400 /* The directory could not be stat'd. We allocate a contents
401 structure for it, but leave it out of the contents hash table. */
402 dir
->contents
= (struct directory_contents
*)
403 xmalloc (sizeof (struct directory_contents
));
404 dir
->contents
->dev
= dir
->contents
->ino
= 0;
405 dir
->contents
->files
= 0;
406 dir
->contents
->dirstream
= 0;
409 if (dir
->contents
->files
== 0)
411 /* The directory was not opened; we must allocate the hash buckets. */
412 dir
->contents
->files
= (struct dirfile
**)
413 xmalloc (sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
414 bzero ((char *) dir
->contents
->files
,
415 sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
418 /* Make a new entry and put it in the table. */
420 new = (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
421 new->next
= dir
->contents
->files
[hash
];
422 dir
->contents
->files
[hash
] = new;
423 new->name
= savestring (filename
, strlen (filename
));
427 /* Return nonzero if FILENAME has been marked impossible. */
430 file_impossible_p (filename
)
434 register char *p
= filename
;
435 register unsigned int hash
;
436 register struct directory_contents
*dir
;
437 register struct dirfile
*next
;
439 dirend
= rindex (filename
, '/');
441 dir
= find_directory (".")->contents
;
444 char *dirname
= (char *) alloca (dirend
- filename
+ 1);
445 bcopy (p
, dirname
, dirend
- p
);
446 dirname
[dirend
- p
] = '\0';
447 dir
= find_directory (dirname
)->contents
;
448 p
= filename
= dirend
+ 1;
451 if (dir
== 0 || dir
->files
== 0)
452 /* There are no files entered for this directory. */
456 p
= filename
= dosify (p
);
459 for (hash
= 0; *p
!= '\0'; ++p
)
461 hash
%= DIRFILE_BUCKETS
;
463 for (next
= dir
->files
[hash
]; next
!= 0; next
= next
->next
)
464 if (streq (filename
, next
->name
))
465 return next
->impossible
;
470 /* Return the already allocated name in the
471 directory hash table that matches DIR. */
477 return find_directory (dir
)->name
;
480 /* Print the data base of directories. */
483 print_dir_data_base ()
485 register unsigned int i
, dirs
, files
, impossible
;
486 register struct directory
*dir
;
488 puts ("\n# Directories\n");
490 dirs
= files
= impossible
= 0;
491 for (i
= 0; i
< DIRECTORY_BUCKETS
; ++i
)
492 for (dir
= directories
[i
]; dir
!= 0; dir
= dir
->next
)
495 if (dir
->contents
== 0)
496 printf ("# %s: could not be stat'd.\n", dir
->name
);
497 else if (dir
->contents
->files
== 0)
498 printf ("# %s (device %d, inode %d): could not be opened.\n",
499 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
502 register unsigned int f
= 0, im
= 0;
503 register unsigned int j
;
504 register struct dirfile
*df
;
505 for (j
= 0; j
< DIRFILE_BUCKETS
; ++j
)
506 for (df
= dir
->contents
->files
[j
]; df
!= 0; df
= df
->next
)
511 printf ("# %s (device %d, inode %d): ",
512 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
514 fputs ("No", stdout
);
517 fputs (" files, ", stdout
);
519 fputs ("no", stdout
);
522 fputs (" impossibilities", stdout
);
523 if (dir
->contents
->dirstream
== 0)
532 fputs ("\n# ", stdout
);
534 fputs ("No", stdout
);
536 printf ("%u", files
);
537 fputs (" files, ", stdout
);
539 fputs ("no", stdout
);
541 printf ("%u", impossible
);
542 printf (" impossibilities in %u directories.\n", dirs
);
545 /* Hooks for globbing. */
549 /* Structure describing state of iterating through a directory hash table. */
553 struct directory_contents
*contents
; /* The directory being read. */
555 unsigned int bucket
; /* Current hash bucket. */
556 struct dirfile
*elt
; /* Current elt in bucket. */
559 /* Forward declarations. */
560 static __ptr_t open_dirstream
__P ((const char *));
561 static struct dirent
*read_dirstream
__P ((__ptr_t
));
564 open_dirstream (directory
)
565 const char *directory
;
567 struct dirstream
*new;
568 struct directory
*dir
= find_directory (directory
);
570 if (dir
->contents
== 0 || dir
->contents
->files
== 0)
571 /* DIR->contents is nil if the directory could not be stat'd.
572 DIR->contents->files is nil if it could not be opened. */
575 /* Read all the contents of the directory now. There is no benefit
576 in being lazy, since glob will want to see every file anyway. */
578 (void) dir_contents_file_exists_p (dir
->contents
, (char *) 0);
580 new = (struct dirstream
*) xmalloc (sizeof (struct dirstream
));
581 new->contents
= dir
->contents
;
583 new->elt
= new->contents
->files
[0];
585 return (__ptr_t
) new;
588 static struct dirent
*
589 read_dirstream (stream
)
592 struct dirstream
*const ds
= (struct dirstream
*) stream
;
593 register struct dirfile
*df
;
595 static unsigned int bufsz
;
597 while (ds
->bucket
< DIRFILE_BUCKETS
)
599 while ((df
= ds
->elt
) != 0)
604 /* The glob interface wants a `struct dirent',
607 unsigned int len
= strlen (df
->name
) + 1;
608 if (sizeof *d
- sizeof d
->d_name
+ len
> bufsz
)
613 if (sizeof *d
- sizeof d
->d_name
+ len
> bufsz
)
614 bufsz
= sizeof *d
- sizeof d
->d_name
+ len
;
615 buf
= xmalloc (bufsz
);
617 d
= (struct dirent
*) buf
;
619 #ifdef _DIRENT_HAVE_D_NAMLEN
620 d
->d_namlen
= len
- 1;
622 memcpy (d
->d_name
, df
->name
, len
);
626 if (++ds
->bucket
== DIRFILE_BUCKETS
)
628 ds
->elt
= ds
->contents
->files
[ds
->bucket
];
640 /* Bogus sunos4 compiler complains (!) about & before functions. */
641 gl
->gl_opendir
= open_dirstream
;
642 gl
->gl_readdir
= read_dirstream
;
643 gl
->gl_closedir
= free
;
645 /* We don't bother setting gl_lstat, since glob never calls it.
646 The slot is only there for compatibility with 4.4 BSD. */