genlist.cpp

Go to the documentation of this file.

/*__            ___                 ***************************************
/   \          /   \          Copyright (c) 1996-2021 Freeciv21 and Freeciv
\_   \        /  __/          contributors. This file is part of Freeciv21.
 _\   \      /  /__     Freeciv21 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.
     _/     /\                  You should have received  a copy of the GNU
    /o)  (o/\ \_                General Public License along with Freeciv21.
    \_____/ /                     If not, see https://www.gnu.org/licenses/.
      \____/        ********************************************************/
 
#include <cstdlib>
 
// utility
#include "fcthread.h"
#include "log.h"
#include "rand.h"
 
#include "genlist.h"
struct genlist *genlist_new() { return genlist_new_full(nullptr); }
 
struct genlist *genlist_new_full(genlist_free_fn_t free_data_func)
{
  genlist *pgenlist = new genlist;
 
  pgenlist->nelements = 0;
  pgenlist->head_link = nullptr;
  pgenlist->tail_link = nullptr;
  pgenlist->free_data_func = free_data_func;
 
  return pgenlist;
}
 
void genlist_destroy(struct genlist *pgenlist)
{
  if (pgenlist == nullptr) {
    return;
  }
 
  genlist_clear(pgenlist);
  delete pgenlist;
}
 
static void genlist_link_new(struct genlist *pgenlist, void *dataptr,
                             struct genlist_link *prev,
                             struct genlist_link *next)
{
  genlist_link *plink = new genlist_link;
 
  plink->dataptr = dataptr;
  plink->prev = prev;
  if (nullptr != prev) {
    prev->next = plink;
  } else {
    pgenlist->head_link = plink;
  }
  plink->next = next;
  if (nullptr != next) {
    next->prev = plink;
  } else {
    pgenlist->tail_link = plink;
  }
  pgenlist->nelements++;
}
 
static void genlist_link_destroy(struct genlist *pgenlist,
                                 struct genlist_link *plink)
{
  if (pgenlist->head_link == plink) {
    pgenlist->head_link = plink->next;
  } else {
    plink->prev->next = plink->next;
  }
 
  if (pgenlist->tail_link == plink) {
    pgenlist->tail_link = plink->prev;
  } else {
    plink->next->prev = plink->prev;
  }
 
  pgenlist->nelements--;
 
  /* NB: detach the link before calling the free function for avoiding
   * re-entrant code. */
  if (nullptr != pgenlist->free_data_func) {
    pgenlist->free_data_func(plink->dataptr);
  }
  delete plink;
}
 
static struct genlist_link *
genlist_link_at_pos(const struct genlist *pgenlist, int pos)
{
  struct genlist_link *plink;
 
  if (pos == 0) {
    return pgenlist->head_link;
  } else if (pos == -1) {
    return pgenlist->tail_link;
  } else if (pos < -1 || pos >= pgenlist->nelements) {
    return nullptr;
  }
 
  if (pos < pgenlist->nelements / 2) { // fastest to do forward search
    for (plink = pgenlist->head_link; pos != 0; pos--) {
      plink = plink->next;
    }
  } else { // fastest to do backward search
    for (plink = pgenlist->tail_link, pos = pgenlist->nelements - pos - 1;
         pos != 0; pos--) {
      plink = plink->prev;
    }
  }
 
  return plink;
}
 
struct genlist *genlist_copy(const struct genlist *pgenlist)
{
  return genlist_copy_full(pgenlist, nullptr, pgenlist->free_data_func);
}
 
struct genlist *genlist_copy_full(const struct genlist *pgenlist,
                                  genlist_copy_fn_t copy_data_func,
                                  genlist_free_fn_t free_data_func)
{
  struct genlist *pcopy = genlist_new_full(free_data_func);
 
  if (pgenlist) {
    struct genlist_link *plink;
 
    if (nullptr != copy_data_func) {
      for (plink = pgenlist->head_link; plink; plink = plink->next) {
        genlist_link_new(pcopy, copy_data_func(plink->dataptr),
                         pcopy->tail_link, nullptr);
      }
    } else {
      for (plink = pgenlist->head_link; plink; plink = plink->next) {
        genlist_link_new(pcopy, plink->dataptr, pcopy->tail_link, nullptr);
      }
    }
  }
 
  return pcopy;
}
 
int genlist_size(const struct genlist *pgenlist)
{
  fc_assert_ret_val(nullptr != pgenlist, 0);
  return pgenlist->nelements;
}
 
struct genlist_link *genlist_link_get(const struct genlist *pgenlist,
                                      int idx)
{
  fc_assert_ret_val(nullptr != pgenlist, nullptr);
 
  return genlist_link_at_pos(pgenlist, idx);
}
 
struct genlist_link *genlist_tail(const struct genlist *pgenlist)
{
  return (nullptr != pgenlist ? pgenlist->tail_link : nullptr);
}
 
void *genlist_get(const struct genlist *pgenlist, int idx)
{
  return genlist_link_data(genlist_link_get(pgenlist, idx));
}
 
