void dlist::remove(void *item)
{
   void *xitem;
   dlink *ilink = get_link(item);   /* item's link */
   if (item == head) {
      head = ilink->next;
      if (head) {
         set_prev(head, NULL);
      }
      if (item == tail) {
         tail = ilink->prev;
      }
   } else if (item == tail) {
      tail = ilink->prev;
      if (tail) {
         set_next(tail, NULL);
      }
   } else {
      xitem = ilink->next;
      set_prev(xitem, ilink->prev);
      xitem = ilink->prev;
      set_next(xitem, ilink->next);
   }
   num_items--;
   if (num_items == 0) {
      head = tail = NULL;
   }
}

static void append_and_clear( los_list_t *left, los_list_t *right )
{
  word *left_first = next( left->header );
  word *left_last = prev( left->header );
  word *right_first = next( right->header );
  word *right_last = prev( right->header );

  if (right_first == right->header) return;   /* Right is empty */

  /* Splice in the right list */
  if (left_first != left->header) {           /* Left is nonempty  */
    set_next( left_last, right_first );       /* Join lists */
    set_prev( right_first, left_last );
  }
  else {			              /* Left is empty */
    set_next( left->header, right_first );    /* Move right to left */
    set_prev( right_first, left->header );
  }

  /* Complete circle */
  set_next( right_last, left->header );
  set_prev( left->header, right_last );

  left->bytes += right->bytes;
  clear_list( right );
}

int add_at_first(linkedlist_t* _list, void* data)
{
    linkedlist_t* list = (linkedlist_t*) _list;
    node* n, *slider;

    if(list->size == 0)
    {
        return add_at_last(list, data);
    }
    else if(list->size == 1)
    {
        n = node_new(data);
        set_head(list, n);
        set_prev(get_tail(list), n);
        set_next(n, get_tail(list));
        list->size++;
    }
    else // list->size > 1
    {
        slider = get_head(list);
        n = node_new(data);
        set_next(n, slider);
        set_prev(slider, n);
        set_head(list, n);
        list->size++;
    }
    return list->size;
}

struct bstree_node *bstree_insert(struct bstree_node *node, struct bstree *tree)
{
	struct bstree_node *key, *parent;
	int is_left;

	key = do_lookup(node, tree, &parent, &is_left);
	if (key)
		return key;

	if (!parent) {
		INIT_NODE(node);
		tree->root = tree->first = tree->last = node;
		return NULL;
	}
	if (is_left) {
		if (parent == tree->first)
			tree->first = node;
		set_prev(get_prev(parent), node);
		set_next(parent, node);
		set_left(node, parent);
	} else {
		if (parent == tree->last)
			tree->last = node;
		set_prev(parent, node);
		set_next(get_next(parent), node);
		set_right(node, parent);
	}
	return NULL;
}

void* linkedlist_remove(linkedlist _list, void* data)
{
    linkedlist_t* list = (linkedlist_t*) _list;
    node* n = find_by_data(list, data);

    if(NULL == n)
        return NULL;

    if(is_first(list, n)) // at the first
    {
        if(is_last(list, n)) // only one exists
        {
            set_head(list, NULL);
            set_tail(list, NULL);
        }
        else // one or more exist
        {
            set_head(list, get_next(n));
            set_prev(n, NULL);
        }
    }
    else if(is_last((linkedlist_t*)_list, n))
    {
        set_next(get_prev(n), NULL);
        set_tail(list, get_prev(n));
    }
    else
    {
        set_prev(get_next(n), get_prev(n));
        set_next(get_prev(n), get_next(n));
    }
    list->size--;
    free(n);
    return data;
}

static int
lru_load(const br_ssl_session_cache_class **ctx,
	br_ssl_server_context *server_ctx,
	br_ssl_session_parameters *params)
{
	br_ssl_session_cache_lru *cc;
	unsigned char id[SESSION_ID_LEN];
	uint32_t x;

	(void)server_ctx;
	cc = (br_ssl_session_cache_lru *)ctx;
	if (!cc->init_done) {
		return 0;
	}
	mask_id(cc, params->session_id, id);
	x = find_node(cc, id, NULL);
	if (x != ADDR_NULL) {
		unsigned version;

		version = br_dec16be(cc->store + x + VERSION_OFF);
		if (version == 0) {
			/*
			 * Entry is disabled, we pretend we did not find it.
			 * Notably, we don't move it to the front of the
			 * LRU list.
			 */
			return 0;
		}
		params->version = version;
		params->cipher_suite = br_dec16be(
			cc->store + x + CIPHER_SUITE_OFF);
		memcpy(params->master_secret,
			cc->store + x + MASTER_SECRET_OFF,
			MASTER_SECRET_LEN);
		if (x != cc->head) {
			/*
			 * Found node is not at list head, so move
			 * it to the head.
			 */
			uint32_t p, n;

			p = get_prev(cc, x);
			n = get_next(cc, x);
			set_next(cc, p, n);
			if (n == ADDR_NULL) {
				cc->tail = p;
			} else {
				set_prev(cc, n, p);
			}
			set_prev(cc, cc->head, x);
			set_next(cc, x, cc->head);
			set_prev(cc, x, ADDR_NULL);
			cc->head = x;
		}
		return 1;
	}
	return 0;
}

