Searching for Link List Implementation (with requirements)

[Beagle]

Folks,

Any recommendations for a link list implementation C source with
sorting, searching, insert and deleting by key? I need to keep track
of many {unsigned int process id (pid), unsigned int file descriptors
(fd)} tuples, and want to store them in a linked list. I want to be
able to search by the pid quickly (e.g. O(lg)), insert, and delete
also by pid as the key. Prior I had been using a hash table (taken
from google codesearch), but the possibility of the key hash mapping
to the same value would crash my program.

Thanks,
BEA

 

[Ben Pfaff]

Any recommendations for a link list implementation C source with
sorting, searching, insert and deleting by key? I need to keep track
of many {unsigned int process id (pid), unsigned int file descriptors
(fd)} tuples, and want to store them in a linked list. I want to be
able to search by the pid quickly (e.g. O(lg)), insert, and delete
also by pid as the key.

Your request doesn't make any sense. A linked list cannot be
searched in O(lg n) time.

Prior I had been using a hash table (taken from google
codesearch), but the possibility of the key hash mapping to the
same value would crash my program.

Perhaps you should debug your hash table implementation.

 

[user923005]

Folks,

Any recommendations for a link list implementation C source with
sorting, searching, insert and deleting by key? I need to keep track
of many {unsigned int process id (pid), unsigned int file descriptors
(fd)} tuples, and want to store them in a linked list. I want to be
able to search by the pid quickly (e.g. O(lg)), insert, and delete
also by pid as the key. Prior I had been using a hash table (taken
from google codesearch), but the possibility of the key hash mapping
to the same value would crash my program.

You could always get a better hash table or fix your program logic.

Anyway, a skiplist is a linked list that gives O(lg(N)) insert,
update, delete, find.

Your question is better suited to
I guess that an AVL tree or a Red-Black tree or a bug free hash table
(and etc.) will also fill the bill.

There is a cache friendly skiplist on sourceforge.

 

[CBFalconer]

Any recommendations for a link list implementation C source with
sorting, searching, insert and deleting by key? I need to keep
track of many {unsigned int process id (pid), unsigned int file
descriptors (fd)} tuples, and want to store them in a linked list.
I want to be able to search by the pid quickly (e.g. O(lg)),
insert, and delete also by pid as the key. Prior I had been using
a hash table (taken from google codesearch), but the possibility
of the key hash mapping to the same value would crash my program.

Try using a bug-free (I believe) hash table. See:

<http://cbfalconer.home.att.net/download/hashlib.zip>

 

[Beagle]

Your request doesn't make any sense.  A linked list cannot be
searched in O(lg n) time.

Why do you say this? If the link list were sorted, or a second sorted
data structure used (e.g. hash or array)?

Perhaps you should debug your hash table implementation.

You are so certain there is a problem with the hash table
implementation, but again I don't see why there would be a bug. I was
saying the possibility.

 

[Chris Dollin]

Why do you say this? If the link list were sorted, or a second sorted
data structure used (e.g. hash or array)?

Then you're not using /just/ a linked list. You asked for a /linked
list/ implementation, not a "hash or array".

You are so certain there is a problem with the hash table
implementation, but again I don't see why there would be a bug. I was
saying the possibility.

Hash tables handle collisions in the hash value [1]. Those that don't
are buggy. Every text I've seen that talks about hash tables also
talks about how to handle collisions.

[1] Unless the likelihood of a collision is so ridiculously small that
it can be neglected.

 

[Richard Tobin]

Your request doesn't make any sense.  A linked list cannot be
searched in O(lg n) time.

[/QUOTE]

Why do you say this? If the link list were sorted, or a second sorted
data structure used (e.g. hash or array)?

If you use an auxilliary data structure it can of course be done.

But sorting by itself is not sufficient - an algorithm that ranges
over all elements of a linked list (with equal probability) by
following the links can't possibly be better than O(n), because
there's no way to get to (say) the last element without accessing
all the others.

-- Richard

 

[Beagle]

You could always get a better hash table or fix your program logic.

Anyway, a skiplist is a linked list that gives O(lg(N)) insert,
update, delete, find.

Your question is better suited to
I guess that an AVL tree or a Red-Black tree or a bug free hash table
(and etc.) will also fill the bill.

There is a cache friendly skiplist on sourceforge.

The hash table has Linux process id as it's key (pids). They are
assigned from 1 to MaxPID (64K or something). If the hash table's is
of size 1543, and the hash function is pid mod 1543, then pids 1543
and 3086 will both map to bucket 0.

There isn't necessarily a bug with the hash implementation, only if
the two pids returns the same fd, which is then closed, i.e. close
(fd); then the program may have closed the wrong file descriptor,
which is a logic error, preventing proper services.

Folks are thinking there is a bug with the hash implementation, I
guess what I may be missing, is, would the hashtable code, if correct,
still return the correct fd? In the case of two pids mapping to the
same bucket, that still thru linear search the and matching the pid
key, it will return the correct value? That is probably my confusion.

Thanks!

 

[Ben Pfaff]

You are so certain there is a problem with the hash table
implementation, but again I don't see why there would be a bug. I was
saying the possibility.

If there is a possibility that a hash collision will crash your
program, then your program is buggy.

 

[user923005]

Then you're not using /just/ a linked list. You asked for a /linked
list/ implementation, not a "hash or array".

A skiplist is a linked list that has all of the desired properties.
http://www.cs.arizona.edu/classes/cs352/fall03/SL.ppt
http://iir.ruc.edu.cn/ppt/2008/10/WangJieping.ppt
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
http://research.cs.queensu.ca/home/daver/235/C2102557243/E20070330101410/Media/SkipList.pdf

You are so certain there is a problem with the hash table
implementation, but again I don't see why there would be a bug. I was
saying the possibility.

Hash tables handle collisions in the hash value [1]. Those that don't
are buggy. Every text I've seen that talks about hash tables also
talks about how to handle collisions.

[1] Unless the likelihood of a collision is so ridiculously small that
    it can be neglected.

If a perfect hash is used, the likelihood of collision is zero.

 

[Mark L Pappin]

Hash tables handle collisions in the hash value [1].
[1] Unless the likelihood of a collision is so ridiculously small
that it can be neglected.

If a perfect hash is used, the likelihood of collision is zero.

ObPedant:
Seems to me that "zero" falls within the bounds of "so ridiculously
small that it can be neglected".

mlp

 

[user923005]

Hash tables handle collisions in the hash value [1].
[1] Unless the likelihood of a collision is so ridiculously small
    that it can be neglected.

If a perfect hash is used, the likelihood of collision is zero.

ObPedant:
Seems to me that "zero" falls within the bounds of "so ridiculously
small that it can be neglected".

Yes, I was just giving a special case that surely fits the bill.

 

[Chris Dollin]

[1] Unless the likelihood of a collision is so ridiculously small that
it can be neglected.

If a perfect hash is used, the likelihood of collision is zero.

The likelihood of a collision /with other keys in the keyset/ is zero.
The likelihood of a collision with nonkeys is significant, eg, unity.

I was thinking more of good hashes into a 64-bit or 128-bit hashspace.

--
"It took a very long time, much longer than the most /Sector General/
generous estimates." - James White

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England