Here’s a link back to the GitHub project page.

Introduction

A set of very simple stack macros for C structures are included with uthash in utstack.h. To use these macros in your own C program, just copy utstack.h into your source directory and use it in your programs.

#include "utstack.h"

These macros support the basic operations of a stack, implemented as an intrusive linked list. A stack supports the "push", "pop", and "count" operations, as well as the trivial operation of getting the top element of the stack.

Download

To download the utstack.h header file, follow the links on https://github.com/troydhanson/uthash to clone uthash or get a zip file, then look in the src/ sub-directory.

BSD licensed

This software is made available under the revised BSD license. It is free and open source.

Platforms

The utstack macros have been tested on:

  • Linux,

  • Mac OS X,

  • Windows, using Visual Studio 2008 and Visual Studio 2010

Usage

Stack (list) head

The stack head is simply a pointer to your element structure. You can name it anything. It must be initialized to NULL. It doubles as a pointer to the top element of your stack.

element *stack = NULL;

Stack operations

The only operations on a stack are O(1) pushing, O(1) popping, and O(n) counting the number of elements on the stack. None of the provided macros permit directly accessing stack elements other than the top element.

To increase the readability of your code, you can use the macro STACK_EMPTY(head) as a more readable alternative to head == NULL, and STACK_TOP(head) as a more readable alternative to head.

STACK_PUSH(stack,add);

push add onto stack

STACK_POP(stack,elt);

pop stack and save previous top as elt

STACK_COUNT(stack,tmp,count);

store number of elements into count

STACK_TOP(stack)

return stack

STACK_EMPTY(stack)

return stack == NULL

The parameters shown in the table above are explained here:

stack

The stack head (a pointer to your element structure).

add

A pointer to the element structure you are adding to the stack.

elt

A pointer that will be assigned the address of the popped element. Need not be initialized.

tmp

A pointer of the same type as elt. Used internally. Need not be initialized.

count

An integer that will be assigned the size of the stack. Need not be initialized.

Example

This example program reads names from a text file (one name per line), and pushes each name on the stack; then pops and prints them in reverse order.

A stack of names
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "utstack.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next;
} el;

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *elt, *tmp;

    char linebuf[sizeof el->bname];
    int count;
    FILE *file = fopen("test11.dat", "r");
    if (file == NULL) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf, sizeof linebuf, file) != NULL) {
        el *name = malloc(sizeof *name);
        if (name == NULL) exit(-1);
        strcpy(name->bname, linebuf);
        STACK_PUSH(head, name);
    }
    fclose(file);

    STACK_COUNT(head, elt, count);
    printf("%d elements were read into the stack\n", count);

    /* now pop, print, and delete each element */
    while (!STACK_EMPTY(head)) {
        printf("%s\n", STACK_TOP(head)->bname);
        STACK_POP(head, elt);
        free(elt);
    }

    return 0;
}

Other names for next

If the element structure’s next field is named something else, a separate group of macros must be used. These work the same as the regular macros, but take the field name as an extra parameter.

These "flexible field name" macros are shown below. They all end with 2. Each operates the same as its counterpart without the 2, but they take the name of the next field as a trailing argument.

STACK_PUSH2(stack,add,next);

push add onto stack

STACK_POP2(stack,elt,next);

pop stack and save previous top as elt

STACK_COUNT2(stack,tmp,count,next);

store number of elements into count