static void remove( word *w )
{
  word *n = next( w );
  word *p = prev( w );

  set_next( p, n );
  set_prev( n, p );
  set_next( w, 0 );
  set_prev( w, 0 );
}

static void insert_at_end( word *w, los_list_t *list )
{
  word *h, *last;

  h = list->header;
  last = prev( h );
  set_next( last, w );         /* add links from last end */
  set_prev( w, last );
  set_next( w, h );            /* add links from header */
  set_prev( h, w );
  list->bytes += size( w );
}

/*
 * Append an item to the list
 */
void dlist::prepend(void *item)
{
   set_next(item, head);
   set_prev(item, NULL);
   if (head) {
      set_prev(head, item);
   }
   head = item;
   if (tail == NULL) {                /* if empty list, */
      tail = item;                    /* item is tail too */
   }
   num_items++;
}

static bool
coalesce_blocks(void *ptr1, void *ptr2)
{
	void *tmpptr = Min(ptr1, ptr2);
	Size new_size;
	void *next;

	ptr2 = Max(ptr1, ptr2);
	ptr1 = tmpptr;

	if (get_end(ptr1) != get_header(ptr2))
		return false;

	Assert(get_next(ptr1) == ptr2);
	Assert(!is_allocated(ptr1));
	Assert(!is_allocated(ptr2));

	new_size = get_size(ptr1) + BLOCK_SIZE(get_size(ptr2));
	get_header(ptr1)->size = new_size;
	/* Mark ptr2 as no longer an ICE BOODA. */
	get_header(ptr2)->magic = 0;

	next = get_next(ptr2);
	set_next(ptr1, next);

	if (next)
		set_prev(next, ptr1);

	return true;
}

/* Deze methode wijst length woorden toe aan een proces. De overgebleven
 * woorden worden gezien als nieuw vrij blok. */
int split_block(long index, long length){
	long blockleng = get_length(index);
	long newidx = index + length + ADMIN_SIZE;
	long newleng = blockleng - length - ADMIN_SIZE;
	
	if(blockleng < length + ADMIN_SIZE + 1){
		/* Geen ruimte voor een nieuw blok van minimaal 1 woord. */
		return -1;
	}
	
	/* Maak het nieuwe blok. Plaats deze na 'length' woorden. */
	new_block(newidx, newleng, index, get_next(index));
	
	/* Als het huidige blok een volgende blok heeft moet de pointer van
	 * dat blok welke naar zijn vorige blok wijst naar het nieuwe blok
	 * gezet worden.*/
	if(get_next(index) != 0){
		set_prev(get_next(index), newidx);
	}
	/* Zet het volgende blok van het huidige blok naar het nieuwe blok. */
	set_next(index, newidx);
	
	/* Zet de length van het huidige blok en zet hem op toegewezen. */
	set_length(index, length);
	set_free(index, 0);
	
	/* Verhoog het aantal loze woorden. */
	mem[1] += ADMIN_SIZE;
	/* Verhoog het aantal toegewezen woorden. */
	mem[0] += length;
	
	/* De index waar begonnen mag worden met schrijven is het blok index
	 * plus de lengte van de administratie. */
	return index + ADMIN_SIZE;
}

/* Deze methode zet het blok op index op vrij, indien mogelijk fuseert het
 * met omringende vrije blokken. */
void free_block(long index){
	long prev = get_prev(index);
	long next = get_next(index);
	
	if(!get_free(index)){
		/* Zet het blok op vrij. */
		set_free(index, 1);
		mem[0] -= get_length(index);
	}
	
	/* Voeg vorige blok samen met het huidige als deze vrij is als een groot
	 * vrij blok. */
	if(prev != 0 && get_free(prev)){
		set_length(prev, get_length(prev) + get_length(index) + ADMIN_SIZE);
		set_next(prev, next);
		
		if(next != 0){
			set_prev(next, prev);
		}
		
		mem[1] -= ADMIN_SIZE;
	}
	
	/* Voeg volgende blok samen met het huidige als deze vrij is als een 
	 * groot vrij blok. */
	if(next != 0 && get_free(next)){
		free_block(next);
	}
}

