ptrstack.c

00001 /***************************************************************************
00002 *cr
00003 *cr (C) Copyright 1995-2019 The Board of Trustees of the
00004 *cr University of Illinois
00005 *cr All Rights Reserved
00006 *cr
00007 ***************************************************************************/
00008 
00009 /***************************************************************************
00010 * RCS INFORMATION:
00011 *
00012 * $RCSfile: ptrstack.c,v $
00013 * $Author: johns $ $Locker: $ $State: Exp $
00014 * $Revision: 1.3 $ $Date: 2019年01月17日 21:21:03 $
00015 *
00016 ***************************************************************************
00017 * DESCRIPTION:
00018 * Trivial stack implementation for use in eliminating recursion
00019 * in molecule graph traversal algorithms.
00020 *
00021 ***************************************************************************/
00022 
00023 #include <stdio.h>
00024 #include <stdlib.h>
00025 #include "ptrstack.h"
00026 
00027 typedef struct {
00028 int growthrate;
00029 int size;
00030 int top;
00031 void **s;
00032 } ptrstack;
00033 
00034 PtrStackHandle ptrstack_create(int size) {
00035 ptrstack *s;
00036 
00037 s = (ptrstack *) malloc(sizeof(ptrstack));
00038 if (s == NULL)
00039 return NULL;
00040 
00041 s->growthrate = 32768;
00042 s->top = -1;
00043 
00044 if (size > 0) {
00045 s->size = size;
00046 s->s = (void **) malloc(s->size * sizeof(void *));
00047 } else {
00048 s->size = 0;
00049 s->s = NULL;
00050 }
00051 
00052 return s;
00053 }
00054 
00055 
00056 void ptrstack_destroy(PtrStackHandle voidhandle) {
00057 ptrstack *s = (ptrstack *) voidhandle;
00058 free(s->s);
00059 s->s = NULL; /* prevent access after free */
00060 free(s);
00061 }
00062 
00063 
00064 int ptrstack_compact(PtrStackHandle voidhandle) {
00065 ptrstack *s = (ptrstack *) voidhandle;
00066 
00067 if (s->size > (s->top + 1)) {
00068 int newsize = s->top + 1;
00069 void **tmp = (void **) realloc(s->s, newsize * sizeof(void *));
00070 if (tmp == NULL)
00071 return -1;
00072 s->s = tmp;
00073 s->size = newsize; 
00074 }
00075 
00076 return 0;
00077 }
00078 
00079 int ptrstack_push(PtrStackHandle voidhandle, void *p) {
00080 ptrstack *s = (ptrstack *) voidhandle;
00081 
00082 s->top++;
00083 if (s->top >= s->size) {
00084 int newsize = s->size + s->growthrate; 
00085 void *tmp = (int *) realloc(s->s, newsize * sizeof(void *));
00086 if (tmp == NULL) {
00087 s->top--;
00088 return -1; /* out of space! */
00089 }
00090 s->s = tmp;
00091 s->size = newsize;
00092 } 
00093 
00094 s->s[s->top] = p; /* push onto the stack */
00095 
00096 return 0;
00097 }
00098 
00099 
00100 int ptrstack_pop(PtrStackHandle voidhandle, void **p) {
00101 ptrstack *s = (ptrstack *) voidhandle;
00102 if (s->top < 0)
00103 return -1;
00104 
00105 *p = s->s[s->top];
00106 s->top--;
00107 
00108 return 0;
00109 }
00110 
00111 int ptrstack_popall(PtrStackHandle voidhandle) {
00112 ptrstack *s = (ptrstack *) voidhandle;
00113 s->top = -1;
00114 
00115 return 0;
00116 }
00117 
00118 int ptrstack_empty(PtrStackHandle voidhandle) {
00119 ptrstack *s = (ptrstack *) voidhandle;
00120 if (s->top < 0) return 1;
00121 else return 0;
00122 }
00123 
00124