Algorithm templates

Algorithms implemented here are “templates”. They are provided as macros which adapt to underlying types. This means these algorithms can run faster as they are not generic, but it also means that each use will generate its own copy.

Currently algorithms to work with arrays (insert, delete, binary search), hash tables (searching) and bitmaps (set, clear, test, find first) are implemented. Main user of these algorithms is kernel itself yet as they are optimized for embedded they are accessible to userspace programs as well.

Functions

uint32_t os_hash_key(uint32_t key)

Macros

BINARY_SEARCH(_ARRAY, _KEY, _VALUE, _SIZE)

This is a template for binary searching over a sorted compacted array. It will search either for exact match or in case the sought key is not present in dataset, for lower bounds - entry present in array sorting just before the sought entry.

As with any binary search, this algorithm assumes that data is sorted. This template expects data to be stored in array of structures with structure containing member holding item’s unique ID. This ID is used for searching.

Example:

typedef}Entry_tunsigned…unsigned

• _ARRAY identification of array which is used to search for entry
• _KEY name of structure member which holds unique ID of entry
• _VALUE unique ID sought for in the array
• _SIZE amount of valid entries currently stored in the array

Returns array offset of entry with matching ID or with ID which is nearest smaller than ID sought for, if sought-for ID is not present.

ARRAY_INSERT(_ARRAY, _POS, _SIZE)

This template will create free space in array, move all entries after the place of insertion one entry higher and increase array size.

_ARRAY array being inserted into

_POS position at which insertion happens

_SIZE lvalue holding current array size (e.g. count of actual stored items rather than allocation size) This template does not check for array overflowing

• _ARRAY array being inserted into
• _POS position at which insertion happens
• _SIZE lvalue holding current array size (e.g. count of actual stored items rather than allocation size)

ARRAY_DELETE(_ARRAY, _POS, _SIZE)

This template will delete item from array, move all entries after the place of insertion one entry lower and decrease array size.

_ARRAY array being inserted into

_POS position at which deletion happens

_SIZE lvalue holding current array size (e.g. count of actual stored items rather than allocation size)

• _ARRAY array being inserted into
• _POS position at which deletion happens
• _SIZE lvalue holding current array size (e.g. count of actual stored items rather than allocation size)

INSERT_SORT(_ARRAY, _KEY, _VALUE, _SIZE, _MAX)

This template will allocate space for inserting new item into sorted array so that it stays sorted. It will do so that the array remains sorted after the insertion. Template code will move array contents around to make space for new entry but won’t write it. That’s caller responsibility.

This algorithm assumes that identifiers of items in array are unique. Thus, if ID passed for new entry already exists in the array, it will be overwritten by subsequent call.

Example:

typedef}Entry_tunsigned…Entry_tunsignedentries[offs]

Note that the algorithm will avoid corrupting memory if there is a request to insert new entry into already-full array but won’t return any special return value. It’s caller’s responsibility to check if array is already full before making the call.

This algorithm works in a way that if ID of new entry already exists in the array, array content won’t be moved around and subsequent write will overwrite the existing entry. If ID doesn’t exist, space for it will be allocated by moving items around the array so the array remains sorted after insertion.

• _ARRAY identification of array which is used to search for entry
• _KEY name of structure member which holds unique ID of entry
• _VALUE unique ID sought for in the array
• _SIZE amount of valid entries currently stored in the array. This argument must be a lvalue as it will be modified during the process.
• _MAX capacity of the array.

Returns array offset where new entry may be inserted. This position is always valid but care has to be taken to check if array capacity is not exhausted. Caller should check that _SIZE < _MAX upon insertion, if entry with given ID didn’t exist before.

HASH_EMPTY

Reserved value denoting that tash table key is empty.

HASH_SEARCH(_HASHTABLE, _KEY, _VALUE, _MAX)

This is a template for searching hash tables. It either finds the entry if it is present in the table or returns position of an entry that is marked as empty.

Example: typedef}Entry_t…Entry_tunsignedentries[offs]

• _HASHTABLE identification of the hash table where search is performed
• _KEY name of structure member which holds unique ID of entry
• _VALUE unique ID sought for in the hash table
• _MAX allocation size of the hash table

BITMAP_SET(_BITMAP, _POS, _SIZE)

Sets bit in bitmap of arbitrary size as if it was one continuous array of bits.

• _BITMAP bitmap identity
• _POS bit to be set
• _SIZE bitmap size

BITMAP_CLEAR(_BITMAP, _POS, _SIZE)

Clears bit in bitmap of arbitrary size as if it was one continuous array of bits.

• _BITMAP bitmap identity
• _POS bit to be set
• _SIZE bitmap size

BITMAP_TEST(_BITMAP, _POS, _SIZE)

Tests if bit in bitmap of arbitrary size is set.

• _BITMAP bitmap identity
• _POS bit to be set
• _SIZE bitmap size

BITMAP_FIRST(_BITMAP, _SIZE)

Returns first bit set in bitmap of arbitrary size as if it was one continuous array of bits.

• _BITMAP bitmap identity
• _SIZE bitmap size

Returns position of first bit counted from the beginning of bitmap, or ~0U if no bit is set.

BITMAP_COPY(_TARGET, _SOURCE, _SIZE)