Home > Articles, Data Structures & Algorithms > A dynamic string data structure helper implementation.

A dynamic string data structure helper implementation.

October 21, 2014 Leave a comment Go to comments

In this article I will present to you a dynamic string data structure helper implementation. In C, a string is just an array of characters terminated with the null character (NUL in ASCII). Also, some times we handle a string by using a pointer to a buffer containing sequential characters terminated also with the null character. The C standard liibrary provides various functions for string manipulation but it seems that whenever we want to extend a string by using pointers we have to perform all the time memory reallocation which leads to a bad evolution of replicated code. In a recent project, I needed to create a string and append to it any number of new strings in order to extend it without using strcat, strcpy, strlen and realloc functions all the time. So, I created a simple dynamic string data structure which solved my specific problem and I would like to share it with you people.

Below, is the header containing the data type definition of the dynamic string:

/*
 *  Copyright (C) 2014  Efstathios Chatzikyriakidis (contact@efxa.org).
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef _DYNAMIC_STRING_HELPER_TYPES_H_
#define _DYNAMIC_STRING_HELPER_TYPES_H_

#include <stddef.h>

#include "shared-types.h"

/*
 * type definitions.
 */

// dynamic string type definition.
typedef struct dynamic_string_t
{
  string_t string;

  size_t string_length;

  size_t buffer_length;
} dynamic_string_t;

#endif // _DYNAMIC_STRING_HELPER_TYPES_H_

Next, follows the header of the source code unit:

/*
 *  Copyright (C) 2014  Efstathios Chatzikyriakidis (contact@efxa.org).
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef _DYNAMIC_STRING_HELPER_UTILITY_H_
#define _DYNAMIC_STRING_HELPER_UTILITY_H_

#include "dynamic-string-helper-types.h"

dynamic_string_t * const dynamic_string_create (size_t buffer_length);

void dynamic_string_clear (dynamic_string_t * dynamic_string);

bool_t dynamic_string_append (dynamic_string_t * const dynamic_string,
                              const string_t const string);

size_t dynamic_string_length (const dynamic_string_t * const dynamic_string);

#endif // _DYNAMIC_STRING_HELPER_UTILITY_H_

Here is the implementation of the source code unit:

/*
 *  Copyright (C) 2014  Efstathios Chatzikyriakidis (contact@efxa.org).
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

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

#include "memory-management-helper-macros.h"
#include "dynamic-string-helper-utility.h"

/*
 * functions.
 */

static unsigned int
get_next_power_of_buffer_length (unsigned int current_length)
{
  --current_length;

  current_length |= current_length >> 0x01;
  current_length |= current_length >> 0x02;
  current_length |= current_length >> 0x04;
  current_length |= current_length >> 0x08;
  current_length |= current_length >> 0x10;

  return ++current_length;
}

static bool_t
dynamic_string_extend (dynamic_string_t * const dynamic_string, 
                       const size_t extra_length)
{
  const size_t total_buffer_length =
    dynamic_string->string_length + extra_length;

  if (total_buffer_length <= dynamic_string->buffer_length)
  {
    return true;
  }

  const unsigned int next_power_of_buffer_length =
    get_next_power_of_buffer_length (total_buffer_length);

  const string_t const string =
    (string_t) realloc (dynamic_string->string, next_power_of_buffer_length);

  if (!string)
  {
    return false;
  }

  dynamic_string->buffer_length = next_power_of_buffer_length;

  dynamic_string->string = string;

  return true;
}

dynamic_string_t * const
dynamic_string_create (size_t buffer_length)
{
  static const size_t initial_buffer_length = 32;

  if (buffer_length < 0)
  {
    buffer_length = initial_buffer_length;
  }

  dynamic_string_t * dynamic_string =
    (dynamic_string_t *) calloc (1, sizeof (dynamic_string_t));

  if (!dynamic_string)
  {
    return NULL;
  }

  dynamic_string->string = NULL;

  dynamic_string->string_length = 0;

  dynamic_string->buffer_length = buffer_length;

  if (dynamic_string->buffer_length > 0)
  {
    dynamic_string->string = (string_t) malloc (dynamic_string->buffer_length);

    if (!dynamic_string->string)
    {
      safe_free (dynamic_string);

      return NULL;
    }
  }

  return dynamic_string;
}

void
dynamic_string_clear (dynamic_string_t * dynamic_string)
{
  if (dynamic_string)
  {
    safe_free(dynamic_string->string);

    safe_free(dynamic_string);
  }
}

size_t
dynamic_string_length (const dynamic_string_t * const dynamic_string)
{
  return dynamic_string->string_length;
}

bool_t
dynamic_string_append (dynamic_string_t * const dynamic_string,
                       const string_t const string)
{
  const size_t string_length = strlen (string);

  if (!dynamic_string_extend (dynamic_string, string_length + 1))
  {
    return false;
  }

  memcpy (&dynamic_string->string[dynamic_string->string_length],
          string,
          string_length);

  dynamic_string->string_length += string_length;

  dynamic_string->string[dynamic_string->string_length] = '\0';

  return true;
}

Lastly, here is an example of using the dynamic string data structure helper:

bool_t
write_http_response (const int file_descriptor,
                     const http_response_t * const http_response)
{
  dynamic_string_t * const response =
    dynamic_string_create (http_response_initial_buffer_length);

  if (!response)
  {
    return false;
  }

  if (!dynamic_string_append (response, http_response->protocol_version) ||
      !dynamic_string_append (response, " ") ||
      !dynamic_string_append (response, http_response->status_code) ||
      !dynamic_string_append (response, " ") ||
      !dynamic_string_append (response, http_response->reason_phrase) ||
      !dynamic_string_append (response, http_line_end_delimiter))
  {
    dynamic_string_clear (response);

    return false;
  }

  const http_header_field_t * headers = http_response->headers;

  while (headers)
  {
    if (!dynamic_string_append (response, headers->name) ||
        !dynamic_string_append (response, http_header_field_delimiter) ||
        !dynamic_string_append (response, headers->value) ||
        !dynamic_string_append (response, http_line_end_delimiter))
    {
      dynamic_string_clear (response);

      return false;
    }

    headers = headers->next;
  }

  if (!dynamic_string_append (response, http_line_end_delimiter) ||
      !dynamic_string_append (response, http_response->body->string))
  {
    dynamic_string_clear (response);

    return false;
  }

  const bool_t written =
    write_to_file_descriptor (file_descriptor,
                              response->string,
                              dynamic_string_length (response));

  dynamic_string_clear (response);

  return written != -1;
}

Happy Hacking!

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: