17.2.5 struct mapping
struct mapping is used to represent a mapping, for the most part
you should be able to write modules and understand Pike internals without
actually touching the internals of a mapping. It also helps that mappings
are very well abstracted, so you can almost always use the supporting
functions instead of fiddling around with the contents of a
struct mapping directly.
This is the contents of a struct mapping:
Mappings are allocated as two separate blocks of memory. One is the
struct mapping which holds pointers into the second memory block.
The second memory block contains the hash table and all key-value pairs.
A key-value pair is represented as a struct keypair which has
the following members:
- INT32 refs;
- The references, as in all data types except int and float.
- INT32 size;
- The number of key-index pairs in the mapping.
- INT32 hashsize;
- The size of the mapping hash table. Normally between 1/2 and 1/4 of the
size of the mapping.
- INT16 flags;
- May contain the flag MAPPING_FLAG_WEAK to have data being
garbage collected even when it is still in the mapping.
- TYPE_FIELD ind_types, val_types;
- These type fields tells what types may be present among the indices
and values of the mapping. See TYPE_FIELD for more information
about type fields.
- struct keypair **hash;
- This is the hash table.
- struct keypair *free_list;
- This is a linked list of free keypairs.
Please note that the free list is separate for each mapping. Also,
when there are no more free key-value pairs the whole memory block
is re-allocated and the mapping is re-hashed with a larger hash table.
- struct keypair *next;
- Pointer to the next key-value pair in this bucket.
Also used to link free key-value pairs together.
- struct svalue ind, val;
- The key and value respectively.
Below is an illustration which shows an example of a small mapping with
hash table, free list and key-index pairs.
As you can see, mappings uses a linked list for each bucket in the
hash table. Also, the current implementation moves key-value pairs to
the top of the hash chain everytime a match is found, this can greately
increase performance in some situations. However, because of this the
order of elements in a mapping can change every time you access it.
Also, since mappings can be re-allocated any time you add an element to
it you can never trust a pointer to a pointer to a struct keypair
if any Pike cod has a chance to execute.