/*
 * GPL HEADER START
 *
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 only,
 * as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License version 2 for more details (a copy is included
 * in the LICENSE file that accompanied this code).
 *
 * You should have received a copy of the GNU General Public License
 * version 2 along with this program; If not, see
 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 *
 * GPL HEADER END
 */
/*
 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
 * Use is subject to license terms.
 */
/*
 * This file is part of Lustre, http://www.lustre.org/
 * Lustre is a trademark of Sun Microsystems, Inc.
 *
 * lustre/include/interval_tree.h
 *
 * Author: Huang Wei <huangwei@clusterfs.com>
 * Author: Jay Xiong <jinshan.xiong@sun.com>
 */

#ifndef _INTERVAL_H__
#define _INTERVAL_H__

#include "../../include/linux/libcfs/libcfs.h"	/* LASSERT. */

struct interval_node {
	struct interval_node   *in_left;
	struct interval_node   *in_right;
	struct interval_node   *in_parent;
	unsigned		in_color:1,
				in_intree:1, /** set if the node is in tree */
				in_res1:30;
	__u8		    in_res2[4];  /** tags, 8-bytes aligned */
	__u64		   in_max_high;
	struct interval_node_extent {
		__u64 start;
		__u64 end;
	} in_extent;
};

enum interval_iter {
	INTERVAL_ITER_CONT = 1,
	INTERVAL_ITER_STOP = 2
};

static inline int interval_is_intree(struct interval_node *node)
{
	return node->in_intree == 1;
}

static inline __u64 interval_high(struct interval_node *node)
{
	return node->in_extent.end;
}

static inline void interval_set(struct interval_node *node,
				__u64 start, __u64 end)
{
	LASSERT(start <= end);
	node->in_extent.start = start;
	node->in_extent.end = end;
	node->in_max_high = end;
}

struct interval_node *interval_insert(struct interval_node *node,
				      struct interval_node **root);
void interval_erase(struct interval_node *node, struct interval_node **root);

#endif