void two_three_insert_balance (Tree *T, Node *x)
{
    Node *sibling, *g; g = NULL;
    bool side, p_side; side = p_side = 0;

    while (x->rd == 0 && x->p != T->head) {                         // VIOLATION
        g = x->p->p;
        sibling = return_sibling (x);
        if ((x->p->rd == 1 || g == T->head) && sibling->rd == 0) {  // Case 1
                promote (T, x->p);
                x = x->p;
        }
        else if (x->p->rd == 0 && g != T->head) {
            side = (x == x->p->child[R]);
            p_side = (x->p == g->child[R]);
            if (side != p_side) {                                   // Case 3
                rotate_balance(x);
                rotate (T, x->p, p_side);
            }
            rotate_balance(g->child[p_side]);                       // Case 2
            rotate (T, g, !p_side);
            promote (T, g->p);
            x = g->p;
        }
        else {                                                      // Balanced
            return; // or x = x->p
        }
    }
}

	void set(int key, int value) {
		//update
		if (hashtable[key]) {
			Node* p = this->hashtable[key];
			p->val = value;
			promote(p);
			return;
		}

		Node *p = NULL;

		if (this->size < this->capacity) {
			p = & entries[size];
			p->next = this->head->next;
			p->pre = this->head;
			this->head->next->pre = p;
			this->head->next = p;
			size += 1;
		} else {
			this->hashtable.erase(this->tail->pre->key);
			p = this->tail->pre;
			promote(p);
		}

		p->key = key;
		p->val = value;
		this->hashtable[key] = p;
		return;
	}

static mle *build_mission_list(int anarchy_mode)
{
	mle *mission_list;
	int top_place;
    char	builtin_mission_filename[FILENAME_LEN];
	char	search_str[PATH_MAX] = MISSION_DIR;

	//now search for levels on disk

//@@Took out this code because after this routine was called once for
//@@a list of single-player missions, a subsequent call for a list of
//@@anarchy missions would not scan again, and thus would not find the
//@@anarchy-only missions.  If we retain the minimum level of install,
//@@we may want to put the code back in, having it always scan for all
//@@missions, and have the code that uses it sort out the ones it wants.
//@@	if (num_missions != -1) {
//@@		if (Current_mission_num != 0)
//@@			load_mission(0);				//set built-in mission as default
//@@		return num_missions;
//@@	}

	MALLOC(mission_list, mle, MAX_MISSIONS);
	num_missions = 0;
	
	add_builtin_mission_to_list(mission_list + num_missions, builtin_mission_filename);  //read built-in first
	add_d1_builtin_mission_to_list(mission_list + num_missions);
	add_missions_to_list(mission_list, search_str, search_str + strlen(search_str), anarchy_mode);
	
	// move original missions (in story-chronological order)
	// to top of mission list
	top_place = 0;
	promote(mission_list, "descent", &top_place); // original descent 1 mission
	promote(mission_list, builtin_mission_filename, &top_place); // d2 or d2demo
	promote(mission_list, "d2x", &top_place); // vertigo

	if (num_missions > top_place)
		qsort(&mission_list[top_place],
		      num_missions - top_place,
		      sizeof(*mission_list),
 				(int (*)( const void *, const void * ))ml_sort_func);


	if (num_missions > top_place)
		qsort(&mission_list[top_place],
		      num_missions - top_place,
		      sizeof(*mission_list),
		      (int (*)( const void *, const void * ))ml_sort_func);

	return mission_list;
}

void retcode(Tree p) {
	Type ty;

	if (p == NULL) {
		if (events.returns)
			apply(events.returns, cfunc, NULL);
		return;
	}
	p = pointer(p);
	ty = assign(freturn(cfunc->type), p);
	if (ty == NULL) {
		error("illegal return type; found `%t' expected `%t'\n",
			p->type, freturn(cfunc->type));
		return;
	}
	p = cast(p, ty);
	if (retv)
		{
			if (iscallb(p))
				p = tree(RIGHT, p->type,
					tree(CALL+B, p->type,
						p->kids[0]->kids[0], idtree(retv)),
					rvalue(idtree(retv)));
			else {
				Type ty = retv->type->type;
				assert(isstruct(ty));
				if (ty->u.sym->u.s.cfields) {
					ty->u.sym->u.s.cfields = 0;
					p = asgntree(ASGN, rvalue(idtree(retv)), p);
					ty->u.sym->u.s.cfields = 1;
				} else
					p = asgntree(ASGN, rvalue(idtree(retv)), p);
			}
			walk(p, 0, 0);
			if (events.returns)
				apply(events.returns, cfunc, rvalue(idtree(retv)));
			return;
		}
	if (events.returns)
		{
			Symbol t1 = genident(AUTO, p->type, level);
			addlocal(t1);
			walk(asgn(t1, p), 0, 0);
			apply(events.returns, cfunc, idtree(t1));
			p = idtree(t1);
		}
	if (!isfloat(p->type))
		p = cast(p, promote(p->type));
	if (isptr(p->type))
		{
			Symbol q = localaddr(p);
			if (q && (q->computed || q->generated))
				warning("pointer to a %s is an illegal return value\n",
					q->scope == PARAM ? "parameter" : "local");
			else if (q)
				warning("pointer to %s `%s' is an illegal return value\n",
					q->scope == PARAM ? "parameter" : "local", q->name);
		}
	walk(tree(mkop(RET,p->type), p->type, p, NULL), 0, 0);
}

/* Construct a binary tree node with given data and insert it into the heap */
priorityQueueEntry priorityQueueInsert(priorityQueue* queue, int key, void* data)
{	
	/* Construction */
	priorityQueueEntry* entry =	(priorityQueueEntry*) malloc(sizeof (priorityQueueEntry));
	entry->key=key;
	entry->data=data;
	entry->parent=NULL;
	entry->childl=NULL;
	entry->childr=NULL;

	/* Insertion */
	queue->size++;
	if(queue->size==1)
		queue->root=entry;
	else {
		/* Find the variable that shall store the new entry */
		priorityQueueEntry* parent=nodeAt(queue, (queue->size)/2);
		priorityQueueEntry* *destination;
		if(queue->size%2==0)
			destination=&(parent->childl);
		else
			destination=&(parent->childr);
		assert(*destination==NULL);
		
		*destination=entry;
		entry->parent=parent;
		promote(entry);
	}
	
	return* entry;
}

/* subtree - construct tree for l - r */
static Tree subtree(int op, Tree l, Tree r) {
	long n;
	Type ty = inttype;

	if (isarith(l->type) && isarith(r->type)) {
		ty = binary(l->type, r->type);
		l = cast(l, ty);
		r = cast(r, ty);		
	} else if (isptr(l->type) && !isfunc(l->type->type) && isint(r->type)) {
		ty = unqual(l->type);
		n = unqual(ty->type)->size;
		if (n == 0)
			error("unknown size for type `%t'\n", ty->type);
		r = cast(r, promote(r->type));
		if (n > 1)
			r = multree(MUL, cnsttree(signedptr, n), r);
		if (isunsigned(r->type))
			r = cast(r, unsignedptr);
		else
			r = cast(r, signedptr);
		return simplify(SUB+P, ty, l, r);
	} else if (compatible(l->type, r->type)) {
		ty = unqual(l->type);
		n = unqual(ty->type)->size;
		if (n == 0)
			error("unknown size for type `%t'\n", ty->type);
		l = simplify(SUB+U, unsignedptr,
			cast(l, unsignedptr), cast(r, unsignedptr));
		return simplify(DIV+I, longtype,
			cast(l, longtype), cnsttree(longtype, n));
	} else
		typeerror(op, l, r);
	return simplify(op, ty, l, r);
}

static Tree addtree(int op, Tree l, Tree r) {
	Type ty = inttype;

	if (isarith(l->type) && isarith(r->type)) {
		ty = binary(l->type, r->type);
		l = cast(l, ty);
		r = cast(r, ty);		
	} else if (isptr(l->type) && isint(r->type))
		return addtree(ADD, r, l);
	else if (  isptr(r->type) && isint(l->type)
	&& !isfunc(r->type->type))
		{
			long n;
			ty = unqual(r->type);
			n = unqual(ty->type)->size;
			if (n == 0)
				error("unknown size for type `%t'\n", ty->type);
			l = cast(l, promote(l->type));
			if (n > 1)
				l = multree(MUL, cnsttree(signedptr, n), l);
			if (isunsigned(l->type))
				l = cast(l, unsignedptr);
			else
				l = cast(l, signedptr);
			if (YYcheck && !isaddrop(r->op))		/* omit */
				return nullcall(ty, YYcheck, r, l);	/* omit */
			return simplify(ADD, ty, l, r);
		}

	else
		typeerror(op, l, r);
	return simplify(op, ty, l, r);
}

 void close(F& f) noexcept(noexcept(f(std::declval<pointer>()))) {
   node_pointer ptr = take_head(stack_closed_tag());
   while (ptr != nullptr) {
     auto next = ptr->next;
     f(promote(ptr));
     ptr = next;
   }
 }

int main(int argc, const char *argv[]) {
	char *titleid = get_title_id(PACKAGE_DIR "/sce_sys/param.sfo");
	if (titleid && strcmp(titleid, "VITASHELL") == 0) {
		if (promote(PACKAGE_DIR) >= 0)
			launchAppByUriExit("VITASHELL");
	}

	return sceKernelExitProcess(0);
}

	int get(int key) {
		Node *p = hashtable[key];
		if (!p) {
			return -1;
		} else {
			promote(p);
			return p->val;
		}
	}

moves pawn_moves(settings * set, cord curr, int color) {
	moves piece_simple_moves;
	piece_simple_moves.len = 0;
	cord dest;
	move * single_move;
	moves promotions;
	int dest_color;
	int y_dir = (color == WHITE) ? 1 : -1;

	dest.y = curr.y + y_dir;

	for (int x = -1; x <= 1; x++) {
		single_move = malloc(sizeof(move));
		if (single_move == NULL) {
			free_list(&piece_simple_moves, &free);
			return error_moves;
		}
		single_move->start = curr;
		single_move->promotion = FALSE;
		single_move->is_castle = FALSE;
		dest.x = curr.x + x;
		if (is_valid_cord(dest)) {
			dest_color = which_color(board_piece(set->board, dest));
			//logical XOR: check if pawn can eat XOR move up
			if (color == dest_color) {
				free(single_move);
				continue;
			}
			if ((x == 0) != (dest_color == other_player(color))) {
				single_move->end = dest;
				board_copy(set->board, single_move->board);
				move_from_to(single_move->board, curr, dest);
				// check if psaudo-legal move is legal
				if (is_king_checked(color, single_move->board)) {
					free(single_move);
					continue;
				}
				if (dest.y == promotion_row(color)) {
					promotions = promote(single_move);
					if (promotions.len == -1){
						free(single_move);
						free_list(&piece_simple_moves, &free);
						return promotions;
					}
					concat(&piece_simple_moves, promotions);
				}
				else if (!add_node(&piece_simple_moves, single_move, sizeof(move))) { //could not add node to linked list
					free(single_move);
					free_list(&piece_simple_moves, &free);
					return error_moves;
				}
				free(single_move);
			}
		}
	}
	return piece_simple_moves;
}

void put(char* key, char* value) {
    NODE *node = NULL;
    if (root)
        node = fetch(key, root);
    if (node) {
        // update the value
        strncpy(node->value, value, STR_MAX_SIZE);
#ifdef SET_IS_USE
        promote(node);
#endif
    } else {
        if (empty_count) { // root == NULL case is covered here also
           node = create_node(key, value);
           empty_count--;
#ifdef SET_IS_USE
            promote(node);
#endif

#ifdef SORT_IGNORE_CASE
            if (root)
                add_leaf(node, root, false);
            else
                rebuild_tree(false); // only for the first element
#else
            if (root)
                add_leaf(node, root);
            else
                rebuild_tree(); // only for the first element
#endif
        } else {
           node = rear.prev;
           strncpy(node->key, key, STR_MAX_SIZE);
           strncpy(node->value, value, STR_MAX_SIZE);
#ifdef SET_IS_USE
            promote(node);
#endif
#ifdef SORT_IGNORE_CASE
            rebuild_tree(false);
#else
            rebuild_tree();
#endif
        }
    }
}

