void prdebug_sock_tag_tree(int indent_level,
			   struct rb_root *sock_tag_tree)
{
	struct rb_node *node;
	struct sock_tag *sock_tag_entry;
	char *str;

	if (!unlikely(qtaguid_debug_mask & DDEBUG_MASK))
		return;

	if (RB_EMPTY_ROOT(sock_tag_tree)) {
		str = "sock_tag_tree=rb_root{}";
		pr_debug("%*d: %s\n", indent_level*2, indent_level, str);
		return;
	}

	str = "sock_tag_tree=rb_root{";
	pr_debug("%*d: %s\n", indent_level*2, indent_level, str);
	indent_level++;
	for (node = rb_first(sock_tag_tree);
	     node;
	     node = rb_next(node)) {
		sock_tag_entry = rb_entry(node, struct sock_tag, sock_node);
		str = pp_sock_tag(sock_tag_entry);
		pr_debug("%*d: %s,\n", indent_level*2, indent_level, str);
		kfree(str);
	}
	indent_level--;
	str = "}";
	pr_debug("%*d: %s\n", indent_level*2, indent_level, str);
}

static struct fiops_ioc *fiops_select_ioc(struct fiops_data *fiopsd)
{
	struct fiops_ioc *ioc;
	struct fiops_rb_root *service_tree = NULL;
	int i;
	struct request *rq;

	for (i = RT_WORKLOAD; i >= IDLE_WORKLOAD; i--) {
		if (!RB_EMPTY_ROOT(&fiopsd->service_tree[i].rb)) {
			service_tree = &fiopsd->service_tree[i];
			break;
		}
	}

	if (!service_tree)
		return NULL;

	ioc = fiops_rb_first(service_tree);

	rq = rq_entry_fifo(ioc->fifo.next);
	/*
	 * we are the only async task and sync requests are in flight, delay a
	 * moment. If there are other tasks coming, sync tasks have no chance
	 * to be starved, don't delay
	 */
	if (!rq_is_sync(rq) && fiopsd->in_flight[1] != 0 &&
			service_tree->count == 1) {
		fiops_log_ioc(fiopsd, ioc,
				"postpone async, in_flight async %d sync %d",
				fiopsd->in_flight[0], fiopsd->in_flight[1]);
		return NULL;
	}

	return ioc;
}

