Minimal stack from unsigned int to track boolean values wtih bits 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 &lt;stdio.h&gt;

#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-&gt;idx = 0;
    for (int i = 0; i &lt; STKMAX; i++)
        s-&gt;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-&gt;kp) * CHAR_BIT,
        elebits = (sizeof s-&gt;idx) * CHAR_BIT,
        arridx = s-&gt;idx/elebits;

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

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

    return ++s-&gt;idx;
}

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

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

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

    return v;
}

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

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

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

int main (void) {

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

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

    while ((v = stack_pop (&amp;s)) &gt;= 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.
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 (&amp;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-&gt;kp, 0, sizeof(unsigned)*STKMAX);


As noted by chux you better use memset(s-&gt;kp, 0, sizeof s-&gt;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.