Re: [boost] [B-tree] Continuing development

Subject: Re: [boost] [B-tree] Continuing development
From: OvermindDL1 (overminddl1_at_[hidden])
Date: 2010-09-25 16:24:49

On Sat, Sep 25, 2010 at 2:10 PM, Brian Wood <woodbrian77_at_[hidden]> wrote:
> Beman Dawes:
>
>> I'm going to attack variable-length keys/data in several steps.
>>
>> 1) Via a very simple string class that has a fixed maximum length, and has a
>> sizeof() that maximum length + 1. Although this wouldn't be suitable for
>> really demanding applications, it should be fine for a lot of every day
>> programming. It is totally non-invasive, so is available right now. See
>> http://github.com/Beman/Boost-Btree/blob/master/boost/btree/detail/fixstr.hpp,
>> or use your own if you've already got such an animal.
>
> Just fyi, I've been experimenting with a similar string --
> http://webEbenezer.net/misc/lil_string.hh .
>
> If an operation would result in a string with length more than 255,
> an exception is thrown. Â This allows the length of the string to be
> marshalled with one byte. Â As you mention this limitation is not a
> problem in many circumstances. Â I'd quibble a little with it not being
> suitable for demanding applications. Â I think it is fine to use it in that
> context, but that you might need to also use other string classes.

Why not use a compressed uint type?  Google's Protocol Buffers
compressed uint compresses an uint just fine, below 128 will be
represented in one byte, etc..., it works very simply, by just having
the MSB be a marker indicating the last byte of the integer if it is
zero, thus it is base 128 instead of base 256 per byte, so as an
example:
hex  ->  compressed bits
0    ->  0000 0000
1    ->  0000 0001
300  ->  1010 1100 0000 0010
And so forth, and if you have looked in the protocol buffer source it
decodes each byte very quickly and efficiently.  So if you are worried
about space, you could use this (especially since I have many use
cases where strings would exceed 255 characters, and we need a
'bytestream' type or so too).