qlist.c File Reference

Doubly Linked-list implementation. More...

Go to the source code of this file.

Functions
qlist_t *	qlist (int options)
	Create new qlist_t linked-list container.
size_t	qlist_setsize (qlist_t *list, size_t max)
	qlist->setsize(): Limit maximum number of elements allowed in this list.
bool	qlist_addfirst (qlist_t *list, const void *data, size_t size)
	qlist->addfirst(): Inserts an element at the beginning of this list.
bool	qlist_addlast (qlist_t *list, const void *data, size_t size)
	qlist->addlast(): Appends an element to the end of this list.
bool	qlist_addat (qlist_t *list, int index, const void *data, size_t size)
	qlist->addat(): Inserts an element at the specified position in this list.
void *	qlist_getfirst (qlist_t *list, size_t *size, bool newmem)
	qlist->getfirst(): Returns the first element in this list.
void *	qlist_getlast (qlist_t *list, size_t *size, bool newmem)
	qlist->getlast(): Returns the last element in this list.
void *	qlist_getat (qlist_t *list, int index, size_t *size, bool newmem)
	qlist->getat(): Returns the element at the specified position in this list.
void *	qlist_popfirst (qlist_t *list, size_t *size)
	qlist->popfirst(): Returns and removes the first element in this list.
void *	qlist_poplast (qlist_t *list, size_t *size)
	qlist->poplast(): Returns and removes the last element in this list.
void *	qlist_popat (qlist_t *list, int index, size_t *size)
	qlist->popat(): Returns and removes the element at the specified position in this list.
bool	qlist_removefirst (qlist_t *list)
	qlist->removefirst(): Removes the first element in this list.
bool	qlist_removelast (qlist_t *list)
	qlist->removelast(): Removes the last element in this list.
bool	qlist_removeat (qlist_t *list, int index)
	qlist->removeat(): Removes the element at the specified position in this list.
bool	qlist_getnext (qlist_t *list, qlist_obj_t *obj, bool newmem)
	qlist->getnext(): Get next element in this list.
size_t	qlist_size (qlist_t *list)
	qlist->size(): Returns the number of elements in this list.
size_t	qlist_datasize (qlist_t *list)
	qlist->size(): Returns the sum of total element size.
void	qlist_reverse (qlist_t *list)
	qlist->reverse(): Reverse the order of elements.
void	qlist_clear (qlist_t *list)
	qlist->clear(): Removes all of the elements from this list.
void *	qlist_toarray (qlist_t *list, size_t *size)
	qlist->toarray(): Returns the serialized chunk containing all the elements in this list.
char *	qlist_tostring (qlist_t *list)
	qlist->tostring(): Returns a string representation of this list, containing string representation of each element.
bool	qlist_debug (qlist_t *list, FILE *out)
	qlist->debug(): Prints stored elements for debugging purposes.
void	qlist_lock (qlist_t *list)
	qlist->lock(): Enters critical section.
void	qlist_unlock (qlist_t *list)
	qlist->unlock(): Leaves critical section.
void	qlist_free (qlist_t *list)
	qlist->free(): Free qlist_t.

Detailed Description

Doubly Linked-list implementation.

qlist container is a doubly Linked-List implementation. qlist provides uniformly named methods to add, get, pop and remove an element at the beginning and end of the list. These operations allow qlist to be used as a stack, queue, or double-ended queue.

[Conceptional Data Structure Diagram]
 
last~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
                                                        |
        +-----------+  doubly  +-----------+  doubly  +-|---------+
first~~~|~>   0   <~|~~~~~~~~~~|~>   1   <~|~~~~~~~~~~|~>   N     |
        +-----|-----+  linked  +-----|-----+  linked  +-----|-----+
              |                      |                      |
        +-----v---------------+      |                +-----v-----+
        | DATA A              |      |                | DATA N    |
        +---------------------+      |                +-----------+
               +---------------------v------------------+
               | DATA B                                 |
               +----------------------------------------+

// create a list.
qlist_t *list = qlist(QLIST_THREADSAFE);
 
// insert elements
list->addlast(list, "e1", sizeof("e1"));
list->addlast(list, "e2", sizeof("e2"));
list->addlast(list, "e3", sizeof("e3"));
 
