Data Structures

Dynamic array in C

Two different approaches, the first uses calloc and free, the other uses malloc and realloc.
http://www.mathcs.emory.edu/~cheung/Courses/255/Syllabus/2-C-adv-data/dyn-array.html
https://stackoverflow.com/questions/3536153/c-dynamically-growing-array

Hash table

The simplest hashing function is to just modulo the key by the size of the table. This will likely result in collisions, but a collision in a hash table does not mean you have a crash/fail. It simply means you must increment the table index until you hit a free spot to use on insert, or until you hit the match on a find.

The example shown here uses a fixed table size, but also mallocs a new element every time it calls insert. That's only because the table stores pointers. This isn't necessary, as the table could hold elements instead of pointers to elements. If you are going to implement with a fixed-size array, there's really no need to use malloc. https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c

Basics of a hash table implementation:

struct DataItem {
   int data;   
   int key;
};

struct DataItem* hashArray[SIZE];

int hashCode(int key) {
   return key % SIZE;
}

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);

   //find the match
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell, wrapping around
      hashIndex = (hashIndex + 1) % SIZE;
   }

   return NULL;
}

/* etc */

Simple circular buffer object

/** \brief Circular buffer definition. */
typedef struct
{
    void  *base;                   /**< \brief buffer base address */
    uint16 index;                  /**< \brief buffer current index */
    uint16 length;                 /**< \brief buffer length*/
} CircularBuffer;

Stack implementation

Variable depth stacks can be implemented with dynamic arrays or linked lists. Dynamic arrays provide random access, which is not necessary for a stack. Resizing a dynamic array is a costly operation, but if managed well there should still be a better performance than a linked list implementation because of the extra pointer data storage and the constant alloc/delete operations needed. However, for a demonstration question using a linked list is more straight forward.

State Machines

The "blocking" SM

One interesting way to use a SM is to contain one in a function which is designed to be called repeatedly for handling the process of executing a specific command, until the entire SM has been run through, and then is primed at the top for later use. The calling loop is in the caller instead of the callee and is akin to pressing Next over and over until the process is complete. An example of this was some PIC code for SPI SD Card driver.

The user is required to call this API multiple times till the status becomes complete. It is expected to call this routine continuously until we get the status as execution successful. The caller should not execute this function again after the execution of the command. It will cause to execute the same command again.

State is kept in an object(struct) a pointer to which is passed into the SM command function.

Command Strings and Tokens

SMs are great for parsing through commands in an expected format, going byte by byte, finding delimiters. For example if you have to create your own string tokenizer.