path: root/array.c

/*  libnul 
 *  Copyright (C) 2008  Søren Sandmann (sandmann@daimi.au.dk)
 *
 *  This library 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 2 of the License, or
 *  (at your option) any later version.
 *
 *  This library 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 library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include <string.h>
#include <glib/gprintf.h>
#include "libnul.h"

/* General array implementation */

typedef struct array_t array_t;

typedef union
{
    double d;
    int    i;
    void  *p;
    long   l;
} align_t;

struct array_t
{
    const int *magic;
    int	       element_size;
    gssize     n_bytes;		/* Number of bytes allocated in total */
    gssize     n_elements;	/* Number of elements in use, not including
				 * the nul terminator
				 */
    gssize     n_prefix_bytes;	/* Number of data bytes used for the application prefix */
    align_t    data[1];
};

static inline array_t *
get_array (const void *data, const int *magic)
{
    array_t *array;
    
    array = (array_t *)((uint8_t *)data - NUL_STRUCT_OFFSET (array_t, data));
    
    g_return_val_if_fail (array->magic == magic, NULL);
    
    return array;
}

static void
array_free (void *data, const int *magic)
{
    array_t *array = get_array (data, magic);
    
    g_free (array);
}

static void
nul_terminate (array_t *array)
{
    char *end = (char *)array->data;

    end += array->n_prefix_bytes;
    end += array->n_elements * array->element_size;

    memset (end, 0, array->element_size);
}

static array_t * G_GNUC_WARN_UNUSED_RESULT
realloc_array (array_t *array, int n_elements) 
{
    gssize n_bytes;
    
    /* FIXME: overflow? */
    n_bytes = NUL_STRUCT_OFFSET (array_t, data);
    n_bytes += (n_elements + 1) * array->element_size;
    n_bytes += array->n_prefix_bytes;
    
    if (n_bytes > array->n_bytes)
    {
	gssize pot;
	
	pot = 1;
	while (pot < n_bytes)
	    pot *= 2;

	array = g_realloc (array, pot);
	array->n_bytes = pot;

	nul_terminate (array);
    }
    
    return array;
}

static void *
array_new (int element_size, const int *magic, int n_prefix_bytes)
{
    array_t *array = g_new (array_t, 1);
    
    array->magic = magic;
    array->element_size = element_size;
    array->n_prefix_bytes = n_prefix_bytes;
    array->n_bytes = sizeof (array_t);
    array->n_elements = 0;

    array = realloc_array (array, 16);
    
    return array->data;
}

static void *
array_delete_head (void *data, const int *magic, gssize n_elements)
{
    array_t *array = get_array (data, magic);
    int n_bytes = n_elements * array->element_size;
    int n_total = array->n_elements * array->element_size;
    char *first;

    if (n_elements < 0 || n_elements > array->n_elements)
	n_bytes = n_total;
    
    /* FIXME: this should be done in constant time */

    first = (char *)array->data + array->n_prefix_bytes;
    
    memmove (first, first + n_bytes, n_total - n_bytes);
    
    array->n_elements -= n_elements;
    
    nul_terminate (array);
    
    return array->data;
}

static void *
array_delete_tail (void *data, const int *magic, int n_elements)
{
    array_t *array = get_array (data, magic);
 
    array->n_elements -= n_elements;
    nul_terminate (array);
    
    return array->data;
}

static void * G_GNUC_WARN_UNUSED_RESULT
array_append_undefined (void *data,
			const int *magic,
			int n_elements,
			void **tail)
{
    array_t *array = get_array (data, magic);

    array = realloc_array (array, array->n_elements + n_elements);

    array->n_elements += n_elements;

    nul_terminate (array);

    if (tail)
	*tail = (char *)array->data + array->n_prefix_bytes + array->element_size * (array->n_elements - n_elements);

    return array->data;
}

static void *
array_append (void *data,
	      const int *magic,
	      void *element)
{
    void *tail;
    
    data = array_append_undefined (data, magic, 1, &tail);

    memcpy (tail, element, get_array (data, magic)->element_size);

    return data;
}

static char *
locate_element (array_t *array,
		void    *element)
{
    int i;

    for (i = 0; i < array->n_elements; ++i)
    {
	char *elt = ((char *)array->data) + array->n_prefix_bytes +
	    i * array->element_size;
	
	if (memcmp (elt, element, array->element_size) == 0)
	    return elt;
    }

    return NULL;
}

static void *
array_remove (void *data,
	      const int *magic,
	      void *element,
	      gboolean fast)
{
    array_t *array = get_array (data, magic);
    char *location = locate_element (array, element);
    char *end;

    if (location)
    {
	end = (char *)array->data +
	    array->n_prefix_bytes + array->n_elements * array->element_size;

	if (fast)
	{
	    memmove (location, end - array->element_size, array->element_size);
	}
	else
	{
	    memmove (location, location + array->element_size,
		     end - (location + array->element_size));
	}
	
	array = realloc_array (array, array->n_elements - 1);

	array->n_elements--;

	nul_terminate (array);
    }

    return array->data;
}

