Re: How to implement a Hash Table in C

"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> writes:

"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message
A lot of algorithm books make a big meal of the basic data
structures. I checked the Java queue classes before writing this post,
I am not asking you to over-complicate it so I don't see how anyone
else's complex interface has anything to do with it.

The Java class is not written by idiots. It is basically what you need
for a production generic queue class. However my code is not
production code. It is there to illustrate how to implement the
algorithm.

But it is not an excuse for your useless example.

I think we will have to leave this argument. I am beginning to see
that we have different opinions about what makes a data structure and
what makes a good program. It seems you think it is fine that your
readers will have to re-invent one of the various methods to
distinguish between a full and an empty queue, and pepper their code
with references to the head and tail counters (like you do in your
program that uses a stack with no 'push', 'pop', 'empty' or 'full'
functions). They will also have to re-write the bits that you *did*
write, since you don't test for full or emptiness, in order to do
anything with it at all.

The alternative to to write generic structures.

No. The alternative is to write a functional, useful, simple,
fixed-length queue of integers (since those are the very sensible
restrictions you put on your example). I am not asking you to make it
generic (in types), or flexible (in size), just usable as your text
claims it to be.

Write a short example that uses your add and remove functions do
anything at all. You'll have to put half of the code for add and
remove (the bits that checks if adding or removing is possible) into
the algorithm. You can't be suggesting that is how one should use a
simple queue -- by putting the slightly tricky full and empty tests
outside of any queue operations? Of course, it is quite reasonable to
leave them out of the add and remove functions for efficiency,
provided there is a user note: "don't call add() unless is_full()
returns false" (and the mirror for the awkwardly named remove()). In
an introductory text, I'd have add() and remove() do these tests, but
if you don't do that they need to be provided as queue operations.

If you'd said, "now you just need to define is_full() and is_empty()
functions and you can start using this queue" that would be a fine
exercise (but I'd include an answer later since it is slightly tricky)
but you seem to be suggesting that it can be used as you have left it.

Maybe this is at the heart of out differences. Maybe you are happy
that a significant implementation issue (how to distinguish between a
full and an empty circular buffer) be peppered about the algorithms
that use the buffer. If so, it partially explains why you left the
queue unfinished, but I don't think it is a good example to set, and it
is a terrible way to write maintainable programs. You do it in the
stack example, so maybe that is what you expect.

If this is not the reason, then I am just at a loss. A book called
Basic Algorithms includes code for a queue. This code can't be used
in any basic algorithm I know without first finishing the design by
deciding how to distinguish between full and empty queues and then either

(a) putting this code, which tests variables that belong to the queue
all over the algorithms that use the queue;
(b) rewriting add and remove so they can signal failure and have them do
these tests; or
(c) finish the interface by adding these two testing operations.

In all these cases I think you need to tell your readers that the queue
is not finished.

<snip more stuff about generic queues>

If you don't believe me, please just answer my original question and
show how to wrote a simple algorithm (any algorithm) using your queue
operations.

That's not the intention. The queue takes only integers and has a
hardwired size. The code shows someone who doesn't know that queues
are importnat data structures how to implement one. It doesn't give
nor is in intended to give a generic "queue" class.

I don't care that it not generic. Did I not say that enough yet? I
am curious that the intention was not that it be used. Given that
assumption, it is easier to write good books. Would it not have been
better to provide a simple but usable (allbeit limited) example? It
is only a few more lines of code. And in case you mistake my
meaning -- no need to make it generic or dynamic.

If you do, you will see how you have move all sorts of
implementation details into the program the uses the queue. Of
course, you could also do it my ditching what you wrote in the book
and implementing a bounded queue properly. It is only a few lines
more code. There would be no need to make it complicated, just usable
and self-contained.

Exactly. You go to the book, then you implement your own queue, as
needed, using the code in the book as a reference if necessary.

Had you finished the implementation it would have been a more useful
reference. Is the "bug" in the code just the fact the you missed out
the sentence: "You need to make one further design decision and then
finish the implementation by writing is_full() and is_empty()
functions."?

You miss the point. I don't want it to be "massively detailed", but
clear, usable and self-contained would be nice.

There are many generic queue libraries. None has gained wide
acceptance. Therefore the bar for "usable" is in fact very high. This
is not true of other languages, but it is true of C.

Set the bar as low as you like. Yours is not usable without either
finishing it, rewriting it, or messing up the code that tries to use
it. I am talking about two functions of a line or two each. I can't
see why you think your "sketch" is more helpful without these or why
adding them is too complex for you to consider.

--
Ben.
.

Relevant Pages

  • Re: Memory manager for a lock-free queue
    ... This queue is actually blocking. ... blocking algorithm which can outperform a lock-free algorithm. ... counter solution to the ABA problem is basically race-condition ... They chose to use 32 bit tag explaining that it would take on ...
    (comp.programming.threads)
  • Re: coerce for arbitrary types
    ... algorithm that Cormen, Leiserson, and Rivest use in their DFS. ... inherently first-in first-out, like a queue, not at all stack-like ... experience, once you get over the hurdle of recursion, ... *intention* is nested lists, *not* arbitrary CONS trees. ...
    (comp.lang.lisp)
  • Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ?
    ... explicitly pad to cache line and align on cache line boundary in ... how to actually align data-structures on cache line boundaries. ... I want the queue to be aligned on a cache line boundary. ... I will test against Dmitriy's awesome queue algorithm, ...
    (comp.programming.threads)
  • Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ?
    ... explicitly pad to cache line and align on cache line boundary in ... how to actually align data-structures on cache line boundaries. ... I want the queue to be aligned on a cache line boundary. ... I will test against Dmitriy's awesome queue algorithm, ...
    (comp.programming.threads)
  • Re: How is it that he is calling his queue the most efficient and fastest mpmc queue ?
    ... explicitly pad to cache line and align on cache line boundary in ... I will test against Dmitriy's awesome queue algorithm, ... Just compile the pop.pas and push.pas tests examples that you ...
    (comp.programming.threads)