1/*
2 * Copyright 2008, Axel D��rfler, axeld@pinc-software.de.
3 * This file may be used under the terms of the MIT License.
4 */
5
6
7#include <stdio.h>
8#include <stdint.h>
9#include <stdlib.h>
10
11
12int32_t fLargestStart = -1;
13int32_t fLargestLength = -1;
14bool fLargestValid = false;
15int32_t fNumBits = 100;
16
17
18void
19allocate(uint16_t start, int32_t length)
20{
21	if (start + length > fNumBits)
22		return;
23
24	if (fLargestValid) {
25		bool cut = false;
26		if (fLargestStart == start) {
27			// cut from start
28			fLargestStart += length;
29			fLargestLength -= length;
30			cut = true;
31		} else if (start > fLargestStart
32			&& start < fLargestStart + fLargestLength) {
33			// cut from end
34			fLargestLength = start - fLargestStart;
35			cut = true;
36		}
37		if (cut && (fLargestLength < fLargestStart
38				|| fLargestLength
39						< (int32_t)fNumBits - (fLargestStart + fLargestLength))) {
40			// might not be the largest block anymore
41			fLargestValid = false;
42		}
43	}
44}
45
46
47void
48free(uint16_t start, int32_t length)
49{
50	if (start + length > fNumBits)
51		return;
52
53	// The range to be freed cannot be part of the valid largest range
54	if (!(!fLargestValid || start + length <= fLargestStart
55		|| start > fLargestStart))
56		printf("ASSERT failed!\n");
57
58	if (fLargestValid
59		&& (start + length == fLargestStart
60			|| fLargestStart + fLargestLength == start
61			|| (start < fLargestStart && fLargestStart > fLargestLength)
62			|| (start > fLargestStart
63				&& (int32_t)fNumBits - (fLargestStart + fLargestLength)
64						> fLargestLength))) {
65		fLargestValid = false;
66	}
67}
68
69
70void
71test(int32_t num, int32_t nextLargestStart, int32_t nextLargestLength,
72	bool nextLargestValid)
73{
74	const char* error = NULL;
75	if (nextLargestValid != fLargestValid)
76		error = "valid differs";
77	else if (!nextLargestValid)
78		return;
79
80	if (nextLargestStart != fLargestStart)
81		error = "start differ";
82	else if (nextLargestLength != fLargestLength)
83		error = "length differs";
84
85	if (error == NULL)
86		return;
87
88	printf("%d: %s: is %d.%d%s, should be %d.%d%s\n", num, error, fLargestStart,
89		fLargestLength, fLargestValid ? "" : " (INVALID)", nextLargestStart,
90		nextLargestLength, nextLargestValid ? "" : " (INVALID)");
91	exit(1);
92}
93
94
95void
96test_allocate(int32_t num, int32_t largestStart, int32_t largestLength,
97	int32_t start, int32_t length, int32_t nextLargestStart,
98	int32_t nextLargestLength, bool nextLargestValid)
99{
100	fLargestStart = largestStart;
101	fLargestLength = largestLength;
102	fLargestValid = true;
103
104	printf("Test %d: %d.%d - allocate %d.%d\n", num, fLargestStart,
105		fLargestLength, start, length);
106
107	allocate(start, length);
108	test(num, nextLargestStart, nextLargestLength, nextLargestValid);
109}
110
111
112void
113test_free(int32_t num, int32_t largestStart, int32_t largestLength, int32_t start,
114	int32_t length, int32_t nextLargestStart, int32_t nextLargestLength,
115	bool nextLargestValid)
116{
117	fLargestStart = largestStart;
118	fLargestLength = largestLength;
119	fLargestValid = true;
120
121	printf("Test %d: %d.%d - free %d.%d\n", num, fLargestStart, fLargestLength,
122		start, length);
123
124	free(start, length);
125	test(num, nextLargestStart, nextLargestLength, nextLargestValid);
126}
127
128
129int
130main(int argc, char** argv)
131{
132	puts("------------- Allocate Tests -------------\n");
133	test_allocate(1, 40, 50, 20, 20, 40, 50, true);	// touch start
134	test_allocate(2, 40, 50, 20, 19, 40, 50, true);	// don't touch start
135	test_allocate(3, 40, 10, 40, 1, 41, 9, false);	// cut start
136	test_allocate(4, 40, 50, 40, 1, 41, 49, true);	// cut start
137	test_allocate(5, 40, 50, 90, 1, 40, 50, true);	// touch end
138	test_allocate(6, 40, 50, 89, 1, 40, 49, true);	// cut end
139	test_allocate(7, 40, 20, 59, 1, 40, 19, false);	// cut end
140	test_allocate(8, 0, 51, 0, 1, 1, 50, true);		// cut start
141	test_allocate(9, 0, 51, 0, 2, 2, 49, true);		// cut start
142	test_allocate(10, 0, 51, 0, 3, 3, 48, false);	// cut start
143
144	puts("------------- Free Tests -------------\n");
145	test_free(1, 40, 50, 20, 20, 40, 50, false);	// touch start
146	test_free(2, 40, 50, 20, 19, 40, 50, true);		// before start
147	test_free(3, 50, 40, 20, 19, 40, 50, false);	// before start
148	test_free(4, 40, 40, 80, 20, 40, 80, false);	// touch end
149	test_free(5, 40, 40, 81, 20, 40, 40, true);		// after end
150	test_free(6, 40, 20, 60, 20, 40, 80, false);	// touch end
151	test_free(7, 40, 20, 61, 20, 40, 80, false);	// after end
152	test_free(8, 40, 20, 41, 20, 40, 80, false);	// after end
153	return 0;
154}
155