char* get(char* key, bool use) {
    if (! root) return NULL;
    
    NODE *node = fetch(key, root);
    if (node) {
        if (use) promote(node);
        return node->value;
    } else
        return NULL;
}

  void dynamic_pst::promote(dynamic_pst::node* node) {

    dynamic_pst::node* empty_node;
        
    if (node->right != 0 && node->right->key_y == node->key_y)
      empty_node = node->right;
    else if (node->left != 0 && node->left->key_y == node->key_y)
      empty_node = node->left;
    else
      return;

    if (empty_node->leaf()) {
      empty_node->placeholder = true;
      return;
    }
    
    point cand_left = point(-INF,-INF);
    point cand_right = point(-INF,-INF);
    
    if (empty_node->left != 0 && !empty_node->left->placeholder)
      cand_left = empty_node->left->key_y;
    
    if (empty_node->right != 0 && !empty_node->right->placeholder)
      cand_right = empty_node->right->key_y;
    
    empty_node->key_y = std::max(cand_left, cand_right, comp_y);
    
    if (empty_node->left != 0 && empty_node->left->leaf() &&
        !empty_node->left->placeholder && empty_node->left->key_y == empty_node->key_y)
      empty_node->left->placeholder = true;
    else if (empty_node->left != 0 && !empty_node->leaf() &&
             empty_node->left->key_y == empty_node->key_y)
      promote(empty_node);
    
    if (empty_node->right != 0 && empty_node->right->leaf() &&
        !empty_node->right->placeholder && empty_node->right->key_y == empty_node->key_y)
      empty_node->right->placeholder = true;
    else if (empty_node->right != 0 && !empty_node->leaf() &&
             empty_node->right->key_y == empty_node->key_y)
      promote(empty_node);
    
  }

renf_elem_class & renf_elem_class::operator*=(const renf_elem_class & rhs) noexcept
{
    if (rhs.is_fmpq())
        inplace_binop(rhs.b, fmpq_mul, renf_elem_mul_fmpq);
    else
    {
        promote(*rhs.nf);
        renf_elem_mul(a, a, rhs.a, nf->renf_t());
    }
    return *this;
}

/* shtree - construct tree for l [>> <<] r */
Tree shtree(int op, Tree l, Tree r) {
	Type ty = inttype;

	if (isint(l->type) && isint(r->type)) {
		ty = promote(l->type);
		l = cast(l, ty);
		r = cast(r, inttype);
	} else
		typeerror(op, l, r);
	return simplify(op, ty, l, r);
}

void LessThanOrEqualFunc::execute() {
    boolean symflag = stack_key(sym_symid).is_true(); 
    ComValue& nval = stack_key(n_symid); 

    ComValue& operand1 = stack_arg(0);
    ComValue& operand2 = stack_arg(1);
    promote(operand1, operand2);
    ComValue result(operand1);
    result.type(ComValue::BooleanType);

    switch (operand1.type()) {
    case ComValue::CharType:
	result.boolean_ref() = operand1.char_val() <= operand2.char_val();
	break;
    case ComValue::UCharType:
	result.boolean_ref() = operand1.uchar_val() <= operand2.uchar_val();
	break;
    case ComValue::ShortType:
	result.boolean_ref() = operand1.short_val() <= operand2.short_val();
	break;
    case ComValue::UShortType:
	result.boolean_ref() = operand1.ushort_val() <= operand2.ushort_val();
	break;
    case ComValue::IntType:
	result.boolean_ref() = operand1.int_val() <= operand2.int_val();
	break;
    case ComValue::UIntType:
	result.boolean_ref() = operand1.uint_val() <= operand2.uint_val();
	break; 
    case ComValue::LongType:
	result.boolean_ref() = operand1.long_val() <= operand2.long_val();
	break;
    case ComValue::ULongType:
	result.boolean_ref() = operand1.ulong_val() <= operand2.ulong_val();
	break;
    case ComValue::FloatType:
	result.boolean_ref() = operand1.float_val() <= operand2.float_val();
	break;
    case ComValue::DoubleType:
	result.boolean_ref() = operand1.double_val() <= operand2.double_val();
	break;
    case ComValue::SymbolType:
	const char* str1 = operand1.symbol_ptr();
	const char* str2 = operand2.symbol_ptr();
	if (nval.is_unknown())
	  result.boolean_ref() = strcmp(str1, str2)<=0;
	else
	  result.boolean_ref() = strncmp(str1, str2, nval.int_val())<=0;
	break;
    }
    reset_stack();
    push_stack(result);
}

