Implementing a stack of strings in C

Applications Programming
1

I'm trying to create a simplified version of dc to learn from. The first thing I notice is that the main stack stores strings. How would I implement a string stack in C? How is something like this:

struct StringStack
{
   const unsigned int pysicalSize;     // physical size of the stack
   const char ** const basePtr;        // cannot change bottommost pointer or pointee
   char **stackPtr;                    // top of stack
   unsigned int logicalSize;           // number of elements in the array
};

Thoughts?

---------- Post updated at 06:33 PM ---------- Previous update was at 04:59 PM ----------

Actually I don't think I need the stackPtr because I can just use the basePtr + the logicalSize.

2

But where is your actual array that will store the strings as they are entered...

3

That would be basePtr, one would think.

You can't make it a const as you'll need to change it at least once, when you allocate memory to it. :wink:

4

Come to think of it, I wrote a simple string list which can easily be modified for what you need. Just one function missing...

// strlist.h

#ifndef __STRLIST_H__
#define __STRLIST_H__

typedef struct strlist
{
        int size;
        int pos;
        char *list[1]; // Actually ends up being larger than one element because of malloc() size
} strlist;

#ifdef __cplusplus
extern "C" {
#endif

strlist *strlist_create(void);
strlist *strlist_resize(strlist *s);
void strlist_free(strlist *s);
strlist *strlist_append(strlist *s, const char *str);

char *strlist_pop(strlist *s);

#ifdef __cplusplus
}
#endif

#endif/*__STRLIST_H__*/

//strlist.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "strlist.h"

#define STRLIST_MINSIZE 16
#define STRLIST_FREE(X) (((X)->size)-((X)->pos))

strlist *strlist_create(void)
{
        strlist *s=malloc(sizeof(strlist)+(sizeof(char *)*STRLIST_MINSIZE));
        s->pos=0;
        s->size=STRLIST_MINSIZE;
        return(s);
}

strlist *strlist_resize(strlist *s)
{
        strlist *n=realloc(s, sizeof(strlist) +
                (sizeof(char *)*(s->size<<1)));

        if(n == NULL)
                return(NULL);

        n->size<<=1;

        return(n);
}

void strlist_free(strlist *s)
{
        int n;
        for(n=0; n<s->pos; n++)
                free(s->list[n]);
        free(s);
}

strlist *strlist_append(strlist *s, const char *str)
{
        if(STRLIST_FREE(s) <= 0)
        {
                strlist *n=strlist_resize(s);
                if(n == NULL)
                        return(NULL);
                s=n;
        }

        s->list[s->pos++]=strdup(str);
        return(s);
}

char *strlist_pop(strlist *s)
{
        if(s->pos <= 0) return(NULL);
        return(s->list[--s->pos]);
}

If it has to enlarge the size of the stack, then the pointer may change, so pay attention to the return value of the functions when they return strlist *'s.

[edit] Oh yeah. And if you pop() a string, you have to free() the pointer it returns.