11
\$\begingroup\$

I'm a beginning C programmer. As an exercise, I have attempted to implement a stack of strings in C. This is my first real exercise working with pointers. I looked at some other similar posts on here, and read through the comments. It seems that most individuals have chosen to do this by using linked lists, whereas I've just created an ArrayStack.

Maybe it would have been better to go the linked list route. Nonetheless, this is how I did it. I'm hoping there's not any glaring errors, but I'm sure there will be.

Also, question: I have a variable for the number of slots available in the array, which is used to determine when more memory needs to be allocated. But it would seem to me that I can use sizeof on the array, and sizeof on a single pointer in the array, and use division to get the number of slots, thus eliminating a variable. Would this be a better approach?

stack.h

#include <stdlib.h>

typedef struct stringstack {
    int count;
    int slots;
    char** stack;
} stringstack;

void * makestack(void);
void push(struct stringstack* ptr, char stringtext[]);
char * pop(struct stringstack* ptr);
char * peek(struct stringstack* ptr);
int isempty(struct stringstack* ptr);
void destroy(struct stringstack* ptr);

stack.c

#include "stack.h"

/* Function creates a new stringstack object and returns a pointer to it */
void * makestack(void) {
    stringstack *ptr = (stringstack *) malloc(sizeof(stringstack));
    ptr->count = 0;
    ptr->slots = 1;
    ptr->stack = (char **) malloc(sizeof(char*));
    return ptr;
}

/* Pushes a string onto the top of a stack */
void push(struct stringstack* ptr, char stringtext[]) {
    ptr->count++;
    if (ptr->count == ptr->slots) /* Allocate more space if necessary */
        ptr->stack = (char **) realloc(ptr->stack, sizeof(char *)*((ptr->slots*=2)+1));
    char *stringptr = (char *) malloc(sizeof(stringtext));
    stringptr = stringtext;
    *(ptr->stack + ptr->count) = stringptr;
}

/* Removes the top item from the stack, returning a pointer to it */
char * pop(struct stringstack* ptr) {
    if (ptr->count>0)
        return *(ptr->stack + ptr->count--);
    return NULL;
}

/* Returns a pointer to top item from stack but does not pop it */
char * peek(struct stringstack* ptr) {
    if (ptr->count>0)
        return *(ptr->stack + ptr->count);
    return NULL;
}

/* Returns whether a stringstack contains at least one string */
int isempty(struct stringstack* ptr) {
    return (ptr->count == 0);
}