static void *
array_set_size (void *data,
		const int *magic,
		gsize n_elements)
{
    array_t *array = get_array (data, magic);
    
    array = realloc_array (array, n_elements);

    array->n_elements = n_elements;

    nul_terminate (array);

    return array->data;
}

static gssize
array_len (const void *data, const int *magic)
{
    array_t *array = get_array (data, magic);

    return array->n_elements;
}

/***************************** individual array implementations ****************************/

/* Generic arrays
 *
 * The idiomatic way to use them is like this:
 *
 *    mytype_t *mytypes = nul_array_new (sizeof (mytype_t));
 *    mytypes = nul_array_append (mytypes, &a_mytype);
 *
 * To iterate through, either use nul_array_len() or rely on
 * the fact that there will always be at least one element
 * with nul bits at the end.
 *
 */

static const int arr_t_magic;

nul_ptr_t
nul_garray_new (int element_size)
{
    return array_new (element_size, &arr_t_magic, 0);
}

nul_ptr_t
nul_garray_new_prefix (int element_size, int prefix_size)
{
    return array_new (element_size, &arr_t_magic, prefix_size);
}

nul_ptr_t
nul_garray_append (nul_ptr_t arr, nul_ptr_t element)
{
    return array_append (arr, &arr_t_magic, element);
}

void
nul_garray_free (nul_ptr_t array)
{
    array_free (array, &arr_t_magic);
}

gsize
nul_garray_len (const nul_ptr_t array)
{
    return array_len (array, &arr_t_magic);
}

nul_ptr_t
nul_garray_remove (nul_ptr_t arr, nul_ptr_t element)
{
    return array_remove (arr, &arr_t_magic, element, FALSE);
}

nul_ptr_t
nul_garray_remove_fast (nul_ptr_t arr, nul_ptr_t element)
{
    return array_remove (arr, &arr_t_magic, element, TRUE);
}

nul_ptr_t
nul_garray_set_size (nul_ptr_t arr, gsize n_elements)
{
    return array_set_size (arr, &arr_t_magic, n_elements);
}

/*
 * Strings
 */
static const int string_t_magic;

nul_string_t *
nul_string_new (void)
{
    return array_new (sizeof (char), &string_t_magic, 0);
}

void
nul_string_free (nul_string_t *str)
{
    array_free (str, &string_t_magic);
}

gsize
nul_string_len (const nul_string_t *str)
{
    return array_len (str, &string_t_magic);
}

gboolean
nul_string_empty (const nul_string_t *str)
{
    return nul_string_len (str) == 0;
}

nul_string_t * G_GNUC_WARN_UNUSED_RESULT
nul_string_append_undefined (nul_string_t  *str,
			     gsize          n_bytes,
			     char         **tail)
{
    return array_append_undefined (str, &string_t_magic, n_bytes, (void **)tail);
}

nul_string_t *
nul_string_append (nul_string_t *str,
		   const char   *bytes,
		   gssize        n_bytes)
{
    char *tail;
    
    str = nul_string_append_undefined (str, n_bytes, &tail);

    memcpy (tail, bytes, n_bytes);
    
    return str;
}

nul_string_t *
nul_string_append_printf (nul_string_t *str,
			  const char   *fmt,
			  ...)
{
    va_list args;
    
    g_return_val_if_fail (fmt != NULL, NULL);
    
    va_start (args, fmt);
    
    str = nul_string_append_vprintf (str, fmt, args);
    
    va_end (args);
    
    return str;
}

nul_string_t *
nul_string_append_vprintf (nul_string_t *str,
			   const char   *fmt,
			   va_list       args)
{
    gsize required;
    gchar *buffer;
    
    required = g_vsnprintf (NULL, 0, fmt, args);
    
    str = nul_string_append_undefined (str, required, &buffer);
    
    g_vsprintf (buffer, fmt, args);
    
    return str;
}

nul_string_t *
nul_string_delete_head (nul_string_t *str,
			gsize         n_bytes)
{
    return array_delete_head (str, &string_t_magic, n_bytes);
}

nul_string_t *
nul_string_delete_tail (nul_string_t *str,
			gsize         n_bytes)
{
    return array_delete_tail (str, &string_t_magic, n_bytes);
}

/*
 * Buffer
 */
struct nul_buffer_t
{
    nul_string_t *data;
};

nul_buffer_t *
nul_buffer_new (void)
{
    nul_buffer_t *buffer = g_new0 (nul_buffer_t, 1);
    
    buffer->data = nul_string_new ();
    
    return buffer;
}

