list.h File Reference

linked list interface More...

#include <types.h>
#include <memory.h>
#include <indexer.h>
#include <iterator.h>

Macros
#define	___LIST_H   0
#define	LIST_INSERT_AT_ANYWHERE   LIST_INSERT_AT_TAIL
#define	list_integer_comparator   list_default_data_comparator
#define	list_create_list_with_heap(h)   list_create_with_type(memory_get_heap(h), LIST_TYPE_LIST, NULL, NULL)
	creates a normal linked list at heap More...
#define	list_create_list()   list_create_with_type(memory_get_heap(NULL), LIST_TYPE_LIST, NULL, NULL)
	creates a normal linked list at default heap heap More...
#define	list_create_sortedlist_with_heap(h, c)   list_create_with_type(memory_get_heap(h), LIST_TYPE_SORTEDLIST, c, NULL)
	creates a sorted linked list at heap More...
#define	list_create_sortedlist(c)   list_create_with_type(memory_get_heap(NULL), LIST_TYPE_SORTEDLIST, c, NULL)
	creates a sorted linked list at default heap More...
#define	list_create_indexedlist_with_heap(h, i)   list_create_with_type(memory_get_heap(h), LIST_TYPE_INDEXEDLIST, NULL, i)
	creates a indexed linked list at heap More...
#define	list_create_indexedlist(i)   list_create_with_type(memory_get_heap(NULL), LIST_TYPE_INDEXEDLIST, NULL, i)
	creates a indexed linked list at default heap More...
#define	list_create_queue_with_heap(h)   list_create_with_type(memory_get_heap(h), LIST_TYPE_QUEUE, NULL, NULL)
	creates a queue at heap More...
#define	list_create_queue()   list_create_with_type(memory_get_heap(NULL), LIST_TYPE_QUEUE, NULL, NULL)
	creates a queue at default heap heap More...
#define	list_create_stack_with_heap(h)   list_create_with_type(memory_get_heap(h), LIST_TYPE_STACK, NULL, NULL)
	creates a stack at heap More...
#define	list_create_stack()   list_create_with_type(memory_get_heap(NULL), LIST_TYPE_STACK, NULL, NULL)
	creates a stack at default heap heap More...
#define	list_destroy(l)   list_destroy_with_type(l, LIST_DESTROY_WITHOUT_DATA, NULL)
#define	list_destroy_with_data(l)   list_destroy_with_type(l, LIST_DESTROY_WITH_DATA, NULL)
#define	list_insert_at_position(l, d, p)   list_insert_at(l, d, LIST_INSERT_AT_POSITION, p)
#define	list_delete_at_position(l, p)   list_delete_at(l, NULL, LIST_DELETE_AT_POSITION, p)
#define	list_delete_at_tail(l)   list_delete_at(l, NULL, LIST_DELETE_AT_TAIL, 0)
#define	list_list_insert(l, d)   list_insert_at(l, d, LIST_INSERT_AT_ANYWHERE, 0)
#define	list_list_delete(l, d)   list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)
#define	list_sortedlist_insert(l, d)   list_insert_at(l, d, LIST_INSERT_AT_SORTED, 0)
#define	list_sortedlist_delete(l, d)   list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)
#define	list_indexedlist_insert(l, d)   list_insert_at(l, d, LIST_INSERT_AT_INDEXED, 0)
#define	list_indexedlist_delete(l, d)   list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)
#define	list_queue_push(l, d)   list_insert_at(l, d, LIST_INSERT_AT_TAIL, 0)
#define	list_queue_pop(l)   list_delete_at(l, NULL, LIST_DELETE_AT_HEAD, 0)
#define	list_stack_push(l, d)   list_insert_at(l, d, LIST_INSERT_AT_HEAD, 0)
#define	list_stack_pop(l)   list_delete_at(l, NULL, LIST_DELETE_AT_HEAD, 0)
#define	list_insert_at_head(l, d)   list_insert_at(l, d, LIST_INSERT_AT_HEAD, 0)
#define	list_contains(l, d)   list_get_position(l, d, NULL)
#define	list_queue_peek(l)   list_get_data_at_position(l, 0);
#define	list_stack_peek(l)   list_get_data_at_position(l, 0);
#define	list_duplicate_list(l)   list_duplicate_list_with_heap(NULL, l);

