Navigation

Changeset 506

Timestamp:

01/12/11 05:37:50 (14 years ago)

Author:

braddr

Message:

fix array sort

Files:

r433	r506
37	37
38	38	private const int _maxspan = 7; // subarrays of _maxspan or fewer elements
39	39	// will be sorted by a simple insertion sort
40	40
41	41	/* Adjust _maxspan according to relative cost of a swap and a compare. Reduce
42	42	_maxspan (not less than 1) if a swap is very expensive such as when you have
43	43	an array of large structures to be sorted, rather than an array of pointers to
44	44	structures. The default value is optimized for a high cost for compares. */
45	45
46	46
47		extern (C) ~~long~~ _adSort(Array a, TypeInfo ti)
	47	extern (C) void[] _adSort(Array a, TypeInfo ti)
48	48	{
49	49	byte*[40] stack; // stack
50	50	byte* i, j; // scan and limit pointers
51	51	auto width = ti.tsize();
52	52
53	53	auto base = cast(byte *)a.ptr;
54	54	auto thresh = _maxspan * width; // size of _maxspan elements in bytes
55	55	auto sp = stack.ptr; // stack pointer
56	56	auto limit = base + a.length * width; // pointer past end of array
57	57	while (1) // repeat until done then return
…	…
114	114	i += width;
115	115	}
116	116
117	117	if (sp > stack.ptr) // if any entries on stack...
118	118	{
119	119	sp -= 2; // pop the base and limit
120	120	base = sp[0];
121	121	limit = sp[1];
122	122	}
123	123	else // else stack empty, all done
124		return cast(~~long~~)(&a);
	124	return cast(void[])(&a);
125	125	}
126	126	assert(0);
127	127	}
128	128
129	129
130	130	unittest
131	131	{
132	132	debug(qsort) printf("array.sort.unittest()\n");
133	133
134	134	int a[] = new int[10];