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 # endif /* HAVE_VMSDIR_H */
41 /* In GNU systems, <dirent.h> defines this macro for us. */
44 #define NAMLEN(d) _D_NAMLEN(d)
47 #if defined (POSIX) && !defined (__GNU_LIBRARY__)
48 /* Posix does not require that the d_ino field be present, and some
49 systems do not provide it. */
50 #define REAL_DIR_ENTRY(dp) 1
51 #define FAKE_DIR_ENTRY(dp)
53 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
54 #define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
64 static char dos_filename
[14];
71 if (strpbrk (filename
, "\"*+,;<=>?[\\]|") != 0)
76 /* First, transform the name part. */
77 for (i
= 0; *filename
!= '\0' && i
< 8 && *filename
!= '.'; ++i
)
78 *df
++ = tolower (*filename
++);
80 /* Now skip to the next dot. */
81 while (*filename
!= '\0' && *filename
!= '.')
83 if (*filename
!= '\0')
86 for (i
= 0; *filename
!= '\0' && i
< 3 && *filename
!= '.'; ++i
)
87 *df
++ = tolower (*filename
++);
90 /* Look for more dots. */
91 while (*filename
!= '\0' && *filename
!= '.')
98 #endif /* __MSDOS__ */
107 static char amiga_filename
[136];
116 /* First, transform the name part. */
117 for (i
= 0; *filename
!= '\0'; ++i
)
119 *df
++ = tolower (*filename
);
125 return amiga_filename
;
140 h
= (h
<< 4) + *name
++;
151 /* fake stat entry for a directory */
153 vmsstat_dir (name
, st
)
161 dir
= opendir (name
);
165 s
= strchr (name
, ':'); /* find device */
169 st
->st_dev
= (char *)vms_hash (name
);
177 st
->st_ino
[0] = h
& 0xff;
178 st
->st_ino
[1] = h
& 0xff00;
179 st
->st_ino
[2] = h
>> 16;
185 /* Hash table of directories. */
187 #ifndef DIRECTORY_BUCKETS
188 #define DIRECTORY_BUCKETS 199
191 struct directory_contents
193 struct directory_contents
*next
;
195 dev_t dev
; /* Device and inode numbers of this dir. */
201 struct dirfile
**files
; /* Files in this directory. */
202 DIR *dirstream
; /* Stream reading this directory. */
205 /* Table of directory contents hashed by device and inode number. */
206 static struct directory_contents
*directories_contents
[DIRECTORY_BUCKETS
];
210 struct directory
*next
;
212 char *name
; /* Name of the directory. */
214 /* The directory's contents. This data may be shared by several
215 entries in the hash table, which refer to the same directory
216 (identified uniquely by `dev' and `ino') under different names. */
217 struct directory_contents
*contents
;
220 /* Table of directories hashed by name. */
221 static struct directory
*directories
[DIRECTORY_BUCKETS
];
224 /* Never have more than this many directories open at once. */
226 #define MAX_OPEN_DIRECTORIES 10
228 static unsigned int open_directories
= 0;
231 /* Hash table of files in each directory. */
235 struct dirfile
*next
;
236 char *name
; /* Name of the file. */
237 char impossible
; /* This file is impossible. */
240 #ifndef DIRFILE_BUCKETS
241 #define DIRFILE_BUCKETS 107
244 static int dir_contents_file_exists_p
PARAMS ((struct directory_contents
*dir
, char *filename
));
245 static struct directory
*find_directory
PARAMS ((char *name
));
247 /* Find the directory named NAME and return its `struct directory'. */
249 static struct directory
*
250 find_directory (name
)
253 register unsigned int hash
= 0;
255 register struct directory
*dir
;
257 if ((*name
== '.') && (*(name
+1) == 0))
260 name
= vmsify (name
,1);
263 for (p
= name
; *p
!= '\0'; ++p
)
265 hash
%= DIRECTORY_BUCKETS
;
267 for (dir
= directories
[hash
]; dir
!= 0; dir
= dir
->next
)
268 if (strieq (dir
->name
, name
))
275 /* The directory was not found. Create a new entry for it. */
277 dir
= (struct directory
*) xmalloc (sizeof (struct directory
));
278 dir
->next
= directories
[hash
];
279 directories
[hash
] = dir
;
280 dir
->name
= savestring (name
, p
- name
);
282 /* The directory is not in the name hash table.
283 Find its device and inode numbers, and look it up by them. */
286 if (vmsstat_dir (name
, &st
) < 0)
288 if (stat (name
, &st
) < 0)
291 /* Couldn't stat the directory. Mark this by
292 setting the `contents' member to a nil pointer. */
297 /* Search the contents hash table; device and inode are the key. */
299 struct directory_contents
*dc
;
302 hash
= ((unsigned int) st
.st_dev
<< 16)
303 | ((unsigned int) st
.st_ino
[0]
304 + (unsigned int) st
.st_ino
[1]
305 + (unsigned int) st
.st_ino
[2]);
307 hash
= ((unsigned int) st
.st_dev
<< 16) | (unsigned int) st
.st_ino
;
309 hash
%= DIRECTORY_BUCKETS
;
311 for (dc
= directories_contents
[hash
]; dc
!= 0; dc
= dc
->next
)
312 if (dc
->dev
== st
.st_dev
314 && dc
->ino
[0] == st
.st_ino
[0]
315 && dc
->ino
[1] == st
.st_ino
[1]
316 && dc
->ino
[2] == st
.st_ino
[2])
318 && dc
->ino
== st
.st_ino
)
324 /* Nope; this really is a directory we haven't seen before. */
326 dc
= (struct directory_contents
*)
327 xmalloc (sizeof (struct directory_contents
));
329 /* Enter it in the contents hash table. */
332 dc
->ino
[0] = st
.st_ino
[0];
333 dc
->ino
[1] = st
.st_ino
[1];
334 dc
->ino
[2] = st
.st_ino
[2];
338 dc
->next
= directories_contents
[hash
];
339 directories_contents
[hash
] = dc
;
341 dc
->dirstream
= opendir (name
);
342 if (dc
->dirstream
== 0)
344 /* Couldn't open the directory. Mark this by
345 setting the `files' member to a nil pointer. */
350 /* Allocate an array of buckets for files and zero it. */
351 dc
->files
= (struct dirfile
**)
352 xmalloc (sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
353 bzero ((char *) dc
->files
,
354 sizeof (struct dirfile
*) * DIRFILE_BUCKETS
);
356 /* Keep track of how many directories are open. */
358 if (open_directories
== MAX_OPEN_DIRECTORIES
)
359 /* We have too many directories open already.
360 Read the entire directory and then close it. */
361 (void) dir_contents_file_exists_p (dc
, (char *) 0);
365 /* Point the name-hashed entry for DIR at its contents data. */
373 /* Return 1 if the name FILENAME is entered in DIR's hash table.
374 FILENAME must contain no slashes. */
377 dir_contents_file_exists_p (dir
, filename
)
378 register struct directory_contents
*dir
;
379 register char *filename
;
381 register unsigned int hash
;
383 register struct dirfile
*df
;
384 register struct dirent
*d
;
386 if (dir
== 0 || dir
->files
== 0)
388 /* The directory could not be stat'd or opened. */
392 filename
= dosify (filename
);
396 filename
= amigafy (filename
);
400 filename
= vmsify (filename
,0);
406 if (*filename
== '\0')
408 /* Checking if the directory exists. */
412 for (p
= filename
; *p
!= '\0'; ++p
)
414 hash
%= DIRFILE_BUCKETS
;
416 /* Search the list of hashed files. */
418 for (df
= dir
->files
[hash
]; df
!= 0; df
= df
->next
)
420 if (strieq (df
->name
, filename
))
422 return !df
->impossible
;
427 /* The file was not found in the hashed list.
428 Try to read the directory further. */
430 if (dir
->dirstream
== 0)
432 /* The directory has been all read in. */
436 while ((d
= readdir (dir
->dirstream
)) != 0)
438 /* Enter the file in the hash table. */
439 register unsigned int newhash
= 0;
441 register unsigned int i
;
443 if (!REAL_DIR_ENTRY (d
))
447 for (i
= 0; i
< len
; ++i
)
448 HASHI (newhash
, d
->d_name
[i
]);
449 newhash
%= DIRFILE_BUCKETS
;
451 df
= (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
452 df
->next
= dir
->files
[newhash
];
453 dir
->files
[newhash
] = df
;
454 df
->name
= savestring (d
->d_name
, len
);
456 /* Check if the name matches the one we're searching for. */
458 && newhash
== hash
&& strieq (d
->d_name
, filename
))
464 /* If the directory has been completely read in,
465 close the stream and reset the pointer to nil. */
469 closedir (dir
->dirstream
);
475 /* Return 1 if the name FILENAME in directory DIRNAME
476 is entered in the dir hash table.
477 FILENAME must contain no slashes. */
480 dir_file_exists_p (dirname
, filename
)
481 register char *dirname
;
482 register char *filename
;
484 return dir_contents_file_exists_p (find_directory (dirname
)->contents
,
488 /* Return 1 if the file named NAME exists. */
499 return ar_member_date (name
) != (time_t) -1;
503 dirend
= rindex (name
, ']');
505 if (dirend
== (char *)1)
506 return dir_file_exists_p ("[]", name
);
508 dirend
= rindex (name
, '/');
510 return dir_file_exists_p (".", name
);
513 return dir_file_exists_p (".", name
);
514 #else /* !VMS && !AMIGA */
515 return dir_file_exists_p ("", name
);
519 dirname
= (char *) alloca (dirend
- name
+ 1);
520 bcopy (name
, dirname
, dirend
- name
);
521 dirname
[dirend
- name
] = '\0';
522 return dir_file_exists_p (dirname
, dirend
+ 1);
525 /* Mark FILENAME as `impossible' for `file_impossible_p'.
526 This means an attempt has been made to search for FILENAME
527 as an intermediate file, and it has failed. */
530 file_impossible (filename
)
531 register char *filename
;
534 register char *p
= filename
;
535 register unsigned int hash
;
536 register struct directory
*dir
;
537 register struct dirfile
*new;
540 dirend
= rindex (p
, ']');
542 if (dirend
== (char *)1)
543 dir
= find_directory ("[]");
545 dirend
= rindex (p
, '/');
548 dir
= find_directory ("");
549 #else /* !VMS && !AMIGA */
550 dir
= find_directory (".");
555 char *dirname
= (char *) alloca (dirend
- p
+ 1);
556 bcopy (p
, dirname
, dirend
- p
);
557 dirname
[dirend
- p
] = '\0';
558 dir
= find_directory (dirname
);
559 filename
= p
= dirend
+ 1;
562 for (hash
= 0; *p
!= '\0'; ++p
)
564 hash
%= DIRFILE_BUCKETS
;
566 if (dir
->contents
== 0)
568 /* The directory could not be stat'd. We allocate a contents
569 structure for it, but leave it out of the contents hash table. */
570 dir
->contents
= (struct directory_contents
*)
571 xmalloc (sizeof (struct directory_contents
));
573 dir
->contents
->dev
= 0;
574 dir
->contents
->ino
[0] = dir
->contents
->ino
[1] =
575 dir
->contents
->ino
[2] = 0;
577 dir
->contents
->dev
= dir
->contents
->ino
= 0;
579 dir
->contents
->files
= 0;
580 dir
->contents
->dirstream
= 0;
583 if (dir
->contents
->files
== 0)
585 /* The directory was not opened; we must allocate the hash buckets. */
586 dir
->contents
->files
= (struct dirfile
**)
587 xmalloc (sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
588 bzero ((char *) dir
->contents
->files
,
589 sizeof (struct dirfile
) * DIRFILE_BUCKETS
);
592 /* Make a new entry and put it in the table. */
594 new = (struct dirfile
*) xmalloc (sizeof (struct dirfile
));
595 new->next
= dir
->contents
->files
[hash
];
596 dir
->contents
->files
[hash
] = new;
597 new->name
= savestring (filename
, strlen (filename
));
601 /* Return nonzero if FILENAME has been marked impossible. */
604 file_impossible_p (filename
)
608 register char *p
= filename
;
609 register unsigned int hash
;
610 register struct directory_contents
*dir
;
611 register struct dirfile
*next
;
614 dirend
= rindex (filename
, ']');
616 dir
= find_directory ("[]")->contents
;
618 dirend
= rindex (filename
, '/');
621 dir
= find_directory ("")->contents
;
622 #else /* !VMS && !AMIGA */
623 dir
= find_directory (".")->contents
;
628 char *dirname
= (char *) alloca (dirend
- filename
+ 1);
629 bcopy (p
, dirname
, dirend
- p
);
630 dirname
[dirend
- p
] = '\0';
631 dir
= find_directory (dirname
)->contents
;
632 p
= filename
= dirend
+ 1;
635 if (dir
== 0 || dir
->files
== 0)
636 /* There are no files entered for this directory. */
640 p
= filename
= dosify (p
);
643 p
= filename
= amigafy (p
);
646 p
= filename
= vmsify (p
, 1);
649 for (hash
= 0; *p
!= '\0'; ++p
)
651 hash
%= DIRFILE_BUCKETS
;
653 for (next
= dir
->files
[hash
]; next
!= 0; next
= next
->next
)
654 if (strieq (filename
, next
->name
))
655 return next
->impossible
;
660 /* Return the already allocated name in the
661 directory hash table that matches DIR. */
667 return find_directory (dir
)->name
;
670 /* Print the data base of directories. */
673 print_dir_data_base ()
675 register unsigned int i
, dirs
, files
, impossible
;
676 register struct directory
*dir
;
678 puts ("\n# Directories\n");
680 dirs
= files
= impossible
= 0;
681 for (i
= 0; i
< DIRECTORY_BUCKETS
; ++i
)
682 for (dir
= directories
[i
]; dir
!= 0; dir
= dir
->next
)
685 if (dir
->contents
== 0)
686 printf ("# %s: could not be stat'd.\n", dir
->name
);
687 else if (dir
->contents
->files
== 0)
689 printf ("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n",
690 dir
->name
, dir
->contents
->dev
,
691 dir
->contents
->ino
[0], dir
->contents
->ino
[1],
692 dir
->contents
->ino
[2]);
694 printf ("# %s (device %d, inode %d): could not be opened.\n",
695 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
699 register unsigned int f
= 0, im
= 0;
700 register unsigned int j
;
701 register struct dirfile
*df
;
702 for (j
= 0; j
< DIRFILE_BUCKETS
; ++j
)
703 for (df
= dir
->contents
->files
[j
]; df
!= 0; df
= df
->next
)
709 printf ("# %s (device %d, inode [%d,%d,%d]): ",
710 dir
->name
, dir
->contents
->dev
,
711 dir
->contents
->ino
[0], dir
->contents
->ino
[1],
712 dir
->contents
->ino
[2]);
714 printf ("# %s (device %d, inode %d): ",
715 dir
->name
, dir
->contents
->dev
, dir
->contents
->ino
);
718 fputs ("No", stdout
);
721 fputs (" files, ", stdout
);
723 fputs ("no", stdout
);
726 fputs (" impossibilities", stdout
);
727 if (dir
->contents
->dirstream
== 0)
736 fputs ("\n# ", stdout
);
738 fputs ("No", stdout
);
740 printf ("%u", files
);
741 fputs (" files, ", stdout
);
743 fputs ("no", stdout
);
745 printf ("%u", impossible
);
746 printf (" impossibilities in %u directories.\n", dirs
);
749 /* Hooks for globbing. */
753 /* Structure describing state of iterating through a directory hash table. */
757 struct directory_contents
*contents
; /* The directory being read. */
759 unsigned int bucket
; /* Current hash bucket. */
760 struct dirfile
*elt
; /* Current elt in bucket. */
763 /* Forward declarations. */
764 static __ptr_t open_dirstream
PARAMS ((const char *));
765 static struct dirent
*read_dirstream
PARAMS ((__ptr_t
));
768 open_dirstream (directory
)
769 const char *directory
;
771 struct dirstream
*new;
772 struct directory
*dir
= find_directory ((char *)directory
);
774 if (dir
->contents
== 0 || dir
->contents
->files
== 0)
775 /* DIR->contents is nil if the directory could not be stat'd.
776 DIR->contents->files is nil if it could not be opened. */
779 /* Read all the contents of the directory now. There is no benefit
780 in being lazy, since glob will want to see every file anyway. */
782 (void) dir_contents_file_exists_p (dir
->contents
, (char *) 0);
784 new = (struct dirstream
*) xmalloc (sizeof (struct dirstream
));
785 new->contents
= dir
->contents
;
787 new->elt
= new->contents
->files
[0];
789 return (__ptr_t
) new;
792 static struct dirent
*
793 read_dirstream (stream
)
796 struct dirstream
*const ds
= (struct dirstream
*) stream
;
797 register struct dirfile
*df
;
799 static unsigned int bufsz
;
801 while (ds
->bucket
< DIRFILE_BUCKETS
)
803 while ((df
= ds
->elt
) != 0)
808 /* The glob interface wants a `struct dirent',
811 unsigned int len
= strlen (df
->name
) + 1;
812 if (sizeof *d
- sizeof d
->d_name
+ len
> bufsz
)
817 if (sizeof *d
- sizeof d
->d_name
+ len
> bufsz
)
818 bufsz
= sizeof *d
- sizeof d
->d_name
+ len
;
819 buf
= xmalloc (bufsz
);
821 d
= (struct dirent
*) buf
;
823 #ifdef _DIRENT_HAVE_D_NAMLEN
824 d
->d_namlen
= len
- 1;
826 memcpy (d
->d_name
, df
->name
, len
);
830 if (++ds
->bucket
== DIRFILE_BUCKETS
)
832 ds
->elt
= ds
->contents
->files
[ds
->bucket
];
844 /* Bogus sunos4 compiler complains (!) about & before functions. */
845 gl
->gl_opendir
= open_dirstream
;
846 gl
->gl_readdir
= read_dirstream
;
847 gl
->gl_closedir
= free
;
849 /* We don't bother setting gl_lstat, since glob never calls it.
850 The slot is only there for compatibility with 4.4 BSD. */