static unsigned int remove_extent(struct results_tree *res, struct extent *extent)
{
	struct dupe_extents *p = extent->e_parent;
	struct rb_node *n;
	unsigned int result;

again:
	p->de_score -= p->de_len;
	p->de_num_dupes--;
	result = p->de_num_dupes;

	list_del_init(&extent->e_list);
	list_del_init(&extent->e_file_extents);
	rb_erase(&extent->e_node, &p->de_extents_root);
	free_extent(extent);

	if (p->de_num_dupes == 1) {
		/* It doesn't make sense to have one extent in a dup
		 * list. */
		abort_on(RB_EMPTY_ROOT(&p->de_extents_root));/* logic error */

		n = rb_first(&p->de_extents_root);
		extent = rb_entry(n, struct extent, e_node);
		goto again;
	}

static void print_summary(const char *filename)
{
	struct sym_ext *sym_ext;
	struct rb_node *node;

	printf("\nSorted summary for file %s\n", filename);
	printf("----------------------------------------------\n\n");

	if (RB_EMPTY_ROOT(&root_sym_ext)) {
		printf(" Nothing higher than %1.1f%%\n", MIN_GREEN);
		return;
	}

	node = rb_first(&root_sym_ext);
	while (node) {
		double percent;
		const char *color;
		char *path;

		sym_ext = rb_entry(node, struct sym_ext, node);
		percent = sym_ext->percent;
		color = get_percent_color(percent);
		path = sym_ext->path;

		color_fprintf(stdout, color, " %7.2f %s", percent, path);
		node = rb_next(node);
	}
}

static int namei_dscan(ext2_ino_t ino, struct ext2_inode *inode,
		       struct dentry *parent, const char *name, int namelen,
		       struct ea_info *eas)
{
	struct target_inode *t = namei_find_inode(ino);
	int offset;

	/* We may have already printed a name for this inode, and no longer
	 * care about it.
	 */
	if (!t)
		return ACTION_COMPLETE;

	if (--t->nlinks == 0)
		rb_erase(&t->rb_node, &namei_targets);

	offset = build_path(parent, 0);
	fprintf(outfile, "%lu %.*s%.*s\n", ino, offset, path_buffer,
			 namelen, name);

	if (RB_EMPTY_ROOT(&namei_targets))
		return ACTION_END_SCAN;

	return ACTION_COMPLETE;
}

/*
 * lookup rb entry in position of @ofs in rb-tree,
 * if hit, return the entry, otherwise, return NULL
 * @prev_ex: extent before ofs
 * @next_ex: extent after ofs
 * @insert_p: insert point for new extent at ofs
 * in order to simpfy the insertion after.
 * tree must stay unchanged between lookup and insertion.
 */
struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root *root,
				struct rb_entry *cached_re,
				unsigned int ofs,
				struct rb_entry **prev_entry,
				struct rb_entry **next_entry,
				struct rb_node ***insert_p,
				struct rb_node **insert_parent,
				bool force)
{
	struct rb_node **pnode = &root->rb_node;
	struct rb_node *parent = NULL, *tmp_node;
	struct rb_entry *re = cached_re;

	*insert_p = NULL;
	*insert_parent = NULL;
	*prev_entry = NULL;
	*next_entry = NULL;

	if (RB_EMPTY_ROOT(root))
		return NULL;

	if (re) {
		if (re->ofs <= ofs && re->ofs + re->len > ofs)
			goto lookup_neighbors;
	}

	while (*pnode) {
		parent = *pnode;
		re = rb_entry(*pnode, struct rb_entry, rb_node);

		if (ofs < re->ofs)
			pnode = &(*pnode)->rb_left;
		else if (ofs >= re->ofs + re->len)
			pnode = &(*pnode)->rb_right;
		else
			goto lookup_neighbors;
	}

	*insert_p = pnode;
	*insert_parent = parent;

	re = rb_entry(parent, struct rb_entry, rb_node);
	tmp_node = parent;
	if (parent && ofs > re->ofs)
		tmp_node = rb_next(parent);
	*next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);

	tmp_node = parent;
	if (parent && ofs < re->ofs)
		tmp_node = rb_prev(parent);
	*prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
	return NULL;

lookup_neighbors:
	if (ofs == re->ofs || force) {
		/* lookup prev node for merging backward later */
		tmp_node = rb_prev(&re->rb_node);
		*prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
	}

void itree_teardown(struct inode_tree *itree)
{
	struct rb_node *rbnode;
	struct itree_node *itnode;

	while (!RB_EMPTY_ROOT(&itree->inodes)) {
		rbnode = rb_first(&itree->inodes);
		rb_erase(rbnode, &itree->inodes);
	}

	while (!RB_EMPTY_ROOT(&itree->sorted)) {
		rbnode = rb_first(&itree->sorted);
		itnode = rb_entry(rbnode, struct itree_node, sorted_node);
		rb_erase(rbnode, &itree->sorted);
		free(itnode);
	}
}

static int namei_init(const char *device, int argc, const char **argv)
{
	unsigned long ino;
	FILE *file;
	int rc;

	while (argc--) {
		if (!strcmp(*argv, "all_names")) {
			namei_all_names = 1;
		} else if (!strncmp(*argv, "file=", 5)) {
			file = fopen(*argv + 5, "r");
			if (!file) {
				int e = errno;
				fprintf(stderr, "Unable to open ");
				errno = e;
				perror(*argv + 5);
				return 1;
			}

			while (!feof(file)) {
				rc = fscanf(file, "%lu", &ino);
				if (rc == 1)
					namei_add_inode(ino);
				else if (rc != EOF) {
					fprintf(stderr, "Bad read from %s\n",
							*argv + 5);
					fclose(file);
					return 1;
				}
			}
			fclose(file);
		} else {
			char *end;
			if (!**argv) {
				fprintf(stderr, "Unable to parse empty action "
						"arg\n");
				return 1;
			}
			ino = strtoul(*argv, &end, 0);
			if (*end || end == *argv) {
				fprintf(stderr, "Invalid action argument "
						"'%s'\n", *argv);
				return 1;
			}
			namei_add_inode(ino);
		}

		argv++;
	}

	if (RB_EMPTY_ROOT(&namei_targets)) {
		fprintf(stderr, "No inodes given to name\n");
		return 1;
	}

	return 0;
}

    void CPageMgr::RemoveIndexTreeIfNeed(size_t pagecount)
    {
        struct SHashNode * hashNode     = GetHashNode(pagecount);
        struct SIndexInfo * indexInfo   = (struct SIndexInfo *)RbSearch(&hashNode->hash_tree, 
                &pagecount, &CPageMgr::HashTreeGetObject, &CPageMgr::HashTreeSearch);

        if (RB_EMPTY_ROOT(&indexInfo->free_tree)) {
            RbRemove(&hashNode->hash_tree, indexInfo, &CPageMgr::HashTreeGetRbNode);
            ReleaseIndexInfo(indexInfo);
        }
    }

static void fiops_charge_vios(struct fiops_data *fiopsd,
	struct fiops_ioc *ioc, u64 vios)
{
	struct fiops_rb_root *service_tree = ioc->service_tree;
	ioc->vios += vios;

	if (RB_EMPTY_ROOT(&ioc->sort_list))
		fiops_del_ioc_rr(fiopsd, ioc);
	else
		fiops_resort_rr_list(fiopsd, ioc);

	fiops_update_min_vios(service_tree);
}

static int i915_gem_userptr_mn_invalidate_range_start(struct mmu_notifier *_mn,
						       struct mm_struct *mm,
						       unsigned long start,
						       unsigned long end,
						       bool blockable)
{
	struct i915_mmu_notifier *mn =
		container_of(_mn, struct i915_mmu_notifier, mn);
	struct i915_mmu_object *mo;
	struct interval_tree_node *it;
	LIST_HEAD(cancelled);

	if (RB_EMPTY_ROOT(&mn->objects.rb_root))
		return 0;

	/* interval ranges are inclusive, but invalidate range is exclusive */
	end--;

	spin_lock(&mn->lock);
	it = interval_tree_iter_first(&mn->objects, start, end);
	while (it) {
		if (!blockable) {
			spin_unlock(&mn->lock);
			return -EAGAIN;
		}
		/* The mmu_object is released late when destroying the
		 * GEM object so it is entirely possible to gain a
		 * reference on an object in the process of being freed
		 * since our serialisation is via the spinlock and not
		 * the struct_mutex - and consequently use it after it
		 * is freed and then double free it. To prevent that
		 * use-after-free we only acquire a reference on the
		 * object if it is not in the process of being destroyed.
		 */
		mo = container_of(it, struct i915_mmu_object, it);
		if (kref_get_unless_zero(&mo->obj->base.refcount))
			queue_work(mn->wq, &mo->work);

		list_add(&mo->link, &cancelled);
		it = interval_tree_iter_next(it, start, end);
	}
	list_for_each_entry(mo, &cancelled, link)
		del_object(mo);
	spin_unlock(&mn->lock);

	if (!list_empty(&cancelled))
		flush_workqueue(mn->wq);

	return 0;
}

/*
 * Get the first inode from the sorted tree, then remove from both. Use
 * itree_get_inode function to retrieve the inode. Returns 1 if any
 * errors occurred, otherwise the inode is returned with its refcount
 * updated.
 */
int itree_fetch(struct inode_tree *itree, __u8 taskid, int duet_fd, char *path,
	unsigned long long *uuid, long long *inmem)
{
	int ret = 0;
	struct rb_node *rbnode;
	struct itree_node *itnode;

	*uuid = 0;
	path[0] = '\0';
again:
	if (RB_EMPTY_ROOT(&itree->sorted))
		return 0;

	/* Grab last node in the sorted tree, and remove from both trees */
	rbnode = rb_last(&itree->sorted);
	itnode = rb_entry(rbnode, struct itree_node, sorted_node);
	rb_erase(&itnode->sorted_node, &itree->sorted);
	rb_erase(&itnode->inodes_node, &itree->inodes);

	*uuid = itnode->uuid;
	*inmem = itnode->inmem;
	free(itnode);

	itree_dbg("itree: fetch picked uuid %llu, inode %lu\n", *uuid,
		DUET_UUID_INO(*uuid));

	/* Check if we've processed it before */
	if (duet_check_done(duet_fd, taskid, *uuid, 1) == 1)
		goto again;

	itree_dbg("itree: fetching uuid %llu, inode %lu\n", *uuid,
		DUET_UUID_INO(*uuid));

	/* Get the path for this inode */
	if (duet_get_path(duet_fd, taskid, *uuid, path)) {
		//fprintf(stderr, "itree: inode path not found\n");
		goto again;
	}

	/* If this isn't a child, mark to avoid, and retry */
	if (path[0] == '\0') {
		//duet_set_done(duet_fd, taskid, *uuid, 1);
		//itree_dbg("itree: marking uuid %llu, ino %lu for task %u to avoid\n",
		//	*uuid, DUET_UUID_INO(*uuid), taskid);
		goto again;
	}

	return ret;
}

/*
 * osd map
 */
void ceph_osdmap_destroy(struct ceph_osdmap *map)
{
	dout("osdmap_destroy %p\n", map);
	if (map->crush)
		crush_destroy(map->crush);
	while (!RB_EMPTY_ROOT(&map->pg_temp)) {
		struct ceph_pg_mapping *pg =
			rb_entry(rb_first(&map->pg_temp),
				 struct ceph_pg_mapping, node);
		rb_erase(&pg->node, &map->pg_temp);
		kfree(pg);
	}
	while (!RB_EMPTY_ROOT(&map->pg_pools)) {
		struct ceph_pg_pool_info *pi =
			rb_entry(rb_first(&map->pg_pools),
				 struct ceph_pg_pool_info, node);
		rb_erase(&pi->node, &map->pg_pools);
		kfree(pi);
	}
	kfree(map->osd_state);
	kfree(map->osd_weight);
	kfree(map->osd_addr);
	kfree(map);
}

void digest_free(struct rb_root *root)
{
	struct rb_node *n = rb_first(root);
	struct d_tree *t;

	while (n) {
		t = rb_entry(n, struct d_tree, t_node);
		n = rb_next(n);
		rb_erase(&t->t_node, root);
		free(t->digest);
		free(t);
	}

	abort_on(!RB_EMPTY_ROOT(root));
}

static int check_rbtree_empty(struct intel_engine_cs *engine)
{
	struct intel_breadcrumbs *b = &engine->breadcrumbs;

	if (b->irq_wait) {
		pr_err("Empty breadcrumbs still has a waiter\n");
		return -EINVAL;
	}

	if (!RB_EMPTY_ROOT(&b->waiters)) {
		pr_err("Empty breadcrumbs, but wait-tree not empty\n");
		return -EINVAL;
	}

	return 0;
}

static void
fiops_merged_requests(struct request_queue *q, struct request *rq,
		    struct request *next)
{
	struct fiops_ioc *ioc = RQ_CIC(rq);
	struct fiops_data *fiopsd = q->elevator->elevator_data;

	fiops_remove_request(next);

	ioc = RQ_CIC(next);
	/*
	 * all requests of this task are merged to other tasks, delete it
	 * from the service tree.
	 */
	if (fiops_ioc_on_rr(ioc) && RB_EMPTY_ROOT(&ioc->sort_list))
		fiops_del_ioc_rr(fiopsd, ioc);
}

