core_list_join.c

Summary
core_list_join.c
DescriptionBenchmark using a linked list.
Functions
cmp_complexCompare the data item in a list cell.
cmp_idxCompare the idx item in a list cell, and regen the data.
core_list_initInitialize list with data.
core_list_insertInsert an item to the list
core_list_removeRemove an item from the list.
core_list_undo_removeUndo a remove operation.
core_list_findFind an item in the list
core_list_reverseReverse a list
core_list_mergesortSort the list in place without recursion.

Description

Benchmark using a linked list.

Linked list is a common data structure used in many applications.

For our purposes, this will excercise the memory units of the processor.  In particular, usage of the list pointers to find and alter data.

We are not using Malloc since some platforms do not support this library.

Instead, the memory block being passed in is used to create a list, and the benchmark takes care not to add more items then can be accomodated by the memory block.  The porting layer will make sure that we have a valid memory block.

All operations are done in place, without using any extra memory.

The list itself contains list pointers and pointers to data items.  Data items contain the following:

idxAn index that captures the initial order of the list.
dataVariable data initialized based on the input parameters.  The 16b are divided as follows:
  • Upper 8b are backup of original data.
  • Bit 7 indicates if the lower 7 bits are to be used as is or calculated.
  • Bits 0-2 indicate type of operation to perform to get a 7b value.
  • Bits 3-6 provide input for the operation.

Functions

cmp_complex

ee_s32 cmp_complex(list_data *a,
list_data *b,
core_results *res)

Compare the data item in a list cell.

Can be used by mergesort.

cmp_idx

ee_s32 cmp_idx(list_data *a,
list_data *b,
core_results *res)

Compare the idx item in a list cell, and regen the data.

Can be used by mergesort.

core_list_init

list_head *core_list_init(ee_u32 blksize,
list_head *memblock,
ee_s16 seed)

Initialize list with data.

Parameters

blksizeSize of memory to be initialized.
memblockPointer to memory block.
seedActual values chosen depend on the seed parameter.  The seed parameter MUST be supplied from a source that cannot be determined at compile time

Returns

Pointer to the head of the list.

core_list_insert

list_head *core_list_insert_new(list_head *insert_point,
list_data *info,
list_head **memblock,
list_data **datablock ,
list_head *memblock_end,
list_data *datablock_end)

Insert an item to the list

Parameters

insert_pointwhere to insert the item.
infodata for the cell.
memblockpointer for the list header
datablockpointer for the list data
memblock_endend of region for list headers
datablock_endend of region for list data

Returns

Pointer to new item.

core_list_remove

list_head *core_list_remove(list_head *item)

Remove an item from the list.

Operation

For a singly linked list, remove by copying the data from the next item over to the current cell, and unlinking the next item.

Note

since there is always a fake item at the end of the list, no need to check for NULL.

Returns

Removed item.

core_list_undo_remove

list_head *core_list_undo_remove(list_head *item_removed,
list_head *item_modified)

Undo a remove operation.

Operation

Since we want each iteration of the benchmark to be exactly the same, we need to be able to undo a remove.  Link the removed item back into the list, and switch the info items.

Parameters

item_removedReturn value from the core_list_remove
item_modifiedList item that was modified during core_list_remove

Returns

The item that was linked back to the list.

core_list_find

list_head *core_list_find(list_head *list,
list_data *info)

Find an item in the list

Operation

Find an item by idx (if not 0) or specific data value

Parameters

listlist head
infoidx or data to find

Returns

Found item, or NULL if not found.

core_list_reverse

list_head *core_list_reverse(list_head *list)

Reverse a list

Operation

Rearrange the pointers so the list is reversed.

Parameters

listlist head
infoidx or data to find

Returns

Found item, or NULL if not found.

core_list_mergesort

list_head *core_list_mergesort(list_head *list,
list_cmp cmp,
core_results *res)

Sort the list in place without recursion.

Description

Use mergesort, as for linked list this is a realistic solution.  Also, since this is aimed at embedded, care was taken to use iterative rather then recursive algorithm.  The sort can either return the list to original order (by idx) , or use the data item to invoke other other algorithms and change the order of the list.

Parameters

listlist to be sorted.
cmpcmp function to use

Returns

New head of the list.

Note

We have a special header for the list that will always be first, but the algorithm could theoretically modify where the list starts.

ee_s32 cmp_complex(list_data *a,
list_data *b,
core_results *res)
Compare the data item in a list cell.
ee_s32 cmp_idx(list_data *a,
list_data *b,
core_results *res)
Compare the idx item in a list cell, and regen the data.
list_head *core_list_init(ee_u32 blksize,
list_head *memblock,
ee_s16 seed)
Initialize list with data.
list_head *core_list_insert_new(list_head *insert_point,
list_data *info,
list_head **memblock,
list_data **datablock ,
list_head *memblock_end,
list_data *datablock_end)
Insert an item to the list
list_head *core_list_remove(list_head *item)
Remove an item from the list.
list_head *core_list_undo_remove(list_head *item_removed,
list_head *item_modified)
Undo a remove operation.
list_head *core_list_find(list_head *list,
list_data *info)
Find an item in the list
list_head *core_list_reverse(list_head *list)
Reverse a list
list_head *core_list_mergesort(list_head *list,
list_cmp cmp,
core_results *res)
Sort the list in place without recursion.
Close