Chained_List.h

Go to the documentation of this file.

/* ############################ MALP License ############################## */
/* # Fri Jan 18 14:00:00 CET 2013                                         # */
/* # Copyright or (C) or Copr. Commissariat a l'Energie Atomique          # */
/* #                                                                      # */
/* # This software is governed by the CeCILL-C license under French law   # */
/* # and abiding by the rules of distribution of free software.  You can  # */
/* # use, modify and/ or redistribute the software under the terms of     # */
/* # the CeCILL-C license as circulated by CEA, CNRS and INRIA at the     # */
/* # following URL http://www.cecill.info.                                # */
/* #                                                                      # */
/* # The fact that you are presently reading this means that you have     # */
/* # had knowledge of the CeCILL-C license and that you accept its        # */
/* # terms.                                                               # */
/* #                                                                      # */
/* # Authors:                                                             # */
/* #   - BESNARD Jean-Baptiste jean-baptiste.besnard@cea.fr               # */
/* #                                                                      # */
/* ######################################################################## */

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#ifndef CHAINED_LIST
#define CHAINED_LIST

#ifdef __cplusplus
  extern "C"
  {
#endif

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

struct chained_list {
        void *p_payload;                
        uint32_t current_offset;        
        uint32_t size_of_trunk;         
    size_t size_of_payload;         
        struct chained_list *p_prev;    
};


struct chained_list *chained_list_init(uint32_t size_of_trunk, size_t size_of_payload);

void chained_list_release(struct chained_list **list);

struct chained_list *chained_list_alloc_next_chunk(struct chained_list
        *current_chunk);

struct chained_list *chained_list_alloc_chunk(uint32_t size_of_trunk,
        size_t size_of_payload);

int chained_list_count(struct chained_list *list);

void *chained_list_push(struct chained_list **list, void *p_payload);

void cond_chained_list_merge(struct chained_list **dest,
                             struct chained_list *source,
                             int (*condition) (void *));

void chained_list_walkthrough(struct chained_list *list,
                              void (*action) (void *));

void chained_list_walkthrough_arg(struct chained_list *list,
                                  void (*action) (void *, void *), void *arg);
struct chained_list_view {
        struct chained_list *last_chunk;    
        uint64_t last_chunk_offset;         
};

static inline void chained_list_view_init( struct chained_list_view *clv )
{
        clv->last_chunk = NULL;
        clv->last_chunk_offset = 0;
}

void *chained_list_get_elem( struct chained_list *list, int (*test_func)(void *, void *), void *value );


/* Inlining of hot getters **/

static inline void *chained_list_get_nth(struct chained_list *list, uint64_t n)
{
        uint64_t local_n = n + 1;

        //printf("BEGIN PROCESS %d ( in %p)\n", n, list);
        struct chained_list *tmp = list;

        while (tmp) {

                //printf("tmp % p OFF %d, local_n %d\n",tmp, tmp->current_offset, local_n);

                if ( (local_n <= tmp->current_offset) && (tmp->current_offset) ) {

                        int applied_offset = ( tmp->current_offset *tmp->size_of_payload) - (local_n * tmp->size_of_payload);

                        //printf("AP OFF FOR %lld is %d over %d\n", local_n , applied_offset,  tmp->current_offset  * tmp->size_of_payload );
                        return (void *) ((char *)tmp->p_payload + applied_offset);
                }

                else {

                        //printf("Going to next %p\n", tmp->p_prev);
                        local_n -= tmp->current_offset;
                        tmp = tmp->p_prev;
                }
        }

        // printf ("Get nth failed \n");
        return NULL;
}


static inline void *chained_list_get_nth_seq(struct chained_list *list, struct chained_list_view *view, uint64_t n)
{
        struct chained_list *tmp = list;
        n++;

        uint64_t tmp_n = 0;

        if( !list )
                return NULL;

        //If we already known an offset and it is lower than n
        if( view->last_chunk ) {
                if( view->last_chunk_offset < n ) {
                        //printf("FAST FORWARD TO OFFSET %lld (%p) \n", view->last_chunk_offset, view->last_chunk);
                        tmp = view->last_chunk;

                        tmp_n = view->last_chunk_offset;
                        n -= view->last_chunk_offset;
                }
        }


        if(  tmp->current_offset <= tmp->current_offset  ) {

                while( tmp ) {
                        if(  (n <= tmp->current_offset) && (tmp->current_offset) ) {
                                //Data is in this chunk
                                //Save this chunk infos
                                view->last_chunk = tmp;
                                view->last_chunk_offset = tmp_n;

                                //printf("SAVING CHUNK %p  OFF : %lld  \n", view->last_chunk, tmp_n );

                                break;
                        } else {
                                n -= tmp->current_offset;
                                tmp_n += tmp->current_offset ;
                                tmp = tmp->p_prev;
                        }
                }
        }

        //printf("CANDIDANDE N : %d over %d \n", n, tmp->current_offset );
        /* n was too large */
        if( !tmp )
                return NULL;

        int applied_offset = ( tmp->current_offset * tmp->size_of_payload ) - (n * tmp->size_of_payload);

        //printf("AP OFF FOR %lld is %d over %d\n", n , applied_offset,  tmp->current_offset  * tmp->size_of_payload );
        return (void *) ((char *)tmp->p_payload + applied_offset);
}

struct Chained_List {
        struct chained_list *list;  
        uint64_t count;             
        uint64_t chunk_size;        
        size_t payload_size;        
};

static inline void Chained_List_init( struct Chained_List *list, uint64_t chunk_size, size_t payload_size )
{
        list->list = NULL;
        list->count = 0;
        list->chunk_size = chunk_size;
        list->payload_size = payload_size;
}

static inline void Chained_List_release( struct Chained_List *list )
{
        chained_list_release( &list->list );
        list->count = 0;
}

static inline void* Chained_List_push( struct Chained_List *list, void *payload )
{
        if( list->list == NULL )
                list->list = chained_list_init( list->chunk_size, list->payload_size );

        void *ret = chained_list_push( &(list->list), payload );
        if( ret )
                list->count++;
        return ret;
}

static inline uint64_t Chained_List_count( struct Chained_List *list )
{
        return list->count;
}

static inline void Chained_List_cond_merge(struct Chained_List *dest, struct Chained_List *source, int (*condition) (void *))
{
        if( source->list == NULL )
                return;
        
        if( dest->list == NULL )
                dest->list = chained_list_init( source->chunk_size, source->payload_size );

        cond_chained_list_merge( &dest->list, source->list, condition);
}

static inline void Chained_List_walkthrough(struct Chained_List *list, void (*action) (void *))
{
        if( list->list == NULL || list->count == 0 )
                return;

        chained_list_walkthrough( list->list, action);
}

static inline void Chained_List_walkthrough_arg(struct Chained_List *list, void (*action) (void *, void *), void *arg)
{
        if( list->list == NULL || list->count == 0)
                return;

        chained_list_walkthrough_arg( list->list, action, arg);
}

static inline void * Chained_List_get_nth(struct Chained_List *list, uint64_t n)
{
        if( list->list == NULL || list->count == 0)
                return NULL;

        return chained_list_get_nth( list->list, n);
}

static inline void *Chained_List_get_nth_seq(struct Chained_List *cl, struct chained_list_view *view, uint64_t n)
{
        if( cl->list == NULL || cl->count == 0 )
                return NULL;

        return chained_list_get_nth_seq( cl->list, view, n);
}

static inline void *Chained_List_get_elem( struct Chained_List *list, int (*test_func)(void *, void *), void *value )
{
        if( list->list == NULL )
                return NULL;

        return chained_list_get_elem( list->list, test_func, value );
}
#ifdef __cplusplus
}
#endif
#endif