1 /* 2 * Copyright (c) 1999-2002, Darren Hiebert 3 * 4 * This source code is released for free distribution under the terms of the 5 * GNU General Public License version 2 or (at your option) any later version. 6 * 7 * This module contains functions managing resizable pointer arrays. 8 */ 9 10 /* 11 * INCLUDE FILES 12 */ 13 #include "general.h" /* must always come first */ 14 15 #include "debug.h" 16 #include "numarray.h" 17 #include "routines.h" 18 19 #include <stdlib.h> 20 #include <string.h> 21 22 #define impNumArray(prefix,Prefix,type) \ 23 \ 24 struct s##Prefix##Array { \ 25 unsigned int max; \ 26 unsigned int count; \ 27 type *array; \ 28 }; \ 29 \ 30 extern prefix##Array *prefix##ArrayNew (void) \ 31 { \ 32 prefix##Array* const result = xMalloc (1, prefix##Array); \ 33 result->max = 8; \ 34 result->count = 0; \ 35 result->array = xMalloc (result->max, type); \ 36 return result; \ 37 } \ 38 \ 39 extern unsigned int prefix##ArrayAdd (prefix##Array *const current, type num) \ 40 { \ 41 Assert (current != NULL); \ 42 if (current->count == current->max) \ 43 { \ 44 current->max *= 2; \ 45 current->array = xRealloc (current->array, current->max, type); \ 46 } \ 47 current->array [current->count] = num; \ 48 return current->count++; \ 49 } \ 50 \ 51 extern void prefix##ArrayRemoveLast (prefix##Array *const current) \ 52 { \ 53 Assert (current != NULL); \ 54 Assert (current->count > 0); \ 55 --current->count; \ 56 } \ 57 \ 58 extern void prefix##ArrayCombine (prefix##Array *const current, prefix##Array *const from) \ 59 { \ 60 unsigned int i; \ 61 Assert (current != NULL); \ 62 Assert (from != NULL); \ 63 for (i = 0 ; i < from->count ; ++i) \ 64 prefix##ArrayAdd (current, from->array [i]); \ 65 from->count = 0; \ 66 prefix##ArrayDelete (from); \ 67 } \ 68 \ 69 extern unsigned int prefix##ArrayCount (const prefix##Array *const current) \ 70 { \ 71 Assert (current != NULL); \ 72 return current->count; \ 73 } \ 74 \ 75 extern bool prefix##ArrayIsEmpty (const prefix##Array *const current) \ 76 { \ 77 return (prefix##ArrayCount(current) == 0); \ 78 } \ 79 \ 80 extern type prefix##ArrayItem (const prefix##Array *const current, const unsigned int indx) \ 81 { \ 82 Assert (current != NULL); \ 83 return current->array [indx]; \ 84 } \ 85 \ 86 extern type prefix##ArrayLast (const prefix##Array *const current) \ 87 { \ 88 Assert (current != NULL); \ 89 Assert (current->count > 0); \ 90 return current->array [current->count - 1]; \ 91 } \ 92 \ 93 extern void prefix##ArrayClear (prefix##Array *const current) \ 94 { \ 95 Assert (current != NULL); \ 96 current->count = 0; \ 97 } \ 98 \ 99 extern void prefix##ArrayDelete (prefix##Array *const current) \ 100 { \ 101 if (current != NULL) \ 102 { \ 103 prefix##ArrayClear (current); \ 104 eFree (current->array); \ 105 eFree (current); \ 106 } \ 107 } \ 108 \ 109 extern bool prefix##ArrayHasTest (const prefix##Array *const current, \ 110 bool (*test)(const type num, void *userData), \ 111 void *userData) \ 112 { \ 113 bool result = false; \ 114 unsigned int i; \ 115 Assert (current != NULL); \ 116 for (i = 0 ; ! result && i < current->count ; ++i) \ 117 result = (*test)(current->array [i], userData); \ 118 return result; \ 119 } \ 120 \ 121 static bool prefix##Eq (const type num, void *userData) \ 122 { \ 123 type *num0 = userData; \ 124 return (num == *num0); \ 125 } \ 126 \ 127 extern bool prefix##ArrayHas (const prefix##Array *const current, type num) \ 128 { \ 129 return prefix##ArrayHasTest (current, prefix##Eq, &num); \ 130 } \ 131 \ 132 extern void prefix##ArrayReverse (const prefix##Array *const current) \ 133 { \ 134 unsigned int i, j; \ 135 type tmp; \ 136 \ 137 Assert (current != NULL); \ 138 for (i = 0, j = current->count - 1 ; i < (current->count / 2); ++i, --j) \ 139 { \ 140 tmp = current->array[i]; \ 141 current->array[i] = current->array[j]; \ 142 current->array[j] = tmp; \ 143 } \ 144 } \ 145 \ 146 extern void prefix##ArrayDeleteItem (prefix##Array* const current, unsigned int indx) \ 147 { \ 148 memmove (current->array + indx, current->array + indx + 1, \ 149 (current->count - indx - 1) * sizeof (*current->array)); \ 150 --current->count; \ 151 } \ 152 static int prefix##GreaterThan(const void *a, const void *b) \ 153 { \ 154 type an = *(type *)a; \ 155 type bn = *(type *)b; \ 156 if (an > bn) \ 157 return 1; \ 158 else if (an == bn) \ 159 return 0; \ 160 else \ 161 return -1; \ 162 } \ 163 static int prefix##LessThan(const void *a, const void *b) \ 164 { \ 165 return prefix##GreaterThan (b, a); \ 166 } \ 167 extern void prefix##ArraySort (prefix##Array *const current, bool descendingOrder) \ 168 { \ 169 if (descendingOrder) \ 170 qsort (current->array, current->count, sizeof (type), prefix##GreaterThan); \ 171 else \ 172 qsort (current->array, current->count, sizeof (type), prefix##LessThan); \ 173 } 174 175 /* We expect the linker we use is enough clever to delete dead code. */ 176 impNumArray(char, Char, char) 177 impNumArray(uchar, Uchar, unsigned char) 178 impNumArray(int, Int, int) 179 impNumArray(uint, Uint, unsigned int) 180 impNumArray(long, Long, long) 181 impNumArray(ulong, Ulong, unsigned long) 182