Typedefs
typedef enum list_insert_delete_at_t	list_insert_delete_at_t
	linked list operation enum More...
typedef enum list_type_t	list_type_t
	linked list type More...
typedef enum list_destroy_type_t	list_destroy_type_t
	linked list destroy type
typedef struct list_t	list_t
typedef struct list_item_t	list_item_t
typedef int8_t(*	list_data_comparator_f) (const void *data1, const void *data2)
	comparing given to data More...
typedef int8_t(*	list_item_destroyer_callback_f) (memory_heap_t *heap, void *data)

Enumerations
enum	list_insert_delete_at_t {   LIST_INSERT_AT_HEAD , LIST_INSERT_AT_TAIL , LIST_INSERT_AT_POSITION , LIST_INSERT_AT_SORTED ,   LIST_INSERT_AT_INDEXED , LIST_DELETE_AT_HEAD , LIST_DELETE_AT_TAIL , LIST_DELETE_AT_FINDBY ,   LIST_DELETE_AT_POSITION }
	linked list operation enum More...
enum	list_type_t {   LIST_TYPE_LIST = 1 << 0 , LIST_TYPE_SORTEDLIST = 1 << 1 , LIST_TYPE_QUEUE = 1 << 2 , LIST_TYPE_STACK = 1 << 3 ,   LIST_TYPE_INDEXEDLIST = 1 << 8 , LIST_TYPE_LINKED = 1 << 9 , LIST_TYPE_ARRAY = 1 << 10 }
	linked list type More...
enum	list_destroy_type_t { LIST_DESTROY_WITHOUT_DATA , LIST_DESTROY_WITH_DATA }
	linked list destroy type More...

Functions
int8_t	list_default_data_comparator (const void *data1, const void *data2)
	linked list default data comparator More...
int8_t	list_string_comprator (const void *data1, const void *data2)
list_t *	list_create_with_type (memory_heap_t *heap, list_type_t type, list_data_comparator_f comparator, indexer_t indexer)
	linked list creator More...
memory_heap_t *	list_get_heap (list_t *list)
	returns list's heap More...
int8_t	list_set_capacity (list_t *list, size_t capacity)
	sets list's capacity More...
list_data_comparator_f	list_set_comparator (list_t *list, list_data_comparator_f comparator)
	updates list's comparator and returns the old one. More...
uint8_t	list_destroy_with_type (list_t *list, list_destroy_type_t type, list_item_destroyer_callback_f destroyer)
	destroys linked list More...
size_t	list_size (const list_t *list)
	returns item count at linked list More...
const void *	list_get_data_from_listitem (list_item_t *list_item)
	return data inside implicit list item type More...
size_t	list_insert_at (list_t *list, const void *data, list_insert_delete_at_t where, size_t position)
	general method for inserting or deleting data from list types. More...
const void *	list_delete_at (list_t *list, const void *data, list_insert_delete_at_t where, size_t position)
	general method for inserting or deleting data from list types. More...
list_item_t *	list_insert_at_head_and_get_list_item (list_t *list, const void *data)
boolean_t	list_move_item_to_head (list_t *list, list_item_t *item)
boolean_t	list_delete_list_item (list_t *list, list_item_t *item)
int8_t	list_get_position (list_t *list, const void *data, size_t *position)
	returns position of given data. More...
const void *	list_get_data_at_position (list_t *list, size_t position)
	returns position of given data. More...
list_t *	list_duplicate_list_with_heap (memory_heap_t *heap, list_t *list)
	duplicates list at the given heap More...
iterator_t *	list_iterator_create (list_t *list)
	creates an iterator from the list More...
int8_t	list_set_equality_comparator (list_t *list, list_data_comparator_f comparator)
	sets equality comparator for list More...
int8_t	list_merge (list_t *self, list_t *list)
	merge given list into self list More...

Detailed Description

linked list interface

This work is licensed under TURNSTONE OS Public License. Please read and understand latest version of Licence.

Macro Definition Documentation

___LIST_H

#define ___LIST_H   0

prevent duplicate header error macro