static void smc_lgr_free_work(struct work_struct *work)
{
	struct smc_link_group *lgr = container_of(to_delayed_work(work),
						  struct smc_link_group,
						  free_work);
	bool conns;

	spin_lock_bh(&smc_lgr_list.lock);
	if (list_empty(&lgr->list))
		goto free;
	read_lock_bh(&lgr->conns_lock);
	conns = RB_EMPTY_ROOT(&lgr->conns_all);
	read_unlock_bh(&lgr->conns_lock);
	if (!conns) { /* number of lgr connections is no longer zero */
		spin_unlock_bh(&smc_lgr_list.lock);
		return;
	}
	list_del_init(&lgr->list); /* remove from smc_lgr_list */
free:
	spin_unlock_bh(&smc_lgr_list.lock);

	if (!lgr->is_smcd && !lgr->terminating)	{
		struct smc_link *lnk = &lgr->lnk[SMC_SINGLE_LINK];

		/* try to send del link msg, on error free lgr immediately */
		if (lnk->state == SMC_LNK_ACTIVE &&
		    !smc_link_send_delete(lnk)) {
			/* reschedule in case we never receive a response */
			smc_lgr_schedule_free_work(lgr);
			return;
		}
	}

	if (!delayed_work_pending(&lgr->free_work)) {
		struct smc_link *lnk = &lgr->lnk[SMC_SINGLE_LINK];

		if (!lgr->is_smcd && lnk->state != SMC_LNK_INACTIVE)
			smc_llc_link_inactive(lnk);
		if (lgr->is_smcd)
			smc_ism_signal_shutdown(lgr);
		smc_lgr_free(lgr);
	}
}

static void smc_lgr_free_work(struct work_struct *work)
{
	struct smc_link_group *lgr = container_of(to_delayed_work(work),
						  struct smc_link_group,
						  free_work);
	bool conns;

	spin_lock_bh(&smc_lgr_list.lock);
	read_lock_bh(&lgr->conns_lock);
	conns = RB_EMPTY_ROOT(&lgr->conns_all);
	read_unlock_bh(&lgr->conns_lock);
	if (!conns) { /* number of lgr connections is no longer zero */
		spin_unlock_bh(&smc_lgr_list.lock);
		return;
	}
	list_del_init(&lgr->list); /* remove from smc_lgr_list */
	spin_unlock_bh(&smc_lgr_list.lock);
	smc_lgr_free(lgr);
}

static int fiops_forced_dispatch(struct fiops_data *fiopsd)
{
	struct fiops_ioc *ioc;
	int dispatched = 0;
	int i;

	for (i = RT_WORKLOAD; i >= IDLE_WORKLOAD; i--) {
		while (!RB_EMPTY_ROOT(&fiopsd->service_tree[i].rb)) {
			ioc = fiops_rb_first(&fiopsd->service_tree[i]);

			while (!list_empty(&ioc->fifo)) {
				fiops_dispatch_request(fiopsd, ioc);
				dispatched++;
			}
			if (fiops_ioc_on_rr(ioc))
				fiops_del_ioc_rr(fiopsd, ioc);
		}
	}
	return dispatched;
}

/*
 * allow the fileserver to request callback state (re-)initialisation
 */
void afs_init_callback_state(struct afs_server *server)
{
	struct afs_vnode *vnode;

	_enter("{%p}", server);

	spin_lock(&server->cb_lock);

	/* kill all the promises on record from this server */
	while (!RB_EMPTY_ROOT(&server->cb_promises)) {
		vnode = rb_entry(server->cb_promises.rb_node,
				 struct afs_vnode, cb_promise);
		_debug("UNPROMISE { vid=%x:%u uq=%u}",
		       vnode->fid.vid, vnode->fid.vnode, vnode->fid.unique);
		rb_erase(&vnode->cb_promise, &server->cb_promises);
		vnode->cb_promised = false;
	}

	spin_unlock(&server->cb_lock);
	_leave("");
}