kDep.c@ 775

Last change on this file since 775 was 733, checked in by bird, 18 years ago
check for buffer overflow.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 13.2 KB

Line
1	/* $Id: kDep.c 733 2006-12-17 04:42:54Z bird $ */
2	/** @file
3	*
4	* kDep - Common Dependency Managemnt Code.
5	*
6	* Copyright (c) 2004-2006 knut st. osmundsen <bird@innotek.de>
7	*
8	*
9	* This file is part of kBuild.
10	*
11	* kBuild is free software; you can redistribute it and/or modify
12	* it under the terms of the GNU General Public License as published by
13	* the Free Software Foundation; either version 2 of the License, or
14	* (at your option) any later version.
15	*
16	* kBuild is distributed in the hope that it will be useful,
17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19	* GNU General Public License for more details.
20	*
21	* You should have received a copy of the GNU General Public License
22	* along with kBuild; if not, write to the Free Software
23	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24	*
25	*/
26
27
28	/*******************************************************************************
29	* Header Files *
30	*******************************************************************************/
31	#include <stdio.h>
32	#include <stdlib.h>
33	#include <string.h>
34	#include <errno.h>
35	#include <ctype.h>
36	#include <limits.h>
37	#include <sys/stat.h>
38	#ifdef __WIN32__
39	# include <windows.h>
40	#endif
41	#if !defined(__WIN32__) && !defined(__OS2__)
42	# include <dirent.h>
43	#endif
44	#ifndef __WIN32__
45	# include <unistd.h>
46	# include <stdint.h>
47	#else
48	typedef unsigned char uint8_t;
49	typedef unsigned short uint16_t;
50	typedef unsigned int uint32_t;
51	#endif
52
53	#include "kDep.h"
54
55	#ifdef NEED_ISBLANK
56	# define isblank(ch) ( (unsigned char)(ch) == ' ' \|\| (unsigned char)(ch) == '\t' )
57	#endif
58
59	#define OFFSETOF(type, member) ( (int)(void )&( ((type )(void *)0)->member) )
60
61
62	/*******************************************************************************
63	* Global Variables *
64	*******************************************************************************/
65	/** List of dependencies. */
66	static PDEP g_pDeps = NULL;
67
68
69	/**
70	* Corrects all slashes to unix slashes.
71	*
72	* @returns pszFilename.
73	* @param pszFilename The filename to correct.
74	*/
75	static char fixslash(char pszFilename)
76	{
77	char *psz = pszFilename;
78	while ((psz = strchr(psz, '\\')) != NULL)
79	*psz++ = '/';
80	return pszFilename;
81	}
82
83
84	#ifdef __WIN32__
85	/**
86	* Corrects the case of a path and changes any path components containing
87	* spaces with the short name (which can be longer).
88	*
89	* Expects a _fullpath!
90	*
91	* @param pszPath Pointer to the path, both input and output.
92	* The buffer must be at least MAX_PATH in length.
93	*/
94	static void fixcase(char *pszPath)
95	{
96	#define my_assert(expr) \
97	do { \
98	if (!(expr)) { \
99	printf("my_assert: %s, file %s, line %d\npszPath=%s\npsz=%s\n", \
100	#expr, __FILE__, __LINE__, pszPath, psz); \
101	__asm { __asm int 3 } \
102	exit(1); \
103	} \
104	} while (0)
105
106	char *psz = pszPath;
107	if (psz == '/' \|\| psz == '\\')
108	{
109	if (psz[1] == '/' \|\| psz[1] == '\\')
110	{
111	/* UNC */
112	my_assert(psz[1] == '/' \|\| psz[1] == '\\');
113	my_assert(psz[2] != '/' && psz[2] != '\\');
114
115	/* skip server name */
116	psz += 2;
117	while (psz != '\\' && psz != '/')
118	{
119	if (!*psz)
120	return;
121	psz++ = toupper(psz);
122	}
123
124	/* skip the share name */
125	psz++;
126	my_assert(psz != '/' && psz != '\\');
127	while (psz != '\\' && psz != '/')
128	{
129	if (!*psz)
130	return;
131	psz++ = toupper(psz);
132	}
133	my_assert(psz == '/' \|\| psz == '\\');
134	psz++;
135	}
136	else
137	{
138	/* Unix spec */
139	psz++;
140	}
141	}
142	else
143	{
144	/* Drive letter */
145	my_assert(psz[1] == ':');
146	psz = toupper(psz);
147	my_assert(psz[0] >= 'A' && psz[0] <= 'Z');
148	my_assert(psz[2] == '/' \|\| psz[2] == '\\');
149	psz += 3;
150	}
151
152	/*
153	* Pointing to the first char after the unc or drive specifier.
154	*/
155	while (*psz)
156	{
157	WIN32_FIND_DATA FindFileData;
158	HANDLE hDir;
159	char chSaved0;
160	char chSaved1;
161	char *pszEnd;
162	int cch;
163	int iLongNameDiff;
164
165
166	/* find the end of the component. */
167	pszEnd = psz;
168	while (pszEnd && pszEnd != '/' && *pszEnd != '\\')
169	pszEnd++;
170	cch = pszEnd - psz;
171
172	/* replace the end with "?\0" */
173	chSaved0 = pszEnd[0];
174	chSaved1 = pszEnd[1];
175	pszEnd[0] = '?';
176	pszEnd[1] = '\0';
177
178	/* find the right filename. */
179	hDir = FindFirstFile(pszPath, &FindFileData);
180	pszEnd[1] = chSaved1;
181	if (!hDir)
182	{
183	pszEnd[0] = chSaved0;
184	return;
185	}
186	pszEnd[0] = '\0';
187	while ( (iLongNameDiff = stricmp(FindFileData.cFileName, psz))
188	&& stricmp(FindFileData.cAlternateFileName, psz))
189	{
190	if (!FindNextFile(hDir, &FindFileData))
191	{
192	pszEnd[0] = chSaved0;
193	return;
194	}
195	}
196	pszEnd[0] = chSaved0;
197	if (iLongNameDiff \|\| !FindFileData.cAlternateFileName[0] \|\| !memchr(psz, ' ', cch))
198	memcpy(psz, !iLongNameDiff ? FindFileData.cFileName : FindFileData.cAlternateFileName, cch);
199	else
200	{
201	/* replace spacy name with the short name. */
202	const int cchAlt = strlen(FindFileData.cAlternateFileName);
203	const int cchDelta = cch - cchAlt;
204	my_assert(cchAlt > 0);
205	if (!cchDelta)
206	memcpy(psz, FindFileData.cAlternateFileName, cch);
207	else
208	{ int cbLeft = strlen(pszEnd) + 1;
209	if ((psz - pszPath) + cbLeft + cchAlt <= _MAX_PATH)
210	{
211	memmove(psz + cchAlt, pszEnd, cbLeft);
212	pszEnd -= cchDelta;
213	memcpy(psz, FindFileData.cAlternateFileName, cchAlt);
214	}
215	else
216	fprintf(stderr, "kDep: case & space fixed filename is growing too long (%d bytes)! '%s'\n",
217	(psz - pszPath) + cbLeft + cchAlt, pszPath);
218	}
219	}
220	my_assert(pszEnd[0] == chSaved0);
221
222	/* advance to the next component */
223	if (!chSaved0)
224	return;
225	psz = pszEnd + 1;
226	my_assert(psz != '/' && psz != '\\');
227	}
228	#undef my_assert
229	}
230
231	#elif defined(__OS2__)
232
233	/**
234	* Corrects the case of a path.
235	*
236	* @param pszPath Pointer to the path, both input and output.
237	* The buffer must be able to hold one more byte than the string length.
238	*/
239	static void fixcase(char *pszFilename)
240	{
241	return;
242	}
243
244	#else
245
246	/**
247	* Corrects the case of a path.
248	*
249	* @param pszPath Pointer to the path, both input and output.
250	*/
251	static void fixcase(char *pszFilename)
252	{
253	char *psz;
254
255	/*
256	* Skip the root.
257	*/
258	psz = pszFilename;
259	while (*psz == '/')
260	psz++;
261
262	/*
263	* Iterate all the components.
264	*/
265	while (*psz)
266	{
267	char chSlash;
268	struct stat s;
269	char *pszStart = psz;
270
271	/*
272	* Find the next slash (or end of string) and terminate the string there.
273	*/
274	while (psz != '/' && psz)
275	*psz++;
276	chSlash = *psz;
277	*psz = '\0';
278
279	/*
280	* Does this part exist?
281	* If not we'll enumerate the directory and search for an case-insensitive match.
282	*/
283	if (stat(pszFilename, &s))
284	{
285	struct dirent *pEntry;
286	DIR *pDir;
287	if (pszStart == pszFilename)
288	pDir = opendir(*pszFilename ? pszFilename : ".");
289	else
290	{
291	pszStart[-1] = '\0';
292	pDir = opendir(pszFilename);
293	pszStart[-1] = '/';
294	}
295	if (!pDir)
296	{
297	*psz = chSlash;
298	break; /* giving up, if we fail to open the directory. */
299	}
300
301	while ((pEntry = readdir(pDir)) != NULL)
302	{
303	if (!strcasecmp(pEntry->d_name, pszStart))
304	{
305	strcpy(pszStart, pEntry->d_name);
306	break;
307	}
308	}
309	closedir(pDir);
310	if (!pEntry)
311	{
312	*psz = chSlash;
313	break; /* giving up if not found. */
314	}
315	}
316
317	/* restore the slash and press on. */
318	*psz = chSlash;
319	while (*psz == '/')
320	psz++;
321	}
322
323	return;
324	}
325
326
327	#endif
328
329
330	/**
331	* 'Optimizes' and corrects the dependencies.
332	*/
333	void depOptimize(int fFixCase)
334	{
335	/*
336	* Walk the list correct the names and re-insert them.
337	*/
338	PDEP pDepOrg = g_pDeps;
339	PDEP pDep = g_pDeps;
340	g_pDeps = NULL;
341	for (; pDep; pDep = pDep->pNext)
342	{
343	#ifdef __WIN32__
344	char szFilename[_MAX_PATH + 1];
345	#else
346	char szFilename[PATH_MAX + 1];
347	#endif
348	char *pszFilename;
349	struct stat s;
350
351	/*
352	* Skip some fictive names like <built-in> and <command line>.
353	*/
354	if ( pDep->szFilename[0] == '<'
355	&& pDep->szFilename[pDep->cchFilename - 1] == '>')
356	continue;
357	pszFilename = pDep->szFilename;
358
359	#if !defined(__OS2__) && !defined(__WIN32__)
360	/*
361	* Skip any drive letters from compilers running in wine.
362	*/
363	if (pszFilename[1] == ':')
364	pszFilename += 2;
365	#endif
366
367	/*
368	* The microsoft compilers are notoriously screwing up the casing.
369	* This will screw up kmk (/ GNU Make).
370	*/
371	if (fFixCase)
372	{
373	#ifdef __WIN32__
374	if (_fullpath(szFilename, pszFilename, sizeof(szFilename)))
375	;
376	else
377	#endif
378	strcpy(szFilename, pszFilename);
379	fixslash(szFilename);
380	fixcase(szFilename);
381	pszFilename = szFilename;
382	}
383
384	/*
385	* Check that the file exists before we start depending on it.
386	*/
387	if (stat(pszFilename, &s))
388	{
389	fprintf(stderr, "kDep: Skipping '%s' - %s!\n", szFilename, strerror(errno));
390	continue;
391	}
392
393	/*
394	* Insert the corrected dependency.
395	*/
396	depAdd(pszFilename, strlen(pszFilename));
397	}
398
399	#if 0 /* waste of time */
400	/*
401	* Free the old ones.
402	*/
403	while (pDepOrg)
404	{
405	pDep = pDepOrg;
406	pDepOrg = pDepOrg->pNext;
407	free(pDep);
408	}
409	#endif
410	}
411
412
413	/**
414	* Prints the dependency chain.
415	*
416	* @returns Pointer to the allocated dependency.
417	* @param pOutput Output stream.
418	*/
419	void depPrint(FILE *pOutput)
420	{
421	PDEP pDep;
422	for (pDep = g_pDeps; pDep; pDep = pDep->pNext)
423	fprintf(pOutput, " \\\n\t%s", pDep->szFilename);
424	fprintf(pOutput, "\n\n");
425	}
426
427
428	/**
429	* Prints empty dependency stubs for all dependencies.
430	*/
431	void depPrintStubs(FILE *pOutput)
432	{
433	PDEP pDep;
434	for (pDep = g_pDeps; pDep; pDep = pDep->pNext)
435	fprintf(pOutput, "%s:\n\n", pDep->szFilename);
436	}
437
438
439	/* sdbm:
440	This algorithm was created for sdbm (a public-domain reimplementation of
441	ndbm) database library. it was found to do well in scrambling bits,
442	causing better distribution of the keys and fewer splits. it also happens
443	to be a good general hashing function with good distribution. the actual
444	function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below
445	is the faster version used in gawk. [there is even a faster, duff-device
446	version] the magic constant 65599 was picked out of thin air while
447	experimenting with different constants, and turns out to be a prime.
448	this is one of the algorithms used in berkeley db (see sleepycat) and
449	elsewhere. */
450	static unsigned sdbm(const char *str)
451	{
452	unsigned hash = 0;
453	int c;
454
455	while ((c = (unsigned const char )str++))
456	hash = c + (hash << 6) + (hash << 16) - hash;
457
458	return hash;
459	}
460
461
462	/**
463	* Adds a dependency.
464	*
465	* @returns Pointer to the allocated dependency.
466	* @param pszFilename The filename.
467	* @param cchFilename The length of the filename.
468	*/
469	PDEP depAdd(const char *pszFilename, size_t cchFilename)
470	{
471	unsigned uHash = sdbm(pszFilename);
472	PDEP pDep;
473	PDEP pDepPrev;
474
475	/*
476	* Check if we've already got this one.
477	*/
478	pDepPrev = NULL;
479	for (pDep = g_pDeps; pDep; pDepPrev = pDep, pDep = pDep->pNext)
480	if ( pDep->uHash == uHash
481	&& pDep->cchFilename == cchFilename
482	&& !memcmp(pDep->szFilename, pszFilename, cchFilename))
483	return pDep;
484
485	/*
486	* Add it.
487	*/
488	pDep = (PDEP)malloc(sizeof(*pDep) + cchFilename);
489	if (!pDep)
490	{
491	fprintf(stderr, "\nOut of memory! (requested %#x bytes)\n\n", sizeof(*pDep) + cchFilename);
492	exit(1);
493	}
494
495	pDep->cchFilename = cchFilename;
496	memcpy(pDep->szFilename, pszFilename, cchFilename + 1);
497	pDep->uHash = uHash;
498
499	if (pDepPrev)
500	{
501	pDep->pNext = pDepPrev->pNext;
502	pDepPrev->pNext = pDep;
503	}
504	else
505	{
506	pDep->pNext = g_pDeps;
507	g_pDeps = pDep;
508	}
509	return pDep;
510	}

Note: See TracBrowser for help on using the repository browser.

source: kBuild/trunk/src/lib/kDep.c@ 775

Download in other formats: