metadata_t * extend_heap(size_t space) {
	int numchunk = (space + META_SIZE + FOOTER_SIZE) / CHUNK_SIZE;
	if ((space + META_SIZE + FOOTER_SIZE) % CHUNK_SIZE > 0) {
		numchunk += 1;
	}
	size_t space_a = numchunk * CHUNK_SIZE;
	void *last_brk = sbrk(space_a);
	if (errno == ENOMEM) {
		printf("no room for extending heap\n");
		return NULL;
	}
	metadata_t *epilogue = to_meta(last_brk + space_a);
	epilogue->prev = NULL;
	epilogue->next = NULL;
	set_alloc(epilogue);
	metadata_t *start = to_meta(last_brk);
	start->prev = NULL;
	start->next = NULL;
	set_free(start);
	set_size(start, space_a - META_SIZE - FOOTER_SIZE);
	footer_t *end = to_footer(to_block(start));
	set_free((metadata_t *)end);
	set_size((metadata_t *)end, space_a - META_SIZE - FOOTER_SIZE);
	//add_node(start);
	bool left_f = is_free((metadata_t *)((void *)start - FOOTER_SIZE));
	if (left_f) {
		//process the linked list
		//change the size of two blocks
		void *ptr = to_block(start);
		delete_node(to_meta(left_block(ptr)));
		int left_size = block_size(left_block(ptr));
		int new_size = left_size + FOOTER_SIZE + META_SIZE + block_size(ptr);
		set_size(to_meta(left_block(ptr)), new_size);
		set_size((metadata_t *)to_footer(ptr), new_size);
		set_free(to_meta(left_block(ptr)));
		set_free((metadata_t *)to_footer(ptr));
		start = to_meta(left_block(ptr));
		// add_node(to_meta(left_block(ptr)));
	}
	add_node(start);
	return start;
}

/*
* place - Set headers and footers for newly allocated blocks. Split blocks
* if enough space is remaining.
*/
static void place(void *ptr, size_t asize)
{
size_t ptr_size = GET_SIZE(HEAD(ptr));
size_t remainder = ptr_size - asize;
/* Remove block from list */
delete_node(ptr);
if (remainder >= MINSIZE) {
/* Split block */
PUT(HEAD(ptr), PACK(asize, 1)); /* Block header */
PUT(FOOT(ptr), PACK(asize, 1)); /* Block footer */
PUT_NOTAG(HEAD(NEXT(ptr)), PACK(remainder, 0)); /* Next header */
PUT_NOTAG(FOOT(NEXT(ptr)), PACK(remainder, 0)); /* Next footer */
insert_node(NEXT(ptr), remainder);
} else {
/* Do not split block */
PUT(HEAD(ptr), PACK(ptr_size, 1)); /* Block header */
PUT(FOOT(ptr), PACK(ptr_size, 1)); /* Block footer */
}
return;
}

hubbub_error unref_node(void *ctx, void *node)
{
    node_t *n = node;

    UNUSED(ctx);

    if (n != (void *) 1) {
        assert(n->refcnt > 0);

        n->refcnt--;

        printf("Unreferencing node %p (%d)\n", node, n->refcnt);

        if (n->refcnt == 0 && n->parent == NULL) {
            delete_node(n);
        }
    }

    return HUBBUB_OK;
}

/* O(n*n), stupid method */
int remove_dup(s_node* root)
{
  s_node* i = root;
  s_node* j;
  s_node* k;
  while ( i ) {
    j = i->next;
    while ( j ) {
      if ( i->data == j->data ) {
        k = j->next;
        delete_node(root, j);
        j = k;
        continue;
      }
      j = j->next;
    }
    i = i->next;
  }
  return 0;
}

node_t *
delete_node(node_t *node)
{
    int i;
    data_t *d;

    if(node == NULL || node->data == NULL) {
	return NULL;
    }
    d = node->data;

    d->deleted = BOOL_TRUE;
    d->text[0] = 'D';

    for(i = 0; i < d->nbr_children; i++) {
	delete_node(d->children[i]);
    }

    return node;
}

//k and v both are in stack
//k td
//v mvalue.data
int insert_kv_mem(struct rbtree *rbt,struct htable *ds,uchar *k,uchar *v,int vlen)
{
 uchar *val = NULL;
 struct mvalue *mv = NULL,tmp;
 int ret = -1;
 struct rbnode *pn = NULL;
 struct ttlnode tn = {0};
 if(vlen < 0 || vlen > MAX_RECORD_SIZE)
	return -1;
 hashval_t hash = nocase_char_hash_function(k);
 hash = get_pre_mem_hash(k);
 val = malloc(vlen);
 if(val == NULL)
	return -1;
 memcpy(val,v,vlen);
 mv = (struct mvalue*)v;
 ret = htable_insert(ds + hash,k,val,1,&tmp); //mem, replace
 if(ret == 2)
	free(val);
 if(mv->ttl == (MAX_TTL + 1))//never expired
	 return 0;
 if(rbt == NULL)
	 return 0;
 //data exists in htable, delete it in ttl tree, then insert
 pthread_mutex_lock(&rbt->lock);
 if(ret != 0)
	{
	 tn.dlen = strlen(k) + 1;
	 //tmp get old data
	 tn.exp = tmp.ttl;
	 tn.data = k;
	 pn = find_node(rbt,&tn);
	 //if update, we had delete tn in rbt
	 //else update tn in rbt
	 if(pn != NULL)
		 delete_node(rbt,pn);
	}
 ret = insert_into_ttltree(rbt,k,mv->ttl);//ttl expired tree
 pthread_mutex_unlock(&rbt->lock);
 return 0;
}

int main(){
	char end='n';
	int op;
	
	do{
		display_menu();
		scanf("%d",&op);
		switch(op){
		
			case 1:
				if(start==NULL){
					printf("\nMessage :\"%d node created yet.\"",no_nodes);
					break;
				}else{
					printf("\n------------Displaying Node------------\n");
					display_link_list();
				}
				break;
			case 2:
				printf("\n------------Node Creation------------\n");
				create_node();
				printf("\nMessage: \"Total %d nodes created yet.\"",no_nodes);
				break;
			case 3:
				
				if(no_nodes==0) printf("\nError: \"Cannot delete nodes because no nodes created yet.\"");
				else{
					printf("\n------------Node Deletion------------\n");
					delete_node();
				} 
				break;
			default:
				printf("Warning: \"Wronge number entered.\"");
		}
		printf("\n\nExit program? Enter y or n : ");
		end=getch();
		printf("\n\n");
	}while(end=='n');
	
	return 0;
}

void net::connection_list::delete_expired(time_t now)
{
	node* nodes = _M_nodes.nodes;

	while (_M_tail != -1) {
		connection* conn = &nodes[_M_tail].conn;

		if (conn->timestamp + kExpirationTimeout > now) {
			return;
		}

#if DEBUG
		const unsigned char* srcip = (const unsigned char*) &conn->srcip;
		const unsigned char* destip = (const unsigned char*) &conn->destip;

		printf("Deleting expired connection: %u.%u.%u.%u:%u %s %u.%u.%u.%u:%u, timestamp: %ld.\n", srcip[0], srcip[1], srcip[2], srcip[3], conn->srcport, (conn->direction == 0) ? "->" : "<-", destip[0], destip[1], destip[2], destip[3], conn->destport, conn->timestamp);
#endif // DEBUG

		delete_node(_M_tail);
	}
}

bool net::connection_list::delete_node(unsigned idx)
{
	connection* conn = &_M_nodes.nodes[idx].conn;

	// Search IP fragment.
	ip_fragment* fragment;
	size_t pos;
	if ((fragment = search(&_M_fragments[conn->srcport], conn->srcip, pos)) == NULL) {
		return false;
	}

	// Search index in IP fragment.
	size_t index;
	if (!search(fragment, conn->srcip, conn->srcport, conn->destip, conn->destport, index)) {
		return false;
	}

	delete_node(conn->srcport, pos, index);

	return true;
}

void testRBtree_delete(CuTest *tc){
    RB_tree tree;
    tree.nil = (RB_node*)malloc(sizeof(RB_node));
    tree.nil->color = BLACK;
    tree.nil->key = -10;

    tree.root = tree.nil;
    int i;
    for(i = 63; i > 0; --i){
        insert_node(&tree, (short int)i);
    }
    for(i = 0; i < 63; i += 2){
        delete_node(&tree, (short int)i);
    }
    //test
    printf("\nRed-Black Tree delete test\nInserted nodes 1-63, even numbers from 0 to 62 removed\n(for 0 no error), ");
    RB_display_keys_in_order(&tree);

    clear_tree(&tree);
    free(tree.nil);
}