gsize
nul_buffer_get_length (nul_buffer_t *buffer)
{
    return nul_string_len (buffer->data);
}

nul_string_t *
nul_buffer_free (nul_buffer_t *buffer,
		 gboolean      free_data)
{
    char *result;
    
    if (free_data)
    {
	nul_string_free (buffer->data);
	result = NULL;
    }
    else
    {
	result = buffer->data;
    }

    g_free (buffer);
    
    return result;
}

/* The data returned is owned by the byte buffer and becomes invalid
 * as soon as any method is called on the buffer.
 */
const gchar *
nul_buffer_peek (nul_buffer_t *buffer,
		 gsize        *n_bytes)
{
    if (n_bytes)
	*n_bytes = nul_string_len (buffer->data);
    
    return buffer->data;
}

gboolean
nul_buffer_is_empty (nul_buffer_t *buffer)
{
    return nul_string_empty (buffer->data);
}

/* This function appends uninitialized data of length @size
 * to the buffer, then returns a pointer to the added data.
 * The intention is that the app can read() into this
 * memory, then use nul_buffer_delete_tail() to delete the
 * area that wasn't read into. Example
 *
 *        guint8 *area = nul_buffer_alloc_tail (buffer, 8192);
 *
 *        n_read = read (fd, area, 8192);
 *
 *        if (n_read < 0)
 *        {
 *	       nul_buffer_delete_tail (buffer, 8192);
 *             handle_error();
 *             n_read = 0;
 *        }
 *        else
 *        {
 *	       nul_buffer_delete_tail (8192 - n_read);
 *
 *             // enjoy the new data in the buffer
 *        }
 */
char *
nul_buffer_alloc_tail (nul_buffer_t *buffer,
		       gsize	     size)
{
    char *tail;
    
    buffer->data = nul_string_append_undefined (buffer->data, size, &tail);
    
    return tail;
}

void
nul_buffer_delete_head (nul_buffer_t *buffer,
			gsize	      size)
{
    buffer->data = nul_string_delete_head (buffer->data, size);
}

void
nul_buffer_delete_tail (nul_buffer_t *buffer,
			gsize	   size)
{
    buffer->data = nul_string_delete_tail (buffer->data, size);
}

void
nul_buffer_append (nul_buffer_t *buffer,
		   const gchar  *bytes,
		   gsize         n_bytes)
{
    buffer->data = nul_string_append (buffer->data, bytes, n_bytes);
}

void
nul_buffer_append_printf (nul_buffer_t *buffer,
			  const gchar *fmt,
			  ...)
{
    va_list args;
    
    g_return_if_fail (fmt != NULL);
    
    va_start (args, fmt);
    
    buffer->data = nul_string_append_vprintf (buffer->data, fmt, args);
    
    va_end (args);
}

nul_string_t *
nul_buffer_steal (nul_buffer_t *buffer,
		  gsize        *n_bytes)
{
    nul_string_t *result = buffer->data;
    
    if (n_bytes)
	*n_bytes = nul_string_len (result);
    
    buffer->data = nul_string_new ();
    
    return result;
}

static void
nul_buffer_swap_content (nul_buffer_t *buffer1,
			 nul_buffer_t *buffer2)
{
    nul_string_t *tmp;
    
    tmp = buffer2->data;
    buffer2->data = buffer1->data;
    buffer1->data = tmp;
}


/* Transfer n_bytes data from the head of @src to tail of @dest,
 * if possible without copying. The data is appended to @dest's data
 * if @dest is not empty
 */
void
nul_buffer_transfer_data (nul_buffer_t    *dest,
			  nul_buffer_t    *src,
			  gssize	   n_bytes)
{
    gsize total = nul_buffer_get_length (src);
    
    if (n_bytes < 0 || n_bytes > total)
	n_bytes = total;
    
    if (nul_buffer_is_empty (dest))
    {
	const char *source = src->data;
	gboolean swap_contents = FALSE;
	
	if (n_bytes > total / 2)
	{
	    source = src->data + n_bytes;
	    n_bytes = total - n_bytes;
	    swap_contents = TRUE;
	}
	
	nul_buffer_append (dest, source, n_bytes);
	
	if (swap_contents)
	{
	    nul_buffer_delete_tail (src, n_bytes);
	    nul_buffer_swap_content (dest, src);
	}
	else
	{
	    nul_buffer_delete_head (src, n_bytes);
	}
    }
    else
    {
	/* FIXME:
	 *
	 *  check whether one of the strings fit in the other's segment.
	 *  if both fit, copy the shortest, if only one, copy that one.
	 *  if none, just append.
	 */
	nul_buffer_append (dest, src->data, n_bytes);

	nul_buffer_delete_head (src, n_bytes);
    }
}