| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * RANDOM ACCESS STACK * */ |
| /* * * */ |
| /* * $Module: RAS * */ |
| /* * * */ |
| /* * Copyright (C) 1999, 2000, 2001 MPI fuer Informatik * */ |
| /* * * */ |
| /* * This program is free software; you can redistribute * */ |
| /* * it and/or modify it under the terms of the GNU * */ |
| /* * General Public License as published by the Free * */ |
| /* * Software Foundation; either version 2 of the License, * */ |
| /* * or (at your option) any later version. * */ |
| /* * * */ |
| /* * This program is distributed in the hope that it will * */ |
| /* * be useful, but WITHOUT ANY WARRANTY; without even * */ |
| /* * the implied warranty of MERCHANTABILITY or FITNESS * */ |
| /* * FOR A PARTICULAR PURPOSE. See the GNU General Public * */ |
| /* * License for more details. * */ |
| /* * * */ |
| /* * You should have received a copy of the GNU General * */ |
| /* * Public License along with this program; if not, write * */ |
| /* * to the Free Software Foundation, Inc., 59 Temple * */ |
| /* * Place, Suite 330, Boston, MA 02111-1307 USA * */ |
| /* * * */ |
| /* * * */ |
| /* $Revision$ * */ |
| /* $State$ * */ |
| /* $Date$ * */ |
| /* $Author$ * */ |
| /* * * */ |
| /* * Contact: * */ |
| /* * Christoph Weidenbach * */ |
| /* * MPI fuer Informatik * */ |
| /* * Stuhlsatzenhausweg 85 * */ |
| /* * 66123 Saarbruecken * */ |
| /* * Email: weidenb@mpi-sb.mpg.de * */ |
| /* * Germany * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| #ifndef _RAS_ |
| #define _RAS_ |
| |
| |
| /**************************************************************/ |
| /* Includes */ |
| /**************************************************************/ |
| |
| #include "misc.h" |
| #include "memory.h" |
| |
| |
| /**************************************************************/ |
| /* Constants and types */ |
| /**************************************************************/ |
| |
| #define ras_alloc -1 /* index of size of allocated space */ |
| #define ras_top -2 /* index of next free element */ |
| #define ras_head 2 /* size of stack head for management purposes */ |
| #define ras_stdsize 16 /* standard stack size */ |
| |
| |
| typedef POINTER *RAS; |
| |
| /* A RAS (Random Access Stack) is a pointer to an array of elements */ |
| /* where the actual size of the stack and its current top pointer */ |
| /* are stored one and two cells before the array pointer. */ |
| |
| |
| /**************************************************************/ |
| /* Inline Functions */ |
| /**************************************************************/ |
| |
| static __inline__ RAS ras_CreateWithSize(int size) |
| /**************************************************************** |
| INPUT: The maximal expected size of the stack to create. |
| RETURNS: A new empty stack. |
| *****************************************************************/ |
| { |
| RAS result; |
| |
| #ifdef CHECK |
| if (size <= 0) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_CreateWithSize: size not positive."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| result = (RAS) memory_Malloc((size + ras_head) * sizeof(POINTER)); |
| result = result + ras_head; /* leave space for head */ |
| result[ras_alloc] = (POINTER) size; |
| result[ras_top] = (POINTER) 0; |
| return result; |
| } |
| |
| |
| static __inline__ RAS ras_Create(void) |
| { |
| return ras_CreateWithSize(ras_stdsize); |
| } |
| |
| |
| static __inline__ void ras_Free(RAS ras) |
| { |
| if (ras != NULL) { |
| memory_Free ( |
| ras - ras_head, |
| (ras_head + (int) ras[ras_alloc]) * sizeof(POINTER) |
| ); |
| } |
| } |
| |
| |
| static __inline__ RAS ras_InitWithSize(RAS ras, int size) |
| /**************************************************************** |
| INPUT: A random access stack the maximal expected size of the |
| stack to init. |
| RETURNS: The initialized and potentially new stack. |
| CAUTION: Because it potentially frees the old stack this |
| function must be called inside an assignment like: |
| stack = ras_InitWithSize(stack, ...) |
| *****************************************************************/ |
| { |
| |
| #ifdef CHECK |
| if (size <= 0) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_InitWithSize: size not positive."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (size > (int) ras[ras_alloc]) { |
| ras_Free(ras); |
| ras = ras_CreateWithSize(size); |
| } |
| else |
| ras[ras_top] = (POINTER) 0; |
| return ras; |
| } |
| |
| |
| static __inline__ RAS ras_Init(RAS ras) |
| /**************************************************************** |
| INPUT: A random access stack. |
| RETURNS: The initialized and potentially new stack. |
| CAUTION: Because it potentially frees the old stack this |
| function must be called inside an assignment like: |
| stack = ras_InitWithSize(stack, ...) |
| *****************************************************************/ |
| { |
| return ras_InitWithSize(ras, ras_stdsize); |
| } |
| |
| |
| static __inline__ int ras_Size(RAS ras) |
| { |
| return (int) ras[ras_top]; |
| } |
| |
| |
| static __inline__ RAS ras_FastPush(RAS ras, POINTER entry) |
| /********************************************************* |
| INPUT: A random access stack and an element to push. |
| RETURNS: The modified stack. |
| CAUTION: The function does not care about stack overflow! |
| **********************************************************/ |
| { |
| int top; |
| |
| #ifdef CHECK |
| if (ras_Size(ras) == (int) ras[ras_alloc]) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_FastPush: stack overflow."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| top = ras_Size(ras); |
| ras[top++] = entry; |
| ras[ras_top] = (POINTER) top; |
| return ras; |
| } |
| |
| |
| static __inline__ RAS ras_Push(RAS ras, POINTER entry) |
| /********************************************************* |
| INPUT: A random access stack and an element to push. |
| RETURNS: The modified and potentially new stack. |
| SUMMARY: Before the push the stack is checked for overflow |
| and in case of overflow its size is doubled while |
| elements are copied to the (new) stack. |
| CAUTION: Must be called inside an assignment: |
| stack = ras_Push(stack, ...) |
| **********************************************************/ |
| { |
| RAS old; |
| int oldsize; |
| POINTER *oldscan, *scan; |
| |
| /* if not enough space allocated, double it: */ |
| if (ras_Size(ras) == (int) ras[ras_alloc]) { |
| old = ras; |
| oldsize = (int) old[ras_alloc]; |
| ras = ras_CreateWithSize(oldsize * 2); |
| ras[ras_top] = (POINTER) oldsize; |
| |
| /* copy entries: */ |
| for (oldscan = old + oldsize - 1,scan = ras + oldsize - 1; oldscan >= old; |
| oldscan--, scan--) |
| *scan = *oldscan; |
| |
| ras_Free(old); |
| } |
| |
| return ras_FastPush(ras, entry); |
| } |
| |
| |
| static __inline__ BOOL ras_LegalIndex(RAS ras, int index) |
| { |
| return 0 <= index && index < ras_Size(ras); |
| } |
| |
| |
| static __inline__ POINTER ras_Get(RAS ras, int index) |
| { |
| #ifdef CHECK |
| if (!ras_LegalIndex(ras, index)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_Get: illegal stack index."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| return ras[index]; |
| } |
| |
| |
| static __inline__ RAS ras_Set(RAS ras, int index, POINTER entry) |
| { |
| #ifdef CHECK |
| if (!ras_LegalIndex(ras, index)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_Set: illegal stack index."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| ras[index] = entry; |
| return ras; |
| } |
| |
| |
| static __inline__ BOOL ras_Empty(RAS ras) |
| { |
| return ras_Size(ras) == 0; |
| } |
| |
| |
| static __inline__ POINTER ras_Pop(RAS ras) |
| { |
| int top; |
| |
| #ifdef CHECK |
| if (ras_Empty(ras)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_Pop: empty stack."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| top = ras_Size(ras) - 1; |
| ras[ras_top] = (POINTER) top; |
| return ras[top]; |
| } |
| |
| |
| static __inline__ POINTER ras_Top(RAS ras) |
| { |
| #ifdef CHECK |
| if (ras_Empty(ras)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In ras_Top: empty stack."); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| return ras[ras_Size(ras) - 1]; |
| } |
| |
| |
| #endif |
| |