6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Note if code uses something wider than unsigned in kp[], 1u in 1u << may need widening. Dirty trick: 1u --> (s->kp[0]&0 + 1) to get the right width. \$\endgroup\$ – chux - Reinstate Monica Aug 31 '17 at 20:40
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hay, thank you for your thoughts. Yes, stack_pop and stack_last need the int return as I'm relying on -1 to indicate empty stack. Agree completely on the error to stdout. They were originally g_warning in gtk, which I just lazily used printffor here. I considered declaring/passing the enum, and your right, that would provide additional typesafety, but within push the value v is just used as a boolean to set the bit to either a 1 if v is any value, and 0 otherwise. A #define STKMAX leaving the enum {LEFT, RIGHT}; would provide a bit more clarity. Good comments. \$\endgroup\$ – David C. Rankin Aug 29 '17 at 7:47
  • \$\begingroup\$ About enum: well, there isn't almost any type safety with enum but I think about it more as documentation. I read function prototype and I immediately know the expected type to use (then, for example, if I see stack_push(&s, GREEN) I immediately know it's wrong. About return code: I don't usually like it that much but then you can use negative values as error codes. \$\endgroup\$ – Adriano Repetti Aug 29 '17 at 7:51
  • \$\begingroup\$ memset(s->kp, 0, sizeof(unsigned)*STKMAX); is OK, yet consider memset(s->kp, 0, sizeof *(s->kp) *STKMAX); or memset(s->kp, 0, sizeof s->kp[0] *STKMAX); as it reduces a dependency on matching a variable with a type - which may evolve. \$\endgroup\$ – chux - Reinstate Monica Aug 29 '17 at 14:35
  • \$\begingroup\$ @chux absolutely true, added tnx. \$\endgroup\$ – Adriano Repetti Aug 29 '17 at 14:38
  • \$\begingroup\$ unsigned vs unsigned int is really a style choice - IMHO, either is acceptable, provided it's consistent. \$\endgroup\$ – Toby Speight Aug 29 '17 at 15:59
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks chux. The lack of limits.h is only due to the project includes being glib.h and gtk/gtk.h. No reason not to include it other than not having chased through the glib/gtk headers to see if it was already done. Signedness difference between push and then pop and last is a return of 0 from push is failure, while both pop and last must return 0 as a value so -1 was used to indicate failure in each. Will work on the comments (and should have), but did not think ahead for comments as part of the review. \$\endgroup\$ – David C. Rankin Aug 30 '17 at 0:45
  • \$\begingroup\$ @DavidC.Rankin Also review printf ("stack full, index: %u\n", s->idx); return 0; Other errors return -1 , this returns 0. Maybe all errors should return same value?. \$\endgroup\$ – chux - Reinstate Monica Aug 30 '17 at 1:46
  • \$\begingroup\$ Yes, you are right. That is just a side effect of a personal preference to return 0/1 failure/success (or even vice-versa) if possible, but I did recognize on implementation that I would have to handle returns differently on push verses pop & last. The difference here being that I didn't use the return value for push for anything other than a success/failure indication (and if somebody is holding down the ctrl+shift+arrow key more than 128 time -- they should be shot). I agree, logically it would make more sense to just use -1 for failure for all. \$\endgroup\$ – David C. Rankin Aug 30 '17 at 1:54
0
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This line is misleading -- well, your right, but it wasn't meant to be. Since all types are unsigned, rather than using the array references I simply used the index. pop and last are identical, except for the decrement, this is intentional. In the implementation handling sequential ctrl+shift+right (or left), I need a way to determine what the last keypress was without popping -- that's why there is a last. \$\endgroup\$ – David C. Rankin Aug 31 '17 at 2:04
  • \$\begingroup\$ @DavidC.Rankin I realize that you need both pop and last, but my point was that the one could be written as a call to the other instead of a near duplicate of it. \$\endgroup\$ – JS1 Aug 31 '17 at 2:24
  • \$\begingroup\$ @JS1 Agree, elebits = (sizeof s->kp[0]) * CHAR_BIT is better. \$\endgroup\$ – chux - Reinstate Monica Aug 31 '17 at 20:38

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.