list_create_indexedlist

#define list_create_indexedlist

(

i

)

list_create_with_type(memory_get_heap(NULL), LIST_TYPE_INDEXEDLIST, NULL, i)

creates a indexed linked list at default heap

Parameters

[in]

i

indexer_t indexer used sorting list.

Returns

list_t

list_create_indexedlist_with_heap

#define list_create_indexedlist_with_heap	(		h,
			i
	)		list_create_with_type(memory_get_heap(h), LIST_TYPE_INDEXEDLIST, NULL, i)

creates a indexed linked list at heap

Parameters

[in]	h	memory_heap_t the heap of linked list.
[in]	i	indexer_t indexer used sorting list.

Returns

list_t

list_create_list

#define list_create_list

(

)

list_create_with_type(memory_get_heap(NULL), LIST_TYPE_LIST, NULL, NULL)

creates a normal linked list at default heap heap

Returns

list_t

list_create_list_with_heap

#define list_create_list_with_heap

(

h

)

list_create_with_type(memory_get_heap(h), LIST_TYPE_LIST, NULL, NULL)

creates a normal linked list at heap

Parameters

[in]

h

memory_heap_t the heap of linked list.

Returns

list_t

list_create_queue

#define list_create_queue

(

)

list_create_with_type(memory_get_heap(NULL), LIST_TYPE_QUEUE, NULL, NULL)

creates a queue at default heap heap

Returns

list_t

list_create_queue_with_heap

#define list_create_queue_with_heap

(

h

)

list_create_with_type(memory_get_heap(h), LIST_TYPE_QUEUE, NULL, NULL)

creates a queue at heap

Parameters

[in]

h

memory_heap_t the heap of queue.

Returns

list_t

list_create_sortedlist

#define list_create_sortedlist

(

c

)

list_create_with_type(memory_get_heap(NULL), LIST_TYPE_SORTEDLIST, c, NULL)

creates a sorted linked list at default heap

Parameters

[in]

c

list_data_comparator_f comparator used sorting list.

Returns

list_t

list_create_sortedlist_with_heap

#define list_create_sortedlist_with_heap	(		h,
			c
	)		list_create_with_type(memory_get_heap(h), LIST_TYPE_SORTEDLIST, c, NULL)

creates a sorted linked list at heap

Parameters

[in]	h	memory_heap_t the heap of linked list.
[in]	c	list_data_comparator_f comparator used sorting list.

Returns

list_t

list_create_stack

#define list_create_stack

(

)

list_create_with_type(memory_get_heap(NULL), LIST_TYPE_STACK, NULL, NULL)

creates a stack at default heap heap

Returns

list_t

list_create_stack_with_heap

#define list_create_stack_with_heap

(

h

)

list_create_with_type(memory_get_heap(h), LIST_TYPE_STACK, NULL, NULL)

creates a stack at heap

Parameters

[in]

h

memory_heap_t the heap of queue.

Returns

list_t

list_delete_at_position

#define list_delete_at_position	(		l,
			p
	)		list_delete_at(l, NULL, LIST_DELETE_AT_POSITION, p)

delete data with position from list

list_delete_at_tail

#define list_delete_at_tail

(

l

)

list_delete_at(l, NULL, LIST_DELETE_AT_TAIL, 0)

delete data at tail (end) of list

list_destroy

#define list_destroy

(

l

)

list_destroy_with_type(l, LIST_DESTROY_WITHOUT_DATA, NULL)

destroy without data macro

list_destroy_with_data

#define list_destroy_with_data

(

l

)

list_destroy_with_type(l, LIST_DESTROY_WITH_DATA, NULL)

destroy with data macro

list_duplicate_list

#define list_duplicate_list

(

l

)

list_duplicate_list_with_heap(NULL, l);

duplicate linked list with same as heap at source list

list_indexedlist_delete

#define list_indexedlist_delete	(		l,
			d
	)		list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)

delete and get data from indexed list

list_indexedlist_insert

#define list_indexedlist_insert	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_INDEXED, 0)

insert data into indexed list

LIST_INSERT_AT_ANYWHERE

#define LIST_INSERT_AT_ANYWHERE   LIST_INSERT_AT_TAIL

