Code Review (Skip List)

[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[i]);
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[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->item;
}
update[i] = 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[i] = 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[i] = update[i]->next[i];
update[i]->next[i] = 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[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->item;
}
update[i] = 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[i]->next[i] != node) {
break;
}
update[i]->next[i] = node->next[i];
}
*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[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->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[i]);
}
printf("\n\n");
node = node->next[0];
}
}

[Phlip]

Robin Cole wrote:

#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

I got this far. Try:

#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) // nada
# define call_trace(msg) // nada
#endif

You can pass VERBOSE on the compiler's command line; check with your
implementation how to. The macro NDEBUG might be available.

Note that "%s(%d): " msg requires msg to be a string literal, because it
uses literal concatenation.

However, as you are learning, you should see if C++ and its standard library
can provide cleaner code.

--
Phlip
http://industrialxp.org/community/bi...UserInterfaces

[Robin Cole]

"Phlip" <ph*******@yahoo.com> wrote

I got this far. Try:

#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)
That's a little obscure for my tastes. I like things to be immediately
obvious for my readers.
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) // nada
The printf was there from a previous library. I can't recall how I used it
at the moment, but replacing the printf with nothing resulted in a
compile-time error.
# define call_trace(msg) // nada
#endif

You can pass VERBOSE on the compiler's command line; check with your
implementation how to. The macro NDEBUG might be available.
I chose not to define VERBOSE on the command line for my test runs. I'm
fully aware of both NDEBUG and compiler switches that let you define names
from the command line, but thanks nonetheless.

Note that "%s(%d): " msg requires msg to be a string literal, because it
uses literal concatenation.

However, as you are learning, you should see if C++ and its standard library can provide cleaner code.

And slower code. I've written skip lists before using C++'s standard
container classes for "cleaner code" that were easily half as fast as the
equivalent hand rolled implementation.

[Mark McIntyre]

On Mon, 24 May 2004 18:12:11 GMT, in comp.lang.c , "Robin Cole"
<ha*********@hotmail.com> wrote:

"Phlip" <ph*******@yahoo.com> wrote

I got this far. Try:

#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)

That's a little obscure for my tastes. I like things to be immediately
obvious for my readers.

That /is/ immediately obvious to anyone who knows C (if one sorts out the
missing printf specifiers).

The original version either requires to you to supply a "msg" that is a
format string, or else it invokes undefined behaviour.

However, as you are learning, you should see if C++ and its standard library
can provide cleaner code.

And slower code. I've written skip lists before using C++'s standard
container classes for "cleaner code" that were easily half as fast as the
equivalent hand rolled implementation.

Then you either
a) had a bad STL implementation (possiblel or
b) you coded it badly (likely).

I find C++ to be just as fast as C for the vast majority of uses.
I just cant write it well as fast. :-(

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[Andrey Tarasevich]

Robin Cole wrote:

...
/* 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;
}
...

Firstly, this code is less inefficient than it could be. There's no need
to involve floating point calculations here. The better way to do the
same thing would be

...
while (rand() < RAND_MAX / 2 && height < max_height)
...

Secondly, the experiment shows that for majority of generic practical
applications you can achieve much better performance (both insertion and
search) with p=3-based distribution (66%, 22%, 7.3%, ...) than with
p=2-based distributions (50%, 25%, 12.5%, ...). You might want to
experiment with different values, but I would recommend you to stick
with p=3:

...
while (rand() < RAND_MAX / 3 && height < max_height)
...

(If you have the original article on the skip lists, you can find there
some theoretical considerations related to the choice of value of 'p'.)
Once again - try this and see what happens in your case.

Thirdly, and most importantly, the entire approach that you use in order
to convert an uniformly distributed pseudo-random generator ('rand()')
into the one used by skip list is grossly inefficient. The method that
you use is good as an illustration in a scientific paper, but it is not
used in practice. You can significantly improve the performance of your
skip list code if you stop calling that 'rand()' function on every
iteration of the inner cycle. In this context it is rather expensive.
Instead, treat the result of the 'rand()' function as a sequence of bits
- a bit stream. In this case the number of the first, say, zero bit in
the stream can be used as the new random height value. This will give
you the necessary p=2-based distribution of the heights. (BTW, this
method is also mentioned in the original skip list paper, if you read it
carefully). That's how it is normally done in practice.

For example, for p=2 the 'random_height' code might look like this

static int random_height( int max_height )
{
static int bit_stream;
static int requests_left = 0;
int height = 1;

while (height < max_height)
{
unsigned char bit;

if (requests_left == 0)
{
bit_stream = rand();
requests_left = N; /* <- put here a log2(RAND_MAX) value */
}

