/*******************************************************************************
    OpenAirInterface
    Copyright(c) 1999 - 2014 Eurecom

    OpenAirInterface 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.


    OpenAirInterface 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 OpenAirInterface.The full GNU General Public License is
   included in this distribution in the file called "COPYING". If not,
   see <http://www.gnu.org/licenses/>.

  Contact Information
  OpenAirInterface Admin: openair_admin@eurecom.fr
  OpenAirInterface Tech : openair_tech@eurecom.fr
  OpenAirInterface Dev  : openair4g-devel@lists.eurecom.fr

  Address      : Eurecom, Campus SophiaTech, 450 Route des Chappes, CS 50193 - 06904 Biot Sophia Antipolis cedex, FRANCE

 *******************************************************************************/
/*! \file list.c
* \brief list management primimtives. It includes three implementations: (1) with mem_blocks, (2) standard list implementation (mem usage 314MB) (3) Linux Queue-based implementation (mem usage 394 MB)
* \author  Navid Nikaein, Mohamed Said MOSLI BOUKSIAA, Lionel GAUTHIER
* \date 2012 - 2014
* \version 0.5
* @ingroup util
*/

#define LIST_C
#define NULL 0

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

//-----------------------------------------------------------------------------
/*
 * initialize list
 */
//-----------------------------------------------------------------------------
void
list_init (list_t * listP, char *nameP)
{
  //-----------------------------------------------------------------------------
  if (nameP) {
    strncpy( listP->name, nameP, LIST_NAME_MAX_CHAR );
    listP->name[LIST_NAME_MAX_CHAR-1] = 0; // terminate string
  }

  listP->tail = NULL;
  listP->head = NULL;
  listP->nb_elements = 0;
}
//-----------------------------------------------------------------------------
void
list_free (list_t * listP)
{
  //-----------------------------------------------------------------------------
  mem_block_t      *le;

  while ((le = list_remove_head (listP))) {
    free_mem_block (le);
  }
}
//-----------------------------------------------------------------------------
mem_block_t *
list_get_head (list_t * listP)
{
  //-----------------------------------------------------------------------------
  return listP->head;
}
//-----------------------------------------------------------------------------
/*
 *  remove an element from head of a list
 *  @param  pointer on targeted list
 *  @return pointer on removed mem_block_t
 */
mem_block_t *
list_remove_head (list_t * listP)
{
  //-----------------------------------------------------------------------------

  // access optimisation
  mem_block_t      *head;
  head = listP->head;

  // almost one element
  if (head != NULL) {
    listP->head = head->next;
    listP->nb_elements = listP->nb_elements - 1;

    // if only one element, update tail
    if (listP->head == NULL) {
      listP->tail = NULL;
    } else {
      head->next = NULL;
    }
  } else {
    //msg("[MEM_MGT][WARNING] remove_head_from_list(%s) no elements\n",listP->name);
  }

  return head;
}

//-----------------------------------------------------------------------------
mem_block_t *
list_remove_element (mem_block_t * elementP, list_t * listP)
{
  //-----------------------------------------------------------------------------

  // access optimisation;
  mem_block_t      *head;

  if (elementP != NULL) {
    // test head
    head = listP->head;

    if (listP->head == elementP) {
      // almost one element
      if (head != NULL) {
        listP->head = head->next;
        listP->nb_elements = listP->nb_elements - 1;

        // if only one element, update tail
        if (listP->head == NULL) {
          listP->tail = NULL;
        } else {
          head->next = NULL;
        }
      }
    } else {
      while (head) {
        if (head->next == elementP) {
          head->next = elementP->next;
          listP->nb_elements = listP->nb_elements - 1;

          if (listP->tail == elementP) {
            listP->tail = head;
          }

          return elementP;
        } else {
          head = head->next;
        }
      }
    }
  }

  return elementP;
}

//-----------------------------------------------------------------------------
/*
 *  add an element to the beginning of a list
 *  @param  pointer on targeted list
 *  @return pointer on removed mem_block_t
 */
void
list_add_head (mem_block_t * elementP, list_t * listP)
{
  //-----------------------------------------------------------------------------

  // access optimisation;
  mem_block_t      *head;

  if (elementP != NULL) {
    head = listP->head;
    listP->nb_elements = listP->nb_elements + 1;

    // almost one element
    if (head == NULL) {
      listP->head = elementP;
      listP->tail = elementP;
    } else {
      elementP->next = head;
      listP->head = elementP;
    }
  }
}

//-----------------------------------------------------------------------------
/*
 *  add an element to the end of a list
 *  @param  pointer on targeted list
 *  @return pointer on removed mem_block_t
 */
void
list_add_tail_eurecom (mem_block_t * elementP, list_t * listP)
{
  mem_block_t      *tail;
  //-----------------------------------------------------------------------------

  if (elementP != NULL) {
    // access optimisation
    listP->nb_elements = listP->nb_elements + 1;
    elementP->next = NULL;
    tail = listP->tail;

    // almost one element
    if (tail == NULL) {
      listP->head = elementP;
    } else {
      tail->next = elementP;
    }

    listP->tail = elementP;
  } else {
    //msg("[CNT_LIST][ERROR] add_cnt_tail() element NULL\n");
  }
}

//-----------------------------------------------------------------------------
void
list_add_list (list_t * sublistP, list_t * listP)
{
  //-----------------------------------------------------------------------------

  if (sublistP) {
    if (sublistP->head) {
      // access optimisation
      mem_block_t      *tail;

      tail = listP->tail;

      // almost one element
      if (tail == NULL) {
        listP->head = sublistP->head;
      } else {
        tail->next = sublistP->head;
      }

      listP->tail = sublistP->tail;
      // clear sublist
      sublistP->head = NULL;
      sublistP->tail = NULL;
      listP->nb_elements = listP->nb_elements + sublistP->nb_elements;
      sublistP->nb_elements = 0;
    }
  }
}

//-----------------------------------------------------------------------------
void
list_display (list_t * listP)
{
  //-----------------------------------------------------------------------------

  mem_block_t      *cursor;
  //  unsigned short             nb_elements = 0;

  // test lists
  if (listP) {
    cursor = listP->head;

    if (cursor) {
      // almost one element
      //msg ("Display list %s %p", listP->name, listP);
      // while (cursor != NULL) {
      // msg ("%d:", cursor->pool_id);
      // msg ("\n");
      // cursor = cursor->next;
      // nb_elements++;
      //}
      //      msg (" found nb_elements %d nb_elements %d\n", nb_elements, listP->nb_elements);
    }
  } else {
    //msg ("[SDU_MNGT][WARNING] display_cnt_list() : list is NULL\n");
  }
}
#ifndef LINUX_LIST
/*! \fn void push_front(struct list* z, double val)
* \brief this function pushes front new values in a predefined list.
* \param z is the predefined list
*       val is the new value to be pushed inside the list
* \return
*/
void
push_front(struct list* z, double val)
{

  struct node* p = (struct node*) malloc(sizeof(struct node));

  p->next = z->head;
  p->val = val;
  z->head = p;

  z->size++;

  return;

}

/*! \fn void initialize(struct list* z)
* \brief initialize a list structure.
* \param z is the list
* \return
*/
void
initialize(struct list* z)
{
  z->head = NULL;
  z->size = 0;

  return;
}

/*! \fn void del(struct list* z)
* \brief delete a list structure.
* \param z is the list
* \return
*/
void
del(struct list* z)
{
  struct node* cur;
  struct node* x = z->head;

  while((x != NULL) && (z->size > 0)) {
    cur = x;
    x = x->next;
    free(cur);
    z->size--;
  }

  z->head = NULL;
  z->size = 0;

  return;
}
/*! \fn void totable(double* table, struct list* v)
* \brief convert a list structure to a table.
* \param table is a pointer to double table
*        v is the list to be converted
* \return
*/
void
totable(double* table, struct list* v)
{
  int i = 0;

  struct node* x = v->head;

  while(x) {
    table[i] = x->val;
    i++;
    x = x->next;
  }

  return;
}
/*! \fn int compare (const void * a, const void * b)
* \brief compare the value of two parameters
* \param a is a double, b is another double
* \return 1 if a>b, -0 if a<b
*/
int compare (const void * a, const void * b)
{
  double x = *(double*)a;
  double y = *(double*)b;

  return ( x > y );
}
#else
// push an element to the head of the list
void push_front(struct list* z, double val)
{
  struct entry* p = (struct entry*) malloc(sizeof(struct entry));
  p->val = val;

  LIST_INSERT_HEAD(&z->head, p, entries);
  z->size++;

  return;

}


// initialization
void initialize(struct list* z)
{
  LIST_INIT(&z->head);
  z->size = 0;

  return;
}

// delete
void del(struct list* z)
{
  while (z->head.lh_first != NULL) {
    free(z->head.lh_first);
    LIST_REMOVE(z->head.lh_first, entries);
  }

  z->size = 0;

  return;
}

// convert the list to a table
void totable(double* table, struct list* v)
{
  int i = 0;

  struct entry* x;

  for (x = v->head.lh_first; x != NULL; x = x->entries.le_next) {
    table[i] = x->val;
    i++;
  }

  return;
}

int compare (const void * a, const void * b)
{
  double x = *(double*)a;
  double y = *(double*)b;

  return ( x > y );
}
#endif

/*! \fn int32_t calculate_median(struct list *loc_list)
* \brief calculate the median of a list
* \param loc_list is the list
* \return the median value
*/
int32_t calculate_median(struct list *loc_list)
{
  int32_t median = 0;

  if (loc_list->size > 0) {
    double* table = (double*) malloc(loc_list->size * sizeof(double));
    totable(table, loc_list);
    /// sort the table in ascending way
    qsort (table, loc_list->size, sizeof(double), &compare);
    /// median is the value at middle the sorted table
    /// Q1 is the value at 1/4 the sorted table
    /// Q3 is the value at 3/4 the sorted table
    median = table[loc_list->size/2];
    free(table);
  }

  return median;
}
