range list core data-structures More...

Macros
#define	NUM unsigned long

#define	BRANCH_FACTOR 4 /* factor of division of the range */

#define	LEAF_SIZE 16 /* how many numbers are represented by a leaf */

#define	NODE_SIZE sizeof(RL_Node)

#define	NODE(tree, idx) (RL_Node *)&tree->root[idx]

#define	ROOT(tree) 0

#define	IS_ROOT(tree, interval) (tree->range_max <= interval)

#define	ROOT_INTERVAL(tree) (tree->root_i * BRANCH_FACTOR)

#define	MIN(a, b) ((a < b) ? a : b)

#define	ON_BITS(n) (active_bits[n - 1])

#define	SET_LEAF_IN(max, node, quad_i)

#define	LEAF_ALL_IN(leaf) (leaf == 65535)

#define	LEAF_ALL_OUT(leaf) (leaf == 0)

#define	ALL_OUT(n) memset(n, 0, NODE_SIZE)

#define	ALL_IN(n) memset(n, 32767, NODE_SIZE)

#define	INODE_CAPACITY (LEAF_SIZE * BRANCH_FACTOR)

#define	QUADRANT_MAX_VALUE(node_num, quadrant, quadrant_interval, max) (MIN(node_num + quadrant_interval * quadrant - 1, max))

#define	NEXT_INTERVAL(interval)

#define	IS_LEAF(interval) ((interval <= LEAF_SIZE) ? 1 : 0)

#define	LAST_LEVEL_INODE(interval) ((interval <= LEAF_SIZE * BRANCH_FACTOR && interval > LEAF_SIZE) ? 1 : 0)

#define	REALLOC_MEM(tree) (tree->mem_alloc < (tree->size + 1) * NODE_SIZE)

#define	MEM_SIZE(tree) (tree->size + 2) * NODE_SIZE

#define	TREE_SIZE(tree) tree->mem_alloc + sizeof(RL_Tree)

#define	BITMAP_empty(b) ((b) == 0)

#define	BITMAP_member(b, n) (((b) & (1 << (n))) != 0)

#define	BITMAP_alone(b, n) ((b) == (1 << (n)))

#define	BITMAP_subset(b1, b2) (((b1) & (b2)) == b2)

#define	BITMAP_same(b1, b2) ((b1) == (b2))

#define	BITMAP_on_all(b) ((b) = 255)

#define	BITMAP_clear(b) ((b) = 0)

#define	BITMAP_and(b1, b2) ((b1) &= (b2))

#define	BITMAP_minus(b1, b2) ((b1) &= ~(b2))

#define	BITMAP_insert(b, n) ((b) \|= (1 << (n)))

#define	BITMAP_delete(b, n) ((b) &= (~(1 << (n))))

#define	BITMAP_copy(b1, b2) ((b1) = (b2))

#define	BITMAP_intersection(b1, b2, b3) ((b1) = ((b2) & (b3)))

#define	BITMAP_difference(b1, b2, b3) ((b1) = ((b2) & (~(b3))))

#define	BUFFER_SIZE 1000

#define	IS_FREEZED(tree) (tree->mem_alloc != 0)

Typedefs
typedef struct rl_struct	RL_Tree

typedef struct s_buffer	RL_Buffer

Enumerations
enum	QUADRANT_STATUS { R_TOTALLY_IN_INTERVAL = 3 , R_PARCIALLY_IN_INTERVAL = 2 , R_NOT_IN_INTERVAL = 0 , R_IGNORE = 1 }

enum	BOOLEAN { TRUE = 1 , FALSE = 0 }

enum	STATUS { IN = 1 , OUT = 0 }

Functions
RL_Tree *	new_rl (NUM max_size)

RL_Tree *	copy_rl (RL_Tree *tree)

void	free_rl (RL_Tree *range)

void	rl_all (RL_Tree *tree, STATUS status)

void	display_tree (RL_Tree *tree)

RL_Tree *	set_in_rl (RL_Tree *tree, NUM number, STATUS status)

BOOLEAN	in_rl (RL_Tree *range, NUM number)

BOOLEAN	freeze_rl (RL_Tree *tree)

RL_Tree *	intersect_rl (RL_Tree range1, RL_Tree range2)

NUM	rl_next_in_bigger (RL_Tree *tree, NUM min)