bit = bit_stream % 2;
bit_stream /= 2;
--requests_left;

if (bit == 0)
break;
}

return height;
}

It is not difficult to modify this code for p=3-based distribution

static int random_height( int max_height )
{
static int bit_stream;
static int requests_left = 0;
int height = 1;

while (height < max_height)
{
unsigned char bit;

if (requests_left == 0)
{
bit_stream = rand();
requests_left = NN; /* <- put here a log3(RAND_MAX) value */
}

bit = bit_stream % 3;
bit_stream /= 3;
--requests_left;

if (bit == 0)
break;
}

return height;
}

Also, it makes sense to replace the standard 'rand()' function with your
own plain and simple pseudo-random generator function of
add-and-multiply type that will return a "longer" value. For example on
my 32-bit platform RAND_MAX is 32767, which gives me only 15 meaningful
bits. Replacing 'rand()' with my own function that generates 32-bit
pseudo-random values helps to reduce the frequency of bit-stream
re-generations considerably.

If you have time and desire, you can try these suggestions one after
another and see their effect on a piece of code that relies heavily on
the insertion performance and search performance. I'm pretty sure that
the effect will be more than noticeable, to say the least.

--
Best regards,
Andrey Tarasevich

[CBFalconer]

Robin Cole wrote:

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:
.... snip ...
With xitem defined as:

/*
Copyright (C) 2004 Robin Cole

xitem.c - Application specific definitions for xitem.
*/

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Andrey Tarasevich]

Andrey Tarasevich wrote:

...
It is not difficult to modify this code for p=3-based distribution

static int random_height( int max_height )
{
static int bit_stream;
static int requests_left = 0;
int height = 1;

while (height < max_height)
{
unsigned char bit;

if (requests_left == 0)
{
bit_stream = rand();
requests_left = NN; /* <- put here a log3(RAND_MAX) value */
}

bit = bit_stream % 3;
bit_stream /= 3;
--requests_left;

if (bit == 0)
break;
Ooops... To obtain the correct p=3-based distribution this should be
changed to

if (bit != 0)
break;
}

return height;
}

--
Best regards,
Andrey Tarasevich

[Default User]

CBFalconer wrote:

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

Where did you get the idea that if someone includes a copyright
statement that their code is a commercial enterprise? Or that if it
doesn't have one, it's not a commercial enterprise?


Brian Rodenborn

[Arthur J. O'Dwyer]

On Mon, 24 May 2004, Default User wrote:

CBFalconer wrote:

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

Where did you get the idea that if someone includes a copyright
statement that their code is a commercial enterprise? Or that if it
doesn't have one, it's not a commercial enterprise?

Yes; I think CBFalconer should have replaced "remove any copyright
statements" with "add an indication of the uses to which you intend
this code to be put." Nothing wrong with leaving the copyright notice;
<way OT> AFAIK, the product is copyrighted to its creator no matter
whether he tells you so or not </way OT>. Of course, public domain
is also nice... :)

-Arthur

[Phlip]

CBFalconer wrote:

/*
Copyright (C) 2004 Robin Cole

xitem.c - Application specific definitions for xitem.
*/

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

The law (at least in the USA) shall reserve the right of copy from every
work, as it is created. This means the first slap of gesso (primer) to a
painter's stretched canvas is already under copyright.