// get
char *e1 = (char*)list->getfirst(list, NULL, true));    // allocated
char *e3  = (char*)list->getat(list, -1, NULL, false)); // no malloc
(...omit...)
free(e1);
 
// pop (get and remove)
char *e2 = (char*)list->popat(list, 1, NULL)); // get allocated copy
(...omit...)
free(e2);
 
// debug output
list->debug(list, stdout, true);
 
// traversal
qlist_obj_t obj;
memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
list->lock(list);
while (list->getnext(list, &obj, false) == true) {
  printf("DATA=%s, SIZE=%zu\n", (char*)obj.data, obj.size);
}
list->unlock(list);
 
// free object
list->free(list);

Definition in file qlist.c.

Function Documentation

qlist()

qlist_t * qlist

(

int

options

)

Create new qlist_t linked-list container.

Parameters

options

combination of initialization options.

Returns

pointer to allocated qlist_t container on success, or NULL on failure.

Return values

errno

will be set in error condition. -ENOMEM : Memory allocation failure.

qlist_t *list = qlist(0);

Note

Available options:

• QLIST_THREADSAFE - make it thread-safe.

Definition at line 124 of file qlist.c.

qlist_setsize()

size_t qlist_setsize	(	qlist_t *	list,
		size_t	max )

qlist->setsize(): Limit maximum number of elements allowed in this list.

Parameters

list	qlist_t container pointer.
max	maximum number of elements. 0 means no limit.

Returns

previous maximum number.

Note

The default maximum number of elements is unlimited.

Definition at line 190 of file qlist.c.

qlist_addfirst()

bool qlist_addfirst	(	qlist_t *	list,
		const void *	data,
		size_t	size )

qlist->addfirst(): Inserts an element at the beginning of this list.

Parameters

list	qlist_t container pointer.
data	a pointer which points data memory.
size	size of the data.

Returns

true on success, otherwise false.

Return values

errno

will be set in error condition. ENOBUFS : List full. Only happens when this list has set to have limited number of elements. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

// create a sample object.
struct my_obj obj;
 
// create a list and add the sample object.
qlist_t *list = qlist();
list->addfirst(list, &obj, sizeof(struct my_obj));

Definition at line 221 of file qlist.c.

qlist_addlast()

bool qlist_addlast	(	qlist_t *	list,
		const void *	data,
		size_t	size )

qlist->addlast(): Appends an element to the end of this list.

Parameters

list	qlist_t container pointer.
data	a pointer which points data memory.
size	size of the data.

Returns

true on success, otherwise false.

Return values

errno

will be set in error condition. ENOBUFS : List full. Only happens when this list has set to have limited number of elements. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Definition at line 239 of file qlist.c.

qlist_addat()

bool qlist_addat	(	qlist_t *	list,
		int	index,
		const void *	data,
		size_t	size )

qlist->addat(): Inserts an element at the specified position in this list.

Parameters

list	qlist_t container pointer.
index	index at which the specified element is to be inserted.
data	a pointer which points data memory.
size	size of the data.

Returns

true on success, otherwise false.

Return values

errno

will be set in error condition. ENOBUFS : List full. Only happens when this list has set to have limited number of elements. ERANGE : Index out of range. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

                   first           last      new
Linked-list        [ A ]<=>[ B ]<=>[ C ]?==?[   ]
(positive index)     0       1       2        3
(negative index)    -3      -2      -1

qlist_t *list = qlist();
list->addat(list, 0, &obj, sizeof(obj));  // same as addfirst().
list->addat(list, -1, &obj, sizeof(obj)); // same as addlast().

Note

Index starts from 0.

Definition at line 276 of file qlist.c.

qlist_getfirst()

void * qlist_getfirst	(	qlist_t *	list,
		size_t *	size,
		bool	newmem )

qlist->getfirst(): Returns the first element in this list.

Parameters

list	qlist_t container pointer.
size	if size is not NULL, element size will be stored.
newmem	whether or not to allocate memory for the element.

Returns

pointer to element on success, or NULL on failure.

Return values

errno

