Implementation of C linked list (Queue) of C strings on mega AVR

Question

I have been working on a mechanism to queue up strings coming into a system via a USART and have implemented it as a singly linked list. I have done my best to profile the code and its memory usage at runtime depending on the amount of data fed to the data structure, but can anyone see anything "wrong" or less than desirable in the code?

StringQueue.h

/**
 * @author Luke R Gary
 * @date 6/1/2015
 * 
 * @note    Not debugged, prolly leakier than a diarrhea butt
 *  
 * @note    Look for a way to implement this driver to store strings in flash memory at the expense of
 *          allocation/traverse time    
 */

#ifndef StringQueue_h
#define StringQueue_h

#include "stdlib.h"
#include "stdint.h"
#include "string.h"
#include "stdio.h"

#define MAX_ELEMENTS 32

//!<@struct node_t
typedef struct 
{
    char * data;                //!< string for node data
    struct node_t * nextNode;   //!< link to next node, may be NULL to indicate rear
}node_t;

//!<@strqueue_t
typedef struct 
{
    node_t *front;          //!< front node
    node_t *rear;           //!< rear node
    uint8_t nodeCount;      //!< current number of nodes
    uint8_t maxElements;    //!< maximum number of nodes
}strqueue_t; 

///
extern char * queueFront(strqueue_t * queue);
///
extern uint8_t enqueue(strqueue_t * queue, const char * str);
///
__inline__ void removeData(node_t * node)
{
    char * str = node->data;
    free(str);
}
///
extern char * dequeue(strqueue_t * queue);
///
extern uint8_t queueIsEmpty(const strqueue_t * queue);
///
extern void queueDisplay(strqueue_t * queue);
///
extern void queueCreate(strqueue_t * queue, uint8_t elements);
///
extern uint8_t queueSize(const strqueue_t * queue);
///
extern uint8_t queueIsFull(const strqueue_t * queue);


#endif

StringQueue.c

    /**
 * @author Luke R Gary
 * @date 6/1/2015
 * 
 * @note Not debugged, prolly leakier than a diarrhea butt
 */

#include "StringQueue.h"

/**
 * @brief returns string at the front of the queue
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return pointer to string
 */