Copyright, and the (c) marker don't imply any commercial endeavor (such as
money invested to register the copyright).

--
Phlip
http://industrialxp.org/community/bi...UserInterfaces

[Stephen Sprunk]

[ For the record, I'm not a lawyer; please consult one before relying on my
interpretation ]

"Phlip" <ph*******@yahoo.com> wrote in message
news:a1***************@newssvr19.news.prodigy.com. ..

CBFalconer wrote:

/*
Copyright (C) 2004 Robin Cole

xitem.c - Application specific definitions for xitem.
*/
If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

You are confusing copyright ownership/licensing with commerce. All of the
code posted to c.l.c is copyrighted one way or another (see below), though
it's reasonable to assume the author implicitly grants a limited license by
asking for help in a public forum.
The law (at least in the USA) shall reserve the right of copy from every
work, as it is created. This means the first slap of gesso (primer) to a
painter's stretched canvas is already under copyright.
The Berne Convention states that any work is copyrighted by its creator
unless explicitly stated otherwise. This is a recent change, BTW, as up
until a few years ago the US considered everything in the public domain
unless explicitly copyrighted.
Copyright, and the (c) marker don't imply any commercial endeavor (such as
money invested to register the copyright).

Registering a copyright entitles the owner to punitive damages, whereas
owners of unregistered copyright can only collect actual losses (at least in
the US). Some might consider registration only worthwhile for those using
commercial licenses, but IMHO that's backwards -- Linus couldn't collect a
dime in court for violations unless he registered Linux since he cannot
suffer an actual loss of revenue for a free product.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin

[CBFalconer]

Default User wrote:

CBFalconer wrote:

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

Where did you get the idea that if someone includes a copyright
statement that their code is a commercial enterprise? Or that if
it doesn't have one, it's not a commercial enterprise?

Maybe not the best choice of words, but I find the action somewhat
offensive. It's something like saying "Blow up my ball, so I can
go off and play with it".

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Arthur J. O'Dwyer]

On Tue, 25 May 2004, CBFalconer wrote:

Default User wrote:

CBFalconer wrote:

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.

Where did you get the idea that if someone includes a copyright
statement that their code is a commercial enterprise? Or that if
it doesn't have one, it's not a commercial enterprise?

Maybe not the best choice of words, but I find the action somewhat
offensive. It's something like saying "Blow up my ball, so I can
go off and play with it".

So just preface all your *responses* with

/*
This bugfix (c) CBFalconer, 2004
Permission to reproduce this line of code is granted
unconditionally, so long as this copyright notice is
retained.
*/

and see how long it takes the OP to remove his copyright notice. ;-)

Seriously, though, I see the OP more as saying, "I've blown up
my ball, but I think it might be leaking. Could you take a look at
it before I go off and play with it?" In which case, it would
definitely be appropriate for the OP to modify his notice to read
something like

/*
This code copyright the OP, 2004. Help and bugfixes provided
by Fred, Bob, Alice, and Chad in comp.lang.c.
*/

Assuming Fred et al. agreed with that choice of wording, of course.
Anyway, don't you think we've scared the OP off already? Can we
get back to programming? ;-)

-Arthur

[Robin Cole]

"Mark McIntyre" <ma**********@spamcop.net> wrote

On Mon, 24 May 2004 18:12:11 GMT, in comp.lang.c , "Robin Cole"
<ha*********@hotmail.com> wrote:

"Phlip" <ph*******@yahoo.com> wrote

I got this far. Try:

#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)

That's a little obscure for my tastes. I like things to be immediately
obvious for my readers.
That /is/ immediately obvious to anyone who knows C (if one sorts out the
missing printf specifiers).

