Re: non-hashed strings (was: Hash Table Collisions)

[Xavier Wang <weasley.wx@...>]

2012/1/10 Eduardo Ochs <eduardoochs@gmail.com>:
> 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/
>

using a userdata is better, I think.