Source file: /~heha/hs/gputils64-210929.zip/libgputils/gplist.cpp

/* Double linked list support
   Copyright 2016	Molnár Károly
*/

#include "stdhdr.h"
#include "libgputils.h"

#define LIST_INVALID_ID                 0

typedef struct gp_node {
  GPNodeHeader(struct gp_node);
} gp_node_t;

typedef struct gp_list {
  GPListHeader(struct gp_node);
} gp_list_t;

static unsigned list_serial_id = 1;

/*------------------------------------------------------------------------------------------------*/

FUNC(void*) gp_list_node_new(size_t Item_size) {
  if (Item_size == 0) {
    fprintf(stderr, "%s(%u) -- Item_size is 0.\n", __FILE__, __LINE__);
    exit(1);
  }

  return new char[Item_size];
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void) gp_list_node_free(void *List, void *Node) {
  gp_list_t *l;

  if ((List == NULL) || (Node == NULL)) {
    return;
  }

  l = (gp_list_t *)List;

  if (l->node_del) {
    (*l->node_del)(Node);
  }
  else {
    free(Node);
  }
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void*) gp_list_node_append(void *List, void *Node) {
  gp_list_t *l;
  gp_node_t *n;

  if ((List == NULL) || (Node == NULL)) {
    return NULL;
  }

  l = (gp_list_t *)List;

  if (l->serial_id == LIST_INVALID_ID) {
    l->serial_id = list_serial_id++;
  }

  n = (gp_node_t *)Node;
  n->prev = l->last;
  n->next = NULL;

  if (l->first == NULL) {
    /* The list is empty. */
    l->first = n;
    l->curr  = n;
  }
  else {
    /* Append the pnew node to the end of the list. */
    l->last->next = n;
  }

  l->last = n;
  n->list_id = l->serial_id;
  (l->num_nodes)++;

  return Node;
}

/*------------------------------------------------------------------------------------------------*/

void *
gp_list_node_insert_after(void *List, void *Node, void *Node_new)
{
  gp_list_t *l;
  gp_node_t *n;
  gp_node_t *pnew;
  gp_node_t *next;

  if ((List == NULL) || (Node == NULL) || (Node_new == NULL)) {
    return NULL;
  }

  l   = (gp_list_t *)List;
  n   = (gp_node_t *)Node;
  pnew = (gp_node_t *)Node_new;

  next      = n->next;
  pnew->prev = n;
  pnew->next = next;

  if (l->last == n) {
    /* This is last node of the list. */
    l->last = pnew;
  }

  if (next) {
    /* The "next" node exists. */
    next->prev = pnew;
  }

  n->next = pnew;
  pnew->list_id = l->serial_id;
  (l->num_nodes)++;

  return Node_new;
}

/*------------------------------------------------------------------------------------------------*/

void *
gp_list_node_insert_before(void *List, void *Node, void *Node_new)
{
  gp_list_t *l;
  gp_node_t *n;
  gp_node_t *pnew;
  gp_node_t *prev;

  if ((List == NULL) || (Node == NULL) || (Node_new == NULL)) {
    return NULL;
  }

  l   = (gp_list_t *)List;
  n   = (gp_node_t *)Node;
  pnew = (gp_node_t *)Node_new;

  prev      = n->prev;
  pnew->prev = prev;
  pnew->next = n;

  if (l->first == n) {
    /* This is first node of the list. */
    l->first = pnew;
    l->curr  = pnew;
  }

  if (prev) {
    /* The "prev" node exists. */
    prev->next = pnew;
  }

  n->prev = pnew;
  pnew->list_id = l->serial_id;
  (l->num_nodes)++;

  return Node_new;
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void*) gp_list_node_remove(void *List, void *Node) {
  if (!List || !Node) return NULL;

  gp_list_t*l = (gp_list_t *)List;
  gp_node_t*n = (gp_node_t *)Node;

  if (n->list_id != l->serial_id) {
    gp_error("The node{%u} does not belong to this list{%u}.", n->list_id, l->serial_id);
    assert(0);
  }

  if (l->first == n) {
    /* This is first node of the list, the next will be the first. */
    l->first = n->next;
    l->curr  = n->next;
  }else{
    /* The previous node connects to next. */
    n->prev->next = n->next;
  }

  if (l->last == n) {
    /* This is last node of the list, the previous will be the last. */
    l->last = n->prev;
  }else{
    /* The next node connects to previous. */
    n->next->prev = n->prev;
  }

  n->prev    = NULL;
  n->next    = NULL;
  n->list_id = 0;
  (l->num_nodes)--;

  return Node;
}

/*------------------------------------------------------------------------------------------------*/

void* gp_list_node_move(void *Dst, void *Src, void *Node) {
  return gp_list_node_append(Dst, gp_list_node_remove(Src, Node));
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void) gp_list_node_delete(void *List, void *Node) {
  gp_list_node_free(List, gp_list_node_remove(List, Node));
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void) gp_list_set_delete_node_func(void *List, gp_node_del_t Function) {
  gp_list_t *l;

  if (List == NULL) {
    return;
  }

  l = (gp_list_t *)List;
  l->node_del = Function;
}

/*------------------------------------------------------------------------------------------------*/