I know C. :-) However, I don't use macros in such a way often, so even
though I know C, it took me a moment to recognize the strategy being used.
What I meant by "immediately obvious" is that a quick glance is all you
need. I had to stare at it for several seconds, so that isn't immediately
obvious. ;-)
The original version either requires to you to supply a "msg" that is a
format string, or else it invokes undefined behaviour.
As I understand it, if there are too few arguments for the format string
then the behavior is undefined. If there are excess arguments then they're
evaluated, but otherwise ignored and the behavior is not undefined (C99,
7.19.6.2, paragraph 2). Even so, the "fixed" version still requires the
caller to supply a "msg" that's a format string if they want var to be
handled.
However, as you are learning, you should see if C++ and its standard library can provide cleaner code.

And slower code. I've written skip lists before using C++'s standard
container classes for "cleaner code" that were easily half as fast as the
equivalent hand rolled implementation.

Then you either
a) had a bad STL implementation (possiblel or

Possible as I was using a compiler known to be poor.
b) you coded it badly (likely).

I particularly enjoyed the assumption that I write bad code. ;-) Yes, my
writing a bad implementation is _more likely_ than a bad STL implementation,
but that doesn't mean I don't know what I'm doing. :-)

[Robin Cole]

Excellent comments, thank you very much. :-) As you can probably tell, my
background in mathematics is lacking. I'll incorporate your suggestions
straight away. :-)

[Robin Cole]

"CBFalconer" <cb********@yahoo.com> wrote

Default User wrote:

CBFalconer wrote:

If you want help with your code, I suggest you first remove any
copyright statements. I don't believe anybody here really wants
to contribute uncompensated code to anyones commercial enterprise.
Where did you get the idea that if someone includes a copyright
statement that their code is a commercial enterprise? Or that if
it doesn't have one, it's not a commercial enterprise?

Maybe not the best choice of words, but I find the action somewhat
offensive.

I'm sorry if I offended you. I'll remove any comments that resemble
copyright notices in future postings. But in response to your first post,
this isn't commercial code. And since nobody is willing to hire a programmer
with no "professional experience", I'm probably not going to be writing
commercial code for some time.
It's something like saying "Blow up my ball, so I can
go off and play with it".

Still not the best choice of words. :-) "Blow up my ball" suggests that I'm
asking you to do the work for me. However, since I've already done the work
and I'm asking for comments on the result of my efforts and ways to improve
my skills based on those comments, "Blow up my ball" isn't a good analogy
IMHO.

If you're really that offended by my request then simply don't reply. I
won't mind. :-)

[CBFalconer]

Robin Cole wrote:

.... snip ...
If you're really that offended by my request then simply don't
reply. I won't mind. :-)

If I was that offended I wouldn't have replied in the first
place. I take it as the sort of thing that is done routinely with
little thought, and I feel it is inappropriate in newsgroups.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Dr Chaos]

Andrey Tarasevich <an**************@hotmail.com> wrote:

In this context it is rather expensive.
Instead, treat the result of the 'rand()' function as a sequence of bits
- a bit stream.

Unfortunately almost all pseudorandom number generators implemented
for rand() do not promise (and do not) to give good random bits to
the mantissa.

Generators for cryptography purposes, on the other hand, are designed
to do that, but they're significantly more expensive per call.

[Andrey Tarasevich]

Dr Chaos wrote:

In this context it is rather expensive.
Instead, treat the result of the 'rand()' function as a sequence of bits
- a bit stream.
Unfortunately almost all pseudorandom number generators implemented
for rand() do not promise (and do not) to give good random bits to
the mantissa.

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic pseudo-random
generators usually perform very well.
Generators for cryptography purposes, on the other hand, are designed
to do that, but they're significantly more expensive per call.
...

That makes the aforementioned technique even more useful, since it
reduces the frequency of calls (compared to the original version).

--
Best regards,
Andrey Tarasevich

[Ben Pfaff]

Dr Chaos <mb****************@NOSPAMyahoo.com> writes:

Andrey Tarasevich <an**************@hotmail.com> wrote:

In this context it is rather expensive.
Instead, treat the result of the 'rand()' function as a sequence of bits
- a bit stream.