will be set in error condition. ENOENT : List is empty. ENOMEM : Memory allocation failure.

size_t size;
void *data = list->getfirst(list, &size, true);
if (data != NULL) {
  (...omit...)
  free(data);
}

Definition at line 389 of file qlist.c.

qlist_getlast()

void * qlist_getlast	(	qlist_t *	list,
		size_t *	size,
		bool	newmem )

qlist->getlast(): Returns the last element in this list.

Parameters

list	qlist_t container pointer.
size	if size is not NULL, element size will be stored.
newmem	whether or not to allocate memory for the element.

Returns

pointer to element on success, or NULL on failure.

Return values

errno

will be set in error condition. ENOENT : List is empty. ENOMEM : Memory allocation failure.

Definition at line 405 of file qlist.c.

qlist_getat()

void * qlist_getat	(	qlist_t *	list,
		int	index,
		size_t *	size,
		bool	newmem )

qlist->getat(): Returns the element at the specified position in this list.

Parameters

list	qlist_t container pointer.
index	index at which the specified element is to be inserted
size	if size is not NULL, element size will be stored.
newmem	whether or not to allocate memory for the element.

Returns

pointer to element on success, or NULL on failure.

Return values

errno
errno	will be set in error condition. -ERANGE : Index out of range. -ENOMEM : Memory allocation failure.

                   first           last
Linked-list        [ A ]<=>[ B ]<=>[ C ]
(positive index)     0       1       2
(negative index)    -3      -2      -1

Note

Negative index can be used for addressing an element from the end in this stack. For example, index -1 is same as getlast() and index 0 is same as getfirst();

Definition at line 436 of file qlist.c.

qlist_popfirst()

void * qlist_popfirst	(	qlist_t *	list,
		size_t *	size )

qlist->popfirst(): Returns and removes the first element in this list.

Parameters

list	qlist_t container pointer.
size	if size is not NULL, element size will be stored.

Returns

pointer to allocated element on success, or NULL on failure.

Return values

errno

will be set in error condition. -ENOENT : List is empty. -ENOMEM : Memory allocation failure.

Definition at line 451 of file qlist.c.

qlist_poplast()

void * qlist_poplast	(	qlist_t *	list,
		size_t *	size )

qlist->poplast(): Returns and removes the last element in this list.

Parameters

list	qlist_t container pointer.
size	if size is not NULL, element size will be stored.

Returns

pointer to allocated element on success, or NULL on failure.

Return values

errno

will be set in error condition. -ENOENT : List is empty. -ENOMEM : Memory allocation failure.

Definition at line 466 of file qlist.c.

qlist_popat()

void * qlist_popat	(	qlist_t *	list,
		int	index,
		size_t *	size )

qlist->popat(): Returns and removes the element at the specified position in this list.

Parameters

list	qlist_t container pointer.
index	index of the element to pop
size	if size is not NULL, element size will be stored.

Returns

pointer to allocated element on success, or NULL on failure.

Return values

errno

will be set in error condition. -ERANGE : Index out of range. -ENOMEM : Memory allocation failure.

                   first           last
Linked-list        [ A ]<=>[ B ]<=>[ C ]
(positive index)     0       1       2
(negative index)    -3      -2      -1

Note

Negative index can be used for addressing an element from the end in this stack. For example, index -1 is same as poplast() and index 0 is same as popfirst();

Definition at line 495 of file qlist.c.

qlist_removefirst()

bool qlist_removefirst

(

qlist_t *

list

)

qlist->removefirst(): Removes the first element in this list.

Parameters

list	qlist_t container pointer.

Returns

a number of removed objects.

Return values

errno

will be set in error condition. -ENOENT : List is empty.

Definition at line 508 of file qlist.c.

qlist_removelast()

bool qlist_removelast

(

qlist_t *

list

)

qlist->removelast(): Removes the last element in this list.

Parameters

list	qlist_t container pointer.

Returns

a number of removed objects.

Return values

errno

will be set in error condition. -ENOENT : List is empty.

Definition at line 521 of file qlist.c.

qlist_removeat()

bool qlist_removeat	(	qlist_t *	list,
		int	index )

qlist->removeat(): Removes the element at the specified position in this list.

