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
12 int32_t fLargestStart = -1;
13 int32_t fLargestLength = -1;
14 bool fLargestValid = false;
15 int32_t fNumBits = 100;
16
17
18 void
allocate(uint16_t start,int32_t length)19 allocate(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
47 void
free(uint16_t start,int32_t length)48 free(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
70 void
test(int32_t num,int32_t nextLargestStart,int32_t nextLargestLength,bool nextLargestValid)71 test(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
95 void
test_allocate(int32_t num,int32_t largestStart,int32_t largestLength,int32_t start,int32_t length,int32_t nextLargestStart,int32_t nextLargestLength,bool nextLargestValid)96 test_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
112 void
test_free(int32_t num,int32_t largestStart,int32_t largestLength,int32_t start,int32_t length,int32_t nextLargestStart,int32_t nextLargestLength,bool nextLargestValid)113 test_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
129 int
main(int argc,char ** argv)130 main(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