|
//////////////////////////////////////////////////////////////
// lnklst.c
// definition of queue functions
#include <stdlib.h>
#include "lnklst.h"
struct basic_nod_t {
struct basic_nod_t *next;
};
static __inline struct basic_nod_t *find_prev_node(struct basic_nod_t *head, struct basic_nod_t *nod)
{
struct basic_nod_t *n = head;
if(nod == NULL)
return NULL;
do
{
if(n->next == nod)
return n;
n = n->next;
} while(n && (n != nod));
return NULL;
}
void add_node_to(void **head, void *node, void *to, int before_or_after)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *n = (struct basic_nod_t*)node;
struct basic_nod_t *tt = (struct basic_nod_t*)to;
if(node == NULL)
return;
if(*h == NULL)
{
*h = n;
n->next = n;
}
else if(before_or_after == 0)
{
//move the 'moved' node to the place before 'to'
if(tt == NULL)
tt = *h;
if(*h == tt)
*h = n;
n->next = tt;
find_prev_node(*h, tt)->next = n;
}
else if(before_or_after == 1)
{
//move the 'moved' node to the place after 'to'
if(tt == NULL)
tt = find_prev_node(*h,*h);
n->next = tt->next;
tt->next = n;
}
}
void add_node(void **head, void *node)
{
add_node_to(head, node, NULL, 1);
}
void del_node(void **head, void *node)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *n = (struct basic_nod_t*)node;
if(head == NULL)
return;
if(*h == NULL)
return;
if(n == *h)
{
if(n == n->next)
{
*h = NULL;
return;
}
*h = n->next;
}
{
struct basic_nod_t *tmp = find_prev_node(*h, n);
if(tmp)
tmp->next = n->next;
}
}
void move_node(void **head, void *moved, void *to, int before_or_after)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *m = (struct basic_nod_t*)moved;
struct basic_nod_t *tt = (struct basic_nod_t*)to;
if( (h == NULL) || (*h == NULL) || (m == tt))
return;
del_node(head, moved);
add_node_to(head, moved, to, before_or_after);
}
void sort_list(void **head, CMP_FUNC nodcmp)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *nod1 = *h;
struct basic_nod_t *nod2 = nod1->next;
int swaped = 1;
if(nod1 == nod1->next)
return;
while(swaped)
{
swaped = 0;
while(1)
{
if((*nodcmp)(nod1, nod2) > 0)
{
move_node(head, nod1, nod2, 1);
nod2 = nod1->next;
swaped = 1;
}
else
{
nod1 = nod2;
nod2 = nod2->next;
}
if(nod2 == *h)
{
nod1 = *h;
nod2 = nod1->next;
break;
}
}
}
}
void add_node_sorted(void **head, void *node, CMP_FUNC nodcmp)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *n = (struct basic_nod_t*)node;
struct basic_nod_t *tmp = *h;
if((*nodcmp)(n, *h) < 0)
{
add_node_to(head, node, *h, 0);
return;
}
if((*nodcmp)(n, find_prev_node(*head,*h)) >= 0)
{
add_node(head, node);
return;
}
do
{
if((*nodcmp)(n, tmp) < 0)
{
add_node_to(head, node, tmp, 0);
break;
}
else
tmp = tmp->next;
} while(tmp && (tmp != *h));
}
int get_node_count(void **head)
{
struct basic_nod_t **h = (struct basic_nod_t**)head;
struct basic_nod_t *tmp = *h;
int count = 0;
if(h == NULL)
return 0;
if(*h == NULL)
return 0;
do {
tmp = tmp->next;
count++;
} while(tmp && (tmp != *h));
return count;
}
|
