/*!
   \file linked_list.c

   \brief Linked list memory manager library
    
   This module provides functions for allocating and freeing identically sized
   blocks of memory. Using these routines for linked lists outperforms
   malloc()/free() by a factor varying approximately from 4 to 12. The cost paid
   for performance is the following :
   every chunk of memory (DEFAULT_CHUNK_SIZE blocks) is actually freed when
   every block in it has been freed by list_free(). In some cases that could
   lead to a lot of memory allocated without being used.
   
   Using this library is preferred when you do allocations only and do the
   freeing at the end. In other cases, if you notice excessive memory usage
   with the library, you should consider using G_malloc()/G_free().
       
   (C) 2008 by the GRASS Development Team

   This program is free software under the 
   GNU General Public License (>=v2). 
   Read the file COPYING that comes with GRASS
   for details.

   \author Rosen Matev

   \date 2008
 */

#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"

#define INITIAL_CHUNKS_ARRAY_SIZE 10
#define DEFAULT_CHUNK_SIZE 256

void list_allocate_chunk(struct linked_list *list) {
    struct list_chunk *chunk;
    int ac = list->allocated_chunks;
    
    if (ac == list->chunks_array_size) {
        list->chunks_array = (struct list_chunk **)realloc(list->chunks_array, 2 * list->chunks_array_size * sizeof(struct list_chunk *));
        list->chunks_array_size *= 2;
    }
    
    chunk = malloc(sizeof(struct list_chunk));
    list->chunks_array[ac] = chunk;
    list->allocated_chunks++;
    
    chunk->owner = list;
    chunk->ca_index = ac;
    chunk->mem = malloc(list->chunk_size * (sizeof(struct list_chunk *) + list->unit_size));
    chunk->size = list->chunk_size;
    chunk->available_unit = 0;
    chunk->freed = 0;
    
    return;
}

/*!
   \brief Creates and initializes a new linked_list structure.

   \param unit_size size of each block of memory (node) to be allocated with list_malloc()

   \return A ready to use linked_list structure
 */
struct linked_list *list_init(int unit_size) {
    struct linked_list *list;
    
    list = malloc(sizeof(struct linked_list));
    list->chunks_array = (struct list_chunk **)malloc(INITIAL_CHUNKS_ARRAY_SIZE * sizeof(struct list_chunk *));
    list->chunks_array_size = INITIAL_CHUNKS_ARRAY_SIZE;
    list->allocated_chunks = 0;
    list->chunk_size = DEFAULT_CHUNK_SIZE;
    list->unit_size = unit_size;
    list_allocate_chunk(list);
    
    return list;
}

/*!
   \brief Frees all memory allocated for the structure.

   \param linked_list pointer to an initialized linked_list structure
 */
void list_destroy(struct linked_list *list) {
    int i;
    
    for (i = 0; i < list->allocated_chunks; i++) {
        if (list->chunks_array[i] != NULL) {
            free(list->chunks_array[i]->mem);
            free(list->chunks_array[i]);
        }
    }
    free(list->chunks_array);
    free(list);
    
    return;
}

/*!
   \brief Returns pointer to an available block of memory.

   \param list pointer to an initialized linked_list structure

   \return Pointer to an available block of memory.
 */
void *list_malloc(struct linked_list *list) {
    int ac;
    struct list_chunk *chunk;
    char *ptr;
    
    ac = list->allocated_chunks;
    chunk = list->chunks_array[ac-1];
    if (chunk->available_unit == chunk->size) {
        list_allocate_chunk(list);
        chunk = list->chunks_array[ac];
    }
    
    ptr = &(chunk->mem[chunk->available_unit * (sizeof(struct list_chunk *) + list->unit_size)]);
    *((struct list_chunk **)ptr) = chunk;
    ptr += sizeof(struct list_chunk *);
    chunk->available_unit++;
    
    return ptr;
}

/* Marks the memory block poined by ptr as free */
/*!
   \brief Marks the memory block poined by ptr as free.

   \param list pointer to an initialized linked_list structure
   \param ptr pointer to a block of memory, allocated with list_malloc()
 */
void list_free(struct linked_list *list, void *ptr) {
    struct list_chunk *chunk;
    
    ptr -= sizeof(struct list_chunk *);
    chunk = *((struct list_chunk **)ptr);
    chunk->freed++;
    if (chunk->freed == chunk->size) {
        free(chunk->mem);
        chunk->mem = NULL;
        list->chunks_array[chunk->ca_index] = NULL;
        free(chunk);
    }
    
    return;
}