node* node_new(void* data)
{
    node* n = (node*) malloc(sizeof(node));
    set_next(n, NULL);
    set_prev(n, NULL);
    n->data = data;
    return n;
}

	ThreadPiece::ThreadPiece(const Vector3d& vertex, const double angle_twist, ThreadPiece* prev, ThreadPiece* next, Thread* my_thread)
: _vertex(vertex), _angle_twist(angle_twist), rot(Matrix3d::Zero()), _my_thread(my_thread)
{
	grad_offsets[0] = Vector3d(grad_eps, 0.0, 0.0);
	grad_offsets[1] = Vector3d(0.0, grad_eps, 0.0);
	grad_offsets[2] = Vector3d(0.0, 0.0, grad_eps);
  set_prev(prev);
  set_next(next);
}

struct splaytree_node *splaytree_insert(struct splaytree_node *node,
                                        struct splaytree *tree)
{
    struct splaytree_node *root = tree->root;
    int res;

    if (!root) {
        INIT_NODE(node);
        tree->root = node;
        tree->first = node;
        tree->last = node;
        return NULL;
    }

    res = do_splay(node, tree);
    if (res == 0)
        return tree->root;

    root = tree->root;
    if (res < 0) {
        struct splaytree_node *left = get_left(root);

        set_left(left, node);
        set_right(root, node);
        if (left)
            set_next(node, get_last(left));
        else
            tree->first = node;
        set_prev(node, root);
    } else {
        struct splaytree_node *right = get_right(root);

        set_right(right, node);
        set_left(root, node);
        if (right)
            set_prev(node, get_first(right));
        else
            tree->last = node;
        set_next(node, root);
    }
    tree->root = node;
    return NULL;
}

static inline void rotate_right(struct splaytree_node *node)
{
    struct splaytree_node *left = get_left(node);	/* can't be NULL */
    struct splaytree_node *r = get_right(left);

    if (r)
        set_left(r, node);
    else
        set_prev(left, node);
    set_right(node, left);
}

static void *
get_block(Size size)
{
	void *block;
	void *best = NULL;
	int best_size;

	SpinLockAcquire(&ShemDynAllocShmem->mutex);

	block = ShemDynAllocShmem->head;
	while (block)
	{
		Size block_size = get_size(block);
		if (size > block_size)
		{
			block = get_next(block);
			continue;
		}
		if (!best || best_size > block_size)
		{
			best = block;
			best_size = block_size;
		}
		block = get_next(block);
	}

	if (best)
	{
		void *prev;
		void *next;

		mark_allocated(best);
		prev = get_prev(best);
		next = get_next(best);

		if (!prev)
			ShemDynAllocShmem->head = next;
		else
			set_next(prev, next);
		if (!next)
			ShemDynAllocShmem->tail = prev;
		else
			set_prev(next, prev);
	}

	SpinLockRelease(&ShemDynAllocShmem->mutex);

	return best;
}

static void set_generation_number( los_list_t *list, int gen_no, bool clear )
{
  word *header, *this, *prev;

  header = list->header;
  this = next( header );
  prev = header;
  while (this != header) {
    gclib_set_generation( this - HEADER_WORDS, size( this ), gen_no );
    if (clear) 
      set_prev( this, prev );
    prev = this;
    this = next( this );
  }
}

bool los_mark( los_t *los, los_list_t *marked, word *w, int gen_no )
{
  word *p = prev( w );

  /* assert( w is the address of a live large object ); */

  if (p == 0)
    return 1;	/* Already marked and moved */

  assert( ishdr( *w ) );
  remove( w );
  los->object_lists[ gen_no ]->bytes -= size( w );
  /* marked->bytes += size( w );  WRONG! -- insert_at_end does this too */
  insert_at_end( w, marked );
  set_prev( w, 0 );
  return 0;
}

int linkedlist_add_at(linkedlist _list, void* data, int i)
{
    linkedlist_t* list = (linkedlist_t*) _list;
    node* slider, *n;

    if(i > (list->size - 1))
        return add_at_last(list, data);

    if(i == 0)
        return add_at_first(list, data);
    else
    {
        slider = find_by_index(list, i);
        n = node_new(data);
        set_next(get_prev(slider), n);
        set_prev(n, get_prev(slider));
        set_next(n, slider);
        list->size++;
        return list->size;
    }
}