list.c File Reference

Commotion double linked-list implementation. More...

#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>
#include "debug.h"
#include "obj.h"
#include "list.h"
#include "tree.h"
#include "extern/halloc.h"

Classes
struct	_listnode_t

Macros
#define	_LIST_NEXT(J)   (((_listnode_t *)J)->next)
#define	_LIST_PREV(J)   (((_listnode_t *)J)->prev)
#define	_DEFINE_LIST(L)

Typedefs
typedef _listnode_t *(*	_listiter_t )(co_obj_t *data, _listnode_t *current, void *context)

Functions
struct _listnode_t	__attribute__ ((packed))
	_DEFINE_LIST (16)
	_DEFINE_LIST (32)
co_obj_t *	co_list_get_first (const co_obj_t *list)
	return first element of given list More...
co_obj_t *	co_list_get_last (const co_obj_t *list)
	return last element of given list More...
size_t	co_list_length (co_obj_t *list)
	return length (number of objects) of given list More...
co_obj_t *	co_list_parse (co_obj_t *list, co_iter_t iter, void *context)
	process list with given iterator function More...
int	co_list_contains (co_obj_t *list, co_obj_t *item)
	determine if list contains specified item More...
int	co_list_insert_before (co_obj_t *list, co_obj_t *new_obj, co_obj_t *this_obj)
	insert new item in list before specified item More...
int	co_list_insert_before_unsafe (co_obj_t *list, co_obj_t *new_obj, co_obj_t *this_obj)
	insert new item in list before specified item without the list managing the item's memory More...
int	co_list_insert_after (co_obj_t *list, co_obj_t *new_obj, co_obj_t *this_obj)
	insert new item in list after specified item More...
int	co_list_insert_after_unsafe (co_obj_t *list, co_obj_t *new_obj, co_obj_t *this_obj)
	insert new item in list after specified item without the list managing the item's memory More...
int	co_list_prepend (co_obj_t *list, co_obj_t *new_obj)
	insert new item at beginning of list More...
int	co_list_prepend_unsafe (co_obj_t *list, co_obj_t *new_obj)
	insert new item at beginning of list without the list managing the item's memory More...
int	co_list_append (co_obj_t *list, co_obj_t *new_obj)
	insert new item at end of list More...
int	co_list_append_unsafe (co_obj_t *list, co_obj_t *new_obj)
	insert new item at end of list without the list managing the item's memory More...
co_obj_t *	co_list_delete (co_obj_t *list, co_obj_t *item)
	delete specified item from list More...
co_obj_t *	co_list_element (co_obj_t *list, const unsigned int index)
	return item at specified position in list More...
size_t	co_list_raw (char *output, const size_t olen, const co_obj_t *list)
	dump raw representation of list More...
size_t	co_list_import (co_obj_t **list, const char *input, const size_t ilen)
	import list from raw representation More...
void	co_list_print_indent (co_obj_t *list, int indent)
	print list with indent More...
int	co_list_print (co_obj_t *list)
	print list More...

Variables
_listnode_t *	prev
_listnode_t *	next
co_obj_t *	value

Detailed Description

Commotion double linked-list implementation.

Author

Josh King (jheretic), jking.nosp@m.@cha.nosp@m.mbana.nosp@m..net

Macro Definition Documentation

#define _DEFINE_LIST

(

L

)

Value:

int co_list##L##_alloc(co_obj_t *output) \
    { \
      output->_type = _list##L; \
      output->_next = NULL; \
      output->_prev = NULL; \
      output->_flags = 0; \
      output->_ref = 0; \
      ((co_list##L##_t *)output)->_len = 0; \
      return 1; \
    } \
  co_obj_t *co_list##L##_create(void) \
    { \
      co_obj_t *output = h_calloc(1, sizeof(co_list##L##_t)); \
      CHECK_MEM(output); \
      CHECK(co_list##L##_alloc(output), \
          "Failed to allocate object."); \
      return output; \
    error: \
      return NULL; \
    }

Function Documentation

int co_list_append	(	co_obj_t *	list,
		co_obj_t *	new_obj
	)

insert new item at end of list

Parameters

list	list object to process
new_obj	item to insert

References co_list_insert_after(), and co_list_length().

Referenced by _schedule(), _watch(), co_cmd_hook(), co_cmd_hook_str(), co_connect(), co_iface_add(), co_list_import(), co_loop_add_process(), co_loop_add_socket(), co_loop_add_timer(), co_profile_add(), co_request_append(), co_request_append_bin(), co_request_append_int(), co_request_append_str(), co_request_append_uint(), co_schema_register(), co_schema_register_global(), and co_socket_receive().

{
  if(co_list_length(list) == 0)
  {
    /* First item in list. */
    _listnode_t *new_node = _listnode_create(new_obj, true);
    _co_list_set_first(list, new_node);
    _co_list_set_last(list, new_node);
    hattach(new_node, list);
    _co_list_increment(list);
    return 1;
  }
  return co_list_insert_after(list, new_obj, (_co_list_get_last_node(list))->value);
}

int co_list_append_unsafe	(	co_obj_t *	list,
		co_obj_t *	new_obj
	)

insert new item at end of list without the list managing the item's memory

Parameters

list	list object to process
new_obj	item to insert

References co_list_insert_after(), and co_list_length().

{
  if(co_list_length(list) == 0)
  {
    /* First item in list. */
    _listnode_t *new_node = _listnode_create(new_obj, false);
    _co_list_set_first(list, new_node);
    _co_list_set_last(list, new_node);
    hattach(new_node, list);
    _co_list_increment(list);
    return 1;
  }
  return co_list_insert_after(list, new_obj, (_co_list_get_last_node(list))->value);
}

int co_list_contains	(	co_obj_t *	list,
		co_obj_t *	item
	)

determine if list contains specified item

Parameters

list	list object to process
item	item to search for

Referenced by co_list_insert_after(), co_list_insert_after_unsafe(), co_list_insert_before(), co_list_insert_before_unsafe(), co_loop_add_socket(), and co_socket_hangup().

{
  _listnode_t * result = _co_list_parse_node(list, _co_list_contains_i, (void *)item);
  if(result != NULL) return 1;
  return 0;
}

co_obj_t* co_list_delete	(	co_obj_t *	list,
		co_obj_t *	item
	)

delete specified item from list

Parameters

list	list object to process
item	item to delete

Referenced by _unschedule(), co_disconnect(), co_iface_remove(), co_loop_remove_process(), co_loop_remove_socket(), co_loop_remove_timer(), co_profile_remove(), and co_socket_hangup().

{
  co_obj_t *ret = NULL;
  _listnode_t *current = _co_list_find_node(list, item);
  if(current != NULL) 
  {
    if(_LIST_PREV(current) != NULL) 
      _LIST_NEXT(_LIST_PREV(current)) = _LIST_NEXT(current);
    else
      _co_list_set_first(list, _LIST_NEXT(current));

    if(_LIST_NEXT(current) != NULL) 
      _LIST_PREV(_LIST_NEXT(current)) = _LIST_PREV(current);
    else
      _co_list_set_last(list, _LIST_PREV(current));

    ret = current->value;
    hattach(current->value, NULL);
    h_free(current);
    _co_list_decrement(list);
    return ret;
  }
  return NULL;
}

co_obj_t* co_list_element	(	co_obj_t *	list,
		const unsigned int	index
	)

return item at specified position in list

Parameters

list	list object to process
index	number of item to return

Referenced by co_call(), dispatcher_cb(), and olsrd_mdp_sign().

{
  CHECK(IS_LIST(list), "Not a list object.");
  _listnode_t *next = _co_list_get_first_node(list);
  unsigned int i = 0;
  if(next != NULL)
  {
    for(i = 0; i < index; i++)
    {
      next = _LIST_NEXT(next);
      if(next == NULL) break;
    }
  }
  CHECK(i == index, "List index not found.");
  return next->value;
error:
  return NULL;
}

co_obj_t* co_list_get_first

(

const co_obj_t *

list

)

return first element of given list

Parameters

list	list object

{
  return (_co_list_get_first_node(list))->value;
}

co_obj_t* co_list_get_last

(

const co_obj_t *

list

)

return last element of given list

Parameters

list	list object

{
  return (_co_list_get_last_node(list))->value;
}

size_t co_list_import	(	co_obj_t **	list,
		const char *	input,
		const size_t	ilen
	)

import list from raw representation

Parameters

list	target pointer to new list object
input	input buffer
ilen	length of input buffer

References co_list_append(), co_list_import(), and co_tree_import().

Referenced by co_call(), co_list_import(), co_tree_import(), and dispatcher_cb().

{
  size_t length = 0, olen = 0, read = 0;
  co_obj_t *obj = NULL;
  const char *cursor = input;
  switch((uint8_t)input[0])
  {
    case _list16:
      length = *((uint16_t *)(input + 1));
      *list = co_list16_create();
      cursor += sizeof(uint16_t) + 1;
      read = sizeof(uint16_t) + 1;
      break;
    case _list32:
      length = *((uint32_t *)(input + 1));
      *list = co_list32_create();
      cursor += sizeof(uint32_t) + 1;
      read = sizeof(uint32_t) + 1;
      break;
    default:
      SENTINEL("Not a list.");
      break;
  }
  for(int i = 0; (i < length && read <= ilen); i++)
  {
    if(((uint8_t)cursor[0] == _list16) || ((uint8_t)cursor[0] == _list32))
    {
      olen = co_list_import(&obj, cursor, ilen - read);
    }
    else if(((uint8_t)cursor[0] == _tree16) || ((uint8_t)cursor[0] == _tree32))
    {
      olen = co_tree_import(&obj, cursor, ilen - read);
    }
    else olen = co_obj_import(&obj, cursor, ilen - read, 0);
    CHECK(olen > 0, "Failed to import object.");
    cursor +=olen;
    read += olen;
    CHECK(co_list_append(*list, obj), "Failed to add object to list.");
  }
  return read;
error:
  return -1;
}

int co_list_insert_after	(	co_obj_t *	list,
		co_obj_t *	new_obj,
		co_obj_t *	this_obj
	)

insert new item in list after specified item

Parameters

list	list object to process
new_obj	item to insert
this_obj	item to insert after

References co_list_contains().

Referenced by co_list_append(), and co_list_append_unsafe().

{
  CHECK(IS_LIST(list), "Not a list object.");
  _listnode_t *this_node = _co_list_find_node(list, this_obj);
  CHECK(this_node != NULL, "Unable to find existing node in \
specified list.");
  CHECK(!co_list_contains(list, new_obj), "New node already in specified \
list.");
  _listnode_t *adjacent = _LIST_NEXT(this_node);
  _listnode_t *new_node = _listnode_create(new_obj, true);
  hattach(new_node, list);
  if(adjacent == NULL)
  {
    /* Last in list. */
    _co_list_set_last(list, new_node);
  }
  else
  {
    _LIST_PREV(adjacent) = new_node;
    _LIST_NEXT(new_node) = adjacent;
  }
  _LIST_PREV(new_node) = this_node;
  _LIST_NEXT(this_node) = new_node;
  _co_list_increment(list);
  return 1;
error:
  return 0;
}

int co_list_insert_after_unsafe	(	co_obj_t *	list,
		co_obj_t *	new_obj,
		co_obj_t *	this_obj
	)

insert new item in list after specified item without the list managing the item's memory

Parameters

list	list object to process
new_obj	item to insert
this_obj	item to insert after

References co_list_contains().

{
  CHECK(IS_LIST(list), "Not a list object.");
  _listnode_t *this_node = _co_list_find_node(list, this_obj);
  CHECK(this_node != NULL, "Unable to find existing node in \
specified list.");
  CHECK(!co_list_contains(list, new_obj), "New node already in specified \
list.");
  _listnode_t *adjacent = _LIST_NEXT(this_node);
  _listnode_t *new_node = _listnode_create(new_obj, false);
  hattach(new_node, list);
  if(adjacent == NULL)
  {
    /* Last in list. */
    _co_list_set_last(list, new_node);
  }
  else
  {
    _LIST_PREV(adjacent) = new_node;
    _LIST_NEXT(new_node) = adjacent;
  }
  _LIST_PREV(new_node) = this_node;
  _LIST_NEXT(this_node) = new_node;
  _co_list_increment(list);
  return 1;
error:
  return 0;
}

int co_list_insert_before	(	co_obj_t *	list,
		co_obj_t *	new_obj,
		co_obj_t *	this_obj
	)

insert new item in list before specified item

Parameters

list	list object to process
new_obj	item to insert
this_obj	item to insert before

References co_list_contains().

Referenced by co_list_prepend(), co_list_prepend_unsafe(), and co_loop_add_timer().

{
  CHECK(IS_LIST(list), "Not a list object.");
  _listnode_t *this_node = _co_list_find_node(list, this_obj);
  CHECK(this_node != NULL, "Unable to find existing node in \
specified list.");
  CHECK(!co_list_contains(list, new_obj), "New node already in specified \
list.");
  _listnode_t *adjacent = _LIST_PREV(this_node);
  _listnode_t *new_node = _listnode_create(new_obj, true);
  hattach(new_node, list);
  if(adjacent == NULL)
  {
    /* First in list. */
    _co_list_set_first(list, new_node);
  }
  else
  {
    _LIST_NEXT(adjacent) = new_node;
    _LIST_PREV(new_node) = adjacent;
  }
  _LIST_NEXT(new_node) = this_node;
  _LIST_PREV(this_node) = new_node;
  _co_list_increment(list);
  return 1;
error:
  return 0;
}

int co_list_insert_before_unsafe	(	co_obj_t *	list,
		co_obj_t *	new_obj,
		co_obj_t *	this_obj
	)

insert new item in list before specified item without the list managing the item's memory

Parameters

list	list object to process
new_obj	item to insert
this_obj	item to insert before

References co_list_contains().

{
  CHECK(IS_LIST(list), "Not a list object.");
  _listnode_t *this_node = _co_list_find_node(list, this_obj);
  CHECK(this_node != NULL, "Unable to find existing node in \
specified list.");
  CHECK(!co_list_contains(list, new_obj), "New node already in specified \
list.");
  _listnode_t *adjacent = _LIST_PREV(this_node);
  _listnode_t *new_node = _listnode_create(new_obj, false);
  hattach(new_node, list);
  if(adjacent == NULL)
  {
    /* First in list. */
    _co_list_set_first(list, new_node);
  }
  else
  {
    _LIST_NEXT(adjacent) = new_node;
    _LIST_PREV(new_node) = adjacent;
  }
  _LIST_NEXT(new_node) = this_node;
  _LIST_PREV(this_node) = new_node;
  _co_list_increment(list);
  return 1;
error:
  return 0;
}

size_t co_list_length

(

co_obj_t *

list

)

return length (number of objects) of given list

Parameters

list	list object

Referenced by co_list_append(), co_list_append_unsafe(), co_list_prepend(), co_list_prepend_unsafe(), and co_plugins_shutdown().

{ 
  return _co_list_change_length(list, 0);
}

co_obj_t* co_list_parse	(	co_obj_t *	list,
		co_iter_t	iter,
		void *	context
	)

process list with given iterator function

Parameters

list	list object to process
iter	iterator function
context	additional arguments to iterator

Referenced by _schedule(), _unschedule(), _watch(), co_iface_get(), co_iface_profile(), co_iface_remove(), co_list_print_indent(), co_loop_add_socket(), co_loop_add_timer(), co_loop_destroy(), co_loop_get_socket(), co_loop_get_timer(), co_loop_remove_process(), co_loop_remove_socket(), co_loop_remove_timer(), co_plugins_shutdown(), co_plugins_start(), co_profile_find(), co_profiles_process(), co_shutdown(), co_socket_destroy(), and serval_socket_cb().

{
  co_obj_t *result = NULL;
  CHECK_MEM(list);
  CHECK(IS_LIST(list), "Not a list object.");
  //co_obj_t *next = _LIST_NEXT(list);
  _listnode_t *next = _co_list_get_first_node(list);
  while(next != NULL && result == NULL)
  {
    result = iter(list, next->value, context);
    next = _LIST_NEXT(next);
  }
  return result;
error:
  return result;
}

int co_list_prepend	(	co_obj_t *	list,
		co_obj_t *	new_obj
	)

insert new item at beginning of list

Parameters

list	list object to process
new_obj	item to insert

References co_list_insert_before(), and co_list_length().

{
  if(co_list_length(list) == 0)
  {
    /* First item in list. */
    _listnode_t *new_node = _listnode_create(new_obj, true);
    _co_list_set_first(list, new_node);
    _co_list_set_last(list, new_node);
    hattach(new_node, list);
    _co_list_increment(list);
    return 1;
  }
  return co_list_insert_before(list, new_obj, (_co_list_get_first_node(list))->value);
}

int co_list_prepend_unsafe	(	co_obj_t *	list,
		co_obj_t *	new_obj
	)

insert new item at beginning of list without the list managing the item's memory

Parameters

list	list object to process
new_obj	item to insert

References co_list_insert_before(), and co_list_length().

{
  if(co_list_length(list) == 0)
  {
    /* First item in list. */
    _listnode_t *new_node = _listnode_create(new_obj, false);
    _co_list_set_first(list, new_node);
    _co_list_set_last(list, new_node);
    hattach(new_node, list);
    _co_list_increment(list);
    return 1;
  }
  return co_list_insert_before(list, new_obj, (_co_list_get_first_node(list))->value);
}

int co_list_print

(

co_obj_t *

list

)

print list

Parameters

list	list object to print

References co_list_print_indent().

{
  CHECK_MEM(list);

  co_list_print_indent(list,0);
  
  return 1;
error:
  return 0;
}

void co_list_print_indent	(	co_obj_t *	list,
		int	indent
	)

print list with indent

Parameters

list	list object to print
indent	level of indent

References co_list_parse().

Referenced by co_list_print().

{
  for (int i = 0; i < indent; i++) printf("  ");
  printf("[\n");
  indent++;
  co_list_parse(list, _co_list_print_i, &indent);
  indent--;
  for (int i = 0; i < indent; i++) printf("  ");
  printf("]");
  if (!indent) printf("\n");
}

size_t co_list_raw	(	char *	output,
		const size_t	olen,
		const co_obj_t *	list
	)

dump raw representation of list

Parameters

output	output buffer
olen	length of output buffer
list	list object to process

References co_list_raw(), and co_tree_raw().

Referenced by co_list_raw(), co_request_alloc(), and co_response_alloc().

{
  size_t written = 0, read = 0;
  char *in = NULL;
  char *out = output;
  switch(CO_TYPE(list))
  {
    case _list16:
      memmove(out, &(list->_type), sizeof(uint8_t));
      out += sizeof(uint8_t);
      memmove(out, &(((co_list16_t *)list)->_len), sizeof(uint16_t));
      out += sizeof(uint16_t);
      written = sizeof(uint8_t) + sizeof(uint16_t);
      break;
    case _list32:
      memmove(out, &(list->_type), sizeof(uint8_t));
      out += sizeof(uint8_t);
      memmove(out, &(((co_list32_t *)list)->_len), sizeof(uint32_t));
      out += sizeof(uint32_t);
      written = sizeof(uint8_t) + sizeof(uint32_t);
      break;
    default:
      SENTINEL("Not a list object.");
      break;
  }
  _listnode_t *next = _co_list_get_first_node(list);
  while(next != NULL && next->value != NULL && written <= olen)
  {
    if((CO_TYPE(next->value) == _list16) || (CO_TYPE(next->value) == _list32))
    {
        read = co_list_raw(out, olen - written, next->value);
        CHECK(read >= 0, "Failed to dump object.");
        CHECK(read + written < olen, "Data too large for buffer.");
    }
    else if ((CO_TYPE(next->value) == _tree16) || (CO_TYPE(next->value) == _tree32))
    {
        read = co_tree_raw(out, olen - written, next->value);
        CHECK(read >= 0, "Failed to dump object.");
        CHECK(read + written < olen, "Data too large for buffer.");
    }
    else
    {
        read = co_obj_raw(&in, next->value);
        CHECK(read >= 0, "Failed to dump object.");
        CHECK(read + written < olen, "Data too large for buffer.");
        memmove(out, in, read);
    }
    DEBUG("List in: %s, read: %d", in, (int)read);
    written += read;
    out += read;
    next = _LIST_NEXT(next);
  }
  return written;
error:
  return -1;
  
}