Built-in key types

Abstact data type union

The adt_t union stores different type of keys are used by abstract data types. It supports unsigned and signed integers, floating-point numbers and void pointers to memory blocks, which may hold actual keys and data, such as strings and complex structures/classes.

C/C++union adt_t
{
    Unsigned integer types
    uint8_t uint8;
    uint16_t uint16;
    uint32_t uint32;
    uint64_t uint64;

    Signed integer types
    sint8_t sint8;
    sint16_t sint16;
    sint32_t sint32;
    sint64_t sint64;

    Floating-point types
    flt32_t flt32;
    flt64_t flt64;

    Other types
    size_t size;
    time_t time;

    Pointer type
    void *ptr;
};

Union adt_t has following members:

• uint8 - 8-bit unsigned integer value
• uint16 - 16-bit unsigned integer value
• uint32 - 32-bit unsigned integer value
• uint64 - 64-bit unsigned integer value
• sint8 - 8-bit signed integer value
• sint16 - 16-bit signed integer value
• sint32 - 32-bit signed integer value
• sint64 - 64-bit signed integer value
• flt32 - 32-bit floating-point value
• flt64 - 64-bit floating-point value
• size - Integer value that holds object size
• time - Integer value that holds unix time
• ptr - Pointer to another memory block which hold actual data

Pair structure

All abstract data types hold elements of following structure.

C/C++struct pair_t
{
    union adt_t key;
    union adt_t data;
};

Each element consists of 2 fields:

• key - the element key
• data - data value is assigned to this key

Both elements of adt_t structire are unions (see definition above), which can hold instant values (numbers) and pointers to another data structures.

Pair copy function prototype

The main goal of copy function is to make deep copy of an element is inserted into ADT container. Copy function may allocate a memory block for new element and then copy its fields into that place. It should always return copy state as boolean value: TRUE if object was successfully copied, or FALSE if not. ADTs use this status to determine if new object was successfully inserted into container, and return operation status according to the state returned by the copy function.

C/C++bool CopyFunc (struct pair_t *target, const struct pair_t *source, void *ptr);

Parameters:

• target - pointer to target data structure, where data pair should be copied
• source - pointer to source data structure, from which data pair should be copied
• ptr - pointer to user's data, may be required by copy function

Return value:

• TRUE (1) if function successfully made a copy of data pair: key and value.
• FALSE (0) if copy function failed (was not able to allocate memory, for example).

Pair delete function prototype

Delete function may be used in pair with copy function, described above, to release a memory block previously allocated for container's element. It also can be used with a reference counter to decrement count of references to existing object, and to delete it if counter is equal to zero. Delete function does not return any state.

C/C++void DelFunc (struct pair_t *data, void *ptr);

Parameters:

• data - pointer to data structure, which should be processed before removing
• ptr - pointer to user's data, may be required by delete function

Return value: None.

Heap index call back function prototype

Index call back function is used to inform your code where the keys were moved during the main heap operations, such as "put", "pop" and "merge". These operations reorder keys to restore correct relations among heap elements. The index call back function gets direct pointer to the element, which was moved, and its new index into the heap. You may use this index to track the new positions of the elements and for fast increasing and decreasing of heap keys, without key searching operations.

C/C++void HeapIndex (const struct pair_t *data, size_t index);

Parameters:

• data - pointer to data structure
• index - heap index where the data was moved

Return value: None.

Filter function prototype

Filter function is common mechanism to filter data in pair vector. It makes decision if checked pair should stay in output vector or it should be filtered out. You may define such functions to use with vectorized search procedures to do fast preprocessing and postprocessing of different data sets.

C/C++bool FilterFunc (const struct pair_t *data, void *ptr);

Parameters:

• data - pointer to data structure
• ptr - pointer to user's data, may be required by filter function

Return value:

• TRUE (1) if pair should pass through the filter (stay in pair vector).
• FALSE (0) if pair should be filtered out from pair vector.

Hash function prototype

Hash function computes 64-bit hash value for the key. This hash value is used by hash table to get an index of the elements chain where the key should be placed. The hash function should generate smooth uniform distribution to work efficient with hash table algorithms.

C/C++size_t HashFunc (union adt_t key);

Parameters:

• key - key value for hashing

Return value: Hash value for provided key.

Key compare function prototype

To sort keys inside the data structures, you need some kind of key compare function, that can easily say which elements are greater or less. The LinAsm library allow you to define your own compare functions and use them with standard data structures. Key compare functions should follow the next prototype and return defined compare states.

C/C++sint64_t KeyCmp (union adt_t key1, union adt_t key2);

Parameters:

• key1 - first key
• key2 - second key

Return value:

• -1 if first key is less than second key.
• 0 if first key is equal to second key.
• +1 if first key is greater than second key.

Tip:If you wish to operate with standard C/C++ types, you may use already implemented key compare functions from this list.

Pair compare function prototype

To sort array of pairs sometimes it is necessary to compare not only keys but also data, is assigned to each key. To make decision if both elements are equal or less/greater a pair compare function takes two pairs and compare both key and data field and then return relation between them. Each pair compare function should satisfy this prototype.

C/C++sint64_t PairCmp (struct pair_t pair1, struct pair_t pair2);

Parameters:

• pair1 - first pair
• pair2 - second pair

Return value:

• -1 if first pair is less than second pair.
• 0 if first pair is equal to second pair.
• +1 if first pair is greater than second pair.

Key compare functions

LinAsm abstract data types collection provides some already defined standard key compare functions, which are wide used. They take two keys and return their relation.

C/C++Unsigned integer keys
sint64_t CmpUint8 (union adt_t key1, union adt_t key2);
sint64_t CmpUint16 (union adt_t key1, union adt_t key2);
sint64_t CmpUint32 (union adt_t key1, union adt_t key2);
sint64_t CmpUint64 (union adt_t key1, union adt_t key2);

Signed integer keys
sint64_t CmpSint8 (union adt_t key1, union adt_t key2);
sint64_t CmpSint16 (union adt_t key1, union adt_t key2);
sint64_t CmpSint32 (union adt_t key1, union adt_t key2);
sint64_t CmpSint64 (union adt_t key1, union adt_t key2);

Floating-point keys
sint64_t CmpFlt32 (union adt_t key1, union adt_t key2);
sint64_t CmpFlt64 (union adt_t key1, union adt_t key2);

Other keys
sint64_t CmpSize (union adt_t key1, union adt_t key2);
sint64_t CmpTime (union adt_t key1, union adt_t key2);

Description: Compare two keys and return key relation (equal, greater, less).

Parameters:

• key1 - first key
• key2 - second key

Return value:

• -1 if first key is less than second key.
• 0 if first key is equal to second key.
• +1 if first key is greater than second key.