void** gp_list_make_block(void *List, size_t Num_nodes, size_t Item_size) {
  gp_list_t     *l;
  gp_node_t    **ptr_array;
  unsigned   id;
  size_t         i;

  if ((List == NULL) || (Num_nodes == 0) || (Item_size == 0)) {
    return NULL;
  }

  l = (gp_list_t *)List;

  if (l->first) {
    gp_error("%s(%u) -- The block list already exists, can not be created again.", __FILE__, __LINE__);
    assert(0);
  }

  id = list_serial_id++;
  ptr_array = new gp_node_t*[Num_nodes];
  l->num_nodes = Num_nodes;
  l->serial_id = id;

  for (i = 0; i < Num_nodes; i++) {
    ptr_array[i] = (gp_node_t *)gp_list_node_new(Item_size);
    ptr_array[i]->list_id = id;
  }

  /* Do not process the last item. */
  Num_nodes--;

  /* Initialize the pointers to create the linked list. */
  for (i = 0; i < Num_nodes; i++) {
    ptr_array[i + 1]->prev = ptr_array[i];
    ptr_array[i]->next     = ptr_array[i + 1];
  }

  /* The first->prev and last->next values is already NULL. (calloc) */

  l->first = ptr_array[0];
  l->curr  = ptr_array[0];
  l->last  = ptr_array[Num_nodes];

  return (void **)ptr_array;
}

/*------------------------------------------------------------------------------------------------*/

static void _fresh_list_ids(gp_list_t *List, gp_node_t *Start_node) {
  gp_node_t    *node;
  unsigned  id;

  id   = List->serial_id;
  node = (Start_node) ? Start_node : List->first;
  while (node) {
    node->list_id = id;
    node = node->next;
  }
}

/*------------------------------------------------------------------------------------------------*/

void gp_list_move(void *Dst, void *Src) {
  gp_list_t *d;
  gp_list_t *s;

  if ((Dst == NULL) || (Src == NULL)) {
    return;
  }

  d = (gp_list_t *)Dst;
  s = (gp_list_t *)Src;

  if (s->first) {
    /* Append the nodes from the "Src" list to the "Dst". */
    if (s->num_nodes == 0) {
      fprintf(stderr, "%s(%u) -- Src->num_nodes: %" SIZE_FMTu, __FILE__, __LINE__, s->num_nodes);
      assert(0);
    }

    if (d->first == NULL) {
      if (d->num_nodes > 0) {
        fprintf(stderr, "%s(%u) -- Dst->num_nodes: %" SIZE_FMTu, __FILE__, __LINE__, d->num_nodes);
        assert(0);
      }

      d->serial_id = list_serial_id++;
      d->first     = s->first;
      d->curr      = s->first;
    }
    else {
      if (d->num_nodes == 0) {
        fprintf(stderr, "%s(%u) -- Dst->num_nodes: %" SIZE_FMTu, __FILE__, __LINE__, d->num_nodes);
        assert(0);
      }

      d->last->next  = s->first;
      s->first->prev = d->last;
    }

    d->last       = s->last;
    d->num_nodes += s->num_nodes;
    _fresh_list_ids(d, s->first);

    /* In the "Src" list will not stay reference onto any node. */
    gp_list_clear(Src);
  }
}

/*------------------------------------------------------------------------------------------------*/

void*gp_list_clone_list(const void *List, int (_cdecl Cmp_func)(const void *, const void *)) {
  const gp_list_t  *l;
  size_t            n_nodes;
  size_t            i;
  gp_node_t        *node;
  gp_node_t       **array;

  if ((List == NULL) || (Cmp_func == NULL)) {
    return NULL;
  }

  l = (const gp_list_t *)List;
  n_nodes = l->num_nodes;

  if (n_nodes == 0) {
    return NULL;
  }

  array = new gp_node_t*[n_nodes];
  node  = l->first;
  i     = 0;
  while (node) {
    array[i] = node;
    ++i;
    assert(i <= n_nodes);
    node = node->next;
  }

  if (n_nodes > 1) {
    qsort(array, n_nodes, sizeof(gp_node_t *), Cmp_func);
  }

  return array;
}

/*------------------------------------------------------------------------------------------------*/

void
gp_list_reset(void *List)
{
  gp_list_t *l;

  if (List == NULL) {
    return;
  }

  l = (gp_list_t *)List;
  l->curr = l->first;
}

/*------------------------------------------------------------------------------------------------*/

void
gp_list_set_access_point(void *List, void *Node)
{
  gp_list_t *l;
  gp_node_t *n;

  if (List == NULL) {
    return;
  }

  l = (gp_list_t *)List;
  n = (gp_node_t *)Node;

  if (n->list_id != l->serial_id) {
    gp_error("The node{%u} does not belong to this list{%u}.", n->list_id, l->serial_id);
    assert(0);
  }

  l->curr = n;
}

/*------------------------------------------------------------------------------------------------*/

void
gp_list_clear(void *List)
{
  if (List == NULL) {
    return;
  }

  memset(List, 0, sizeof(gp_list_t));
}

/*------------------------------------------------------------------------------------------------*/

FUNC(void) gp_list_delete(void *List) {
  gp_list_t *l;
  gp_node_t *node;
  gp_node_t *next;

  if (!List) return;

  l = (gp_list_t *)List;

  node = l->first;
  while (node) {
    next = node->next;
    gp_list_node_delete(List, node);
    node = next;
  }

  gp_list_clear(List);
}
Detected encoding: UTF-80