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;
}

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;
   }
}

 void push(node_base* p)
 {
     set_next(p, NULL);
     exclusive_lock_guard< mutex_type > _(m_Tail.mutex);
     set_next(m_Tail.node, p);
     m_Tail.node = p;
 }

void* fixed_size_allocator::_alloc( size_t ) {
	refs++;
#ifdef DEBUG_POOL_ALLOCATOR
	allocs++;current++;
	if(current>max)max=current;
#endif
	void* p = head_of_free_list;
	if(p)  {
		head_of_free_list = get_next(p);
	} else {

		char* new_block = new char[sizeof(block_head) + num_objects * object_size];
		((block_head*)new_block)->next = head;
		head = (block_head*)new_block;
		new_block += sizeof(block_head);
		for(std::size_t i = object_size; i < (num_objects - 1) * object_size; i += object_size) {
			set_next(&new_block[i], &new_block[i + object_size]);
		}
		set_next(&new_block[(num_objects - 1) * object_size], 0);
		p = new_block;
		head_of_free_list = &new_block[object_size];

#ifdef DEBUG_POOL_ALLOCATOR
		blocks++;
#endif
	}
	return p;
}

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 );
}

/*@ 
   set_union - find the union of two sets

Input arguments:
+ s - The first set
- t - The second set

Output arguments:
None

Returns:
A new set that is the union of the two input sets if successful,
NULL otherwise.

Notes:
s and t must contain the same types of elements
@*/
struct set *set_union(struct set *s, struct set *t)
{
    void * e;
    struct set *tmp, *u, *v; 

    /* Try to make sure that these two sets contain the same types */
    if (s->cmp != t->cmp || s->elemsize != t->elemsize)
	return NULL;
    
    /* Whichever set we iterate over should be smaller because iteration is O(n) */
    /* while bsearch is O(log n) */
    if (s->size < t->size)
	u = s, v = t;
    else 
	u = t, v = s;

    tmp = set_copy(v);
    if (tmp == NULL)
	return NULL;
    
    /* Insert all the elements of u not in v */
    for (set_reset(u), e = set_next(u); e != NULL; e = set_next(u)){
	if (!set_exists(v, e))
	    set_insert(tmp, e);
    }

    return tmp;
}

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;
}

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;
}

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
flow_uninit_scan_statements (flownode_t *node, set_t *defs, set_t *uninit)
{
	set_t      *stuse;
	set_t      *stdef;
	statement_t *st;
	set_iter_t *var_i;
	flowvar_t  *var;
	operand_t  *op;

	// defs holds only reaching definitions. make it hold only reaching
	// uninitialized definitions
	set_intersection (defs, uninit);
	stuse = set_new ();
	stdef = set_new ();
	for (st = node->sblock->statements; st; st = st->next) {
		flow_analyze_statement (st, stuse, stdef, 0, 0);
		for (var_i = set_first (stuse); var_i; var_i = set_next (var_i)) {
			var = node->graph->func->vars[var_i->element];
			if (set_is_intersecting (defs, var->define)) {
				def_t      *def = flowvar_get_def (var);
				if (def) {
					if (options.warnings.uninited_variable) {
						warning (st->expr, "%s may be used uninitialized",
								 def->name);
					}
				} else {
					bug (st->expr, "st %d, uninitialized temp %s",
						 st->number, operand_string (var->op));
				}
			}
			// avoid repeat warnings in this node
			set_difference (defs, var->define);
		}
		for (var_i = set_first (stdef); var_i; var_i = set_next (var_i)) {
			var = node->graph->func->vars[var_i->element];
			// kill any reaching uninitialized definitions for this variable
			set_difference (defs, var->define);
			if (var->op->op_type == op_temp) {
				op = var->op;
				if (op->o.tempop.alias) {
					var = op->o.tempop.alias->o.tempop.flowvar;
					if (var)
						set_difference (defs, var->define);
				}
				for (op = op->o.tempop.alias_ops; op; op = op->next) {
					var = op->o.tempop.flowvar;
					if (var)
						set_difference (defs, var->define);
				}
			}
		}
	}
	set_delete (stuse);
	set_delete (stdef);
}