char * queueFront(strqueue_t * queue)
{
    if ((queue->front != NULL) && (queue->rear != NULL))
        return (queue->front->data);
    else
        return 0;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @param   str [description]
 * 
 * @return [description]
 */
uint8_t enqueue(strqueue_t * queue, const char * str)
{
    // if first element and last element in queue. i.e. no allocations yet
    if(queue->front == NULL)
    {
        queue->rear             = (node_t *)malloc(sizeof(node_t));
        queue->rear->nextNode   = NULL; // null link
        queue->rear->data       = malloc(strlen(str) + 1);
        queue->rear->data       = strncpy(queue->rear->data, (char *)str, strlen(str));
        queue->front            = queue->rear;
    }
    // if any elements exist so fart
    else
    {
        node_t *temp            = (node_t *)malloc(sizeof(node_t));
        queue->rear->nextNode   = temp; // link to next rear node
        temp->data              = malloc(strlen(str) + 1);
        temp->data              = strncpy(temp->data, (char *)str, strlen(str));
        temp->nextNode          = NULL; //ensure rear maintains null link

        queue->rear = temp;     
    }
    return queue->nodeCount++;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return [description]
 */
char * dequeue(strqueue_t * queue)
{
    node_t * temp = queue->front;

    if(queue->front == NULL)
    {
        return NULL;
    } 
    if(queue->front == queue->rear)
    {
        queue->front    = NULL;
        queue->rear     = NULL;
    }
    else
    {
        queue->front = (node_t *)queue->front->nextNode;
    }
    queue->nodeCount--;

    removeData(temp);
    free(temp);

    return queue->front->data;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return [description]
 */
uint8_t queueIsEmpty(const strqueue_t *queue)
{
    if(queue->front == NULL && queue->rear == NULL && queue->nodeCount == 0)
        return 1;
    else
        return 0;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return [description]
 */
void queueDisplay(strqueue_t *queue)
{
    node_t * tempNode = queue->front;
    while(tempNode != NULL)
    {
        printf("%s\n", tempNode->data);
        tempNode = tempNode->nextNode;
    }
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @param elements [description]
 */
void queueCreate(strqueue_t * queue, uint8_t elements)
{
    queue->front        =   NULL;
    queue->rear         =   NULL; 
    queue->nodeCount    =   0;

    if(elements == 0)
        queue->maxElements  =   MAX_ELEMENTS;
    else
        queue->maxElements  =   elements;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return [description]
 */
uint8_t queueSize(const strqueue_t * queue)
{
    return queue->nodeCount;
}

/**
 * @brief [brief description]
 * @details [long description]
 * 
 * @param   queue   a queue structure reference
 * @return [description]
 */
uint8_t queueIsFull(const strqueue_t *queue)
{
    if(queue->front != NULL && queue->nodeCount >= MAX_ELEMENTS)
        return 1;
    else
        return 0;
}

Answer 1

Dequeue broken

The dequeue() function as currently written is freeing the first node's data and returning the second node's data. I think dequeue() should return the first node's data. Worse yet, if the queue only contains one node, this line will dereference NULL:

    return queue->front->data;

Here is a quick rewrite:

char *dequeue(strqueue_t *queue)
{
    node_t *temp = queue->front;
    char   *ret  = NULL;

    if (queue->front == NULL)
        return NULL;

    queue->front = queue->front->nextNode;
    if (queue->front == NULL)
        queue->rear = NULL;

    queue->nodeCount--;
    ret = temp->data;
    free(temp);
    return ret;
}

Wrong type definition

I was wondering why you needed all those (node_t *) casts. I discovered that your type definition was wrong:

typedef struct
{
    char * data;
    struct node_t * nextNode;
}node_t;

What's missing is that you are using struct node_t * but your struct was never named struct node_t. It was typedef'd to node_t but you also need the struct node_t to be able to declare the pointer. Here is the correct way:

typedef struct node_t // <-- You were missing node_t here.
{
    char * data;
    struct node_t * nextNode;
} node_t;

Now you can remove all of your (node_t *) casts.

Enqueue could be simplified

Currently, the two main blocks of your enqueue are nearly identical. One handles the empty queue case and the other handles the existing queue case. But each case allocates a new node and fills it in with values. Also, I'm not sure that returning the old size of the queue is useful. Shouldn't it return the new size? Here's how I would rewrite the function:

int enqueue(strqueue_t * queue, const char * str)
{
    node_t *temp = malloc(sizeof(node_t));

    temp->data = malloc(strlen(str)+1);
    strcpy(temp->data, str);
    temp->nextNode = NULL;

    if (queue->front == NULL)
        queue->front = temp;
    else
        queue->rear->nextNode = temp;
    queue->rear = temp;

    return ++queue->nodeCount;
}

No enforcement of maxElements

I don't think you need to limit your linked list to a maximum number of elements. But if you're going to have a limit, then you should be enforcing it. Right now, there is no check in enqueue() to make sure you don't go past the limit.

Redundant checks

In a couple of places, you do redundant checks in your if statements. For example:

uint8_t queueIsEmpty(const strqueue_t *queue)
{
    if(queue->front == NULL && queue->rear == NULL && queue->nodeCount == 0)
        return 1;
    else
        return 0;
}

checks three conditions. But any one of those three conditions would mean an empty list so you can just pick one:

bool queueIsEmpty(const strqueue_t *queue)
{
    return queue->nodeCount == 0;
}

Here is another place with redundant checks. But there are other problems:

char * queueFront(strqueue_t * queue)
{
    if ((queue->front != NULL) && (queue->rear != NULL))
        return (queue->front->data);
    else
        return 0;
}

You have some extra parentheses here. Also, you return 0 instead of NULL. I would also go ahead and make this function return const char * because it would be bad for the caller to do something like free the data when the data is still in the queue. It depends on your usage case, though.

const char * queueFront(const strqueue_t * queue)
{
    if (queue->front == NULL)
        return NULL;
    return queue->front->data;
}

const keyword

I commend you on your use of const when appropriate. You missed one spot in queueDisplay(), but otherwise well done.

Things I agree with other reviewers on

1. You don't need to use extern when declaring function prototypes.
2. You should use <header.h> instead of "header.h" for standard headers.
3. Use bool and <stdbool.h>.
4. An array version would be more efficient. I'm not sure if you were doing this just to practice linked lists, though.

Answer 2

Standard headers should be included between < >. By using quotes, your are telling the compiler to look first into the current directory, then in the standard include path. This is a waste of time, since I doubt that you have a custom C library with your project?

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

---

Unless you plan on having your code compile as C++, then you should avoid casting the return value of malloc. In C void* converts implicitly to any other pointer type. This is not true for C++.

Unless you need to compile in dual mode, it is best to avoid the cast, since it introduces maintenance overhead and some repetition of types.

---

__inline__ void removeData(node_t * node)

__inline__ (with the double underscores) is a GCC extension from the time inline wasn't standard yet. Unless your compiler doesn't support inline, you have no reason to use the GCC specific keyword.

---

The extern on your function prototypes is not necessary. It is allowed on function prototypes to be orthogonal with global variables, I'm guessing. Removing it should have no side effects. Since it only adds verbosity to the header file, I don't see any reason to use it on function prototypes.

---

Bit of a personal preference here, but in a place such as:

uint8_t queueIsFull(const strqueue_t *queue) 
{
    if(queue->front != NULL && queue->nodeCount >= MAX_ELEMENTS)
        return 1;
    else
        return 0; 
}

I would avoid the if/else and simply return the expression:

uint8_t queueIsFull(const strqueue_t *queue)
{
    return queue->front != NULL && queue->nodeCount >= MAX_ELEMENTS;
}

By the way, that function returns true or false, so its return type should be bool. (Note: include <stdbool.h> somewhere).

---

Arguably another piece of personal preference, but I think the following is making an excessive use of parenthesis:

char * queueFront(strqueue_t * queue)
{
    if ((queue->front != NULL) && (queue->rear != NULL))
        return (queue->front->data);
    else
        return 0;
}

The ( ) pair in the return statement is useless. return is not a function call. In the if statement they also make no difference. And you are not consistently using the style of wrapping each part of an if in ( ), so I would just drop it.

---

This is a very minor point, but include guards, being preprocessor directives, are usually defined using the ALL_UPPERCASE notation:

#ifndef STRING_QUEUE_H
#define STRING_QUEUE_H

---

I personally recommend always adding curly braces { } on all if/else statements. It will make your code more maintainable and might even help avoiding bugs like the (in)famous goto fail from OpenSSL.

---

As a side note, since you haven't edited your doxygen comment blocks, maybe just remove them. As they stand, it only serves to clutter your source files.

Answer 3

I may be biased, but I think some excellent advice for anyone trying to program in C is "Learn C++, and then write C++ in C." This immediately leads to a lot of minor improvements in your code...

• The verbs enqueue and dequeue are verbose (and dequeue might be mistaken for the name of a data type in its own right). Prefer the verbs push and pop.

• C doesn't have namespaces (or member functions), so you should get in the habit of prefixing all your "queue member functions" with a unique prefix. You've done that with e.g. queueFront, but you missed enqueue and dequeue; those should be named queueEnqueue (preferably queuePush) and queueDequeue (preferably queuePop) instead.

• We haven't finished vivisecting your naming scheme yet: The name of the datatype is strqueue_t, but the "member function" prefix is queue and the name of the header file is "StringQueue.h". That's very confusing. Let's make the member function prefix strqueue_ instead: strqueue_t, strqueue_push(), strqueue_pop(), strqueue_is_full(), "strqueue.h". Perfect!

• Oh, and STRQUEUE_MAX_ELEMENTS.

---

Okay, so what's this strqueue_is_full() function doing? This queue has a maximum length?! That pretty much defeats the purpose of a linked list, which is basically the worst data structure imaginable except for the fact that it can grow unboundedly. If you know up front how big your data is (or will-ever-be), you should use a heap-allocated array instead. You'll end up using ~50% of the memory (because you no longer store the "next" pointers) and ~0% of the runtime (because pushing onto the queue no longer involves malloc, and popping no longer involves free).

Try writing up the array version and see how much faster it is. My bet is that the finished code will be half the number of lines, too. (Here's a generic ringbuffer using the technique, in 75 lines. Not that I'm holding this up as a shining example of C style, but it's exactly what you want except that it "auto-pops" old elements when full, whereas you let the queue keep growing "beyond full", which I don't really understand. Do you have a use case for "beyond-full" queues, or is that an accidental "misfeature" of your implementation?)

---

Your strqueue_pop (née dequeue) function simply does not work, for any input. Consider the case of a 1-element queue, where queue->front == queue->rear. In that case, you set queue->front = NULL; and then return queue->front->data;, i.e., you unconditionally dereference NULL. I believe the bugs for >1 element are subtler, but they're definitely still there. Keep in mind that C pointers are not smart and do not reference-count; just because you "saved" the value of queue->front in temp does not make it okay to dereference temp after you've freed queue->front.

---

Finally, you've got a string-manipulation bug.

strncpy(temp->data, (char *)str, strlen(str));

If the string in str is "hello", this copies 5 characters into temp->data: namely, 'h', 'e', 'l', 'l', 'o'. You never copy the terminating '\0' byte! So you've allocated 6 bytes, but initialized only 5 of them; you don't have a null-terminated string, and printf is going to blow up when you get to it.

strncpy is NEVER EVER EVER appropriate. Treat it the same way you would treat gets: it is not in the vocabulary of an educated programmer. (And the same goes for strncat.) Show me any code that uses strncpy, and I will show you bug-riddled code.

The function you want here is the standard function for copying strings; it's spelled strcpy. (If you don't care about 100% ISO-compliance and don't care about any memory allocator but malloc, save yourself another minor hassle by using strdup. But do not use strncpy; it is never appropriate.)

Answer 4

• Use invariants

  If perchance queue->front == NULL, it is reasonable to expect queue->rear == NULL and queue->nodeCount == 0 as well; otherwise it is not a runtime error but a bug in the logic. One of the rare cases to use assert.

• Don't repeat yourself

  The code in if and else paths of enqueue is alarmingly similar. Try to factor the common parts out. For example,

  uint8_t enqueue(strqueue_t * queue, const char * str)
  {
      node_t *temp            = (node_t *)malloc(sizeof(node_t));
      temp->data              = malloc(strlen(str) + 1);
      temp->data              = strncpy(temp->data, (char *)str, strlen(str));
      temp->nextNode          = NULL; //ensure rear maintains null link
  
      if(queue->front == NULL)
      {
          assert(queue->rear == NULL);
          queue->front = tmp;
      }
  
      queue->rear = temp;     
      return queue->nodeCount++;
  }