/* dlist.c - linked list routines by Harry Sintonen
faster swapnodes() by Jamie van den Berge
mergesortlist() by Fabio Alemagna
dlist.c and dlist.h are public domain as long name of all contributers
still appear in both files.
*/
/* HISTORY
2107A1 - cleaned up the source & the header file. placed in public
domain. - Harry
1012A1 - added qsortlist() routine. - Harry
2204A3 - added faster swapnodes() by Jamie van den Berge
. - Harry
1512A3 - fixed LISTEMPTY macro. - Harry
1703A4 - added mergesortlist by Fabio Alemagna
. - Harry
0610A6 - fixed LISTEMPTY macro to avoid type-punned ptr warning.
thx Rennex. - Harry
NOTES:
API design was very stronly influenced by AmigaOS exec list routines,
since I am very familiar with them. No documentation is included, the
use is too obvious (at least for me, oh well... ;-) - Harry
*/
#include
#include "dlist.h"
#ifdef __cplusplus
extern "C" {
#endif
void newlist(
struct dlist *l)
{
l->l_head = (struct dnode *) &l->l_tail;
l->l_tail = NULL;
l->l_tailpred = (struct dnode *) &l->l_head;
}
void addhead(
struct dlist *l,
struct dnode *n)
{
n->n_succ = l->l_head;
n->n_pred = (struct dnode *) &l->l_head;
l->l_head->n_pred = n;
l->l_head = n;
}
void addtail(
struct dlist *l,
struct dnode *n)
{
n->n_succ = (struct dnode *) &l->l_tail;
n->n_pred = l->l_tailpred;
l->l_tailpred->n_succ = n;
l->l_tailpred = n;
}
void insert(
struct dlist *l,
struct dnode *n,
struct dnode *afterof)
{
if (afterof == NULL)
{
addhead(l, n);
return;
}
n->n_pred = afterof;
n->n_succ = afterof->n_succ;
afterof->n_succ = n;
n->n_succ->n_pred = n;
}
struct dnode *remhead(
struct dlist *l)
{
struct dnode *n = NULL;
/* anything to remove?
*/
if (!LISTEMPTY(l))
{
n = l->l_head;
n->n_succ->n_pred = n->n_pred;
n->n_pred->n_succ = n->n_succ;
}
return n;
}
struct dnode *remtail(
struct dlist *l)
{
struct dnode *n = NULL;
/* anything to remove?
*/
if (!LISTEMPTY(l))
{
n = l->l_tailpred;
n->n_succ->n_pred = n->n_pred;
n->n_pred->n_succ = n->n_succ;
}
return n;
}
void remnode(
struct dnode *n)
{
n->n_succ->n_pred = n->n_pred;
n->n_pred->n_succ = n->n_succ;
}
struct dnode *findnode(
struct dlist *l,
struct dnode *n)
{
struct dnode *worknode;
worknode = (struct dnode *) &l->l_head;
while ((worknode = worknode->n_succ))
{
if (worknode == n)
{
return n;
}
}
return NULL;
}
struct dnode *callfornode(
struct dlist *l,
LISTFUNCPTR func,
void *userdata,
unsigned long int flags)
{
struct dnode *worknode, *nextnode;
if (flags & CFNF_BACKWARDS)
{
worknode = l->l_tailpred;
while ((nextnode = worknode->n_pred))
{
if (func(worknode, userdata))
{
return worknode;
}
worknode = nextnode;
}
}
else
{
worknode = l->l_head;
while ((nextnode = worknode->n_succ))
{
if (func(worknode, userdata))
{
return worknode;
}
worknode = nextnode;
}
}
return NULL;
}
#if 1
static
void swapnodes(
struct dnode *b,
struct dnode *y)
{
/*
// Fast linked list node swap - by Jamie van den Berge
//
// Using just 10 assignments, 14 ptr dereferences and 2 pointers on stack.
// Public domain so long as my name remains in this function.
*/
struct dnode *x, *z;
/* give the nodes before/after y a name... */
x = y->n_pred;
z = y->n_succ;
/* now let x and z believe they got b inbetween */
x->n_succ = b;
z->n_pred = b;
/* let y think it has the nodes before/after b (named a and c) around it */
y->n_succ = b->n_succ;
y->n_pred = b->n_pred;
/* now let b believe it's between x and y */
b->n_succ = z;
b->n_pred = x;
/* which leaves us to make a and c believe they got y inbetween, however:
we didnt store the pointers to a and c! luckily we can reference
them from node y though.. */
y->n_pred->n_succ = y;
y->n_succ->n_pred = y;
}
#else
static
void swapnodes(
struct dnode *a,
struct dnode *b)
{
struct dnode t;
t.n_succ = (a->n_succ == b) ? a : a->n_succ;
t.n_pred = (a->n_pred == b) ? a : a->n_pred;
a->n_succ->n_pred = b;
a->n_succ = (b->n_succ == a) ? b : b->n_succ;
a->n_pred->n_succ = b;
a->n_pred = (b->n_pred == a) ? b : b->n_pred;
b->n_succ->n_pred = a;
b->n_succ = t.n_succ;
b->n_pred->n_succ = a;
b->n_pred = t.n_pred;
}
#endif
void qsortlist(
struct dlist *l,
struct dnode *basenode,
unsigned long int nmemb,
COMPARFUNCPTR compar)
{
struct dnode *worknode;
struct dnode *leftnode, *rightnode, *middlenode = NULL;
unsigned long int cnt, left, right;
/* NULL basenode mean list head
*/
if (basenode == NULL)
{
basenode = l->l_head;
}
#ifdef USE_QSL_ALL
/* calculate number of nodes from base position to tail of the list
*/
for (cnt = 0, worknode = basenode; worknode = worknode->n_succ;) { cnt++; }
/* adjust nmemb, if necessary
*/
if (nmemb == QSL_ALL || nmemb > cnt)
{
nmemb = cnt;
}
#endif
while (nmemb > 1)
{
left = 0; leftnode = basenode; /* left node */
right = nmemb - 1;
for (cnt = 0, worknode = basenode; ; cnt++, worknode = worknode->n_succ)
{
if (cnt == right / 2) /* middle node ((left + right) / 2) */
{
middlenode = worknode;
}
else if (cnt == right) /* right node */
{
rightnode = worknode;
break;
}
}
for (;;)
{
while ((*compar)(middlenode, leftnode) > 0)
{
/* look for one >= middle
*/
left++; leftnode = leftnode->n_succ;
}
while ((*compar)(middlenode, rightnode) < 0)
{
/* look for one <= middle
*/
right--; rightnode = rightnode->n_pred;
}
if (left >= right)
{
/* we found no pair
*/
break;
}
/* Swap leftnode & rightnode in the list
*/
swapnodes(leftnode, rightnode);
/* Swap leftnode & rightnode pointers
*/
worknode = leftnode;
leftnode = rightnode;
rightnode = worknode;
if (basenode == leftnode || basenode == rightnode)
{
/* Recalculate basenode address! (IMPORTANT!)
*/
basenode = (basenode == leftnode) ? rightnode : leftnode;
}
/* Note: automagically keep track of middle node
*/
/* These two are already sorted
*/
left++; leftnode = leftnode->n_succ;
right--; rightnode = rightnode->n_pred;
}
/* left points to first element of right interval now (right to last of left)
*/
right++;
for (cnt = right, worknode = basenode; cnt--; worknode = worknode->n_succ) {}
/* do recursion on smaller interval and iteration on larger one,
avoids recursion to save stack storage & avoid recursion overhead
*/
if (right < nmemb - right)
{
qsortlist(l, basenode, right, compar);
basenode = worknode;
nmemb -= right;
}
else
{
qsortlist(l, worknode, nmemb - right, compar);
nmemb = right;
}
}
}
static inline
struct dnode *mslmerge(
struct dnode *l,
COMPARFUNCPTR compar)
{
struct dnode *l1, *last_l1, *l2, *last_l2, *next_l;
struct dnode *first = NULL, **first_ptr, **last_ptr = &first;
l1 = l;
/* l1 points to the 1st sublist, l2 points to the 2nd.
Should there be no l2, we don't need to do anything special, as
l1 will already be linked with the rest of the list AND it won't
obviously need to be merged with another list.
*/
while (l1 && (l2 = (last_l1 = l1->n_pred)->n_succ))
{
last_l2 = l2->n_pred;
next_l = last_l2->n_succ;
/* This will make the below loop slightly faster, since there will only
be tests against the constant NULL.
*/
last_l1->n_succ = NULL;
last_l2->n_succ = NULL;
/* Pointer to the beginning of the merged sublist
*/
first_ptr = last_ptr;
do
{
if ((*compar)(l1, l2) < 0)
{
l1->n_pred = (struct dnode *)((char *)last_ptr -
offsetof(struct dnode, n_succ));
*last_ptr = l1;
l1 = l1->n_succ;
}
else
{
l2->n_pred = (struct dnode *)((char *)last_ptr -
offsetof(struct dnode, n_succ));
*last_ptr = l2;
l2 = l2->n_succ;
}
last_ptr = &(*last_ptr)->n_succ;
} while (l1 && l2);
if (l1)
{
l1->n_pred = (struct dnode *)((char *)last_ptr -
offsetof(struct dnode, n_succ));
*last_ptr = l1;
(*first_ptr)->n_pred = last_l1;
last_ptr = &last_l1->n_succ;
}
else if (l2)
{
l2->n_pred = (struct dnode *)((char *)last_ptr -
offsetof(struct dnode, n_succ));
*last_ptr = l2;
(*first_ptr)->n_pred = last_l2;
last_ptr = &last_l2->n_succ;
}
else
{
(*first_ptr)->n_pred = (struct dnode *)((char *)last_ptr -
offsetof(struct dnode, n_succ));
}
l1 = *last_ptr = next_l;
}
return first;
}
void mergesortlist(
struct dlist *l,
COMPARFUNCPTR compar)
{
struct dnode *head, *tail;
struct dnode *l1, *l2, *first, **last_ptr;
if (!l)
return;
head = l->l_head;
tail = l->l_tailpred;
if (tail == (struct dnode *) l || head == tail)
return;
tail->n_succ = NULL;
last_ptr = &first;
/* The mslmerge() function requires a list of sublists, each of which
has to be a circular list. Since the given list doesn't have these
properties, we need to divide the sorting algorithm in 2 parts:
1) we first go trough the list once, making every node's Pred pointer
point to the node itself, so that the given list of n nodes is
transformed in a list of n circular sublists. Here we do the merging
"manually", without the help of the mslmerge() function, as we have
to deal with just couples of nodes, thus we can do some extra
optimization.
2) We then feed the resulting list to the mslmerge() function, as many
times as it takes to the mslmerge() function to give back just one
circular list, rather than a list of circular sublists: that will be
our sorted list.
*/
/* This is the first part.
*/
l1 = head;
l2 = l1->n_succ;
do
{
/* It can happen that the 2 nodes are already in the right,
order and thus we only need to make a circular list out
of them, or their order needs to be reversed, but
in either case, the below line is necessary, because:
1) In the first case, it serves to build the
circular list.
2) In the 2nd case, it does hald the job of
reversing the order of the nodes (the
other half is done inside the if block).
*/
l1->n_pred = l2;
if ((*compar)(l1, l2) >= 0)
{
/* l2 comes before l1, so rearrange them and
make a circular list out of them.
*/
l1->n_succ = l2->n_succ;
l2->n_succ = l1;
l2->n_pred = l1;
l1 = l2;
}
*last_ptr = l1;
last_ptr = &l1->n_pred->n_succ;
l1 = *last_ptr;
} while (l1 && (l2 = l1->n_succ));
/* An orphan node? Add it at the end of the list of sublists and
make a circular list out of it.
*/
if (l1)
{
l1->n_pred = l1;
*last_ptr = l1;
}
/* And this is the 2nd part.
*/
while (first->n_pred->n_succ)
first = mslmerge(first, compar);
/* Now we fix up the list header.
*/
l->l_head = first;
l->l_tailpred = first->n_pred;
first->n_pred->n_succ = (struct dnode *)&l->l_tail;
first->n_pred = (struct dnode *)&l->l_head;
}
#ifdef __cplusplus
} // extern "C"
#endif