Parameters

list	qlist_t container pointer.
index	index at which the specified element is to be removed.

Returns

a number of removed objects.

Return values

errno

will be set in error condition. -ERANGE : Index out of range.

Definition at line 536 of file qlist.c.

qlist_getnext()

bool qlist_getnext	(	qlist_t *	list,
		qlist_obj_t *	obj,
		bool	newmem )

qlist->getnext(): Get next element in this list.

Parameters

list	qlist_t container pointer.
obj	found data will be stored in this structure
newmem	whether or not to allocate memory for the element.

Returns

true if found otherwise false

Return values

errno

will be set in error condition. -ENOENT : No next element. -ENOMEM : Memory allocation failure.

Note

obj should be initialized with 0 by using memset() before first call. If newmem flag is true, user should free obj.name and obj.data resources.

qlist_t *list = qlist();
(...add data into list...)
 
qlist_obj_t obj;
memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
list->lock(list);   // can be omitted in single thread model.
while (list->getnext(list, &obj, false) == true) {
 printf("DATA=%s, SIZE=%zu\n", (char*)obj.data, obj.size);
}
list->unlock(list); // release lock.

Definition at line 583 of file qlist.c.

qlist_size()

size_t qlist_size

(

qlist_t *

list

)

qlist->size(): Returns the number of elements in this list.

Parameters

list	qlist_t container pointer.

Returns

the number of elements in this list.

Definition at line 631 of file qlist.c.

qlist_datasize()

size_t qlist_datasize

(

qlist_t *

list

)

qlist->size(): Returns the sum of total element size.

Parameters

list	qlist_t container pointer.

Returns

the sum of total element size.

Definition at line 642 of file qlist.c.

qlist_reverse()

void qlist_reverse

(

qlist_t *

list

)

qlist->reverse(): Reverse the order of elements.

Parameters

list	qlist_t container pointer.

Definition at line 651 of file qlist.c.

qlist_clear()

void qlist_clear

(

qlist_t *

list

)

qlist->clear(): Removes all of the elements from this list.

Parameters

list	qlist_t container pointer.

Definition at line 673 of file qlist.c.

qlist_toarray()

void * qlist_toarray	(	qlist_t *	list,
		size_t *	size )

qlist->toarray(): Returns the serialized chunk containing all the elements in this list.

Parameters

list	qlist_t container pointer.
size	if size is not NULL, chunk size will be stored.

Returns

an allocated pointer, or NULL if the list is empty.

Return values

errno

will be set in error condition. -ENOENT : List is empty. -ENOMEM : Memory allocation failure.

Definition at line 702 of file qlist.c.

qlist_tostring()

char * qlist_tostring

(

qlist_t *

list

)

qlist->tostring(): Returns a string representation of this list, containing string representation of each element.

Parameters

list	qlist_t container pointer.

Returns

an allocated string, or NULL if the list is empty.

Return values

errno

will be set in error condition. -ENOENT : List is empty. -ENOMEM : Memory allocation failure.

Note

Return string is always terminated by '\0'.

Definition at line 746 of file qlist.c.

qlist_debug()

bool qlist_debug	(	qlist_t *	list,
		FILE *	out )

qlist->debug(): Prints stored elements for debugging purposes.

Parameters

list	qlist_t container pointer.
out	output stream such as stdout or stderr.

Returns

true on success, otherwise false.

Return values

errno

will be set in error condition. -EIO : Invalid output stream.

Definition at line 787 of file qlist.c.

qlist_lock()

void qlist_lock

(

qlist_t *

list

)

qlist->lock(): Enters critical section.

Parameters

list	qlist_t container pointer.

Note

From user side, normally locking operation is only needed when traverse all elements using qlist->getnext().

Definition at line 815 of file qlist.c.

qlist_unlock()

void qlist_unlock

(

qlist_t *

list

)

qlist->unlock(): Leaves critical section.

Parameters

list	qlist_t container pointer.

Definition at line 824 of file qlist.c.

qlist_free()

void qlist_free

(

qlist_t *

list

)

qlist->free(): Free qlist_t.

Parameters

list	qlist_t container pointer.

Definition at line 833 of file qlist.c.