/* 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);
}
| Vorgefundene Kodierung: UTF-8 | 0
|