cutils.c@ 24345

Last change on this file since 24345 was 17040, checked in by vboxsync, 16 years ago
recompiler_new: svn properties.
Property svn:eol-style set to `native`
File size: 16.0 KB

Line
1	/*
2	* Simple C functions to supplement the C library
3	*
4	* Copyright (c) 2006 Fabrice Bellard
5	*
6	* Permission is hereby granted, free of charge, to any person obtaining a copy
7	* of this software and associated documentation files (the "Software"), to deal
8	* in the Software without restriction, including without limitation the rights
9	* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10	* copies of the Software, and to permit persons to whom the Software is
11	* furnished to do so, subject to the following conditions:
12	*
13	* The above copyright notice and this permission notice shall be included in
14	* all copies or substantial portions of the Software.
15	*
16	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19	* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21	* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22	* THE SOFTWARE.
23	*/
24	#include "qemu-common.h"
25
26	#ifdef VBOX
27	#include "osdep.h"
28
29	static inline int toupper(int ch) {
30	if ( (unsigned int)(ch - 'a') < 26u )
31	ch += 'A' - 'a';
32	return ch;
33	}
34
35	/* Quick sort from OpenSolaris:
36	http://src.opensolaris.org/source/raw/onnv/onnv-gate/usr/src/common/util/qsort.c */
37	/*
38	* choose a median of 3 values
39	*
40	* note: cstyle specifically prohibits nested conditional operators
41	* but this is the only way to do the median of 3 function in-line
42	*/
43	#define med3(a, b, c) (cmp((a), (b)) < 0) \
44	? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \
45	: ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a))
46
47	#define THRESH_L 5 /* threshold for insertion sort */
48	#define THRESH_M3 20 /* threshold for median of 3 */
49	#define THRESH_M9 50 /* threshold for median of 9 */
50
51	typedef struct {
52	char *b_lim;
53	size_t nrec;
54	} stk_t;
55
56	/*
57	* The following swap functions should not create a stack frame
58	* the SPARC call / return instruction will be executed
59	* but the a save / restore will not be executed
60	* which means we won't do a window turn with the spill / fill overhead
61	* verify this by examining the assembly code
62	*/
63
64	/* ARGSUSED */
65	static void
66	swapp32(uint32_t r1, uint32_t r2, size_t cnt)
67	{
68	uint32_t temp;
69
70	temp = *r1;
71	r1++ = r2;
72	*r2++ = temp;
73	}
74
75	/* ARGSUSED */
76	static void
77	swapp64(uint64_t r1, uint64_t r2, size_t cnt)
78	{
79	uint64_t temp;
80
81	temp = *r1;
82	r1++ = r2;
83	*r2++ = temp;
84	}
85
86	static void
87	swapi(uint32_t r1, uint32_t r2, size_t cnt)
88	{
89	uint32_t temp;
90
91	/* character by character */
92	while (cnt--) {
93	temp = *r1;
94	r1++ = r2;
95	*r2++ = temp;
96	}
97	}
98
99	static void
100	swapb(char r1, char r2, size_t cnt)
101	{
102	char temp;
103
104	/* character by character */
105	while (cnt--) {
106	temp = *r1;
107	r1++ = r2;
108	*r2++ = temp;
109	}
110	}
111
112	/*
113	* qsort() is a general purpose, in-place sorting routine using a
114	* user provided call back function for comparisons. This implementation
115	* utilizes a ternary quicksort algorithm, and cuts over to an
116	* insertion sort for partitions involving fewer than THRESH_L records.
117	*
118	* Potential User Errors
119	* There is no return value from qsort, this function has no method
120	* of alerting the user that a sort did not work or could not work.
121	* We do not print an error message or exit the process or thread,
122	* Even if we can detect an error, We CANNOT silently return without
123	* sorting the data, if we did so the user could never be sure the
124	* sort completed successfully.
125	* It is possible we could change the return value of sort from void
126	* to int and return success or some error codes, but this gets into
127	* standards and compatibility issues.
128	*
129	* Examples of qsort parameter errors might be
130	* 1) record size (rsiz) equal to 0
131	* qsort will loop and never return.
132	* 2) record size (rsiz) less than 0
133	* rsiz is unsigned, so a negative value is insanely large
134	* 3) number of records (nrec) is 0
135	* This is legal - qsort will return without examining any records
136	* 4) number of records (nrec) is less than 0
137	* nrec is unsigned, so a negative value is insanely large.
138	* 5) nrec * rsiz > memory allocation for sort array
139	* a segment violation may occur
140	* corruption of other memory may occur
141	* 6) The base address of the sort array is invalid
142	* a segment violation may occur
143	* corruption of other memory may occur
144	* 7) The user call back function is invalid
145	* we may get alignment errors or segment violations
146	* we may jump into never-never land
147	*
148	* Some less obvious errors might be
149	* 8) The user compare function is not comparing correctly
150	* 9) The user compare function modifies the data records
151	*/
152
153	void
154	qemu_qsort(
155	void *basep,
156	size_t nrec,
157	size_t rsiz,
158	int (cmp)(const void , const void *))
159	{
160	size_t i; /* temporary variable */
161
162	/* variables used by swap */
163	void (swapf)(char , char *, size_t);
164	size_t loops;
165
166	/* variables used by sort */
167	stk_t stack[8 * sizeof (nrec) + 1];
168	stk_t *sp;
169	char b_lim; / bottom limit */
170	char b_dup; / bottom duplicate */
171	char b_par; / bottom partition */
172	char t_lim; / top limit */
173	char t_dup; / top duplicate */
174	char t_par; / top partition */
175	char m1, m2, m3; / median pointers */
176	uintptr_t d_bytelength; /* byte length of duplicate records */
177	int b_nrec;
178	int t_nrec;
179	int cv; /* results of compare (bottom / top) */
180
181	/*
182	* choose a swap function based on alignment and size
183	*
184	* The qsort function sorts an array of fixed length records.
185	* We have very limited knowledge about the data record itself.
186	* It may be that the data record is in the array we are sorting
187	* or it may be that the array contains pointers or indexes to
188	* the actual data record and all that we are sorting is the indexes.
189	*
190	* The following decision will choose an optimal swap function
191	* based on the size and alignment of the data records
192	* swapp64 will swap 64 bit pointers
193	* swapp32 will swap 32 bit pointers
194	* swapi will swap an array of 32 bit integers
195	* swapb will swap an array of 8 bit characters
196	*
197	* swapi and swapb will also require the variable loops to be set
198	* to control the length of the array being swapped
199	*/
200	if ((((uintptr_t)basep & (sizeof (uint64_t) - 1)) == 0) &&
201	(rsiz == sizeof (uint64_t))) {
202	loops = 1;
203	swapf = (void ()(char , char *, size_t))swapp64;
204	} else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
205	(rsiz == sizeof (uint32_t))) {
206	loops = 1;
207	swapf = (void ()(char , char *, size_t))swapp32;
208	} else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
209	((rsiz & (sizeof (uint32_t) - 1)) == 0)) {
210	loops = rsiz / sizeof (int);
211	swapf = (void ()(char , char *, size_t))swapi;
212	} else {
213	loops = rsiz;
214	swapf = swapb;
215	}
216
217	/*
218	* qsort is a partitioning sort
219	*
220	* the stack is the bookkeeping mechanism to keep track of all
221	* the partitions.
222	*
223	* each sort pass takes one partition and sorts it into two partitions.
224	* at the top of the loop we simply take the partition on the top
225	* of the stack and sort it. See the comments at the bottom
226	* of the loop regarding which partitions to add in what order.
227	*
228	* initially put the whole partition on the stack
229	*/
230	sp = stack;
231	sp->b_lim = (char *)basep;
232	sp->nrec = nrec;
233	sp++;
234	while (sp > stack) {
235	sp--;
236	b_lim = sp->b_lim;
237	nrec = sp->nrec;
238
239	/*
240	* a linear insertion sort i faster than a qsort for
241	* very small number of records (THRESH_L)
242	*
243	* if number records < threshold use linear insertion sort
244	*
245	* this also handles the special case where the partition
246	* 0 or 1 records length.
247	*/
248	if (nrec < THRESH_L) {
249	/*
250	* Linear insertion sort
251	*/
252	t_par = b_lim;
253	for (i = 1; i < nrec; i++) {
254	t_par += rsiz;
255	b_par = t_par;
256	while (b_par > b_lim) {
257	b_par -= rsiz;
258	if ((*cmp)(b_par, b_par + rsiz) <= 0) {
259	break;
260	}
261	(*swapf)(b_par, b_par + rsiz, loops);
262	}
263	}
264
265	/*
266	* a linear insertion sort will put all records
267	* in their final position and will not create
268	* subpartitions.
269	*
270	* therefore when the insertion sort is complete
271	* just go to the top of the loop and get the
272	* next partition to sort.
273	*/
274	continue;
275	}
276
277	/* quicksort */
278
279	/*
280	* choose a pivot record
281	*
282	* Ideally the pivot record will divide the partition
283	* into two equal parts. however we have to balance the
284	* work involved in selecting the pivot record with the
285	* expected benefit.
286	*
287	* The choice of pivot record depends on the number of
288	* records in the partition
289	*
290	* for small partitions (nrec < THRESH_M3)
291	* we just select the record in the middle of the partition
292	*
293	* if (nrec >= THRESH_M3 && nrec < THRESH_M9)
294	* we select three values and choose the median of 3
295	*
296	* if (nrec >= THRESH_M9)
297	* then we use an approximate median of 9
298	* 9 records are selected and grouped in 3 groups of 3
299	* the median of each of these 3 groups is fed into another
300	* median of 3 decision.
301	*
302	* Each median of 3 decision is 2 or 3 compares,
303	* so median of 9 costs between 8 and 12 compares.
304	*
305	* i is byte distance between two consecutive samples
306	* m2 will point to the pivot record
307	*/
308	if (nrec < THRESH_M3) {
309	m2 = b_lim + (nrec / 2) * rsiz;
310	} else if (nrec < THRESH_M9) {
311	/* use median of 3 */
312	i = ((nrec - 1) / 2) * rsiz;
313	m2 = med3(b_lim, b_lim + i, b_lim + 2 * i);
314	} else {
315	/* approx median of 9 */
316	i = ((nrec - 1) / 8) * rsiz;
317	m1 = med3(b_lim, b_lim + i, b_lim + 2 * i);
318	m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i);
319	m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i);
320	m2 = med3(m1, m2, m3);
321	}
322
323	/*
324	* quick sort partitioning
325	*
326	* The partition limits are defined by bottom and top pointers
327	* b_lim and t_lim.
328	*
329	* qsort uses a fairly standard method of moving the
330	* partitioning pointers, b_par and t_par, to the middle of
331	* the partition and exchanging records that are in the
332	* wrong part of the partition.
333	*
334	* Two enhancements have been made to the basic algorithm.
335	* One for handling duplicate records and one to minimize
336	* the number of swaps.
337	*
338	* Two duplicate records pointers are (b_dup and t_dup) are
339	* initially set to b_lim and t_lim. Each time a record
340	* whose sort key value is equal to the pivot record is found
341	* it will be swapped with the record pointed to by
342	* b_dup or t_dup and the duplicate pointer will be
343	* incremented toward the center.
344	* When partitioning is complete, all the duplicate records
345	* will have been collected at the upper and lower limits of
346	* the partition and can easily be moved adjacent to the
347	* pivot record.
348	*
349	* The second optimization is to minimize the number of swaps.
350	* The pointer m2 points to the pivot record.
351	* During partitioning, if m2 is ever equal to the partitioning
352	* pointers, b_par or t_par, then b_par or t_par just moves
353	* onto the next record without doing a compare.
354	* If as a result of duplicate record detection,
355	* b_dup or t_dup is ever equal to m2,
356	* then m2 is changed to point to the duplicate record and
357	* b_dup or t_dup is incremented with out swapping records.
358	*
359	* When partitioning is done, we may not have the same pivot
360	* record that we started with, but we will have one with
361	* an equal sort key.
362	*/
363	b_dup = b_par = b_lim;
364	t_dup = t_par = t_lim = b_lim + rsiz * (nrec - 1);
365	for (;;) {
366
367	/* move bottom pointer up */
368	for (; b_par <= t_par; b_par += rsiz) {
369	if (b_par == m2) {
370	continue;
371	}
372	cv = cmp(b_par, m2);
373	if (cv > 0) {
374	break;
375	}
376	if (cv == 0) {
377	if (b_dup == m2) {
378	m2 = b_par;
379	} else if (b_dup != b_par) {
380	(*swapf)(b_dup, b_par, loops);
381	}
382	b_dup += rsiz;
383	}
384	}
385
386	/* move top pointer down */
387	for (; b_par < t_par; t_par -= rsiz) {
388	if (t_par == m2) {
389	continue;
390	}
391	cv = cmp(t_par, m2);
392	if (cv < 0) {
393	break;
394	}
395	if (cv == 0) {
396	if (t_dup == m2) {
397	m2 = t_par;
398	} else if (t_dup != t_par) {
399	(*swapf)(t_dup, t_par, loops);
400	}
401	t_dup -= rsiz;
402	}
403	}
404
405	/* break if we are done partitioning */
406	if (b_par >= t_par) {
407	break;
408	}
409
410	/* exchange records at upper and lower break points */
411	(*swapf)(b_par, t_par, loops);
412	b_par += rsiz;
413	t_par -= rsiz;
414	}
415
416	/*
417	* partitioning is now complete
418	*
419	* there are two termination conditions from the partitioning
420	* loop above. Either b_par or t_par have crossed or
421	* they are equal.
422	*
423	* we need to swap the pivot record to its final position
424	* m2 could be in either the upper or lower partitions
425	* or it could already be in its final position
426	*/
427	/*
428	* R[b_par] > R[m2]
429	* R[t_par] < R[m2]
430	*/
431	if (t_par < b_par) {
432	if (m2 < t_par) {
433	(*swapf)(m2, t_par, loops);
434	m2 = b_par = t_par;
435	} else if (m2 > b_par) {
436	(*swapf)(m2, b_par, loops);
437	m2 = t_par = b_par;
438	} else {
439	b_par = t_par = m2;
440	}
441	} else {
442	if (m2 < t_par) {
443	t_par = b_par = t_par - rsiz;
444	}
445	if (m2 != b_par) {
446	(*swapf)(m2, b_par, loops);
447	}
448	m2 = t_par;
449	}
450
451	/*
452	* move bottom duplicates next to pivot
453	* optimized to eliminate overlap
454	*/
455	d_bytelength = b_dup - b_lim;
456	if (b_par - b_dup < d_bytelength) {
457	b_dup = b_lim + (b_par - b_dup);
458	}
459	while (b_dup > b_lim) {
460	b_dup -= rsiz;
461	b_par -= rsiz;
462	(*swapf)(b_dup, b_par, loops);
463	}
464	b_par = m2 - d_bytelength;
465
466	/*
467	* move top duplicates next to pivot
468	*/
469	d_bytelength = t_lim - t_dup;
470	if (t_dup - t_par < d_bytelength) {
471	t_dup = t_lim - (t_dup - t_par);
472	}
473	while (t_dup < t_lim) {
474	t_dup += rsiz;
475	t_par += rsiz;
476	(*swapf)(t_dup, t_par, loops);
477	}
478	t_par = m2 + d_bytelength;
479
480	/*
481	* when a qsort pass completes there are three partitions
482	* 1) the lower contains all records less than pivot
483	* 2) the upper contains all records greater than pivot
484	* 3) the pivot partition contains all record equal to pivot
485	*
486	* all records in the pivot partition are in their final
487	* position and do not need to be accounted for by the stack
488	*
489	* when adding partitions to the stack
490	* it is important to add the largest partition first
491	* to prevent stack overflow.
492	*
493	* calculate number of unsorted records in top and bottom
494	* push resulting partitions on stack
495	*/
496	b_nrec = (b_par - b_lim) / rsiz;
497	t_nrec = (t_lim - t_par) / rsiz;
498	if (b_nrec < t_nrec) {
499	sp->b_lim = t_par + rsiz;
500	sp->nrec = t_nrec;
501	sp++;
502	sp->b_lim = b_lim;
503	sp->nrec = b_nrec;
504	sp++;
505	} else {
506	sp->b_lim = b_lim;
507	sp->nrec = b_nrec;
508	sp++;
509	sp->b_lim = t_par + rsiz;
510	sp->nrec = t_nrec;
511	sp++;
512	}
513	}
514	}
515
516	#endif
517	void pstrcpy(char buf, int buf_size, const char str)
518	{
519	int c;
520	char *q = buf;
521
522	if (buf_size <= 0)
523	return;
524
525	for(;;) {
526	c = *str++;
527	if (c == 0 \|\| q >= buf + buf_size - 1)
528	break;
529	*q++ = c;
530	}
531	*q = '\0';
532	}
533
534	/* strcat and truncate. */
535	char pstrcat(char buf, int buf_size, const char *s)
536	{
537	int len;
538	len = strlen(buf);
539	if (len < buf_size)
540	pstrcpy(buf + len, buf_size - len, s);
541	return buf;
542	}
543
544	int strstart(const char str, const char val, const char **ptr)
545	{
546	const char p, q;
547	p = str;
548	q = val;
549	while (*q != '\0') {
550	if (p != q)
551	return 0;
552	p++;
553	q++;
554	}
555	if (ptr)
556	*ptr = p;
557	return 1;
558	}
559
560	int stristart(const char str, const char val, const char **ptr)
561	{
562	const char p, q;
563	p = str;
564	q = val;
565	while (*q != '\0') {
566	if (toupper(p) != toupper(q))
567	return 0;
568	p++;
569	q++;
570	}
571	if (ptr)
572	*ptr = p;
573	return 1;
574	}
575
576	#ifndef VBOX
577	time_t mktimegm(struct tm *tm)
578	{
579	time_t t;
580	int y = tm->tm_year + 1900, m = tm->tm_mon + 1, d = tm->tm_mday;
581	if (m < 3) {
582	m += 12;
583	y--;
584	}
585	t = 86400 * (d + (153 * m - 457) / 5 + 365 * y + y / 4 - y / 100 +
586	y / 400 - 719469);
587	t += 3600 * tm->tm_hour + 60 * tm->tm_min + tm->tm_sec;
588	return t;
589	}
590	#endif

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

source: vbox/trunk/src/recompiler/cutils.c@ 24345

Download in other formats: