/*

   +----------------------------------------------------------------------+

   | Zend Engine                                                          |

   +----------------------------------------------------------------------+

   | Copyright © Zend Technologies Ltd., a subsidiary company of          |

   |     Perforce Software, Inc., and Contributors.                       |

   +----------------------------------------------------------------------+

   | This source file is subject to the Modified BSD License that is      |

   | bundled with this package in the file LICENSE, and is available      |

   | through the World Wide Web at <https://www.php.net/license/>.        |

   |                                                                      |

   | SPDX-License-Identifier: BSD-3-Clause                                |

   +----------------------------------------------------------------------+

   | Authors: Andi Gutmans <andi@php.net>                                 |

   |          Zeev Suraski <zeev@php.net>                                 |

   +----------------------------------------------------------------------+

*/

#include "zend.h"

#include "zend_llist.h"

#include "zend_sort.h"

ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)

{

  l->head  = NULL;

  l->tail  = NULL;

  l->count = 0;

  l->size  = size;

  l->dtor  = dtor;

  l->persistent = persistent;

}

ZEND_API void zend_llist_add_element(zend_llist *l, const void *element)

{

  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

  tmp->prev = l->tail;

  tmp->next = NULL;

  if (l->tail) {

    l->tail->next = tmp;

  } else {

    l->head = tmp;

  }

  l->tail = tmp;

  memcpy(tmp->data, element, l->size);

  ++l->count;

}

ZEND_API void zend_llist_prepend_element(zend_llist *l, const void *element)

{

  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

  tmp->next = l->head;

  tmp->prev = NULL;

  if (l->head) {

    l->head->prev = tmp;

  } else {

    l->tail = tmp;

  }

  l->head = tmp;

  memcpy(tmp->data, element, l->size);

  ++l->count;

}

#define DEL_LLIST_ELEMENT(current, l) \

      if ((current)->prev) {\

        (current)->prev->next = (current)->next;\

      } else {\

        (l)->head = (current)->next;\

      }\

      if ((current)->next) {\

        (current)->next->prev = (current)->prev;\

      } else {\

        (l)->tail = (current)->prev;\

      }\

      if ((l)->dtor) {\

        (l)->dtor((current)->data);\

      }\

      pefree((current), (l)->persistent);\

      --l->count;

ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))

{

  zend_llist_element *current=l->head;

  while (current) {

    if (compare(current->data, element)) {

      DEL_LLIST_ELEMENT(current, l);

      break;

    }

    current = current->next;

  }

}

ZEND_API void zend_llist_destroy(zend_llist *l)

{

  zend_llist_element *current=l->head, *next;

  while (current) {

    next = current->next;

    if (l->dtor) {

      l->dtor(current->data);

    }

    pefree(current, l->persistent);

    current = next;

  }

  l->head  = NULL;

  l->tail  = NULL;

  l->count = 0;

}

ZEND_API void zend_llist_clean(zend_llist *l)

{

  zend_llist_destroy(l);

}

ZEND_API void zend_llist_remove_tail(zend_llist *l)

{

  zend_llist_element *old_tail = l->tail;

  if (!old_tail) {

    return;

  }

  if (old_tail->prev) {

    old_tail->prev->next = NULL;

  } else {

    l->head = NULL;

  }

  l->tail = old_tail->prev;

  --l->count;

  if (l->dtor) {

    l->dtor(old_tail->data);

  }

  pefree(old_tail, l->persistent);

}

ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)

{

  zend_llist_element *ptr;

  zend_llist_init(dst, src->size, src->dtor, src->persistent);

  ptr = src->head;

  while (ptr) {

    zend_llist_add_element(dst, ptr->data);

    ptr = ptr->next;

  }

}

ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))

{

  zend_llist_element *element, *next;

  element=l->head;

  while (element) {

    next = element->next;

    if (func(element->data)) {

      DEL_LLIST_ELEMENT(element, l);

    }

    element = next;

  }

}

ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)

{

  zend_llist_element *element;

  for (element=l->head; element; element=element->next) {

    func(element->data);

  }

}

static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)

{

  zend_llist_element *t;

  t = *p;

  *p = *q;

  *q = t;

}

ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)

{

  size_t i;

  zend_llist_element **elements;

  zend_llist_element *element, **ptr;

  if (l->count == 0) {

    return;

  }

  elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));

  ptr = &elements[0];

  for (element=l->head; element; element=element->next) {

    *ptr++ = element;

  }

  zend_sort(elements, l->count, sizeof(zend_llist_element *),

      (compare_func_t) comp_func, (swap_func_t) zend_llist_swap);

  l->head = elements[0];

  elements[0]->prev = NULL;

  for (i = 1; i < l->count; i++) {

    elements[i]->prev = elements[i-1];

    elements[i-1]->next = elements[i];

  }

  elements[i-1]->next = NULL;

  l->tail = elements[i-1];

  efree(elements);

}

ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg)

{

  zend_llist_element *element;

  for (element=l->head; element; element=element->next) {

    func(element->data, arg);

  }

}

ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)

{

  zend_llist_element *element;

  va_list args;

  va_start(args, num_args);

  for (element=l->head; element; element=element->next) {

    func(element->data, num_args, args);

  }

  va_end(args);

}

ZEND_API size_t zend_llist_count(zend_llist *l)

{

  return l->count;

}

ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)

{

  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  *current = l->head;

  if (*current) {

    return (*current)->data;

  } else {

    return NULL;

  }

}

ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)

{

  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  *current = l->tail;

  if (*current) {

    return (*current)->data;

  } else {

    return NULL;

  }

}

ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)

{

  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  if (*current) {

    *current = (*current)->next;

    if (*current) {

      return (*current)->data;

    }

  }

  return NULL;

}

ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)

{

  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  if (*current) {

    *current = (*current)->prev;

    if (*current) {

      return (*current)->data;

    }

  }

  return NULL;

}