# core_list_join.c

Summary

core_list_join.c |
Description | Benchmark using a linked list.
Functions |
cmp_complex | Compare the data item in a list cell.
cmp_idx | Compare the idx item in a list cell, and regen the data.
core_list_init | Initialize list with data.
core_list_insert | Insert an item to the list
core_list_remove | Remove an item from the list.
core_list_undo_remove | Undo a remove operation.
core_list_find | Find an item in the list
core_list_reverse | Reverse a list
core_list_mergesort | Sort 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:

idx | An index that captures the initial order of the list.
data | Variable 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

blksize | Size of memory to be initialized.
memblock | Pointer to memory block.
seed | Actual 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_point | where to insert the item.
info | data for the cell.
memblock | pointer for the list header
datablock | pointer for the list data
memblock_end | end of region for list headers
datablock_end | end 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_removed | Return value from the core_list_remove
item_modified | List 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

list | list head
info | idx 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

list | list head
info | idx 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

list | list to be sorted.
cmp | cmp 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