void *genlist_front(const struct genlist *pgenlist)
{
  return genlist_link_data(genlist_head(pgenlist));
}
 
void *genlist_back(const struct genlist *pgenlist)
{
  return genlist_link_data(genlist_tail(pgenlist));
}
 
void genlist_clear(struct genlist *pgenlist)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (0 < pgenlist->nelements) {
    genlist_free_fn_t free_data_func = pgenlist->free_data_func;
    struct genlist_link *plink = pgenlist->head_link, *plink2;
 
    pgenlist->head_link = nullptr;
    pgenlist->tail_link = nullptr;
 
    pgenlist->nelements = 0;
 
    if (nullptr != free_data_func) {
      do {
        plink2 = plink->next;
        free_data_func(plink->dataptr);
        delete plink;
      } while (nullptr != (plink = plink2));
    } else {
      do {
        plink2 = plink->next;
        delete plink;
      } while (nullptr != (plink = plink2));
    }
  }
}
 
void genlist_unique(struct genlist *pgenlist)
{
  genlist_unique_full(pgenlist, nullptr);
}
 
void genlist_unique_full(struct genlist *pgenlist,
                         genlist_comp_fn_t comp_data_func)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (2 <= pgenlist->nelements) {
    struct genlist_link *plink = pgenlist->head_link, *plink2;
 
    if (nullptr != comp_data_func) {
      do {
        plink2 = plink->next;
        if (nullptr != plink2
            && comp_data_func(plink->dataptr, plink2->dataptr)) {
          // Remove this element.
          genlist_link_destroy(pgenlist, plink);
        }
      } while ((plink = plink2) != nullptr);
    } else {
      do {
        plink2 = plink->next;
        if (nullptr != plink2 && plink->dataptr == plink2->dataptr) {
          // Remove this element.
          genlist_link_destroy(pgenlist, plink);
        }
      } while ((plink = plink2) != nullptr);
    }
  }
}
 
bool genlist_remove(struct genlist *pgenlist, const void *punlink)
{
  struct genlist_link *plink;
 
  fc_assert_ret_val(nullptr != pgenlist, false);
 
  for (plink = pgenlist->head_link; nullptr != plink; plink = plink->next) {
    if (plink->dataptr == punlink) {
      genlist_link_destroy(pgenlist, plink);
      return true;
    }
  }
 
  return false;
}
 
int genlist_remove_all(struct genlist *pgenlist, const void *punlink)
{
  struct genlist_link *plink;
  int count = 0;
 
  fc_assert_ret_val(nullptr != pgenlist, 0);
 
  for (plink = pgenlist->head_link; nullptr != plink;) {
    if (plink->dataptr == punlink) {
      struct genlist_link *pnext = plink->next;
 
      genlist_link_destroy(pgenlist, plink);
      count++;
      plink = pnext;
    } else {
      plink = plink->next;
    }
  }
 
  return count;
}
 
bool genlist_remove_if(struct genlist *pgenlist,
                       genlist_cond_fn_t cond_data_func)
{
  fc_assert_ret_val(nullptr != pgenlist, false);
 
  if (nullptr != cond_data_func) {
    struct genlist_link *plink = pgenlist->head_link;
 
    for (; nullptr != plink; plink = plink->next) {
      if (cond_data_func(plink->dataptr)) {
        genlist_link_destroy(pgenlist, plink);
        return true;
      }
    }
  }
 
  return false;
}
 
int genlist_remove_all_if(struct genlist *pgenlist,
                          genlist_cond_fn_t cond_data_func)
{
  fc_assert_ret_val(nullptr != pgenlist, 0);
 
  if (nullptr != cond_data_func) {
    struct genlist_link *plink = pgenlist->head_link;
    int count = 0;
 
    while (nullptr != plink) {
      if (cond_data_func(plink->dataptr)) {
        struct genlist_link *pnext = plink->next;
 
        genlist_link_destroy(pgenlist, plink);
        count++;
        plink = pnext;
      } else {
        plink = plink->next;
      }
    }
    return count;
  }
 
  return 0;
}
 
void genlist_erase(struct genlist *pgenlist, struct genlist_link *plink)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (nullptr != plink) {
    genlist_link_destroy(pgenlist, plink);
  }
}
 
void genlist_pop_front(struct genlist *pgenlist)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (nullptr != pgenlist->head_link) {
    genlist_link_destroy(pgenlist, pgenlist->head_link);
  }
}
 
void genlist_pop_back(struct genlist *pgenlist)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (nullptr != pgenlist->tail_link) {
    genlist_link_destroy(pgenlist, pgenlist->tail_link);
  }
}
 