static void swstmt(int loop, int lab, int lev) {
	Tree e;
	struct swtch sw;
	Code head, tail;

	t = gettok();
	expect('(');
	definept(NULL);
	e = expr(')');
	if (!isint(e->type)) {
		error("illegal type `%t' in switch expression\n",
			e->type);
		e = retype(e, inttype);
	}
	e = cast(e, promote(e->type));
	if (generic(e->op) == INDIR && isaddrop(e->kids[0]->op)
	&& e->kids[0]->u.sym->type == e->type
	&& !isvolatile(e->kids[0]->u.sym->type)) {
		sw.sym = e->kids[0]->u.sym;
		walk(NULL, 0, 0);
	} else {
		sw.sym = genident(REGISTER, e->type, level);
		addlocal(sw.sym);
		walk(asgn(sw.sym, e), 0, 0);
	}
	head = code(Switch);
	sw.lab = lab;
	sw.deflab = NULL;
	sw.ncases = 0;
	sw.size = SWSIZE;
	sw.values = newarray(SWSIZE, sizeof *sw.values, FUNC);
	sw.labels = newarray(SWSIZE, sizeof *sw.labels, FUNC);
	refinc /= 10.0;
	statement(loop, &sw, lev);
	if (sw.deflab == NULL) {
		sw.deflab = findlabel(lab);
		definelab(lab);
		if (sw.ncases == 0)
			warning("switch statement with no cases\n");
	}
	if (findlabel(lab + 1)->ref)
		definelab(lab + 1);
	tail = codelist;
	codelist = head->prev;
	codelist->next = head->prev = NULL;
	if (sw.ncases > 0)
		swgen(&sw);
	branch(lab);
	head->next->prev = codelist;
	codelist->next = head->next;
	codelist = tail;
}

static
cmp_op(stream, node) {
    auto op = node[0];

    auto type; /* By this point the types must be compatible */
    if ( node[3][2][0] == '*' ) type = node[3][2];
    else type = usual_conv( node[3][2], node[4][2] );

    auto is_unsgn = type[5];
    auto sz = type_size(type);

    expr_code( stream, node[3], 0 );
    promote( stream, is_unsgn, type_size( node[3][2] ), sz );
    asm_push( stream );
    expr_code( stream, node[4], 0 );
    promote( stream, is_unsgn, type_size( node[4][2] ), sz );

    if      ( op == '<'   ) pop_lt(stream, sz, is_unsgn);
    else if ( op == '>'   ) pop_gt(stream, sz, is_unsgn);
    else if ( op == '<='  ) pop_le(stream, sz, is_unsgn);
    else if ( op == '>='  ) pop_ge(stream, sz, is_unsgn);
    else if ( op == '=='  ) pop_eq(stream, sz);
    else if ( op == '!='  ) pop_ne(stream, sz);
}

void checkAndInsert(int x){
    int lru_index;
    int pos;
    cache_blk_t *blkPtr;
    blkPtr=searchBlock(x); 
    int index;
    if(!blkPtr){ //value not found 
                //insert new value to lru pos
                //and promote
        
        #ifdef DEBUG
        printf("cache miss, inserting value %d\n",x);
        #endif 
        if(strategy_type==PLRU){
            blkPtr=find_plru();
            lru_index=getIndex(blkPtr);
            printf("evicting value:%d on pos %d for %d\n",blkPtr->value,lru_index,x);
            blkPtr->value=x;
            promote(blkPtr);
        }
        else{ //using IPV vector
            placeValue(x,15, ipv[16]); //17 position denodes the position a value is placed
        }
    }
    else{
        #ifdef DEBUG
        printf("cache hit!..promoting %d\n",getIndex(blkPtr));
        #endif
        if(strategy_type==PLRU)
            promote(blkPtr); 
        else{
                index=getIndex(blkPtr);
                placeValue(x,index,ipv[index]);
        }
    }
}