R
Robin Cole
I'd like a code review if anyone has the time. The code implements a basic
skip list library for generic use. I use the following header for debug
macros:
/*
public.h - Public declarations and macros
*/
#ifndef PUBLIC
#define PUBLIC
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, file, line, var) printf(msg, file, line, var)
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) printf("")
# define call_trace(msg)
#endif
extern unsigned long alloc_count;
#define xmalloc(x) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc(sizeof *(x)))
#define xnmalloc(x, n) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc((n) * sizeof *(x)))
#define xfree(x) (alloc_count = x ? alloc_count - 1 : alloc_count, \
trace("%s - free line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), free(x))
#define deref(x) (assert((x) != NULL), (x))
#define bounds(i, n) (assert((i) >= 0 && (i) < (n)), (i))
#endif
The definitions for public.h are:
/*
public.c - Public definitions.
*/
#include "public.h"
unsigned long alloc_count = 0;
And I make use of the following item header in the test driver:
/*
Copyright (C) 2004 Robin Cole
xitem.h - Application specific data structure contents.
Make changes to this file and xitem.c to specialize.
*/
#ifndef XITEM
#define XITEM
/* Required typedef for compatibility */
typedef struct object xitem;
struct object {
char *item;
};
int compare_xitem(xitem *a, xitem *b);
xitem *make_xitem(char *item);
void destroy_xitem(xitem *old_xitem);
#endif
With xitem defined as:
/*
Copyright (C) 2004 Robin Cole
xitem.c - Application specific definitions for xitem.
*/
#include <assert.h>
#include <string.h>
#include "public.h"
#include "xitem.h"
/*
Compare two xitems. Return -1, 0, +1 if a is less, equal or greater
*/
int
compare_xitem(
xitem *a,
xitem *b
)
{
assert(a != NULL);
assert(b != NULL);
return strcmp(a->item, b->item);
}
/*
Create a new xitem. Return a pointer to the memory block.
*/
xitem *
make_xitem(
char *item
)
{
xitem *new_xitem;
assert(item != NULL);
new_xitem = xmalloc(new_xitem);
call_trace("xmalloc: new_xitem in make_xitem");
if (!new_xitem) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
return NULL;
}
new_xitem->item = xnmalloc(new_xitem->item, strlen(item) + 1);
call_trace("xnmalloc: xitem_item(new_xitem) in make_xitem");
if (!new_xitem->item) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
xfree(new_xitem);
call_trace("xfree: new_xitem in make_xitem");
return NULL;
}
strcpy(new_xitem->item, item);
return new_xitem;
}
/*
Destroy an existing xitem and its contents
*/
void
destroy_xitem(
xitem *old_xitem
)
{
assert(old_xitem != NULL);
xfree(old_xitem->item);
call_trace("xfree: xitem_item(old_xitem) in destroy_xitem");
xfree(old_xitem);
call_trace("xfree: old_xitem in destroy_xitem");
}
Here's the code for the skip list library with a test main as a simple
driver:
/*
Copyright (C) 2004 Robin Cole
- Created (5/14/2004) Robin Cole
- Final touches (5/15/2004) Robin Cole
- Conventionalized and generalized (5/21/2004) Robin Cole
xlist - Skip list demo implementation
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "public.h"
#include "xitem.h"
typedef struct node xnode;
typedef struct list xlist;
static xnode *nil;
struct node {
void *item; /* Client contents */
int height; /* # of next links */
xnode **next; /* Skip links, dynamically allocated */
};
static void verify_xnode(xnode *node);
xnode *make_xnode(void *item, int height);
void destroy_xnode(xnode *node, void (*destroy)(void *old_item));
struct list {
xnode *head; /* Dummy header of skip list */
int size; /* Number of client items */
int max_height; /* Maximum possible skip height
(client defined) */
int (*compare)(void *a, void *b); /* Generic comparison for items */
};
static void verify_xlist(xlist *list);
xlist *make_xlist(int max_height, int (*compare)(void *a, void *b));
void destroy_xlist(xlist *list, void (*destroy)(void *old_item));
int insert_xlist(xlist *list, void *item);
int remove_xlist(xlist *list, void **old_item, void *item);
int search_xlist(xlist *list, void **found_item, void *item);
void display_xlist(xlist *list);
int
main(void)
{
xlist *list;
xitem *item, *save;
int i;
char *a[] = {
/* "a","h","b","g","c","f","d","e","d","a","h" /* Alternating insertion
and duplicates */
"a","b","c","d","e","f","g","h","d","a","h" /* Ascending insertion and
duplicates */
/* "h","g","f","e","d","c","b","a","d","a","h" /* Descending insertion
and duplicates */
};
list = make_xlist(4, compare_xitem);
if (!list) {
fprintf(stderr, "Fatal error: Data structure creation failed\n");
return EXIT_FAILURE;
}
for (i = 0; i < sizeof a / sizeof *a; i++) {
xitem *new_item = make_xitem(a);
if (!new_item) {
fprintf(stderr, "Error creating item\n");
break;
}
if (!insert_xlist(list, new_item)) {
fprintf(stderr, "Error inserting item\n");
destroy_xitem(new_item);
}
display_xlist(list);
printf("\n===============\n");
getchar();
}
item = make_xitem("e");
if (item) {
printf("Search result: %d\n", search_xlist(list, &save, item));
remove_xlist(list, &save, item);
if (save) {
destroy_xitem(save);
}
display_xlist(list);
printf("\n===============\n");
getchar();
printf("Search result: %d\n", search_xlist(list, &save, item));
destroy_xitem(item);
}
destroy_xlist(list, destroy_xitem);
return EXIT_SUCCESS;
}
/*
xnode handlers
*/
/* xnode assertions */
static void verify_xnode(xnode *node)
{
assert(node != NULL);
assert(node->height > 0);
assert(node->next != NULL);
}
/* Allocate and initialize an xnode */
xnode *
make_xnode(
void *item, /* May be null to represent invalid items */
int height
)
{
xnode *node;
assert(height > 0);
node = xmalloc(node);
call_trace("xmalloc: node in make_xnode");
if (!node) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
node->next = xnmalloc(node->next, height);
call_trace("xnmalloc: node->next in make_xnode");
if (!node->next) {
fprintf(stderr, "Memory exhausted\n");
xfree(node);
call_trace("xfree: node in make_xnode");
return NULL;
}
node->item = item;
node->height = height;
while (height--) {
node->next[height] = nil;
}
return node;
}
/* Release memory for an xnode */
void
destroy_xnode(
xnode *node,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
verify_xnode(node);
xfree(node->next);
call_trace("xfree: node->next in destroy_xnode");
if (node->item && destroy) {
destroy(node->item);
}
xfree(node);
call_trace("xfree: node in destroy_xnode");
}
/*
xlist handlers
*/
/* xlist assertions */
static void verify_xlist(xlist *list)
{
assert(list != NULL);
assert(list->head != NULL);
assert(list->max_height > 0);
assert(list->compare != NULL);
}
/* Allocate and initialize an xlist */
xlist *
make_xlist(
int max_height, /* Largest possible height of a node */
int (*compare)(void *a, void *b) /* Function for comparing items */
)
{
xlist *list;
assert(max_height > 0);
assert(compare != NULL);
list = xmalloc(list);
call_trace("xmalloc: list in make_xlist");
if (!list) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
nil = xmalloc(nil);
call_trace("xmalloc: nil in make_xlist");
if (!nil) {
fprintf(stderr, "Memory exhausted\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
nil->item = NULL;
list->head = make_xnode(NULL, max_height);
if (!list->head) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
list->size = 0;
list->head->height = 1;
list->max_height = max_height;
list->compare = compare;
return list;
}
/* Release memory for an xlist */
void
destroy_xlist(
xlist *list,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
xnode *node; /* Traverse the list */
xnode *save; /* Save the link for memory release */
verify_xlist(list);
verify_xnode(list->head);
node = list->head;
while (node != nil) {
save = node->next[0];
destroy_xnode(node, destroy);
node = save;
}
xfree(nil);
call_trace("xfree: nil in destroy_xlist");
xfree(list);
call_trace("xfree: list in destroy_xlist");
}
/* Random height [0..max_height) with probability 1/2 */
static int
random_height(
int max_height /* Exclusive upper bound */
)
{
int height = 1;
while ((double)rand() / RAND_MAX < .5 && height < max_height) {
++height;
}
return height;
}
/* Insert an item into an xlist */
int
insert_xlist(
xlist *list,
void *item /* Item to insert */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
update = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
fprintf(stderr, "Warning: Duplicate detected. List is unchanged\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
else {
int height = random_height(list->max_height);
if (height > list->head->height) {
for (i = list->head->height; i < height; i++) {
update = list->head;
}
list->head->height = height;
}
node = make_xnode(item, height);
if (!node) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
for (i = 0; i < height; i++) {
node->next = update->next;
update->next = node;
}
++list->size;
}
xfree(update);
call_trace("xfree: update in insert_xlist");
return 1;
}
/* Remove an item from an xlist */
int
remove_xlist(
xlist *list,
void **old_item, /* Save the old item for client use */
void *item /* item to search for */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(old_item != NULL);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
update = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
xnode *next; /* Link for shrink step */
for (i = 0; i < list->head->height; i++) {
if (update->next != node) {
break;
}
update->next = node->next;
}
*old_item = node->item;
xfree(node->next);
call_trace("xfree: node->next in remove_xlist");
xfree(node);
call_trace("xfree: node in remove_xlist");
next = list->head->next[list->head->height - 1];
while (list->head->height > 0 && next == nil) {
--list->head->height;
next = list->head->next[list->head->height - 1];
}
--list->size;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 1;
}
else {
*old_item = NULL;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 0;
}
}
/* Locate an item in an xlist */
int
search_xlist(
xlist *list,
void **found_item, /* Save the found item for client use */
void *item /* item to search for */
)
{
xnode *node; /* Traverse the list */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(found_item != NULL);
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
*found_item = node->item;
return 1;
}
else {
*found_item = NULL;
return 0;
}
}
/* Safe print from display_xlist */
static char *
get_item(
xitem *item
)
{
if (!item) {
return "(null)";
}
else {
return item->item;
}
}
/* Display details and structure of an xlist */
void
display_xlist(
xlist *list
)
{
xnode *node;
int i;
verify_xlist(list);
verify_xnode(list->head);
printf("List size: %d\n"
"nil: %p\n"
"Max height: %d\n\n", list->size, (void *)nil, list->max_height);
node = list->head;
while (node != nil) {
printf("Address: %p\n"
"Item: %s\n"
"Height: %d\n"
"Next: ", (void *)node, get_item(node->item), node->height);
for (i = 0; i < node->height; i++) {
printf("[%d]: %p ", i, (void *)node->next);
}
printf("\n\n");
node = node->next[0];
}
}
skip list library for generic use. I use the following header for debug
macros:
/*
public.h - Public declarations and macros
*/
#ifndef PUBLIC
#define PUBLIC
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, file, line, var) printf(msg, file, line, var)
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) printf("")
# define call_trace(msg)
#endif
extern unsigned long alloc_count;
#define xmalloc(x) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc(sizeof *(x)))
#define xnmalloc(x, n) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc((n) * sizeof *(x)))
#define xfree(x) (alloc_count = x ? alloc_count - 1 : alloc_count, \
trace("%s - free line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), free(x))
#define deref(x) (assert((x) != NULL), (x))
#define bounds(i, n) (assert((i) >= 0 && (i) < (n)), (i))
#endif
The definitions for public.h are:
/*
public.c - Public definitions.
*/
#include "public.h"
unsigned long alloc_count = 0;
And I make use of the following item header in the test driver:
/*
Copyright (C) 2004 Robin Cole
xitem.h - Application specific data structure contents.
Make changes to this file and xitem.c to specialize.
*/
#ifndef XITEM
#define XITEM
/* Required typedef for compatibility */
typedef struct object xitem;
struct object {
char *item;
};
int compare_xitem(xitem *a, xitem *b);
xitem *make_xitem(char *item);
void destroy_xitem(xitem *old_xitem);
#endif
With xitem defined as:
/*
Copyright (C) 2004 Robin Cole
xitem.c - Application specific definitions for xitem.
*/
#include <assert.h>
#include <string.h>
#include "public.h"
#include "xitem.h"
/*
Compare two xitems. Return -1, 0, +1 if a is less, equal or greater
*/
int
compare_xitem(
xitem *a,
xitem *b
)
{
assert(a != NULL);
assert(b != NULL);
return strcmp(a->item, b->item);
}
/*
Create a new xitem. Return a pointer to the memory block.
*/
xitem *
make_xitem(
char *item
)
{
xitem *new_xitem;
assert(item != NULL);
new_xitem = xmalloc(new_xitem);
call_trace("xmalloc: new_xitem in make_xitem");
if (!new_xitem) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
return NULL;
}
new_xitem->item = xnmalloc(new_xitem->item, strlen(item) + 1);
call_trace("xnmalloc: xitem_item(new_xitem) in make_xitem");
if (!new_xitem->item) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
xfree(new_xitem);
call_trace("xfree: new_xitem in make_xitem");
return NULL;
}
strcpy(new_xitem->item, item);
return new_xitem;
}
/*
Destroy an existing xitem and its contents
*/
void
destroy_xitem(
xitem *old_xitem
)
{
assert(old_xitem != NULL);
xfree(old_xitem->item);
call_trace("xfree: xitem_item(old_xitem) in destroy_xitem");
xfree(old_xitem);
call_trace("xfree: old_xitem in destroy_xitem");
}
Here's the code for the skip list library with a test main as a simple
driver:
/*
Copyright (C) 2004 Robin Cole
- Created (5/14/2004) Robin Cole
- Final touches (5/15/2004) Robin Cole
- Conventionalized and generalized (5/21/2004) Robin Cole
xlist - Skip list demo implementation
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "public.h"
#include "xitem.h"
typedef struct node xnode;
typedef struct list xlist;
static xnode *nil;
struct node {
void *item; /* Client contents */
int height; /* # of next links */
xnode **next; /* Skip links, dynamically allocated */
};
static void verify_xnode(xnode *node);
xnode *make_xnode(void *item, int height);
void destroy_xnode(xnode *node, void (*destroy)(void *old_item));
struct list {
xnode *head; /* Dummy header of skip list */
int size; /* Number of client items */
int max_height; /* Maximum possible skip height
(client defined) */
int (*compare)(void *a, void *b); /* Generic comparison for items */
};
static void verify_xlist(xlist *list);
xlist *make_xlist(int max_height, int (*compare)(void *a, void *b));
void destroy_xlist(xlist *list, void (*destroy)(void *old_item));
int insert_xlist(xlist *list, void *item);
int remove_xlist(xlist *list, void **old_item, void *item);
int search_xlist(xlist *list, void **found_item, void *item);
void display_xlist(xlist *list);
int
main(void)
{
xlist *list;
xitem *item, *save;
int i;
char *a[] = {
/* "a","h","b","g","c","f","d","e","d","a","h" /* Alternating insertion
and duplicates */
"a","b","c","d","e","f","g","h","d","a","h" /* Ascending insertion and
duplicates */
/* "h","g","f","e","d","c","b","a","d","a","h" /* Descending insertion
and duplicates */
};
list = make_xlist(4, compare_xitem);
if (!list) {
fprintf(stderr, "Fatal error: Data structure creation failed\n");
return EXIT_FAILURE;
}
for (i = 0; i < sizeof a / sizeof *a; i++) {
xitem *new_item = make_xitem(a);
if (!new_item) {
fprintf(stderr, "Error creating item\n");
break;
}
if (!insert_xlist(list, new_item)) {
fprintf(stderr, "Error inserting item\n");
destroy_xitem(new_item);
}
display_xlist(list);
printf("\n===============\n");
getchar();
}
item = make_xitem("e");
if (item) {
printf("Search result: %d\n", search_xlist(list, &save, item));
remove_xlist(list, &save, item);
if (save) {
destroy_xitem(save);
}
display_xlist(list);
printf("\n===============\n");
getchar();
printf("Search result: %d\n", search_xlist(list, &save, item));
destroy_xitem(item);
}
destroy_xlist(list, destroy_xitem);
return EXIT_SUCCESS;
}
/*
xnode handlers
*/
/* xnode assertions */
static void verify_xnode(xnode *node)
{
assert(node != NULL);
assert(node->height > 0);
assert(node->next != NULL);
}
/* Allocate and initialize an xnode */
xnode *
make_xnode(
void *item, /* May be null to represent invalid items */
int height
)
{
xnode *node;
assert(height > 0);
node = xmalloc(node);
call_trace("xmalloc: node in make_xnode");
if (!node) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
node->next = xnmalloc(node->next, height);
call_trace("xnmalloc: node->next in make_xnode");
if (!node->next) {
fprintf(stderr, "Memory exhausted\n");
xfree(node);
call_trace("xfree: node in make_xnode");
return NULL;
}
node->item = item;
node->height = height;
while (height--) {
node->next[height] = nil;
}
return node;
}
/* Release memory for an xnode */
void
destroy_xnode(
xnode *node,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
verify_xnode(node);
xfree(node->next);
call_trace("xfree: node->next in destroy_xnode");
if (node->item && destroy) {
destroy(node->item);
}
xfree(node);
call_trace("xfree: node in destroy_xnode");
}
/*
xlist handlers
*/
/* xlist assertions */
static void verify_xlist(xlist *list)
{
assert(list != NULL);
assert(list->head != NULL);
assert(list->max_height > 0);
assert(list->compare != NULL);
}
/* Allocate and initialize an xlist */
xlist *
make_xlist(
int max_height, /* Largest possible height of a node */
int (*compare)(void *a, void *b) /* Function for comparing items */
)
{
xlist *list;
assert(max_height > 0);
assert(compare != NULL);
list = xmalloc(list);
call_trace("xmalloc: list in make_xlist");
if (!list) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
nil = xmalloc(nil);
call_trace("xmalloc: nil in make_xlist");
if (!nil) {
fprintf(stderr, "Memory exhausted\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
nil->item = NULL;
list->head = make_xnode(NULL, max_height);
if (!list->head) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
list->size = 0;
list->head->height = 1;
list->max_height = max_height;
list->compare = compare;
return list;
}
/* Release memory for an xlist */
void
destroy_xlist(
xlist *list,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
xnode *node; /* Traverse the list */
xnode *save; /* Save the link for memory release */
verify_xlist(list);
verify_xnode(list->head);
node = list->head;
while (node != nil) {
save = node->next[0];
destroy_xnode(node, destroy);
node = save;
}
xfree(nil);
call_trace("xfree: nil in destroy_xlist");
xfree(list);
call_trace("xfree: list in destroy_xlist");
}
/* Random height [0..max_height) with probability 1/2 */
static int
random_height(
int max_height /* Exclusive upper bound */
)
{
int height = 1;
while ((double)rand() / RAND_MAX < .5 && height < max_height) {
++height;
}
return height;
}
/* Insert an item into an xlist */
int
insert_xlist(
xlist *list,
void *item /* Item to insert */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
update = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
fprintf(stderr, "Warning: Duplicate detected. List is unchanged\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
else {
int height = random_height(list->max_height);
if (height > list->head->height) {
for (i = list->head->height; i < height; i++) {
update = list->head;
}
list->head->height = height;
}
node = make_xnode(item, height);
if (!node) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
for (i = 0; i < height; i++) {
node->next = update->next;
update->next = node;
}
++list->size;
}
xfree(update);
call_trace("xfree: update in insert_xlist");
return 1;
}
/* Remove an item from an xlist */
int
remove_xlist(
xlist *list,
void **old_item, /* Save the old item for client use */
void *item /* item to search for */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(old_item != NULL);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
update = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
xnode *next; /* Link for shrink step */
for (i = 0; i < list->head->height; i++) {
if (update->next != node) {
break;
}
update->next = node->next;
}
*old_item = node->item;
xfree(node->next);
call_trace("xfree: node->next in remove_xlist");
xfree(node);
call_trace("xfree: node in remove_xlist");
next = list->head->next[list->head->height - 1];
while (list->head->height > 0 && next == nil) {
--list->head->height;
next = list->head->next[list->head->height - 1];
}
--list->size;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 1;
}
else {
*old_item = NULL;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 0;
}
}
/* Locate an item in an xlist */
int
search_xlist(
xlist *list,
void **found_item, /* Save the found item for client use */
void *item /* item to search for */
)
{
xnode *node; /* Traverse the list */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(found_item != NULL);
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next;
verify_xnode(node);
current_item = node->next->item;
}
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
*found_item = node->item;
return 1;
}
else {
*found_item = NULL;
return 0;
}
}
/* Safe print from display_xlist */
static char *
get_item(
xitem *item
)
{
if (!item) {
return "(null)";
}
else {
return item->item;
}
}
/* Display details and structure of an xlist */
void
display_xlist(
xlist *list
)
{
xnode *node;
int i;
verify_xlist(list);
verify_xnode(list->head);
printf("List size: %d\n"
"nil: %p\n"
"Max height: %d\n\n", list->size, (void *)nil, list->max_height);
node = list->head;
while (node != nil) {
printf("Address: %p\n"
"Item: %s\n"
"Height: %d\n"
"Next: ", (void *)node, get_item(node->item), node->height);
for (i = 0; i < node->height; i++) {
printf("[%d]: %p ", i, (void *)node->next);
}
printf("\n\n");
node = node->next[0];
}
}