void show_tile (void)
{
  set_grid(current_tile[5]);
  set_next(next_tile[5]);   

  show_grid();

  set_grid(0);
  set_next(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::append(void *item)
{
   set_next(item, NULL);
   set_prev(item, tail);
   if (tail) {
      set_next(tail, item);
   }
   tail = item;
   if (head == NULL) {                /* if empty list, */
      head = item;                    /* item is head as well */
   }
   num_items++;
}

int main(int argc, char *argv[])
{
    int i, size = 100, *x;
    struct set *s, *t, *u;
    
    if (argc > 1)
	size = atoi(argv[1]);
    
    srand(time(NULL));

    s = set_create(size, sizeof(int), cmpint);
    t = set_create(size, sizeof(int), cmpint);
    if (s == NULL || t == NULL){
	printf("Unable to create the test set\n");
	return 1;
    }

    printf("Inserting into first set...\n");
    for (i = 0; i < size; i++){
	int y = rand() % size;

	printf("%d ", y);
	set_insert(s, &y);
    }
    printf("\n\n");

    printf("The set contains:\n");
    for (set_reset(s), x = set_next(s); x != NULL; x = set_next(s)) 
	printf("%d ", *x);
    printf("\n\n");

    printf("Inserting into second set...\n");
    for (i = 0; i < size; i++){
	int y = rand() % size;

	printf("%d ", y);
	set_insert(t, &y);
    }
    printf("\n\n");

    printf("The set contains:\n");
    for (set_reset(t), x = set_next(t); x != NULL; x = set_next(t)) 
	printf("%d ", *x);
    printf("\n\n");

    u = set_union(s, t);
    printf("The union of the two sets is:\n");
    for (set_reset(u), x = set_next(u); x != NULL; x = set_next(u)) 
	printf("%d ", *x);
    printf("\n\n");
    set_destroy(u);

    u = set_diff(s, t);
    printf("The difference of the two sets is:\n");
    for (set_reset(u), x = set_next(u); x != NULL; x = set_next(u)) 
	printf("%d ", *x);
    printf("\n\n");
    
    return 0;
}

int kmp(char* s,char* t,unsigned pos)
{
	int j=0;
	int s_len=strlen(s);
	int t_len=strlen(t);	
	int * next;
	if(t_len==0) return -1;
	next=(int*)malloc(sizeof(int)*t_len);	
	set_next(t,next,t_len);
	while(s_len-pos>=t_len)
	{
		while(j<t_len&&s[pos]==t[j]) 
		{
			++pos;
			++j;
		}
		if(j==t_len) 
		{
			free(next);
			return pos-t_len;
		}
		j=next[j];
		if(j==-1)
		{
			++pos;
			j=0;
		}
	}
	free(next);
	return -1;
}

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 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);
	}
}

static void
flow_find_loops (flowgraph_t *graph)
{
	flownode_t *node;
	set_iter_t *succ;
	flowloop_t *loop, *l;
	flowloop_t *loop_list = 0;
	int         i;

	for (i = 0; i < graph->num_nodes; i++) {
		node = graph->nodes[i];
		for (succ = set_first (node->successors); succ;
			 succ = set_next (succ)) {
			if (set_is_member (node->dom, succ->element)) {
				loop = make_loop (graph, node->id, succ->element);
				for (l = loop_list; l; l = l->next) {
					if (l->head == loop->head
						&& !set_is_subset (l->nodes, loop->nodes)
						&& !set_is_subset (loop->nodes, l->nodes)) {
						set_union (l->nodes, loop->nodes);
						delete_loop (loop);
						loop = 0;
						break;
					}
				}
				if (loop) {
					loop->next = loop_list;
					loop_list = loop;
				}
			}
		}
	}
	graph->loops = loop_list;
}

int
client_addr_init(struct ntp_peer *p)
{
    struct sockaddr_in	*sa_in;
    struct sockaddr_in6	*sa_in6;
    struct ntp_addr		*h;

    for (h = p->addr; h != NULL; h = h->next) {
        switch (h->ss.ss_family) {
        case AF_INET:
            sa_in = (struct sockaddr_in *)&h->ss;
            if (ntohs(sa_in->sin_port) == 0)
                sa_in->sin_port = htons(123);
            p->state = STATE_DNS_DONE;
            break;
        case AF_INET6:
            sa_in6 = (struct sockaddr_in6 *)&h->ss;
            if (ntohs(sa_in6->sin6_port) == 0)
                sa_in6->sin6_port = htons(123);
            p->state = STATE_DNS_DONE;
            break;
        default:
            fatalx("king bula sez: wrong AF in client_addr_init");
            /* not reached */
        }
    }

    p->query->fd = -1;
    set_next(p, 0);

    return (0);
}