Detailed Description

range list core data-structures

Definition in file range_list.h.

Macro Definition Documentation

◆ ALL_IN

#define ALL_IN ( n ) memset(n, 32767, NODE_SIZE)

Definition at line 93 of file range_list.h.

◆ ALL_OUT

#define ALL_OUT ( n ) memset(n, 0, NODE_SIZE)

Definition at line 92 of file range_list.h.

◆ BITMAP_alone

#define BITMAP_alone	(	b,
		n
	)	((b) == (1 << (n)))

Definition at line 147 of file range_list.h.

◆ BITMAP_and

#define BITMAP_and	(	b1,
		b2
	)	((b1) &= (b2))

Definition at line 154 of file range_list.h.

◆ BITMAP_clear

#define BITMAP_clear ( b ) ((b) = 0)

Definition at line 153 of file range_list.h.

◆ BITMAP_copy

#define BITMAP_copy	(	b1,
		b2
	)	((b1) = (b2))

Definition at line 158 of file range_list.h.

◆ BITMAP_delete

#define BITMAP_delete	(	b,
		n
	)	((b) &= (~(1 << (n))))

Definition at line 157 of file range_list.h.

◆ BITMAP_difference

#define BITMAP_difference	(	b1,
		b2,
		b3
	)	((b1) = ((b2) & (~(b3))))

Definition at line 160 of file range_list.h.

◆ BITMAP_empty

#define BITMAP_empty ( b ) ((b) == 0)

Definition at line 145 of file range_list.h.

◆ BITMAP_insert

#define BITMAP_insert	(	b,
		n
	)	((b) \|= (1 << (n)))

Definition at line 156 of file range_list.h.

◆ BITMAP_intersection

#define BITMAP_intersection	(	b1,
		b2,
		b3
	)	((b1) = ((b2) & (b3)))

Definition at line 159 of file range_list.h.

◆ BITMAP_member

#define BITMAP_member	(	b,
		n
	)	(((b) & (1 << (n))) != 0)

Definition at line 146 of file range_list.h.

◆ BITMAP_minus

#define BITMAP_minus	(	b1,
		b2
	)	((b1) &= ~(b2))

Definition at line 155 of file range_list.h.

◆ BITMAP_on_all

#define BITMAP_on_all ( b ) ((b) = 255)

Definition at line 151 of file range_list.h.

◆ BITMAP_same

#define BITMAP_same	(	b1,
		b2
	)	((b1) == (b2))

Definition at line 149 of file range_list.h.

◆ BITMAP_subset

#define BITMAP_subset	(	b1,
		b2
	)	(((b1) & (b2)) == b2)

Definition at line 148 of file range_list.h.

◆ BRANCH_FACTOR

#define BRANCH_FACTOR 4 /* factor of division of the range */

Definition at line 69 of file range_list.h.

◆ BUFFER_SIZE

#define BUFFER_SIZE 1000

Definition at line 168 of file range_list.h.

◆ INODE_CAPACITY

#define INODE_CAPACITY (LEAF_SIZE * BRANCH_FACTOR)

Definition at line 94 of file range_list.h.

◆ IS_FREEZED

#define IS_FREEZED ( tree ) (tree->mem_alloc != 0)

Definition at line 188 of file range_list.h.

◆ IS_LEAF

#define IS_LEAF ( interval ) ((interval <= LEAF_SIZE) ? 1 : 0)

Definition at line 107 of file range_list.h.

◆ IS_ROOT

#define IS_ROOT	(	tree,
		interval
	)	(tree->range_max <= interval)

Definition at line 77 of file range_list.h.

◆ LAST_LEVEL_INODE

#define LAST_LEVEL_INODE ( interval ) ((interval <= LEAF_SIZE * BRANCH_FACTOR && interval > LEAF_SIZE) ? 1 : 0)

Definition at line 109 of file range_list.h.

◆ LEAF_ALL_IN

#define LEAF_ALL_IN ( leaf ) (leaf == 65535)

Definition at line 87 of file range_list.h.

◆ LEAF_ALL_OUT

#define LEAF_ALL_OUT ( leaf ) (leaf == 0)

Definition at line 89 of file range_list.h.

◆ LEAF_SIZE

#define LEAF_SIZE 16 /* how many numbers are represented by a leaf */

