Undo and redo functionality for a GTK+ program

Question

I'm working on a small GTK+ program and I'm now implementing undo and redo capabilities. This is the code that I'm using to handle the different states.

It's just a linked list storing the allocated char * returned by the text buffer. It monitors the size of the structure and the char *s so it will always be less than the maximum size set.

What should I change?

Header:

#ifndef TEXT_STATE_H
#define TEXT_STATE_H

#include <stdlib.h>
#include <stdbool.h>

#define TS_SUCCESS 0
#define TS_ERROR 1
#define TS_GREATER_THAN_BUFFER 2
#define TS_FAILED_TO_ALLOCATE_NODE 4

/* Here's how it works:
    1 - a buffer is set
    2 - every new state is pushed to the next position, if there are other "next"
states, they are removed, so if the user clicks undo then writes, he can't redo the
previous "next" states
    3 - if the new state is bigger than the total allocated space, an error is
returned
    4 - if there's not enough space for the new state, the oldest is removed 
repeatedly until there's space.
    5 - if it fails to allocate the node structure, nothing is done and an error 
is returned

    Size means total size, structure + text. So there's no chance of using a lot
more memory when the text states are really small.
*/

/* Store the state */
typedef struct Text_Node Text_Node;

typedef struct {
    char *text;
    size_t size; //including '\0'
} State;

/* The states are stored in a linked-list */
typedef struct {
    Text_Node *first;
    Text_Node *current;
    Text_Node *last;
    size_t in_use;
    size_t buffer_size;
} Text_State;

//Set up the structure, buffer size
static inline void ts_init(Text_State *ts, size_t buffer_size)
{
    ts->first = NULL;
    ts->current = NULL;
    ts->last = NULL;
    ts->in_use = 0;
    ts->buffer_size = buffer_size;
}

//Free all
void ts_free(Text_State *ts);

//Free all, keep buffer size, set structure so it can be used again (e.g. when
//a new document is created)
void ts_clear(Text_State *ts);

//Push new state, delete all old "next" states
int ts_push_state(Text_State *ts, char *text);

//Set state to the next if there's one and return it, otherwise return NULL
const State *ts_redo(Text_State *ts);

//Set state to the previous if there's one and return it, otherwise return NULL
const State *ts_undo(Text_State *ts);

//Return if there are next states
bool ts_can_redo(Text_State *ts);

//Return if there are previous states
bool ts_can_undo(Text_State *ts);

//Set state to the newest, return it
const State *ts_redo_all(Text_State *ts);

//Set state to the oldest, return it
const State *ts_undo_all(Text_State *ts);

//Set buffer size. If it's smaller, the first and last state will be removed 
//repeatedly until the buffer size is smaller or equal to the new size
void ts_set_size(Text_State *ts, size_t new_size);

#endif

Source:

#include "text_state.h"
#include <string.h>

struct Text_Node {
    State state;
    Text_Node *next;
    Text_Node *previous;
};

/////////
//  Internal functions
///////
static inline size_t available_space(Text_State *ts)
{
    return ts->buffer_size - ts->in_use;
}

static inline size_t space_required(Text_Node *node)
{
    return sizeof(Text_Node) + node->state.size;
}

//Return an allocated copy of node
static inline Text_Node *make_node_like(Text_Node *node)
{
    Text_Node *temp = malloc(sizeof(Text_Node));
    if(temp != NULL)
        *temp = *node;

    return temp;
}

static inline bool enough_space(Text_State *ts, Text_Node *node)
{
    return available_space(ts) >= space_required(node);
}

static inline bool buffer_is_too_small(Text_State *ts, Text_Node *node)
{
    return space_required(node) > ts->buffer_size;
}

//There must be a first node for it to work
static void remove_first_node(Text_State *ts)
{
    Text_Node *node = ts->first;

    if(node == ts->current)
        ts->current = node->next;

    if(node->next != NULL)
        node->next->previous = NULL;

    //Last node
    else
        ts->last = NULL;

    ts->first = node->next;
    ts->in_use -= space_required(node);

    free(node->state.text);
    free(node);
}

static void remove_last_node(Text_State *ts)
{
    Text_Node *node = ts->last;

    if(node == ts->current)
        ts->current = node->previous;

    if(node->previous != NULL)
        node->previous->next = NULL;

    //First node
    else
        ts->first = NULL;

    ts->last = node->previous;
    ts->in_use -= space_required(node);

    free(node->state.text);
    free(node);
}

//Remove the current node only if there's no other option
static void remove_one(Text_State *ts, size_t *counter)
{
    ++*counter;

    //The undo list is probably longer
    if(*counter % 3 != 0){
        if(ts->first != ts->current)
            remove_first_node(ts);

        else
            remove_last_node(ts);
    }

    else {
        if(ts->last != ts->current)
            remove_last_node(ts);

        else
            remove_first_node(ts);  
    }
}

static void remove_all_nodes_after(Text_State *ts, Text_Node *node)
{
    Text_Node *next = node->next;
    node->next = NULL;

    while((node = next) != NULL){
        next = node->next;

        ts->in_use -= space_required(node);
        free(node->state.text);
        free(node);
    }
}

