/*
   american fuzzy lop++ - linked list code
   ---------------------------------------

   Originally written by Michal Zalewski

   Now maintained by Marc Heuse <mh@mh-sec.de>,
                     Heiko Eissfeldt <heiko.eissfeldt@hexco.de>,
                     Andrea Fioraldi <andreafioraldi@gmail.com>,
                     Dominik Maier <mail@dmnk.co>

   Copyright 2016, 2017 Google Inc. All rights reserved.
   Copyright 2019-2024 AFLplusplus Project. All rights reserved.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at:

     https://www.apache.org/licenses/LICENSE-2.0

   This allocator is not designed to resist malicious attackers (the canaries
   are small and predictable), but provides a robust and portable way to detect
   use-after-free, off-by-one writes, stale pointers, and so on.

 */

#ifndef AFL_LIST
#define AFL_LIST

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#include "debug.h"
#include "afl-prealloc.h"

/* How many elements to allocate before malloc is needed */
#define LIST_PREALLOC_SIZE (64)

typedef struct list_element {

  PREALLOCABLE;

  struct list_element *prev;
  struct list_element *next;
  void                *data;

} element_t;

typedef struct list {

  element_t element_prealloc_buf[LIST_PREALLOC_SIZE];
  s32       element_prealloc_count;

} list_t;

static inline element_t *get_head(list_t *list) {

  /* The first element is the head */
  return list->element_prealloc_buf;

}

static inline void list_free_el(list_t *list, element_t *el) {

  PRE_FREE(el, list->element_prealloc_count);

}

static inline void list_append(list_t *list, void *el) {

  element_t *head = get_head(list);
  if (!head->next) {

    /* initialize */

    memset(list, 0, sizeof(list_t));
    PRE_ALLOC_FORCE(head, list->element_prealloc_count);
    head->next = head->prev = head;

  }

  element_t *el_box = NULL;

  PRE_ALLOC(el_box, list->element_prealloc_buf, LIST_PREALLOC_SIZE,
            list->element_prealloc_count);
  if (!el_box) { FATAL("failed to allocate list element"); }
  el_box->data = el;
  el_box->next = head;
  el_box->prev = head->prev;
  head->prev->next = el_box;
  head->prev = el_box;

}

/* Simple foreach.
   Pointer to the current element is in `el`,
   casted to (a pointer) of the given `type`.
   A return from this block will return from calling func.
*/

#define LIST_FOREACH(list, type, block)                            \
  do {                                                             \
                                                                   \
    list_t    *li = (list);                                        \
    element_t *head = get_head((li));                              \
    element_t *el_box = (head)->next;                              \
    if (!el_box) FATAL("foreach over uninitialized list");         \
    while (el_box != head) {                                       \
                                                                   \
      __attribute__((unused)) type *el = (type *)((el_box)->data); \
      /* get next so el_box can be unlinked */                     \
      element_t *next = el_box->next;                              \
      {block};                                                     \
      el_box = next;                                               \
                                                                   \
    }                                                              \
                                                                   \
  } while (0);

/* In foreach: remove the current el from the list */

#define LIST_REMOVE_CURRENT_EL_IN_FOREACH() \
  do {                                      \
                                            \
    el_box->prev->next = next;              \
    el_box->next->prev = el_box->prev;      \
    list_free_el(li, el_box);               \
                                            \
  } while (0);

/* Same as foreach, but will clear list in the process */

#define LIST_FOREACH_CLEAR(list, type, block) \
  do {                                        \
                                              \
    LIST_FOREACH((list), type, {              \
                                              \
      {block};                                \
      LIST_REMOVE_CURRENT_EL_IN_FOREACH();    \
                                              \
    });                                       \
                                              \
  } while (0);

/* remove an item from the list */

static inline void list_remove(list_t *list, void *remove_me) {

  LIST_FOREACH(list, void, {

    if (el == remove_me) {

      el_box->prev->next = el_box->next;
      el_box->next->prev = el_box->prev;
      el_box->data = NULL;
      list_free_el(list, el_box);
      return;

    }

  });

  FATAL("List item to be removed not in list");

}

/* Returns true if el is in list */

static inline bool list_contains(list_t *list, void *contains_me) {

  LIST_FOREACH(list, void, {

    if (el == contains_me) return true;

  });

  return false;

}

#endif