Re: Questions about writing a C library

[Philippe Lhoste <PhiLho@...>]

Phil Bewig wrote:
> I suppose it's fair to say that the three fundamental data
> structures in computing are arrays, lists, and hash tables
> (I still remember how amazed I was when I first learned
> about hash tables, almost thirty years ago -- they seemed
> like magic them, and sometimes still do today).  It's also
> probably fair to say that most imperative languages are
> built around arrays, most functional languages are built
> around lists, and most scripting languages are built around
> hash tables.  And even further, it's probably fair to say
> that all three data structures can do a reasonable job of
> simulating each other, so whichever one your language gives
> you, it's always possible to get your task written.  But
> the three are fundamentally different, with varying strengths
> and weaknesses, and there is no reason to say that lua uses
> hash tables, so linked lists are somehow unclean.
>
> I note that all three people who responded on the mailing
> list objected to my use of the list data structure.  That
> surprises me.  Lists are intrinsically ordered, tables are
> intrinsically unordered.  Lists take one object per node,
> tables take two objects, key and value, per node.  Lists
> and tables are just ... different.  Is there some reason
> lua people don't like lists?  Is there some unmentionable
> tar pit you are all trying to steer me away from?

Hello Phil

Since you are a self-proclamed beginner, you may have missed the point 
that there is actually two kinds of tables in Lua, with different 
internal management:
the hash table that you mention, with key/value pairs, unordered; and 
the array, using consecutive implicit numbers starting a 1 as "keys", 
implemented as such, ie. with direct access to the value by its index, 
without collision, and of course ordered (there is a table.sort 
function...).

Actually, both kinds of tables have the same syntax and Lua manage the 
difference transparently; you can even mix them freely: entries with 
string keys and sparse indexes are hashed, entries with indexes (keys) 
from 1 to n (without gap) are indexed.

Eg. taken from the manual:

x = 2
g = 3.1415926535897932384
f = function (p) return p * 5 end
a = {[f(1)] = g; "x", "y"; x = 1, f(x), [30] = 23; 45}
-- Dump the array part of the table, by index order
for i, v in ipairs(a) do
  print(i, v)
end
print""
-- Dump the whole table (including the array part) in random order
for i, v in pairs(a) do
  print(i, v)
end

Note that the array can be built in any order:
a = { [3] = 23, [1] = 2, [2] = 213 }
is OK.
a = { [3] = 23, [4] = 2, [2] = 213 }
isn't OK, because index 1 is missing.

Now to your linked list:
I believe you can implement it with arrays, because the table library 
offers functions like table.insert and table.remove. The language offers 
direct access to a value, and the basic library offers iterators.
This way, you can shift entries as needed.
I don't know if it is as efficient as a C linked list, but I trust it is 
quite efficient, not moving data around, just indexes.

HTH.

--
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
http://jove.prohosting.com/~philho/ (outdated)
http://philho.multimania.com (in French, for files to download)
--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--=#=--