static void push_new_node(Text_State *ts, Text_Node *node)
{
    //Handle first node
    if(ts->current == NULL){
        node->previous = node->next = NULL;
        ts->first = ts->current = ts->last = node;
        ts->in_use += space_required(node);
        return;
    }

    node->previous = ts->current;
    node->next = NULL;
    ts->current->next = node;
    ts->current = ts->last = node;
    ts->in_use += space_required(node);
}


/////////
//  Public functions
///////
void ts_free(Text_State *ts)
{
    Text_Node *next;
    Text_Node *current;

    for(current = ts->first; current != NULL; current = next){
        next = current->next;
        free(current->state.text);
        free(current);
    }
}

//Keep the buffer size
void ts_clear(Text_State *ts)
{
    ts_free(ts);
    ts->first = NULL;
    ts->current = NULL;
    ts->last = NULL;
    ts->in_use = 0;
}

int ts_push_state(Text_State *ts, char *text)
{
    Text_Node temp;
    temp.state.text = text;
    temp.state.size = strlen(text) + 1;

    //Handle separately
    if(!enough_space(ts, &temp)){
        if(buffer_is_too_small(ts, &temp))
            return TS_ERROR | TS_GREATER_THAN_BUFFER;

        //After this point, it can't fail
        Text_Node *new_node = make_node_like(&temp);
        if(new_node == NULL)
            return TS_ERROR | TS_FAILED_TO_ALLOCATE_NODE;

        //First remove all nodes that will be removed anyway
        remove_all_nodes_after(ts, ts->current);

        //Remove the oldest nodes if it's necessary
        while(!enough_space(ts, &temp))
            remove_first_node(ts);

        push_new_node(ts, new_node);
        return TS_SUCCESS;
    }

    Text_Node *new_node = make_node_like(&temp);
    if(new_node == NULL)
        return TS_ERROR | TS_FAILED_TO_ALLOCATE_NODE;

    push_new_node(ts, new_node);
    return TS_SUCCESS;
}

const State *ts_redo(Text_State *ts)
{
    if(ts->current != NULL && ts->current->next != NULL){
        ts->current = ts->current->next;
        return &ts->current->state;
    }

    return NULL;
}

const State *ts_undo(Text_State *ts)
{
    if(ts->current != NULL && ts->current->previous != NULL){
        ts->current = ts->current->previous;
        return &ts->current->state;
    }

    return NULL;
}

bool ts_can_redo(Text_State *ts)
{
    return ts->current != NULL && ts->current->next != NULL;
}

bool ts_can_undo(Text_State *ts)
{
    return ts->current != NULL && ts->current->previous != NULL;
}

const State *ts_redo_all(Text_State *ts)
{
    if(ts->current == NULL)
        return NULL;

    ts->current = ts->last;
    return &ts->current->state;
}

const State *ts_undo_all(Text_State *ts)
{
    if(ts->current == NULL)
        return NULL;

    ts->current = ts->first;
    return &ts->current->state;
}

void ts_set_size(Text_State *ts, size_t new_size)
{
    if(new_size >= ts->buffer_size){
        ts->buffer_size = new_size;
        return;
    }

    //Prefer removing the first since it will probably be further from the current
    size_t counter = 0;  
    do {
        remove_one(ts, &counter);
    } while(ts->buffer_size > new_size);

    ts->buffer_size = new_size;
}

Answer 1

Just a few notes:

• You have some #define statements at the beginning of your header.

     #define TS_SUCCESS 0
     #define TS_ERROR 1
     #define TS_GREATER_THAN_BUFFER 2
     #define TS_FAILED_TO_ALLOCATE_NODE 4
  

  You could use an enum instead.

  typedef enum 
  {
      SUCCESS = 0;
      ERROR = 1;
      GREATER_THAN_BUFFER = 2;
      FAILED_TO_ALLOCATE_NODE = 4;
  } TS;
  

  If FAILED_TO_ALLOCATE_NODE could be set to equal 3, this could even be reduced to a one-liner.

  typedef enum {SUCCESS, ERROR, GREATER_THAN_BUFFER, FAILED_TO_ALLOCATE_NODE} TS;
  

• I'm usually not a fan of including <stdbool.h>. The only reason you use it is for return values.

     static inline bool buffer_is_too_small(Text_State *ts, Text_Node *node)
     {
         return space_required(node) > ts->buffer_size;
     }
  

  I prefer to just return int values themselves. This way, you can return a value to indicate an error (probably a negative number), a value to indicate success (probably 0), and/or a value to guide the user if there is an error (for example, buffer_is_too_small could return how much larger the buffer needs to be).

• Your NULL checks can be simplified.

  if(node->previous != NULL)
       node->previous->next = NULL;
  

  The != NULL can be excluded while testing node->previous.

  if(node) node->previous->next = NULL;
  

  It is also quite simple to check if a value is NULL in a simpler form.

  if(!ts->current)  // Same as: if(ts->current == NULL)
  {
      ...
  }
  

• I'm not the biggest fan of your very large comments.

  /////////
  //  Public functions
  ///////
  

  But that is to your discretion.