Minimal stack from unsigned int to track boolean values wtih bits

Question

This grew out of a need to track sequential ctrl+shift+Left/Right-arrow keypress events on a gtk editor. It is a small stack implementation for boolean values (for LEFT, RIGHT) that uses the bits of a predefined array of unsigned for storage. The amount of storage is determined by the constant STKMAX which simply specifies the number of unsigned elements in the array. The reason for using this as opposed to some builtin GtkStack, etc. was simply for storage efficiency where only 32+ bits were needed, compared to Gtk's traditional over-allocation for minimal data structures.

Here, I'm not that concerned with whether I used unsigned where uint32_t would be better, but more whether there is anything inherently wrong with packing bits and indexing the various array elements that make up the stack storage that I may be overlooking. I've thought through it and the logic and implementation seems sound -- but I could have easily missed something that will come back to bite me.

With that, here's the code and a short driver that intentionally attempts to add more than the stack will hold to validate stack-full behavior:

#include <stdio.h>

#ifndef CHAR_BIT
# define CHAR_BIT  8
#endif

enum { LEFT, RIGHT, STKMAX = 4 };

typedef struct {
    unsigned int kp[STKMAX], idx;   /* array for stack, bit-index */
} selstack;

/** zero the stack values */
void stack_clear (selstack *s)
{
    s->idx = 0;
    for (int i = 0; i < STKMAX; i++)
        s->kp[i] = 0;
}

/** stack_push set bit at index to 0 or 1 based on v.
 *  increment bit-index after setting bit.
 */
int stack_push (selstack *s, int v)
{
    /* total bits, bits per-array-element, array index */
    unsigned arrbits = (sizeof s->kp) * CHAR_BIT,
        elebits = (sizeof s->idx) * CHAR_BIT,
        arridx = s->idx/elebits;

    if (s->idx == arrbits) {
        printf ("stack full, index: %u\n", s->idx);
        return 0;
    }

    if (v)  /* set bit at index */
        s->kp[arridx] |= (1u << (s->idx % elebits));
    else    /* clear bit at index */
        s->kp[arridx] &= ~(1u << (s->idx % elebits));

    return ++s->idx;
}

/** stack_pop - decrement index, get bit at index, clear bit. */
int stack_pop (selstack *s)
{
    if (!s->idx) {
        printf ("stack empty, index: %u\n", s->idx);
        return -1;
    }

    /* number of bits per-array-element, decrement index */
    unsigned elebits = (sizeof s->idx) * CHAR_BIT,
        arridx = --s->idx/elebits,
        /* get bit value at index */
        v = (s->kp[arridx] >> (s->idx % elebits)) & 1;

    /* zero bit at index */
    s->kp[arridx] &= ~(1u << (s->idx % elebits));

    return v;
}

/** stack_last - get bit for last pushed value. */
int stack_last (selstack *s)
{
    if (!s->idx) {
        printf ("stack empty, index: %u\n", s->idx);
        return -1;
    }

    /* number of bits per-array-element, computed index */
    unsigned elebits = (sizeof s->idx) * CHAR_BIT,
        arridx = (s->idx - 1)/elebits;

    /* return bit at index */
    return (s->kp[arridx] >> ((s->idx - 1) % elebits)) & 1;
}

int main (void) {

    int v;
    selstack s;
    stack_clear (&s);

    for (int i = 0; i < 132; i++)
        if (i < 32 || (64 <= i && i < 96))
            stack_push (&s, RIGHT);
        else
            stack_push (&s, LEFT);

    while ((v = stack_pop (&s)) >= 0)
        printf ("popped[%3u] : %s\n", s.idx, v ? "RIGHT" : "LEFT");

    return 0;
}

Let me know if there are any gotchas I'm not picking up on.

Answer 1

Reading this:

enum { LEFT, RIGHT, STKMAX = 4 };

I expect to see use LEFT and STKMAX interchangeably however they're different things you packed together for convenience. Split it and readers won't need to browse all your code to understand that they can't use STKMAX where FALSE or TRUE are expected. Is stack_push (&s, STKMAX); valid and meaningful?

---