/* 
 * place - Place block of asize bytes at start of free block bp 
 *         and split if remainder would be at least minimum block size
 */
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp)); // size of free block 
    size_t remainder = csize - asize;
    /* Remove block from free list */
    delete_node(bp);
 

    if ((csize - asize) >= (2*DSIZE)) { 
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(remainder, 0));
        PUT(FTRP(bp), PACK(remainder, 0));
        insert_node(bp, remainder);
    }
    else { 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/* MAIN PROGRAM */
int main()
{
	Node_ptr my_list = NULL;

	assign_list(my_list);

	cout << "\nTHE LIST IS NOW:\n";
	print_list(my_list);

	cout << "forwards: ";
	print_forwards(my_list);
	cout << endl;

	cout << "backwards: ";
	print_backwards(my_list);
	cout << endl;

	char word[20], lookfor[20];

	cout << endl << "word to insert: ";
	cin.getline(word,20);

	cout << endl << "to be inserted after (' ' for right at beginning): ";
	cin.getline(lookfor,20);

	add_after(my_list, lookfor, word);

	cout << endl << "\nTHE LIST IS NOW:\n";
	print_list(my_list);

	cout << endl << "word to delete: ";
	cin.getline(word,20);

	delete_node(my_list, word);

	cout << endl << "\nTHE LIST IS NOW:\n";
	print_list(my_list);

	return 0;
}

void DeleteTuple(storage::DataTable *table) {
  auto &txn_manager = concurrency::TransactionManagerFactory::GetInstance();
  auto txn = txn_manager.BeginTransaction();
  std::unique_ptr<executor::ExecutorContext> context(
      new executor::ExecutorContext(txn));

  std::vector<storage::Tuple *> tuples;

  // Delete
  planner::DeletePlan delete_node(table, false);
  executor::DeleteExecutor delete_executor(&delete_node, context.get());

  // Predicate

  // WHERE ATTR_0 > 60
  expression::TupleValueExpression *tup_val_exp =
      new expression::TupleValueExpression(VALUE_TYPE_INTEGER, 0, 0);
  expression::ConstantValueExpression *const_val_exp =
      new expression::ConstantValueExpression(
          ValueFactory::GetIntegerValue(60));
  auto predicate = new expression::ComparisonExpression<expression::CmpGt>(
      EXPRESSION_TYPE_COMPARE_GREATERTHAN, tup_val_exp, const_val_exp);

  // Seq scan
  std::vector<oid_t> column_ids = {0};
  std::unique_ptr<planner::SeqScanPlan> seq_scan_node(
      new planner::SeqScanPlan(table, predicate, column_ids));
  executor::SeqScanExecutor seq_scan_executor(seq_scan_node.get(),
                                              context.get());

  // Parent-Child relationship
  delete_node.AddChild(std::move(seq_scan_node));
  delete_executor.AddChild(&seq_scan_executor);

  EXPECT_TRUE(delete_executor.Init());
  EXPECT_TRUE(delete_executor.Execute());
  // EXPECT_TRUE(delete_executor.Execute());

  txn_manager.CommitTransaction();
}

void binary_search_tree::remove(const std::string &key)
{
    bstnode *t = get_node_by_key(key, root);
    if(t == NULL) return; /* Not exists */

    bstnode *y;
    bstnode *x;
    {
        if(t->left == NULL || t->right == NULL)
            y = t;
        else
            y = get_tree_successor(t);
    }

    {
        if(t->left != NULL)
            x = y->left;
        else
            x = y->right;
    }

    {
        if(x != NULL) x->parent = y->parent;
    }

    {
        if(y->parent == NULL)
            root = x;
        else if(y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    }

    {
        if(y != t) t->element = y->element;
    }

    delete_node(y);
}

/* This deletes a node from the tree.
   Note that this does not release the data that the node points to
*/
void 
trbt_delete32(trbt_tree_t *tree, uint32_t key)
{
	trbt_node_t *node;

	node=tree->root;

	while(node){
		if(key==node->key32){
			delete_node(node, False);
			return;
		}
		if(key<node->key32){
			node=node->left;
			continue;
		}
		if(key>node->key32){
			node=node->right;
			continue;
		}
	}
}

void test_parse_paren() {
    struct token_list *tkl = make_token_list();
    struct token *tk0 = make_token(tok_punc, "(", 0.0, 0);
    struct token *tk1 = make_token(tok_number, NULL, 0.0, 42);
    struct token *tk2 = make_token(tok_punc, "+", 0.0, 0);
    struct token *tk3 = make_token(tok_number, NULL, 0.0, 24);
    struct token *tk4 = make_token(tok_punc, ")", 0.0, 0);
    append_token_list(tkl, tk0);
    append_token_list(tkl, tk1);
    append_token_list(tkl, tk2);
    append_token_list(tkl, tk3);
    append_token_list(tkl, tk4);
    struct ast_node *result = parse_paren(tkl);
    EXPECT_EQ(result->val, tk2);
    EXPECT_EQ(result->num_children, 2);
    EXPECT_EQ(result->children[0]->val, tk1);
    EXPECT_EQ(result->children[1]->val, tk3);
    EXPECT_EQ(result->children[0]->num_children, 0);
    EXPECT_EQ(result->children[1]->num_children, 0);
    destroy_token_list(tkl);
    delete_node(result);
}

void add_node(c_node *node, c_list *list){
	if(list) {
		//pthread_rwlock_wrlock((list->lock));
		if(node){
			while(list->bytes_left < node->length) {
				c_node *tmp_node = evict_list(list);
				delete_node(tmp_node);
			}
			if(!list->tail) {
				list->head = list->tail = node;
				list->bytes_left -= node->length;
			}
			else {
				list->tail->next = node;
				node->prev = list->tail;
				list->tail = node;
				list->bytes_left -= node->length;
			}
		}
		//pthread_rwlock_unlock((list->lock));
	}
}

hubbub_error unref_node(void *ctx, void *node)
{
	node_t *n = node;

	UNUSED(ctx);

	if (n != (void *) 1) {
		assert(n->refcnt > 0);

		n->refcnt--;

		printf("Unreferencing node %p (%d) [%d : %s]\n", node, 
				n->refcnt, n->type, 
				n->type == ELEMENT ? n->data.element.name : "");

		if (n->refcnt == 0 && n->parent == NULL) {
			delete_node(n);
		}
	}

	return HUBBUB_OK;
}

ErrorCode MatchDocument(DocID doc_id, const char* doc_str) {

//	DNode_t* lazy_node = lazy_list->head.next;
//
//	while ((lazy_node = lazy_list->head.next) != &(lazy_list->tail)) {
//		lazyStart((QueryDescriptor*) (lazy_node->data));
////		cir_queue_insert(cirq_busy_queries, lazy_node->data);
////#ifndef THREAD_ENABLE
////		lazyStart(0);
////#endif
//		lazy_nodes[((QueryDescriptor*) (lazy_node->data))->queryId] = 0;
//		delete_node(lazy_node);
//	}

	DNode_t* lazy_node = lazy_list->head.next, *tmp;

	while (lazy_node != &(lazy_list->tail)) {
		tmp = lazy_node->next;
		lazyStart((QueryDescriptor*) (lazy_node->data));
		lazy_nodes[((QueryDescriptor*) (lazy_node->data))->queryId] = 0;
		delete_node(lazy_node);
		lazy_node = tmp;
	}

#ifdef THREAD_ENABLE
	waitTillFull(&cirq_free_segments);
#endif
	docCount++;
	char *doc_buf = (char *) cir_queue_remove(&cirq_free_docs);
	strcpy(doc_buf, doc_str);
	DocumentDescriptor *desc = newDocumentDescriptor();
	desc->docId = doc_id;
	desc->document = doc_buf;
	cir_queue_insert(&cirq_busy_docs, desc);
#ifndef THREAD_ENABLE
	matcher_thread(0);
#endif
	return EC_SUCCESS;
}

static void *coalesce(void *ptr)
{
    size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    size_t size = GET_SIZE(HDRP(ptr));
    

    // Do not coalesce with previous block if the previous block is tagged with Reallocation tag
    if (GET_TAG(HDRP(PREV_BLKP(ptr))))
        prev_alloc = 1;

    if (prev_alloc && next_alloc) {                         // Case 1
        return ptr;
    }
    else if (prev_alloc && !next_alloc) {                   // Case 2
        delete_node(ptr);
        delete_node(NEXT_BLKP(ptr));
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));
        PUT(FTRP(ptr), PACK(size, 0));
    } else if (!prev_alloc && next_alloc) {                 // Case 3 
        delete_node(ptr);
        delete_node(PREV_BLKP(ptr));
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
        PUT(FTRP(ptr), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    } else {                                                // Case 4
        delete_node(ptr);
        delete_node(PREV_BLKP(ptr));
        delete_node(NEXT_BLKP(ptr));
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    
    insert_node(ptr, size);
    
    return ptr;
}