insert data at anywhere of list (at tail for o(1))

list_insert_at_head

#define list_insert_at_head	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_HEAD, 0)

insert data into head

list_insert_at_position

#define list_insert_at_position	(		l,
			d,
			p
	)		list_insert_at(l, d, LIST_INSERT_AT_POSITION, p)

insert data with position into list

list_list_delete

#define list_list_delete	(		l,
			d
	)		list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)

delete and get data from normal list

list_list_insert

#define list_list_insert	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_ANYWHERE, 0)

insert data into normal list

list_queue_pop

#define list_queue_pop

(

l

)

list_delete_at(l, NULL, LIST_DELETE_AT_HEAD, 0)

delete and get data from queue

list_queue_push

#define list_queue_push	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_TAIL, 0)

insert data into queue

list_sortedlist_delete

#define list_sortedlist_delete	(		l,
			d
	)		list_delete_at(l, d, LIST_DELETE_AT_FINDBY, 0)

delete and get data from sorted list

list_sortedlist_insert

#define list_sortedlist_insert	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_SORTED, 0)

insert data into sorted list

list_stack_pop

#define list_stack_pop

(

l

)

list_delete_at(l, NULL, LIST_DELETE_AT_HEAD, 0)

delete and get data from stack

list_stack_push

#define list_stack_push	(		l,
			d
	)		list_insert_at(l, d, LIST_INSERT_AT_HEAD, 0)

insert data into stack

Typedef Documentation

list_data_comparator_f

typedef int8_t(* list_data_comparator_f) (const void *data1, const void *data2)

comparing given to data

Parameters

[in]	data1
[in]	data2

Returns

<0 if, data1 lt data2, 0 if data1 eq data2, >0 if data1 gt data2

compares data1 and data2. this comparator used when linked list sorted.

list_insert_delete_at_t

typedef enum list_insert_delete_at_t list_insert_delete_at_t

linked list operation enum

inserting/deleting will be performed with this values.

list_type_t

typedef enum list_type_t list_type_t

linked list type

used only information

Enumeration Type Documentation

list_destroy_type_t

enum list_destroy_type_t

linked list destroy type

Enumerator
LIST_DESTROY_WITHOUT_DATA	destroy linked list without its data
LIST_DESTROY_WITH_DATA	destroy linked list with its data

list_insert_delete_at_t

enum list_insert_delete_at_t

linked list operation enum

inserting/deleting will be performed with this values.

Enumerator
LIST_INSERT_AT_HEAD	insert data at head of list
LIST_INSERT_AT_TAIL	insert data at tail of list
LIST_INSERT_AT_POSITION	insert data at given position (start at 0) of list
LIST_INSERT_AT_SORTED	insert data into list with sorted
LIST_INSERT_AT_INDEXED	insert data into list with indexed
LIST_DELETE_AT_HEAD	delete data from head of list
LIST_DELETE_AT_TAIL	delete data from tail of list
LIST_DELETE_AT_FINDBY	delete data from list with searching inside the list
LIST_DELETE_AT_POSITION	delete data at given position (start at 0) of list

list_type_t

enum list_type_t

linked list type

used only information

Enumerator
LIST_TYPE_LIST	normal list
LIST_TYPE_SORTEDLIST	sorted list
LIST_TYPE_QUEUE	queue
LIST_TYPE_STACK	stack
LIST_TYPE_INDEXEDLIST	indexed list
LIST_TYPE_LINKED	linked list
LIST_TYPE_ARRAY	array list

Function Documentation

list_create_with_type()

list_t * list_create_with_type	(	memory_heap_t *	heap,
		list_type_t	type,
		list_data_comparator_f	comparator,
		indexer_t	indexer
	)

linked list creator

Parameters

[in]	heap	memory_heap_t the heap where linked list will be at.
[in]	type	list_type_t linked list type
[in]	comparator	list_data_comparator_f data comparator used at sorted list
[in]	indexer	indexer_t index linked list nodes.

Returns

list_t

creates linked list with given arguments. for each type of linked list there is a macro. do not use this method directly.

if heap is null then linked list created at default heap.

list_default_data_comparator()