/* Frees a stringtack from memory */
void destroy(struct stringstack* ptr) {
    size_t n;
    for (n = 0; n <= ptr->count; n++ )
        free(ptr->stack+n);
    free(ptr->stack);
    free(ptr);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! That looks like an interesting implementation. I hope you get good reviews! \$\endgroup\$ – Phrancis Nov 19 '14 at 0:21
10
\$\begingroup\$
  • makestack should return a struct stringstack * instead of void *.

  • malloc and realloc may fail. Check their return values.

  • push doesn't copy the string (it only makes a redundant copy of the pointer). It is OK as long as you can guarantee that the string parameter has a lifetime long enough. Consider a scenario:

    void foo(struct stringstack * stack)
    {
        char bar[] = "aaa";
        push(stack, bar);
    }
    

    Upon the return, bar disappears, and the stack entry points to the pretty random place in the application stack. Do not expect to have "aaa" there.

    To actually copy the string, do

     *(ptr->stack + ptr->count) = strdup(stringtext);
    

    which may introduce other problems in interacting with client (who owns the string after peek?). Unfortunately, C doesn't offer a clean solution.

  • You may want to shrink the stack when ptr->count hits the low watermark of ptr->slots.

\$\endgroup\$
  • \$\begingroup\$ Oh, you're right. Yeah that's kind of a big error on my part for the push function... I knew there would be one! Thank you (for the other stuff as well.) \$\endgroup\$ – Chris Qu Nov 19 '14 at 0:46
6
\$\begingroup\$

First, to answer your question about sizeof, run this simple test code:

char * str_1    = "foo1";
char   str_2[5] = "foo2";

printf("%zu\n", sizeof(str_1)); // 8 or 4
printf("%zu\n", sizeof(str_2)); // 5

On my machine, it prints 8 and 5. This is because sizeof behaves differently when applied to an array vs a pointer to an array. If you apply sizeof to an array which its size is known at compile time, sizeof will produce the size in bytes of such array. If you apply it to a pointer to an array of variable size, allocated either dynamically or by acquiring a pointer to a static array, sizeof will produce the size in bytes of the pointer, hence the 8 for the first printf call (on my machine pointers are 8 bytes wide). So no, you can't use sizeof to infer the size of a dynamically allocated array.

Code review:

You don't need to include <stdio.h> in the header. It would be better to only include it in the implementation. Also, your header lack an include guard.


The stringstack implementation could be hidden. If you declare an opaque/incomplete type in the header, the definition of the struct could go in the .c file. That would make it hidden to outside users, so you would also have to provide methods to get the stack size, etc. Hiding implementation details is generally desirable, since it makes the code more robust to change. So you might consider this approach. Example:

stack.h:

typedef struct stringstack;

/* All the function prototypes... */

stack.c:

typedef struct stringstack {
    int count;
    int slots;
    char** stack;
} stringstack;

/* The code... */

makestack() should return a pointer to stringstack, not void*. Also, since you have declared the type with a typedef struct, you can omit the struct tag when referring to stringstack.


Personally, I find tightlypacked names hard to read. Consider using snake_case for the multi-word function names. Also, calling the stack type StringStack to differentiate it from the name of a function wouldn't be a bad idea.


Read-only function parameters of pointer type should be const, to document the intent of the function. Since you only read the string in push(), the ideal function signature would be:

void push(struct stringstack* ptr, const char stringtext[])

Functions that only query the stack, like isempty() could also take the stack pointer by const stringstack*.


Use assertions to enforce invariants. The invariant of every function is that the stack pointer is not null. You should assert that on function entry to ensure a null pointer is trapped right away.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hm, yeah. You're right about the sizeof thing. I knew that wouldn't work, but for some reason I brainfarted. -.- Thank you for all of your suggestions. I have a bit of reading to do (assert, include guarding.) But I understand the other suggestions, and I like them. \$\endgroup\$ – Chris Qu Nov 19 '14 at 1:17
4
\$\begingroup\$

I've modified your code with some cleanups. My comments are in "//" style comments to explain the changes. The main things I changed:

  1. The stack now uses array index [0]. Previously, that index was just wasted.
  2. The code uses const when appropriate.
  3. The code uses ptr->stack[i] instead of ptr->stack + i.
  4. struct stringstack was replaced with just stringstack.
  5. An allocated copy is made of each string pushed.
  6. The destroy function had a bug in it which is now fixed.

Here is the modified code:

/* Function creates a new stringstack object and returns a pointer to it */
// Return stringstack * instead of void *.
stringstack * makestack(void) {
    stringstack *ptr = (stringstack *) malloc(sizeof(stringstack));
    ptr->count = 0;
    ptr->slots = 1;
    ptr->stack = (char **) malloc(sizeof(char*));
    return ptr;
}

/* Pushes a string onto the top of a stack */
// Use "const" whenever an argument will not be modified.
// Use "stringstack" instead of "struct stringstack" since you have the typedef.
void push(stringstack* ptr, const char *stringtext) {
    if (ptr->count == ptr->slots) {/* Allocate more space if necessary */
        // Separate ptr->slots *= 2 to its own line for readability.
        // No need for "ptr->slots + 1" now that we are using all the slots.
        ptr->slots *= 2;
        ptr->stack = (char **) realloc(ptr->stack, sizeof(char *)*ptr->slots);
    }
    // Use [] instead of + for indexing.  Also note the ptr->count++ which
    // matches with the --ptr->count in the pop() function.  The stack is
    // 0-based instead of 1-based so it doesn't waste an array slot.
    ptr->stack[ptr->count++] = strdup(stringtext);
}

/* Removes the top item from the stack, returning a pointer to it */
char * pop(stringstack* ptr) {
    // Handle error cases upfront.  (This is stylistic, so it's up to you).
    if (ptr->count == 0)
        return NULL;
    return ptr->stack[--ptr->count];
}

/* Returns a pointer to top item from stack but does not pop it */
char * peek(const stringstack* ptr) {
    if (ptr->count == 0)
        return NULL;
    return ptr->stack[ptr->count-1];
}

/* Returns whether a stringstack contains at least one string */
int isempty(const stringstack* ptr) {
    return (ptr->count == 0);
}

/* Frees a stringstack from memory */
void destroy(stringstack* ptr) {
    size_t n;
    // Previously, you were freeing ptr->stack[0] which was never allocated.
    // With the new 0-based stack, it is correct to free ptr->stack[0], but
    // not ptr->stack[ptr->count].  So I modified the for loop.
    for (n = 0; n < ptr->count; n++ )
        free(ptr->stack[n]);
    free(ptr->stack);
    free(ptr);
}

Also, you should check the return value of malloc and realloc. I didn't make the change in my example here because I didn't know what you wanted your code to do if that happened.

\$\endgroup\$
  • 1
    \$\begingroup\$ Note that strdup() is POSIX but not standard C. \$\endgroup\$ – 200_success Nov 19 '14 at 22:41
  • \$\begingroup\$ Thank you, reading your edits has been very useful to me. \$\endgroup\$ – Chris Qu Nov 20 '14 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.