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