1/* 2 * = = == === ===== ======== ============= ===================== 3 * == pt::rde (critcl) - Data Structures - Generic stack 4 */ 5 6#include <stack.h> /* Our public API */ 7#include <util.h> /* Allocation macros */ 8 9/* 10 * = = == === ===== ======== ============= ===================== 11 */ 12 13typedef struct RDE_STACK_ { 14 long int max; /* Size of the cell array. */ 15 long int top; /* Index of the topmost _unused_ cell in the 16 * array === Index of the _next_ cell to use 17 * === Size of the stack. */ 18 RDE_STACK_CELL_FREE freeCellProc; 19 void** cell; /* Array of the stack cells. */ 20} RDE_STACK_; 21 22 23/* 24 * = = == === ===== ======== ============= ===================== 25 */ 26 27SCOPE RDE_STACK 28rde_stack_new (RDE_STACK_CELL_FREE freeCellProc) 29{ 30 RDE_STACK s = ALLOC (RDE_STACK_); 31 s->cell = NALLOC (RDE_STACK_INITIAL_SIZE, void*); 32 s->max = RDE_STACK_INITIAL_SIZE; 33 s->top = 0; 34 s->freeCellProc = freeCellProc; 35 36 return s; 37} 38 39SCOPE void 40rde_stack_del (RDE_STACK s) 41{ 42 if (s->freeCellProc && s->top) { 43 long int i; 44 for (i=0; i < s->top; i++) { 45 ASSERT_BOUNDS(i,s->max); 46 s->freeCellProc ( s->cell [i] ); 47 } 48 } 49 50 ckfree ((char*) s->cell); 51 ckfree ((char*) s); 52} 53 54SCOPE void 55rde_stack_push (RDE_STACK s, void* item) 56{ 57 if (s->top >= s->max) { 58 long int new = s->max ? (2 * s->max) : RDE_STACK_INITIAL_SIZE; 59 void** cell = (void**) ckrealloc ((char*) s->cell, new * sizeof(void*)); 60 ASSERT (cell,"Memory allocation failure for RDE stack"); 61 s->max = new; 62 s->cell = cell; 63 } 64 65 ASSERT_BOUNDS(s->top,s->max); 66 s->cell [s->top] = item; 67 s->top ++; 68} 69 70SCOPE void* 71rde_stack_top (RDE_STACK s) 72{ 73 ASSERT_BOUNDS(s->top-1,s->max); 74 return s->cell [s->top - 1]; 75} 76 77SCOPE void 78rde_stack_pop (RDE_STACK s, long int n) 79{ 80 ASSERT (n >= 0, "Bad pop count"); 81 if (n == 0) return; 82 83 if (s->freeCellProc) { 84 while (n) { 85 s->top --; 86 ASSERT_BOUNDS(s->top,s->max); 87 s->freeCellProc ( s->cell [s->top] ); 88 n --; 89 } 90 } else { 91 s->top -= n; 92 } 93} 94 95SCOPE void 96rde_stack_trim (RDE_STACK s, long int n) 97{ 98 ASSERT (n >= 0, "Bad trimsize"); 99 100 if (s->freeCellProc) { 101 while (s->top > n) { 102 s->top --; 103 ASSERT_BOUNDS(s->top,s->max); 104 s->freeCellProc ( s->cell [s->top] ); 105 } 106 } else { 107 s->top = n; 108 } 109} 110 111SCOPE void 112rde_stack_drop (RDE_STACK s, long int n) 113{ 114 ASSERT (n >= 0, "Bad pop count"); 115 if (n == 0) return; 116 s->top -= n; 117} 118 119SCOPE void 120rde_stack_move (RDE_STACK dst, RDE_STACK src) 121{ 122 ASSERT (dst->freeCellProc == src->freeCellProc, "Ownership mismatch"); 123 124 /* 125 * Note: The destination takes ownership of the moved cell, thus there is 126 * no need to run free on them. 127 */ 128 129 while (src->top > 0) { 130 src->top --; 131 ASSERT_BOUNDS(src->top,src->max); 132 rde_stack_push (dst, src->cell [src->top] ); 133 } 134} 135 136SCOPE void 137rde_stack_get (RDE_STACK s, long int* cn, void*** cc) 138{ 139 *cn = s->top; 140 *cc = s->cell; 141} 142 143SCOPE long int 144rde_stack_size (RDE_STACK s) 145{ 146 return s->top; 147} 148 149/* 150 * = = == === ===== ======== ============= ===================== 151 */ 152 153 154/* 155 * Local Variables: 156 * mode: c 157 * c-basic-offset: 4 158 * fill-column: 78 159 * End: 160 */ 161