Internals.md revision b4e91091ecafdafd7fa393609080466bdb453d73
169a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark KlaraFlatBuffer Internals {#flatbuffers_internals} 269a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara==================== 326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThis section is entirely optional for the use of FlatBuffers. In normal 526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenusage, you should never need the information contained herein. If you're 626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmersseninterested however, it should give you more of an appreciation of why 726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenFlatBuffers is both efficient and convenient. 826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Format components 1026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 1126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenA FlatBuffer is a binary file and in-memory format consisting mostly of 1226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenscalars of various sizes, all aligned to their own size. Each scalar is 1326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenalso always represented in little-endian format, as this corresponds to 1426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenall commonly used CPUs today. FlatBuffers will also work on big-endian 1526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenmachines, but will be slightly slower because of additional 1626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenbyte-swap intrinsics. 1726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 1826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenOn purpose, the format leaves a lot of details about where exactly 1926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthings live in memory undefined, e.g. fields in a table can have any 2069a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klaraorder, and objects to some extent can be stored in many orders. This is 2126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenbecause the format doesn't need this information to be efficient, and it 2226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenleaves room for optimization and extension (for example, fields can be 2326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenpacked in a way that is most compact). Instead, the format is defined in 24d8a173ddc7331075c3e25afa97f85321fca9ebcfWouter van Oortmerssenterms of offsets and adjacency only. This may mean two different 25d8a173ddc7331075c3e25afa97f85321fca9ebcfWouter van Oortmerssenimplementations may produce different binaries given the same input 26d8a173ddc7331075c3e25afa97f85321fca9ebcfWouter van Oortmerssenvalues, and this is perfectly valid. 2726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 2826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Format identification 2926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 3026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThe format also doesn't contain information for format identification 3126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenand versioning, which is also by design. FlatBuffers is a statically typed 3226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssensystem, meaning the user of a buffer needs to know what kind of buffer 3326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenit is. FlatBuffers can of course be wrapped inside other containers 3426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenwhere needed, or you can use its union feature to dynamically identify 3526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenmultiple possible sub-objects stored. Additionally, it can be used 3626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssentogether with the schema parser if full reflective capabilities are 3726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssendesired. 3826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 3926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenVersioning is something that is intrinsically part of the format (the 4026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenoptionality / extensibility of fields), so the format itself does not 4126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenneed a version number (it's a meta-format, in a sense). We're hoping 4226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthat this format can accommodate all data needed. If format breaking 4326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenchanges are ever necessary, it would become a new kind of format rather 4426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthan just a variation. 4526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 4626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Offsets 4726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 4826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThe most important and generic offset type (see `flatbuffers.h`) is 4966de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssen`uoffset_t`, which is currently always a `uint32_t`, and is used to 5066de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenrefer to all tables/unions/strings/vectors (these are never stored 5166de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenin-line). 32bit is 5226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenintentional, since we want to keep the format binary compatible between 5326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen32 and 64bit systems, and a 64bit offset would bloat the size for almost 5426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenall uses. A version of this format with 64bit (or 16bit) offsets is easy to set 5526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenwhen needed. Unsigned means they can only point in one direction, which 5626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssentypically is forward (towards a higher memory location). Any backwards 5726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenoffsets will be explicitly marked as such. 5826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 5966de19ace80bae3bf377e43e9698597170bc9031Wouter van OortmerssenThe format starts with an `uoffset_t` to the root object in the buffer. 6026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 6126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenWe have two kinds of objects, structs and tables. 6226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 6326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Structs 6426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 6526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThese are the simplest, and as mentioned, intended for simple data that 6626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenbenefits from being extra efficient and doesn't need versioning / 6726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenextensibility. They are always stored inline in their parent (a struct, 6826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssentable, or vector) for maximum compactness. Structs define a consistent 6926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenmemory layout where all components are aligned to their size, and 7026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenstructs aligned to their largest scalar member. This is done independent 7126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenof the alignment rules of the underlying compiler to guarantee a cross 7226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenplatform compatible layout. This layout is then enforced in the generated 7326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssencode. 7426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 7526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Tables 7626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 774e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenUnlike structs, these are not stored in inline in their parent, but are 784e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenreferred to by offset. 794e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 804e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenThey start with an `soffset_t` to a vtable. This is a signed version of 8189d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van Oortmerssen`uoffset_t`, since vtables may be stored anywhere relative to the object. 8289d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van OortmerssenThis offset is substracted (not added) from the object start to arrive at 8389d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van Oortmerssenthe vtable start. This offset is followed by all the 8466de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenfields as aligned scalars (or offsets). Unlike structs, not all fields 8566de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenneed to be present. There is no set order and layout. 8626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 8726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenTo be able to access fields regardless of these uncertainties, we go 8826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthrough a vtable of offsets. Vtables are shared between any objects that 8926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenhappen to have the same vtable values. 9026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 9166de19ace80bae3bf377e43e9698597170bc9031Wouter van OortmerssenThe elements of a vtable are all of type `voffset_t`, which is 9289d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van Oortmerssena `uint16_t`. The first element is the size of the vtable in bytes, 9389d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van Oortmerssenincluding the size element. The second one is the size of the object, in bytes 9489d2b0861b2f74e84ec698a2536d48eb7ca62268Wouter van Oortmerssen(including the vtable offset). This size could be used for streaming, to know 954e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenhow many bytes to read to be able to access all *inline* fields of the object. 9666de19ace80bae3bf377e43e9698597170bc9031Wouter van OortmerssenThe remaining elements are the N offsets, where N is the amount of fields 9726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssendeclared in the schema when the code that constructed this buffer was 9826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssencompiled (thus, the size of the table is N + 2). 9926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 10026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenAll accessor functions in the generated code for tables contain the 10126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenoffset into this table as a constant. This offset is checked against the 10226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenfirst field (the number of elements), to protect against newer code 10326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenreading older data. If this offset is out of range, or the vtable entry 10426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenis 0, that means the field is not present in this object, and the 10526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssendefault value is return. Otherwise, the entry is used as offset to the 10626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenfield to be read. 10726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 10826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Strings and Vectors 10926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 11026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenStrings are simply a vector of bytes, and are always 11126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssennull-terminated. Vectors are stored as contiguous aligned scalar 11266de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenelements prefixed by a 32bit element count (not including any 1134e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssennull termination). Neither is stored inline in their parent, but are referred to 1144e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenby offset. 11526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 11626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Construction 11726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 11866de19ace80bae3bf377e43e9698597170bc9031Wouter van OortmerssenThe current implementation constructs these buffers backwards (starting 11966de19ace80bae3bf377e43e9698597170bc9031Wouter van Oortmerssenat the highest memory address of the buffer), since 12026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthat significantly reduces the amount of bookkeeping and simplifies the 12126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenconstruction API. 12226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 12326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen### Code example 12426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 12526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenHere's an example of the code that gets generated for the `samples/monster.fbs`. 12626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenWhat follows is the entire file, broken up by comments: 12726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 12826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen // automatically generated, do not modify 12926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 13026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen #include "flatbuffers/flatbuffers.h" 13126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 13226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen namespace MyGame { 13326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen namespace Sample { 13426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 13526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenNested namespace support. 13626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 13726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen enum { 13826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Color_Red = 0, 13926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Color_Green = 1, 14026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Color_Blue = 2, 14126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; 14226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 14326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen inline const char **EnumNamesColor() { 14426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen static const char *names[] = { "Red", "Green", "Blue", nullptr }; 14526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen return names; 14626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen } 14726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 14826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen inline const char *EnumNameColor(int e) { return EnumNamesColor()[e]; } 14926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 15026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenEnums and convenient reverse lookup. 15126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 15226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen enum { 15326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Any_NONE = 0, 15426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Any_Monster = 1, 15526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; 15626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 15726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen inline const char **EnumNamesAny() { 15826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen static const char *names[] = { "NONE", "Monster", nullptr }; 15926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen return names; 16026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen } 16126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 16226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen inline const char *EnumNameAny(int e) { return EnumNamesAny()[e]; } 16326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 16426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenUnions share a lot with enums. 16526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 16626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen struct Vec3; 16726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen struct Monster; 16826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 1698c5d7f7deae36b71c1d13e4edc877ba8e35d3acfWouter van OortmerssenPredeclare all data types since circular references between types are allowed 1708c5d7f7deae36b71c1d13e4edc877ba8e35d3acfWouter van Oortmerssen(circular references between object are not, though). 17126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 17226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen MANUALLY_ALIGNED_STRUCT(4) Vec3 { 17326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen private: 17426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float x_; 17526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float y_; 17626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float z_; 17726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 17826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen public: 17926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen Vec3(float x, float y, float z) 18026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen : x_(flatbuffers::EndianScalar(x)), y_(flatbuffers::EndianScalar(y)), z_(flatbuffers::EndianScalar(z)) {} 18126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 18226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float x() const { return flatbuffers::EndianScalar(x_); } 18326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float y() const { return flatbuffers::EndianScalar(y_); } 18426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen float z() const { return flatbuffers::EndianScalar(z_); } 18526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; 18626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen STRUCT_END(Vec3, 12); 18726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 18826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThese ugly macros do a couple of things: they turn off any padding the compiler 18926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenmight normally do, since we add padding manually (though none in this example), 19026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenand they enforce alignment chosen by FlatBuffers. This ensures the layout of 19126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthis struct will look the same regardless of compiler and platform. Note that 19226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthe fields are private: this is because these store little endian scalars 19326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenregardless of platform (since this is part of the serialized data). 19426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen`EndianScalar` then converts back and forth, which is a no-op on all current 19526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenmobile and desktop platforms, and a single machine instruction on the few 19626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenremaining big endian platforms. 19726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 19826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen struct Monster : private flatbuffers::Table { 19926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen const Vec3 *pos() const { return GetStruct<const Vec3 *>(4); } 20026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen int16_t mana() const { return GetField<int16_t>(6, 150); } 20126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen int16_t hp() const { return GetField<int16_t>(8, 100); } 20226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen const flatbuffers::String *name() const { return GetPointer<const flatbuffers::String *>(10); } 20326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen const flatbuffers::Vector<uint8_t> *inventory() const { return GetPointer<const flatbuffers::Vector<uint8_t> *>(14); } 20426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen int8_t color() const { return GetField<int8_t>(16, 2); } 20526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; 20626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 20726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenTables are a bit more complicated. A table accessor struct is used to point at 20826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthe serialized data for a table, which always starts with an offset to its 20926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenvtable. It derives from `Table`, which contains the `GetField` helper functions. 21026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenGetField takes a vtable offset, and a default value. It will look in the vtable 21126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenat that offset. If the offset is out of bounds (data from an older version) or 21226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenthe vtable entry is 0, the field is not present and the default is returned. 21326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenOtherwise, it uses the entry as an offset into the table to locate the field. 21426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 21526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen struct MonsterBuilder { 21626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen flatbuffers::FlatBufferBuilder &fbb_; 21726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen flatbuffers::uoffset_t start_; 21826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_pos(const Vec3 *pos) { fbb_.AddStruct(4, pos); } 21926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_mana(int16_t mana) { fbb_.AddElement<int16_t>(6, mana, 150); } 22026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_hp(int16_t hp) { fbb_.AddElement<int16_t>(8, hp, 100); } 22126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_name(flatbuffers::Offset<flatbuffers::String> name) { fbb_.AddOffset(10, name); } 22226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_inventory(flatbuffers::Offset<flatbuffers::Vector<uint8_t>> inventory) { fbb_.AddOffset(14, inventory); } 22326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen void add_color(int8_t color) { fbb_.AddElement<int8_t>(16, color, 2); } 22426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen MonsterBuilder(flatbuffers::FlatBufferBuilder &_fbb) : fbb_(_fbb) { start_ = fbb_.StartTable(); } 22526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen flatbuffers::Offset<Monster> Finish() { return flatbuffers::Offset<Monster>(fbb_.EndTable(start_, 7)); } 22626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; 22726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 22826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen`MonsterBuilder` is the base helper struct to construct a table using a 22926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen`FlatBufferBuilder`. You can add the fields in any order, and the `Finish` 23026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssencall will ensure the correct vtable gets generated. 23126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 23269a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara inline flatbuffers::Offset<Monster> CreateMonster(flatbuffers::FlatBufferBuilder &_fbb, 23369a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara const Vec3 *pos, int16_t mana, 23469a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara int16_t hp, 23569a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara flatbuffers::Offset<flatbuffers::String> name, 23669a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara flatbuffers::Offset<flatbuffers::Vector<uint8_t>> inventory, 23769a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara int8_t color) { 23826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen MonsterBuilder builder_(_fbb); 23926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_inventory(inventory); 24026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_name(name); 24126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_pos(pos); 24226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_hp(hp); 24326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_mana(mana); 24426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen builder_.add_color(color); 24526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen return builder_.Finish(); 24626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen } 24726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 24826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen`CreateMonster` is a convenience function that calls all functions in 24926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen`MonsterBuilder` above for you. Note that if you pass values which are 25026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssendefaults as arguments, it will not actually construct that field, so 25126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenyou can probably use this function instead of the builder class in 25226a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenalmost all cases. 25326a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 25426a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen inline const Monster *GetMonster(const void *buf) { return flatbuffers::GetRoot<Monster>(buf); } 25526a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 25626a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van OortmerssenThis function is only generated for the root table type, to be able to 25726a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssenstart traversing a FlatBuffer from a raw buffer pointer. 25826a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 25926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; // namespace MyGame 26026a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen }; // namespace Sample 26126a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 2624e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen### Encoding example. 2634e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2644e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenBelow is a sample encoding for the following JSON corresponding to the above 2654e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenschema: 2664e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2674e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen { pos: { x: 1, y: 2, z: 3 }, name: "fred", hp: 50 } 2684e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2694e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenResulting in this binary buffer: 2704e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2714e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen // Start of the buffer: 2724e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint32_t 20 // Offset to the root table. 2734e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2744e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen // Start of the vtable. Not shared in this example, but could be: 2754e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint16_t 16 // Size of table, starting from here. 2764e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint16_t 22 // Size of object inline data. 2774e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint16_t 4, 0, 20, 16, 0, 0 // Offsets to fields from start of (root) table, 0 for not present. 2784e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2794e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen // Start of the root table: 2804e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen int32_t 16 // Offset to vtable used (default negative direction) 2814e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen float 1, 2, 3 // the Vec3 struct, inline. 2824e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint32_t 8 // Offset to the name string. 2834e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen int16_t 50 // hp field. 2844e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen int16_t 0 // Padding for alignment. 2854e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen 2864e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen // Start of name string: 2874e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen uint32_t 4 // Length of string. 2884e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssen int8_t 'f', 'r', 'e', 'd', 0, 0, 0, 0 // Text + 0 termination + padding. 28926a30738a4fa4e92300821fd761764ec8df2dcf2Wouter van Oortmerssen 2904e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenNote that this not the only possible encoding, since the writer has some 2914e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenflexibility in which of the children of root object to write first (though in 2924e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van Oortmerssenthis case there's only one string), and what order to write the fields in. 2934e4a5142fb2d50c08856b3c3292bcf9c649ed2e7Wouter van OortmerssenDifferent orders may also cause different alignments to happen. 29469a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara 2958a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van Oortmerssen### Additional reading. 2968a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van Oortmerssen 2978a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van OortmerssenThe author of the C language implementation has made a similar 2988a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van Oortmerssen[document](https://github.com/dvidelabs/flatcc/blob/master/doc/binary-format.md#flatbuffers-binary-format) 2998a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van Oortmerssenthat may further help clarify the format. 3008a2cc7cc4ebef69d455c6fe4e14399eb51033c5eWouter van Oortmerssen 301aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen# FlexBuffers 302aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 303aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe [schema-less](@ref flexbuffers) version of FlatBuffers have their 304aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenown encoding, detailed here. 305aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 306aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenIt shares many properties mentioned above, in that all data is accessed 307aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenover offsets, all scalars are aligned to their own size, and 308aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenall data is always stored in little endian format. 309aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 310aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenOne difference is that FlexBuffers are built front to back, so children are 311aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenstored before parents, and the root of the data starts at the last byte. 312aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 313aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenAnother difference is that scalar data is stored with a variable number of bits 314aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen(8/16/32/64). The current width is always determined by the *parent*, i.e. if 315aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthe scalar sits in a vector, the vector determines the bit width for all 316aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenelements at once. Selecting the minimum bit width for a particular vector is 317aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssensomething the encoder does automatically and thus is typically of no concern 318aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssento the user, though being aware of this feature (and not sticking a double in 319aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthe same vector as a bunch of byte sized elements) is helpful for efficiency. 320aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 321aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenUnlike FlatBuffers there is only one kind of offset, and that is an unsigned 322aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmersseninteger indicating the number of bytes in a negative direction from the address 323aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenof itself (where the offset is stored). 324aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 325aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Vectors 326aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 327aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe representation of the vector is at the core of how FlexBuffers works (since 328aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenmaps are really just a combination of 2 vectors), so it is worth starting there. 329aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 330aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenAs mentioned, a vector is governed by a single bit width (supplied by its 331aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenparent). This includes the size field. For example, a vector that stores the 332aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmersseninteger values `1, 2, 3` is encoded as follows: 333aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 334aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen uint8_t 3, 1, 2, 3, 4, 4, 4 335aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 336aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe first `3` is the size field, and is placed before the vector (an offset 337aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenfrom the parent to this vector points to the first element, not the size 338aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenfield, so the size field is effectively at index -1). 339aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenSince this is an untyped vector `SL_VECTOR`, it is followed by 3 type 340aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenbytes (one per element of the vector), which are always following the vector, 341aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenand are always a uint8_t even if the vector is made up of bigger scalars. 342aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 343aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Types 344aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 345aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenA type byte is made up of 2 components (see flexbuffers.h for exact values): 346aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 347aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen* 2 lower bits representing the bit-width of the child (8, 16, 32, 64). 348aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen This is only used if the child is accessed over an offset, such as a child 349aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen vector. It is ignored for inline types. 350aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen* 6 bits representing the actual type (see flexbuffers.h). 351aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 352aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThus, in this example `4` means 8 bit child (value 0, unused, since the value is 353aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenin-line), type `SL_INT` (value 1). 354aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 355aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Typed Vectors 356aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 357aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThese are like the Vectors above, but omit the type bytes. The type is instead 358aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssendetermined by the vector type supplied by the parent. Typed vectors are only 359aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenavailable for a subset of types for which these savings can be significant, 360aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssennamely inline signed/unsigned integers (`TYPE_VECTOR_INT` / `TYPE_VECTOR_UINT`), 361aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenfloats (`TYPE_VECTOR_FLOAT`), and keys (`TYPE_VECTOR_KEY`, see below). 362aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 363aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenAdditionally, for scalars, there are fixed length vectors of sizes 2 / 3 / 4 364aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthat don't store the size (`TYPE_VECTOR_INT2` etc.), for an additional savings 365aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenin space when storing common vector or color data. 366aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 367aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Scalars 368aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 369aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenFlexBuffers supports integers (`TYPE_INT` and `TYPE_UINT`) and floats 370aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen(`TYPE_FLOAT`), available in the bit-widths mentioned above. They can be stored 371aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenboth inline and over an offset (`TYPE_INDIRECT_*`). 372aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 373aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe offset version is useful to encode costly 64bit (or even 32bit) quantities 374aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmersseninto vectors / maps of smaller sizes, and to share / repeat a value multiple 375aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssentimes. 376aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 377b4e91091ecafdafd7fa393609080466bdb453d73rouzier### Booleans and Nulls 378b4e91091ecafdafd7fa393609080466bdb453d73rouzier 379b4e91091ecafdafd7fa393609080466bdb453d73rouzierBooleans (`TYPE_BOOL`) and nulls (`TYPE_NULL`) are encoded as inlined unsigned integers. 380b4e91091ecafdafd7fa393609080466bdb453d73rouzier 381aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Blobs, Strings and Keys. 382aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 383aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenA blob (`TYPE_BLOB`) is encoded similar to a vector, with one difference: the 384aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenelements are always `uint8_t`. The parent bit width only determines the width of 385aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthe size field, allowing blobs to be large without the elements being large. 386aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 387aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenStrings (`TYPE_STRING`) are similar to blobs, except they have an additional 0 388aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssentermination byte for convenience, and they MUST be UTF-8 encoded (since an 389aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenaccessor in a language that does not support pointers to UTF-8 data may have to 390aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenconvert them to a native string type). 391aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 392aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenA "Key" (`TYPE_KEY`) is similar to a string, but doesn't store the size 393aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenfield. They're so named because they are used with maps, which don't care 394aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenfor the size, and can thus be even more compact. Unlike strings, keys cannot 395aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssencontain bytes of value 0 as part of their data (size can only be determined by 396aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen`strlen`), so while you can use them outside the context of maps if you so 397aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssendesire, you're usually better off with strings. 398aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 399aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### Maps 400aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 401aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenA map (`TYPE_MAP`) is like an (untyped) vector, but with 2 prefixes before the 402aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssensize field: 403aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 404aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| index | field | 405aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| ----: | :----------------------------------------------------------- | 406aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| -3 | An offset to the keys vector (may be shared between tables). | 407aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| -2 | Byte width of the keys vector. | 408aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| -1 | Size (from here on it is compatible with `TYPE_VECTOR`) | 409aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| 0 | Elements. | 410aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen| Size | Types. | 411aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 412aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenSince a map is otherwise the same as a vector, it can be iterated like 413aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssena vector (which is probably faster than lookup by key). 414aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 415aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe keys vector is a typed vector of keys. Both the keys and corresponding 416aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenvalues *have* to be stored in sorted order (as determined by `strcmp`), such 417aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthat lookups can be made using binary search. 418aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 419aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe reason the key vector is a seperate structure from the value vector is 420aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssensuch that it can be shared between multiple value vectors, and also to 421b4e91091ecafdafd7fa393609080466bdb453d73rouzierallow it to be treated as its own individual vector in code. 422aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 423aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenAn example map { foo: 13, bar: 14 } would be encoded as: 424aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 425b4e91091ecafdafd7fa393609080466bdb453d73rouzier 0 : uint8_t 'b', 'a', 'r', 0 426b4e91091ecafdafd7fa393609080466bdb453d73rouzier 4 : uint8_t 'f', 'o', 'o', 0 427aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 8 : uint8_t 2 // key vector of size 2 428aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen // key vector offset points here 429b4e91091ecafdafd7fa393609080466bdb453d73rouzier 9 : uint8_t 9, 6 // offsets to bar_key and foo_key 430b4e91091ecafdafd7fa393609080466bdb453d73rouzier 11: uint8_t 2, 1 // offset to key vector, and its byte width 431aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 13: uint8_t 2 // value vector of size 432aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen // value vector offset points here 433b4e91091ecafdafd7fa393609080466bdb453d73rouzier 14: uint8_t 14, 13 // values 434aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 16: uint8_t 4, 4 // types 435aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 436aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen### The root 437aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 438aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenAs mentioned, the root starts at the end of the buffer. 439aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenThe last uint8_t is the width in bytes of the root (normally the parent 440aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssendetermines the width, but the root has no parent). The uint8_t before this is 441aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssenthe type of the root, and the bytes before that are the root value (of the 442aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssennumber of bytes specified by the last byte). 443aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 444aac6be1153eb5343f03dd60101ee438636e9300bWouter van OortmerssenSo for example, the integer value `13` as root would be: 445aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 446aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen uint8_t 13, 4, 1 // Value, type, root byte width. 447aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 448aac6be1153eb5343f03dd60101ee438636e9300bWouter van Oortmerssen 44969a31b807a85e9a5ca4efb839f37ecb6dcf3eed5Mark Klara<br> 450