Definition at line 70 of file range_list.h.

◆ MEM_SIZE

#define MEM_SIZE ( tree ) (tree->size + 2) * NODE_SIZE

Definition at line 113 of file range_list.h.

◆ MIN

#define MIN	(	a,
		b
	)	((a < b) ? a : b)

Definition at line 80 of file range_list.h.

◆ NEXT_INTERVAL

#define NEXT_INTERVAL ( interval )

Value:

  ((interval <= LEAF_SIZE * BRANCH_FACTOR)                                     \
       ? LEAF_SIZE                                                             \
       : interval / BRANCH_FACTOR + interval % BRANCH_FACTOR)

Definition at line 102 of file range_list.h.

◆ NODE

#define NODE	(	tree,
		idx
	)	(RL_Node *)&tree->root[idx]

Definition at line 74 of file range_list.h.

◆ NODE_SIZE

#define NODE_SIZE sizeof(RL_Node)

Definition at line 72 of file range_list.h.

◆ NUM

#define NUM unsigned long

Definition at line 39 of file range_list.h.

◆ ON_BITS

#define ON_BITS ( n ) (active_bits[n - 1])

Definition at line 82 of file range_list.h.

◆ QUADRANT_MAX_VALUE

#define QUADRANT_MAX_VALUE	(	node_num,
		quadrant,
		quadrant_interval,
		max
	)	(MIN(node_num + quadrant_interval * quadrant - 1, max))

Definition at line 98 of file range_list.h.

◆ REALLOC_MEM

#define REALLOC_MEM ( tree ) (tree->mem_alloc < (tree->size + 1) * NODE_SIZE)

Definition at line 112 of file range_list.h.

◆ ROOT

#define ROOT ( tree ) 0

Definition at line 75 of file range_list.h.

◆ ROOT_INTERVAL

#define ROOT_INTERVAL ( tree ) (tree->root_i * BRANCH_FACTOR)

Definition at line 78 of file range_list.h.

◆ SET_LEAF_IN

#define SET_LEAF_IN	(	max,
		node,
		quad_i
	)

Value:

(node.leaf = \

ON_BITS(max - quad_i + 1))

Definition at line 83 of file range_list.h.

◆ TREE_SIZE

#define TREE_SIZE ( tree ) tree->mem_alloc + sizeof(RL_Tree)

Definition at line 115 of file range_list.h.

Typedef Documentation

◆ RL_Buffer

typedef struct s_buffer RL_Buffer

Definition at line 141 of file range_list.h.

◆ RL_Tree

typedef struct rl_struct RL_Tree

Definition at line 134 of file range_list.h.

Enumeration Type Documentation

◆ BOOLEAN

enum BOOLEAN

Definition at line 164 of file range_list.h.

◆ QUADRANT_STATUS

enum QUADRANT_STATUS

Definition at line 62 of file range_list.h.

◆ STATUS

enum STATUS

Definition at line 165 of file range_list.h.

Function Documentation

◆ copy_rl()

RL_Tree * copy_rl ( RL_Tree * tree )

Definition at line 139 of file range_list.c.

◆ display_tree()

void display_tree ( RL_Tree * tree )

Definition at line 771 of file range_list.c.

◆ free_rl()

void free_rl ( RL_Tree * range )

Definition at line 166 of file range_list.c.

◆ freeze_rl()

BOOLEAN freeze_rl ( RL_Tree * tree )

Definition at line 222 of file range_list.c.

◆ in_rl()

BOOLEAN in_rl	(	RL_Tree *	range,
		NUM	number
	)

Definition at line 213 of file range_list.c.

◆ new_rl()

RL_Tree * new_rl ( NUM max_size )

Definition at line 95 of file range_list.c.

◆ rl_all()

void rl_all	(	RL_Tree *	tree,
		STATUS	status
	)

Definition at line 197 of file range_list.c.

◆ rl_next_in_bigger()

NUM rl_next_in_bigger	(	RL_Tree *	tree,
		NUM	min
	)

Definition at line 246 of file range_list.c.

◆ set_in_rl()

RL_Tree * set_in_rl	(	RL_Tree *	tree,
		NUM	number,
		STATUS	status
	)

Definition at line 177 of file range_list.c.

Macros

Typedefs

Enumerations

Functions