void genlist_insert(struct genlist *pgenlist, void *data, int pos)
{
  fc_assert_ret(nullptr != pgenlist);
 
  if (0 == pgenlist->nelements) {
    // List is empty, ignore pos.
    genlist_link_new(pgenlist, data, nullptr, nullptr);
  } else if (0 == pos) {
    // Prepend.
    genlist_link_new(pgenlist, data, nullptr, pgenlist->head_link);
  } else if (-1 >= pos || pos >= pgenlist->nelements) {
    // Append.
    genlist_link_new(pgenlist, data, pgenlist->tail_link, nullptr);
  } else {
    // Insert before plink.
    struct genlist_link *plink = genlist_link_at_pos(pgenlist, pos);
 
    fc_assert_ret(nullptr != plink);
    genlist_link_new(pgenlist, data, plink->prev, plink);
  }
}
 
void genlist_insert_after(struct genlist *pgenlist, void *data,
                          struct genlist_link *plink)
{
  fc_assert_ret(nullptr != pgenlist);
 
  genlist_link_new(pgenlist, data, plink,
                   nullptr != plink ? plink->next : pgenlist->head_link);
}
 
void genlist_insert_before(struct genlist *pgenlist, void *data,
                           struct genlist_link *plink)
{
  fc_assert_ret(nullptr != pgenlist);
 
  genlist_link_new(pgenlist, data,
                   nullptr != plink ? plink->prev : pgenlist->tail_link,
                   plink);
}
 
void genlist_prepend(struct genlist *pgenlist, void *data)
{
  fc_assert_ret(nullptr != pgenlist);
 
  genlist_link_new(pgenlist, data, nullptr, pgenlist->head_link);
}
 
void genlist_append(struct genlist *pgenlist, void *data)
{
  fc_assert_ret(nullptr != pgenlist);
 
  genlist_link_new(pgenlist, data, pgenlist->tail_link, nullptr);
}
 
struct genlist_link *genlist_search(const struct genlist *pgenlist,
                                    const void *data)
{
  struct genlist_link *plink;
 
  fc_assert_ret_val(nullptr != pgenlist, nullptr);
 
  for (plink = pgenlist->head_link; plink; plink = plink->next) {
    if (plink->dataptr == data) {
      return plink;
    }
  }
 
  return nullptr;
}
 
struct genlist_link *genlist_search_if(const struct genlist *pgenlist,
                                       genlist_cond_fn_t cond_data_func)
{
  fc_assert_ret_val(nullptr != pgenlist, nullptr);
 
  if (nullptr != cond_data_func) {
    struct genlist_link *plink = pgenlist->head_link;
 
    for (; nullptr != plink; plink = plink->next) {
      if (cond_data_func(plink->dataptr)) {
        return plink;
      }
    }
  }
 
  return nullptr;
}
 
void genlist_sort(struct genlist *pgenlist,
                  int (*compar)(const void *, const void *))
{
  const size_t n = genlist_size(pgenlist);
  void **sortbuf;
  struct genlist_link *myiter;
  unsigned int i;
 
  if (n <= 1) {
    return;
  }
 
  sortbuf = new void *[n];
  myiter = genlist_head(pgenlist);
  for (i = 0; i < n; i++, myiter = myiter->next) {
    sortbuf[i] = myiter->dataptr;
  }
 
  qsort(sortbuf, n, sizeof(*sortbuf), compar);
 
  myiter = genlist_head(pgenlist);
  for (i = 0; i < n; i++, myiter = myiter->next) {
    myiter->dataptr = sortbuf[i];
  }
  delete[] sortbuf;
}
 
void genlist_shuffle(struct genlist *pgenlist)
{
  const int n = genlist_size(pgenlist);
  std::vector<void *> sortbuf;
  struct genlist_link *myiter;
  std::vector<int> shuffle;
  int i;
  sortbuf.resize(n);
  shuffle.resize(n);
 
  if (n <= 1) {
    return;
  }
 
  myiter = genlist_head(pgenlist);
  for (i = 0; i < n; i++, myiter = myiter->next) {
    sortbuf[i] = myiter->dataptr;
    // also create the shuffle list
    shuffle[i] = i;
  }
 
  // randomize it
  std::shuffle(shuffle.begin(), shuffle.end(), fc_rand_state());
 
  // create the shuffled list
  myiter = genlist_head(pgenlist);
  for (i = 0; i < n; i++, myiter = myiter->next) {
    myiter->dataptr = sortbuf[shuffle[i]];
  }
}
 
void genlist_reverse(struct genlist *pgenlist)
{
  struct genlist_link *head, *tail;
  int counter;
 
  fc_assert_ret(nullptr != pgenlist);
 
  head = pgenlist->head_link;
  tail = pgenlist->tail_link;
  for (counter = pgenlist->nelements / 2; 0 < counter; counter--) {
    // Swap.
    void *temp = head->dataptr;
    head->dataptr = tail->dataptr;
    tail->dataptr = temp;
 
    head = head->next;
    tail = tail->prev;
  }
}
 
void genlist_allocate_mutex(struct genlist *pgenlist)
{
  pgenlist->mutex.lock();
}
 
void genlist_release_mutex(struct genlist *pgenlist)
{
  pgenlist->mutex.unlock();
}