Previous section To contents Next section

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:

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.
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:
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.
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.

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.

FUNCTION
m_sizeof

FUNCTION
m_ind_types

FUNCTION
m_val_types

FUNCTION
MAPPING_LOOP

FUNCTION
free_mapping

FUNCTION
allocate_mapping

FUNCTION
mapping_insert

FUNCTION
mapping_get_item_ptr

FUNCTION
map_delete

FUNCTION
low_mapping_lookup

FUNCTION
low_mapping_string_lookup

FUNCTION
simple_mapping_string_lookup

FUNCTION
mapping_string_insert

FUNCTION
mapping_indices

FUNCTION
mapping_values

FUNCTION
mapping_to_array

FUNCTION
mapping_replace

FUNCTION
mkmapping

FUNCTION
copy_mapping
Previous section To contents Next section