/* Add a key-value pair. */
void
format_add(struct format_tree *ft, const char *key, const char *fmt, ...)
{
	struct format_entry	*fe;
	va_list			 ap;

	fe = xmalloc(sizeof *fe);
	fe->key = xstrdup(key);

	va_start(ap, fmt);
	xvasprintf(&fe->value, fmt, ap);
	va_end(ap);

	RB_INSERT(format_tree, ft, fe);
}

void
ct_match_insert_rb(struct ct_match *match, char *string)
{
	struct ct_match_node	*n;

	if (match->cm_mode != CT_MATCH_RB)
		CABORTX("match mode %d is not rb", match->cm_mode);
	n = e_calloc(1, sizeof(struct ct_match_node));
	n->cmn_string = e_strdup(string);
	if (RB_INSERT(ct_match_tree, match->cm_rb_head, n)) {
		/* pattern already exists free it */
		e_free(&n->cmn_string);
		e_free(&n);
	}
}

static void
ramstat_set(const char *name, const struct stat_value *val)
{
	struct ramstat_entry	*np, lk;

	log_trace(TRACE_STAT, "ramstat: set: %s", name);
	(void)strlcpy(lk.key, name, sizeof (lk.key));
	np = RB_FIND(stats_tree, &stats, &lk);
	if (np == NULL) {
		np = xcalloc(1, sizeof *np, "ramstat_set");
		(void)strlcpy(np->key, name, sizeof (np->key));
		RB_INSERT(stats_tree, &stats, np);
	}
	log_trace(TRACE_STAT, "ramstat: %s: n/a -> n/a", name);
	np->value = *val;
}

int uv_signal_start(uv_signal_t* handle, uv_signal_cb signal_cb, int signum) {
  uv_err_t err;

  /* If the user supplies signum == 0, then return an error already. If the */
  /* signum is otherwise invalid then uv__signal_register will find out */
  /* eventually. */
  if (signum == 0) {
    uv__set_artificial_error(handle->loop, UV_EINVAL);
    return -1;
  }

  /* Short circuit: if the signal watcher is already watching {signum} don't */
  /* go through the process of deregistering and registering the handler. */
  /* Additionally, this avoids pending signals getting lost in the (small) */
  /* time frame that handle->signum == 0. */
  if (signum == handle->signum) {
    handle->signal_cb = signal_cb;
    return 0;
  }

  /* If the signal handler was already active, stop it first. */
  if (handle->signum != 0) {
    int r = uv_signal_stop(handle);
    /* uv_signal_stop is infallible. */
    assert(r == 0);
  }

  EnterCriticalSection(&uv__signal_lock);

  err = uv__signal_register(signum);
  if (err.code != UV_OK) {
    /* Uh-oh, didn't work. */
    handle->loop->last_err = err;
    LeaveCriticalSection(&uv__signal_lock);
    return -1;
  }

  handle->signum = signum;
  RB_INSERT(uv_signal_tree_s, &uv__signal_tree, handle);

  LeaveCriticalSection(&uv__signal_lock);

  handle->signal_cb = signal_cb;
  uv__handle_start(handle);

  return 0;
}

struct options_entry *
options_set_number(struct options *oo, const char *name, long long value)
{
	struct options_entry	*o;

	if ((o = options_find1(oo, name)) == NULL) {
		o = xmalloc(sizeof *o);
		o->name = xstrdup(name);
		RB_INSERT(options_tree, &oo->tree, o);
		memcpy(&o->style, &grid_default_cell, sizeof o->style);
	} else if (o->type == OPTIONS_STRING)
		free(o->str);

	o->type = OPTIONS_NUMBER;
	o->num = value;
	return (o);
}

void
mode_key_init_trees(void)
{
	const struct mode_key_table	*mtab;
	const struct mode_key_entry	*ment;
	struct mode_key_binding		*mbind;

	for (mtab = mode_key_tables; mtab->name != NULL; mtab++) {
		RB_INIT(mtab->tree);
		for (ment = mtab->table; ment->key != KEYC_NONE; ment++) {
			mbind = xmalloc(sizeof *mbind);
			mbind->key = ment->key;
			mbind->cmd = ment->cmd;
			RB_INSERT(mode_key_tree, mtab->tree, mbind);
		}
	}
}

static void
ramstat_decrement(const char *name, size_t val)
{
	struct ramstat_entry	*np, lk;

	log_trace(TRACE_STAT, "ramstat: decrement: %s", name);
	(void)strlcpy(lk.key, name, sizeof (lk.key));
	np = RB_FIND(stats_tree, &stats, &lk);
	if (np == NULL) {
		np = xcalloc(1, sizeof *np, "ramstat_decrement");
		(void)strlcpy(np->key, name, sizeof (np->key));
		RB_INSERT(stats_tree, &stats, np);
	}
	log_trace(TRACE_STAT, "ramstat: %s (%p): %zd -> %zd",
	    name, name, np->value.u.counter, np->value.u.counter - val);
	np->value.u.counter -= val;
}

void
ct_extract_insert_entry(struct ct_pending_files *head, struct fnode *fnode)
{
	struct ct_pending_file	*cpf;

	CNDBG(CT_LOG_FILE, "%s: inserting %s", __func__, fnode->fn_fullname);
	cpf = e_calloc(1, sizeof(*cpf));
	cpf->cpf_name = e_strdup(fnode->fn_fullname);
	cpf->cpf_uid = fnode->fn_uid;
	cpf->cpf_gid = fnode->fn_gid;
	cpf->cpf_mode = fnode->fn_mode;
	cpf->cpf_mtime = fnode->fn_mtime;
	cpf->cpf_atime = fnode->fn_atime;

	TAILQ_INIT(&cpf->cpf_links);
	RB_INSERT(ct_pending_files, head, cpf);
}

int uv_timer_start(uv_timer_t* handle,
                   uv_timer_cb cb,
                   uint64_t timeout,
                   uint64_t repeat) {
  if (uv__is_active(handle))
    uv_timer_stop(handle);

  handle->timer_cb = cb;
  handle->timeout = handle->loop->time + timeout;
  handle->repeat = repeat;
  /* start_id is the second index to be compared in uv__timer_cmp() */
  handle->start_id = handle->loop->timer_counter++;

  RB_INSERT(uv__timers, &handle->loop->timer_handles, handle);
  uv__handle_start(handle);

  return 0;
}

/****************************************************************************
 **                                                                        **
 ** Name:    emm_proc_common_initialize()                              **
 **                                                                        **
 ** Description: Initialize EMM procedure callback functions executed for  **
 **      the UE with the given identifier                          **
 **                                                                        **
 ** Inputs:  ueid:      UE lower layer identifier                  **
 **      success:   EMM procedure executed upon successful EMM **
 **             common procedure completion                **
 **      reject:    EMM procedure executed if the EMM common   **
 **             procedure failed or is rejected            **
 **      failure:   EMM procedure executed upon transmission   **
 **             failure reported by lower layer            **
 **      abort:     EMM common procedure executed when the on- **
 **             going EMM procedure is aborted             **
 **      args:      EMM common procedure argument parameters   **
 **      Others:    None                                       **
 **                                                                        **
 ** Outputs:     None                                                      **
 **      Return:    RETURNok, RETURNerror                      **
 **      Others:    _emm_common_data                           **
 **                                                                        **
 ***************************************************************************/
int
emm_proc_common_initialize (
  unsigned int ueid,
  emm_common_success_callback_t _success,
  emm_common_reject_callback_t _reject,
  emm_common_failure_callback_t _failure,
  emm_common_abort_callback_t _abort,
  void *args)
{
  struct emm_common_data_s               *emm_common_data_ctx = NULL;

  LOG_FUNC_IN;
#if NAS_BUILT_IN_EPC
  assert (ueid > 0);
  emm_common_data_ctx = emm_common_data_context_get (&emm_common_data_head, ueid);
#else
  assert (ueid < EMM_DATA_NB_UE_MAX);
#endif

  if (emm_common_data_ctx == NULL) {
    emm_common_data_ctx = (emm_common_data_t *) malloc (sizeof (emm_common_data_t));
    emm_common_data_ctx->ueid = ueid;
#if NAS_BUILT_IN_EPC
    RB_INSERT (emm_common_data_map, &emm_common_data_head.emm_common_data_root, emm_common_data_ctx);
#endif

    if (emm_common_data_ctx) {
      emm_common_data_ctx->ref_count = 0;
    }
  }

  if (emm_common_data_ctx) {
    emm_common_data_ctx->ref_count += 1;
    emm_common_data_ctx->success = _success;
    emm_common_data_ctx->reject = _reject;
    emm_common_data_ctx->failure = _failure;
    emm_common_data_ctx->abort = _abort;
    emm_common_data_ctx->args = args;
    LOG_FUNC_RETURN (RETURNok);
  }

  LOG_FUNC_RETURN (RETURNerror);
}

int uv_timer_start(uv_timer_t* handle,
                   uv_timer_cb cb,
                   int64_t timeout,
                   int64_t repeat) {
  assert(timeout >= 0);
  assert(repeat >= 0);

  if (uv__is_active(handle))
    uv_timer_stop(handle);

  handle->timer_cb = cb;
  handle->timeout = handle->loop->time + timeout;
  handle->repeat = repeat;

  RB_INSERT(uv__timers, &handle->loop->timer_handles, handle);
  uv__handle_start(handle);

  return 0;
}

static void
add_tree_node(tcpr_tree_t *newnode)
{
    tcpr_tree_t *node;

    /* try to find a simular entry in the tree */
    node = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);

    dbgx(3, "%s", tree_printnode("add_tree", node));

    /* new entry required */
    if (node == NULL) {
        /* increment counters */
        if (newnode->type == DIR_SERVER) {
            newnode->server_cnt++;
        }
        else if (newnode->type == DIR_CLIENT) {
            newnode->client_cnt++;
        }
        /* insert it in */
        RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);

    }
    else {
        /* we found something, so update it */
        dbgx(2, "   node: %p\nnewnode: %p", node, newnode);
        dbgx(3, "%s", tree_printnode("update node", node));
        /* increment counter */
        if (newnode->type == DIR_SERVER) {
            node->server_cnt++;
        }
        else if (newnode->type == DIR_CLIENT) {
            /* temp debug code */
            node->client_cnt++;
        }
                    
        /* didn't insert it, so free it */
        safe_free(newnode);
    }

    dbg(2, "------- START NEXT -------");
    dbgx(3, "%s", tree_print(&treeroot));
}

void notify_sel(int slot, const dm_selector sel,
		const DM_VALUE value, enum notify_type type)
{
#if defined(SDEBUG)
        char b1[MAX_PARAM_NAME_LEN];
#endif
	struct notify_item si;

	uint32_t ntfy = value.notify;

	if (ntfy == 0)
		/* not notify's at all */
		return;

	debug("(): %s, %08x ... %d", dm_sel2name(sel, b1, sizeof(b1)), ntfy, slot);

	dm_selcpy(si.sb, sel);

	for (int i = 0; i < 16; i++) {
		/* skip notify for slot */
		if (i != slot) {
			int level = ntfy & 0x0003;
			if (level) {
				struct notify_item *item;
				item = RB_FIND(notify_queue, &slots[i].queue, &si);
				if (!item) {
					item = malloc(sizeof(struct notify_item));
					if (!item)
						continue;
					dm_selcpy(item->sb, sel);

					RB_INSERT(notify_queue, &slots[i].queue, item);
					notify_pending = 1;
				}
				item->level = level;
				item->type = type;
				item->value = value;
			}
		}
		ntfy >>= 2;
	}
}

int flexran_agent_create_channel(void *channel_info,
				 int (*msg_send)(void *data, int size, int priority, void *channel_info),
				 int (*msg_recv)(void **data, int *size, int *priority, void *channel_info),
				 void (*release)(flexran_agent_channel_t *channel)) {
  
  int channel_id = ++flexran_agent_channel_id;
  flexran_agent_channel_t *channel = (flexran_agent_channel_t *) malloc(sizeof(flexran_agent_channel_t));
  channel->channel_id = channel_id;
  channel->channel_info = channel_info;
  channel->msg_send = msg_send;
  channel->msg_recv = msg_recv;
  channel->release = release;
  
  /*element should be a real pointer*/
  RB_INSERT(flexran_agent_channel_map, &channel_instance.flexran_agent_head, channel); 
  
  LOG_I(FLEXRAN_AGENT,"Created a new channel with id 0x%lx\n", channel->channel_id);
 
  return channel_id; 
}

int drm_adddraw(struct drm_device *dev, void *data, struct drm_file *file_priv)
{
	struct drm_draw *draw = data;
	struct bsd_drm_drawable_info *info;

	info = malloc(sizeof(struct bsd_drm_drawable_info), DRM_MEM_DRAWABLE,
	    M_NOWAIT | M_ZERO);
	if (info == NULL)
		return ENOMEM;

	info->handle = alloc_unr(dev->drw_unrhdr);
	DRM_SPINLOCK(&dev->drw_lock);
	RB_INSERT(drawable_tree, &dev->drw_head, info);
	draw->handle = info->handle;
	DRM_SPINUNLOCK(&dev->drw_lock);

	DRM_DEBUG("%d\n", draw->handle);

	return 0;
}

struct options_entry *
options_set_string(struct options *oo, const char *name, const char *fmt, ...)
{
	struct options_entry	*o;
	va_list			 ap;

	if ((o = options_find1(oo, name)) == NULL) {
		o = xmalloc(sizeof *o);
		o->name = xstrdup(name);
		RB_INSERT(options_tree, &oo->tree, o);
		memcpy(&o->style, &grid_default_cell, sizeof o->style);
	} else if (o->type == OPTIONS_STRING)
		free(o->str);

	va_start(ap, fmt);
	o->type = OPTIONS_STRING;
	xvasprintf(&o->str, fmt, ap);
	va_end(ap);
	return (o);
}

int arp_cache_insert(in_addr_t ip_addr, const mac_addr_t haddr,
                     enum arp_cache_entry_type type)
{
    size_t i;
    struct arp_cache_entry * it;
    struct arp_cache_entry * entry = NULL;

    if (ip_addr == 0) {
        return 0;
    }

    it = arp_cache;
    for (i = 0; i < num_elem(arp_cache); i++) {
        if (it->age == ARP_CACHE_FREE) {
            entry = it;
        } else if ((entry && entry->age > it->age) ||
                   (!entry && it->age >= 0)) {
            entry = it;
        }
        /* TODO Use RB_FIND first */
        if (it->ip_addr == ip_addr) {
            /* This is a replacement for an existing entry. */
            entry = it;
            break;
        }
        it++;
    }
    if (!entry) {
        errno = ENOMEM;
        return -1;
    } else if (entry->age >= 0) {
        RB_REMOVE(arp_cache_tree, &arp_cache_head, entry);
    }

    entry->ip_addr = ip_addr;
    memcpy(entry->haddr, haddr, sizeof(mac_addr_t));
    entry->age = (int)type;
    RB_INSERT(arp_cache_tree, &arp_cache_head, entry);

    return 0;
}

struct peak_track *
peak_track_acquire(struct peak_tracks *self, const struct peak_track *ref)
{
	struct peak_track *flow;

	if (unlikely(!ref)) {
		return (NULL);
	}

	flow = RB_FIND(peak_track_tree, &self->flows, ref);
	if (likely(flow)) {
		TAILQ_REMOVE(&self->tos, flow, tq_to);
		TAILQ_INSERT_TAIL(&self->tos, flow, tq_to);

		return (flow);
	}

	if (prealloc_empty(&self->mem)) {
		flow = TAILQ_FIRST(&self->tos);
		TAILQ_REMOVE(&self->tos, flow, tq_to);
		RB_REMOVE(peak_track_tree, &self->flows, flow);
		prealloc_put(&self->mem, flow);
	}

	flow = prealloc_get(&self->mem);
	if (unlikely(!flow)) {
		panic("flow pool empty\n");
	}

	bzero(flow, sizeof(*flow));
	memcpy(flow, ref, TRACK_SIZE(ref));

	if (unlikely(RB_INSERT(peak_track_tree, &self->flows, flow))) {
		panic("can't insert flow\n");
	}

	flow->id = __sync_fetch_and_add(&next_flow_id, 1);
	TAILQ_INSERT_TAIL(&self->tos, flow, tq_to);

	return (flow);
}

/*
 * This is called when an inode backend flush is finished.  We have to make
 * sure that RDIRTY is not set unless dirty bufs are present.  Dirty bufs
 * can get destroyed through operations such as truncations and leave
 * us with a stale redo_fifo_next.
 */
void
hammer_redo_fifo_end_flush(hammer_inode_t ip)
{
	hammer_mount_t hmp = ip->hmp;

	if (ip->flags & HAMMER_INODE_RDIRTY) {
		RB_REMOVE(hammer_redo_rb_tree, &hmp->rb_redo_root, ip);
		ip->flags &= ~HAMMER_INODE_RDIRTY;
	}
	if ((ip->flags & HAMMER_INODE_BUFS) == 0)
		ip->redo_fifo_next = 0;
	if (ip->redo_fifo_next) {
		ip->redo_fifo_start = ip->redo_fifo_next;
		if (RB_INSERT(hammer_redo_rb_tree, &hmp->rb_redo_root, ip)) {
			panic("hammer_generate_redo: cannot reinsert "
			      "inode %p on redo FIFO",
			      ip);
		}
		ip->flags |= HAMMER_INODE_RDIRTY;
	}
}

char *
group_create(struct ctl_group *ctl)
{
	struct group *g;

	if ((g = group_new()) == NULL)
		return "out of memory";

	strlcpy(g->name, ctl->name, sizeof g->name);
	g->next = group_use(&default_group);

	if (RB_FIND(group_tree, &groups, g)) {
		free(g);
		return "group already there";
	}

	RB_INSERT(group_tree, &groups, g);

	log_debug("group created: %s", g->name);
	return NULL;
}