int8_t list_default_data_comparator	(	const void *	data1,
		const void *	data2
	)

linked list default data comparator

Parameters

data1	item 1
data2	item 2

Returns

-1 data1<data2, 0 data1=data2, 1 data1>data2

assumes data1 and data2 is size_t pointer

list_delete_at()

const void * list_delete_at	(	list_t *	list,
		const void *	data,
		list_insert_delete_at_t	where,
		size_t	position
	)

general method for inserting or deleting data from list types.

Parameters

[in]	list	the list
[in]	data	the data
[in]	where	where and how the data will be inserted
[in]	position	if data will be deleted by position

Returns

the deleted data

list_destroy_with_type()

uint8_t list_destroy_with_type	(	list_t *	list,
		list_destroy_type_t	type,
		list_item_destroyer_callback_f	destroyer
	)

destroys linked list

Parameters

[in]	list	list_t* the list to be destoyed
[in]	type	list_destroy_type_t the type with
[in]	destroyer	list_item_destroyer_callback_f destroyer callback, it frees list item

Returns

0 on success.

this method destroys only the linked list with choice of preserving data. if you do not destroy the data a memory leak will be happened if without data destroying

list_duplicate_list_with_heap()

list_t * list_duplicate_list_with_heap	(	memory_heap_t *	heap,
		list_t *	list
	)

duplicates list at the given heap

Parameters

[in]	heap	the heap where the list will be created
[in]	list	source list

Returns

a new list at heap

if heap is NULL then the new heap is same as source list's heap.

list_get_data_at_position()

const void * list_get_data_at_position	(	list_t *	list,
		size_t	position
	)

returns position of given data.

Parameters

list	list to search
position	position of data

Returns

data if found or null

list_get_data_from_listitem()

const void * list_get_data_from_listitem

(

list_item_t *

list_item

)

return data inside implicit list item type

Parameters

[in]

list_item

list item

Returns

data inside the list.

list_get_heap()

memory_heap_t * list_get_heap

(

list_t *

list

)

returns list's heap

Parameters

[in]

list

list to be get heap

Returns

memory_heap_t

list_get_position()

int8_t list_get_position	(	list_t *	list,
		const void *	data,
		size_t *	position
	)

returns position of given data.

Parameters

[in]	list	list to search
[in]	data	data to search
	[position]	position the position of data if found

Returns

0 if data found, else -1.

list_insert_at()

size_t list_insert_at	(	list_t *	list,
		const void *	data,
		list_insert_delete_at_t	where,
		size_t	position
	)

general method for inserting or deleting data from list types.

Parameters

[in]	list	the list
[in]	data	the data
[in]	where	where and how the data will be inserted
[in]	position	if data will be added by position

Returns

insertation location

list_iterator_create()

iterator_t * list_iterator_create

(

list_t *

list

)

creates an iterator from the list

Parameters

[in]

list

source list

Returns

the iterator

the returned type is implicit. see also list_iterator_internal_t iterator is created at the heap of list.

list_merge()

int8_t list_merge	(	list_t *	self,
		list_t *	list
	)

merge given list into self list

Parameters

[in]	self	source list
[in]	list	destination list

Returns

0 on success

list_set_capacity()

int8_t list_set_capacity	(	list_t *	list,
		size_t	capacity
	)

sets list's capacity

Parameters

[in]	list	list to be modified
	capacity	new capacity

Returns

0 on success

if list is null then this method returns -1. if new capacity is less than current size of list then this method returns -1. if list is not array list then this method returns -2.

list_set_comparator()

list_data_comparator_f list_set_comparator	(	list_t *	list,
		list_data_comparator_f	comparator
	)

updates list's comparator and returns the old one.

Parameters

[in]	list	list to be modified
	comparator	new comparator

Returns

old comparator

list_set_equality_comparator()

int8_t list_set_equality_comparator	(	list_t *	list,
		list_data_comparator_f	comparator
	)

sets equality comparator for list

Parameters

[in]	list	source list
[in]	comparator	comparator function

Returns

0 on success

list_size()

size_t list_size

(

const list_t *

list

)

returns item count at linked list

Parameters

[in]

list

list_t* the list whose size will be returned

Returns

size_t linked list size