You already know you may use uint32_t instead of unsigned int but, at least, you should really use unsigned, the extra int in the declaration adds nothing to your code (but that's just an opinion then take it or leave it).

---

unsigned int kp[STKMAX], idx;

I prefer, for clarity, to have one single variable declaration for each line. I'd also change names to something more meaningful. For example, why idx can't be indexOfNextAvailableBit? We don't need to obfuscate our code and I do not neet to read stack_push() to understand how it's used to determine what it is.

---

stack_clear() can be simplified to use memset(), any decent compiler will (probably) recognize it and use the best algorithm to perform the task (loop, unrolled loop, plain memset(), something more esoteric/fancy).

memset(s->kp, 0, sizeof(unsigned)*STKMAX);

As noted by chux you better use memset(s->kp, 0, sizeof s->kp[0] *STKMAX) "as it reduces a dependency on matching a variable with a type - which may evolve".

---

In stack_push() you should again declare one variable each time, no need to save few keystrokes and it makes declaration easier to read. Also here you should use more meaningful names, ideally I would like to read the variable name and go to the next line, there should be no need to read and understand the expression to determine what it is going on. I'm stressing on this but it's a very important concept when after 1 year you go back to your 500k/1M LOC codebase to fix a bug.

---

It's not a big compile-time protection but you have an enum, give it a name and use it for the parameter v (which may be value). Callers are still able to push 41 instead of TRUE and FALSE but you're documenting your function interface (and see next paragraph).

---

You may want to validate inputs.

---

Do not print error messages to stdout. For two reasons: first because stdout is for program output and errors should go to stderr, second because it's not your code responsibility to inform the user, you're just handling a stack of booleans and an appropriate return code is enough.

---

/* set bit at index */

If you feel you need a comment for this then you're missing the opportunity to introduce a separate self-explicative setBitAtIndex() method.

---

Do you really need to return the index of the next available bit? It's never a parameter for your functions then caller is probably not interested in it (and it's available in selstack). You may want to use return value as error code (eventually, from C11, consider to use errno_t).

---

Above applies to stack_pop() and stack_last() as well.

Answer 2

define CHAR_BIT is curious. That standard defined is in <limits.h>, yet code did not include that. Suggest adding it and only retain the #ifndef CHAR_BIT if there is a compelling reason.

#include <limits.h>
//#ifndef CHAR_BIT
//  #define CHAR_BIT  8
//#endif

Consider the effects of auto formatting

// before - nice - so far
unsigned arrbits = (sizeof s->kp) * CHAR_BIT,
    elebits = (sizeof s->idx) * CHAR_BIT,
    arridx = s->idx/elebits;

// after - now hard to read
unsigned arrbits = (sizeof s->kp) * CHAR_BIT, elebits = (sizeof s->idx)
  * CHAR_BIT, arridx = s->idx / elebits;

// Better
unsigned arrbits = (sizeof s->kp) * CHAR_BIT;
unsigned elebits = (sizeof s->idx) * CHAR_BIT;
unsigned arridx = s->idx/elebits;

Explain interface. What is the int stack_push() returns? Consider that this comment may belong in a .h file where a viewer lacks access to the source code.

Why does the return type sign-ness differ from ++s->idx? Recommend consistency or quiet sign conversion with a cast or mask.

/** stack_push set bit at index to 0 or 1 based on v.
 *  increment bit-index after setting bit.
 *  returns ???????
 */
int stack_push(selstack *s, int v) {

Why sign-ness difference in int stack_pop(selstack *s) ... unsigned v = ... return v; } Recommend consistency as above.

Explain interface: int stack_pop(selstack *s) as the return is 1 of 3 values, yet that is not apparent form the comment nor the signature. Again, consider the function declaration and comment may exist in a .h file.

Answer 3

Wrong variable being measured

This line is misleading:

    elebits = (sizeof s->idx) * CHAR_BIT,

It really should be this instead:

    elebits = (sizeof s->kp[0]) * CHAR_BIT,

When I first read the line I got confused because I thought elebits had something to do with the index. It just so happens that both s->idx and s->kp[0] are of type unsigned, but what you are measuring here is the bit width of each element in s->kp, not the bit width of idx, which could be a completely different type.

Potential overflow

In this line:

unsigned arrbits = (sizeof s->kp) * CHAR_BIT,

there is a potential for arrbits to overflow. On a target with 16-bit integers, an overflow will occur when STKMAX is 4096 or greater. On a target with 32-bit integers, an overflow will occur when STKMAX is 128M or greater.

Duplicated code

stack_pop() and stack_last() are nearly identical. The only difference is that stack_pop() decrements the stack index and clears the popped bit in the array (which is unnecessary). I think stack_pop() could just be:

int stack_pop (selstack *s)
{
    int ret = stack_last(s);

    if (ret != -1)
        --s->idx;
    return ret;
}

The above doesn't clear the bit in the array, but if you insist that the bit must be cleared when popped, it could still be done where you didn't duplicate the function.

Use const when possible

Since stack_last() doesn't modify s, you could add a const qualifier to it:

int stack_last (const selstack *s)