non-hashed strings (was: Hash Table Collisions)

[Eduardo Ochs <eduardoochs@...>]

On Tue, Jan 10, 2012 at 1:38 AM, Xavier Wang <weasley.wx@gmail.com> wrote:
>
> 2012/1/10 Roberto Ierusalimschy <roberto@inf.puc-rio.br>:
> >> If such a "external contents string" type were added to Lua, it would be
> >> helpful to have an explicit "gc" callback as part of the Lua object,
> >> which would get called when the Lua object was freed, and could free the
> >> separate string buffer.
> >
> > It should have something like this, but we still have to figure out
> > some details (for instance, whether such function could access the Lua
> > state).
> >
> > -- Roberto
> >
>
> Hi Roberto,
>
> I really think that a programming language should have two kinds of
> string: One for Symbol and One for really string.
>
> Symbol is used as hash-table key, flags, etc. Its just the Lua string
> now. it has registered in a global string table, compared with
> pointer, and has a pre-calculate hash value. its just like identify in
> a language: we don't care its content, but only use it as a signature.
>
> String is a real byte array, It can be changed, It doesn't need using
> as hash-table key (but it could), It may be very long and has doesn't
> need to pre-calculate a hash, compare two really string is expensive,
> long String can use Copy-On-Write but it's not matter.
>
> Now it's the balance between Symbol and String, and their using scene.
>
> I really like string implement in nowadays lua, simple, and beautiful.
> but a language should have a really mutable string. I have write a
> module lbuffer[1] to implement a real string. but it can not using as
> hash key and even can not compare directly.
>
> so, maybe small string is a symbol, and bigger string is a string is a
> good idea, another idea is just have two string type internal, just
> like light userdata and userdata, light C function and C function,
> etc.
>

Are you implying that mutable, hon-hashed strings should also support
concatenation, string.sub, comparison, matching, etc? If you do not
require that then there's a trivial way to implement mutable strings,
which is by writing these Lua functions in C:

  malloc(nbytes)     -- returns an address
  free(addr)         -- expects an address of a malloc'ed block
  peek(addr, nbytes) -- returns a hashed, i.e., interned, string
  poke(addr, str)    -- copies str to an arbitrary memory position

and there writting wrappers around them to make them safer...

However, if you _do_ want something like string library functions that
operate on these "mutable strings" (by the way, let me confess this is
the first time that I think about that - I've been using the low-level
approach above for some time, and I've been quite happy with it) then
you would need to either A) write your variations for the functions in
lstring.c, or B) try to convince the Lua team to do that for you in
some next version of Lua. I would go for (A) if I were you.

  Cheers,
    Eduardo Ochs
    eduardoochs@gmail.com
    http://angg.twu.net/