/* This file is part of PODIFF.
Copyright (C) 2011-2020 Sergey Poznyakoff
PODIFF 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, or (at your option)
any later version.
PODIFF is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this PODIFF. If not, see . */
#include
#include
#include "podiff.h"
struct list *
list_create()
{
struct list *lp = emalloc(sizeof(*lp));
memset(lp, 0, sizeof(*lp));
return lp;
}
size_t
list_size(struct list *lp)
{
return lp ? lp->count : 0;
}
void
list_insert_entry(struct list *lp,
struct list_entry *anchor,
struct list_entry *ent, int before)
{
struct list_entry *p;
if (!anchor) {
ent->prev = NULL;
ent->next = lp->head;
if (lp->head)
lp->head->prev = ent;
else
lp->tail = ent;
lp->head = ent;
lp->count++;
return;
}
if (before) {
list_insert_entry(lp, anchor->prev, ent, 0);
return;
}
ent->prev = anchor;
if (p = anchor->next)
p->prev = ent;
else
lp->tail = ent;
ent->next = p;
anchor->next = ent;
lp->count++;
}
void
list_remove_entry(struct list *lp, struct list_entry *ent)
{
struct list_entry *p;
if (p = ent->prev)
p->next = ent->next;
else
lp->head = ent->next;
if (p = ent->next)
p->prev = ent->prev;
else
lp->tail = ent->prev;
ent->next = ent->prev = NULL;
lp->count--;
}
void
list_append(struct list *lp, void *val)
{
struct list_entry *ep = emalloc(sizeof(*ep));
ep->data = val;
list_insert_entry(lp, lp->tail, ep, 0);
}
void
list_add(struct list *dst, struct list *src)
{
if (!src->head)
return;
src->head->prev = dst->tail;
if (dst->tail)
dst->tail->next = src->head;
else
dst->head = src->head;
dst->tail = src->tail;
dst->count += src->count;
src->head = src->tail = NULL;
src->count = 0;
}
void
list_push(struct list *lp, void *val)
{
struct list_entry *ep = emalloc(sizeof(*ep));
ep->data = val;
list_insert_entry(lp, NULL, ep, 0);
}
void *
list_pop(struct list *lp)
{
void *data;
struct list_entry *ep = lp->head;
if (ep) {
data = ep->data;
list_remove_entry(lp, ep);
free(ep);
} else
data = NULL;
return data;
}
void *
list_remove_tail(struct list *lp)
{
void *data;
struct list_entry *ep;
if (!lp->tail)
return NULL;
ep = lp->tail;
data = lp->tail->data;
list_remove_entry(lp, ep);
free(ep);
return data;
}
void
list_clear(struct list *lp)
{
struct list_entry *ep = lp->head;
while (ep) {
struct list_entry *next = ep->next;
if (lp->free_entry)
lp->free_entry(ep->data);
free(ep);
ep = next;
}
lp->head = lp->tail = NULL;
lp->count = 0;
}
void
list_free(struct list *lp)
{
if (lp) {
list_clear(lp);
free(lp);
}
}
static int
_ptrcmp(const void *a, const void *b)
{
return a != b;
}
void *
list_locate(struct list *lp, void *data)
{
struct list_entry *ep;
int (*cmp)(const void *, const void *) = lp->cmp ? lp->cmp : _ptrcmp;
for (ep = lp->head; ep; ep = ep->next) {
if (cmp(ep->data, data) == 0)
return ep->data;
}
return NULL;
}
void *
list_index(struct list *lp, size_t idx)
{
struct list_entry *ep;
for (ep = lp->head; ep && idx; ep = ep->next, idx--)
;
return ep ? ep->data : NULL;
}
void
list_join(struct list *a, struct list *b)
{
if (!b->head)
return;
b->head->prev = a->tail;
if (a->tail)
a->tail->next = b->head;
else
a->head = b->head;
a->tail = b->tail;
}
void
list_qsort(struct list *list)
{
struct list_entry *cur, *middle;
struct list high_list, low_list;
int rc;
if (!list->head)
return;
cur = list->head;
do {
cur = cur->next;
if (!cur)
return;
} while ((rc = list->cmp(list->head->data, cur->data)) == 0);
/* Select the lower of the two as the middle value */
middle = (rc > 0) ? cur : list->head;
/* Split into two sublists */
low_list.head = low_list.tail = NULL;
high_list.head = high_list.tail = NULL;
low_list.free_entry = high_list.free_entry = NULL;
low_list.cmp = high_list.cmp = list->cmp;
for (cur = list->head; cur; ) {
struct list_entry *next = cur->next;
cur->next = NULL;
if (list->cmp(middle->data, cur->data) < 0)
list_insert_entry(&high_list, high_list.tail,
cur, 0);
else
list_insert_entry(&low_list, low_list.tail,
cur, 0);
cur = next;
}
/* Sort both sublists recursively */
list_qsort(&low_list);
list_qsort(&high_list);
/* Join both lists in order */
list_join(&low_list, &high_list);
/* Return the resulting list */
list->head = low_list.head;
list->tail = low_list.tail;
}