Unfortunately almost all pseudorandom number generators implemented
for rand() do not promise (and do not) to give good random bits to
the mantissa.

Here is a portable PRNG that does:
http://benpfaff.org/writings/clc/random.html
It uses a stream cipher to generate random bits. (However, it is
not engineered for cryptographic strength, so please don't try to
use it that way.)
--
"I don't have C&V for that handy, but I've got Dan Pop."
--E. Gibbons

[CBFalconer]

Andrey Tarasevich wrote:

Dr Chaos wrote:

.... snip ...

Unfortunately almost all pseudorandom number generators
implemented for rand() do not promise (and do not) to give good
random bits to the mantissa.

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic
pseudo-random generators usually perform very well.

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush.
"Churchill and Bush can both be considered wartime leaders, just
as Secretariat and Mr Ed were both horses." - James Rhodes.

[Ben Pfaff]

CBFalconer <cb********@yahoo.com> writes:

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

You're missing that for some applications is useful to be able to
traverse a list in sorted order and modify the list, keeping it
in sorted order, at the same time. Neither a hash table nor a
sorted list is ideal for such applications: a hash table cannot
be efficiently traversed in sorted order and a sorted list cannot
be efficiently modified in sorted order. The paper on binary and
balanced trees available from my website at
http://benpfaff.org/papers describes two such applications; skip
lists can be used for the same applications, but I have not
implemented them (yet).

--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup

[Andrey Tarasevich]

CBFalconer wrote:

...
Unfortunately almost all pseudorandom number generators
implemented for rand() do not promise (and do not) to give good
random bits to the mantissa.

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic
pseudo-random generators usually perform very well.

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?
...

As you already noted yourself, hash-based containers do not immediately
impose any meaningful ordering on the stored sequence of elements. Skip
lists do. Sorted sequences have many useful applications besides
implementing look-up tables.

Performing an additional sorting step on hash table (as you suggested
above) is, of course, completely unacceptable in virtually any
application that needs to maintain a sorted sequence in on-line mode.

--
Best regards,
Andrey Tarasevich

[CBFalconer]

Andrey Tarasevich wrote:

CBFalconer wrote:

...
Unfortunately almost all pseudorandom number generators
implemented for rand() do not promise (and do not) to give good
random bits to the mantissa.

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic
pseudo-random generators usually perform very well.

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?
...

As you already noted yourself, hash-based containers do not
immediately impose any meaningful ordering on the stored sequence
of elements. Skip lists do. Sorted sequences have many useful
applications besides implementing look-up tables.

Performing an additional sorting step on hash table (as you
suggested above) is, of course, completely unacceptable in
virtually any application that needs to maintain a sorted
sequence in on-line mode.

I see. In many cases the optimum would be to insert the item in
both the skip-list and the hash table. Of course a combination
hash/red-black tree might perform the same function. The
skip-list would be better when the predecessor is needed.

Please don't remove attributions for quotations you leave
unsnipped.

--
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison

[Charles Richmond]

CBFalconer wrote:

Andrey Tarasevich wrote:

Dr Chaos wrote:

... snip ...

Unfortunately almost all pseudorandom number generators
implemented for rand() do not promise (and do not) to give good
random bits to the mantissa.

Yes, but this particular application (skip lists) does not really
require an exceptionally good random mantissa. Simplistic
pseudo-random generators usually perform very well.

I fail to see any reason for the existence of skip-lists, since
access is much slower than hash tables, and any hash table can be
walked and made into a list (including a skip-list) on demand.
The result can then be merge-sorted in O(nLOGn) on any field(s)
desired. What am I missing?

The same might be said of AVL trees...or given AVL trees, why
do we need Red-Black trees??? I suppose that some folks feel
more comfortable with balanced trees than with hash tables...

I personally found skip-lists to be interesting...even though
I have *never* used them in a project of any sort.

--
+-------------------------------
| Charles and Francis Richmond
| richmond at plano dot net
| Re-Defeat Bush!!!
+-------------------------------