1 /******************************************************************************************* 2 3 Copyright (C) 2004,2005,2006,2007,2008 (Nuno A. Fonseca) <nuno.fonseca@gmail.com> 4 5 This program is free software; you can redistribute it and/or 6 modify it under the terms of the GNU General Public License 7 as published by the Free Software Foundation; either 8 version 2 of the License, or (at your option) any later 9 version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 19 20 21 Last rev: $Id: range_list.h,v 1.1 2008-03-26 23:05:22 nunofonseca Exp $ 22 **************************************************************************/ 23 24 25 /* 26 Leaf 27 Each leaf uses 16 bits ( each bit represents one number ) 28 29 */ 30 #define NUM unsigned long 31 /* 32 Node 33 Each node (non leaf) uses 8 bits. 34 - 8 bits are used to represent the state of the 4 subtrees ( subranges ). 35 - 2 bits are used to represent the state for each subtreee 36 37 States of a subtree: 38 00 (0) - range not in interval 39 11 (3)- all range in interval 40 10 (2)- range parcially in interval 41 42 An extra byte is used to keep the number of nodes in the subtrees. 43 */ 44 struct s_node { 45 //short quadrant; 46 unsigned short int quadrant_1: 2; // 47 unsigned short int quadrant_2: 2; 48 unsigned short int quadrant_3: 2; 49 unsigned short int quadrant_4: 2; 50 unsigned short int num_subnodes: 8; 51 }; 52 53 typedef enum { R_TOTALLY_IN_INTERVAL=3, R_PARCIALLY_IN_INTERVAL=2, R_NOT_IN_INTERVAL=0, R_IGNORE=1} QUADRANT_STATUS; 54 55 56 #define BRANCH_FACTOR 4 /* factor of division of the range */ 57 #define LEAF_SIZE 16 /* how many numbers are represented by a leaf */ 58 59 #define NODE_SIZE sizeof(RL_Node) 60 61 #define NODE(tree,idx) (RL_Node*)&tree->root[idx] 62 #define ROOT(tree) 0 63 64 #define IS_ROOT(tree,interval) (tree->range_max<=interval) 65 #define ROOT_INTERVAL(tree) (tree->root_i*BRANCH_FACTOR) 66 67 #define MIN(a,b) ((a<b)?a:b) 68 69 #define ON_BITS(n) (active_bits[n-1]) // mask to check if bits until n are in 70 #define SET_LEAF_IN(max,node,quad_i) (node.leaf=ON_BITS(max-quad_i+1)) // mask to check if bits until n are in 71 72 #define LEAF_ALL_IN(leaf) (leaf==65535) // return true if all numbers in leaf are IN (selected) 73 #define LEAF_ALL_OUT(leaf) (leaf==0) // return true if all numbers in leaf are OUT 74 75 #define ALL_OUT(n) memset(n,0,NODE_SIZE) // turn out a node 76 #define ALL_IN(n) memset(n,32767,NODE_SIZE) // turn in a leaf 77 #define INODE_CAPACITY (LEAF_SIZE*BRANCH_FACTOR) // minimum range that a inode stores 78 79 // returns the maximum number that a quadrant stores 80 #define QUADRANT_MAX_VALUE(node_num,quadrant,quadrant_interval,max) (MIN(node_num+quadrant_interval*quadrant-1,max)) 81 82 // returns the interval size for the next level in the tree 83 #define NEXT_INTERVAL(interval) ((interval<=LEAF_SIZE*BRANCH_FACTOR)?LEAF_SIZE:interval/BRANCH_FACTOR+interval%BRANCH_FACTOR) 84 85 86 87 #define IS_LEAF(interval) ((interval<=LEAF_SIZE)?1:0) // check if a interval of type Leaf 88 #define LAST_LEVEL_INODE(interval) ((interval<=LEAF_SIZE*BRANCH_FACTOR && interval>LEAF_SIZE)?1:0) 89 90 #define REALLOC_MEM(tree) (tree->mem_alloc < (tree->size+1)*NODE_SIZE) 91 #define MEM_SIZE(tree) (tree->size+2)*NODE_SIZE 92 93 94 #define TREE_SIZE(tree) tree->mem_alloc+sizeof(RL_Tree) 95 96 97 typedef union { 98 struct s_node i_node; 99 unsigned short int leaf; 100 } RL_Node; /* A node is a internal node (inode) or a leaf depending on their depth in the tree */ 101 102 103 /* 104 Range_List 105 Contains the root node, max range size, 106 */ 107 struct rl_struct { 108 RL_Node* root; 109 NUM size; // number of nodes 110 NUM mem_alloc; // memory allocated for *root 111 NUM range_max; // maximum value of the interval 112 NUM root_i; // root interval 113 }; 114 typedef struct rl_struct RL_Tree; 115 116 117 /* Buffer */ 118 struct s_buffer { 119 RL_Node* root_node; 120 unsigned long size; // memory (in bytes) allocated for root_node 121 }; 122 typedef struct s_buffer RL_Buffer; 123 124 //---------------------------------------------------------------- 125 // Bits operations 126 #define BITMAP_empty(b) ((b) == 0) 127 #define BITMAP_member(b,n) (((b) & (1<<(n))) != 0) 128 #define BITMAP_alone(b,n) ((b) == (1<<(n))) 129 #define BITMAP_subset(b1,b2) (((b1) & (b2)) == b2) 130 #define BITMAP_same(b1,b2) ((b1) == (b2)) 131 132 #define BITMAP_on_all(b) ((b) = 255) 133 134 #define BITMAP_clear(b) ((b) = 0) 135 #define BITMAP_and(b1,b2) ((b1) &= (b2)) 136 #define BITMAP_minus(b1,b2) ((b1) &= ~(b2)) 137 #define BITMAP_insert(b,n) ((b) |= (1<<(n))) 138 #define BITMAP_delete(b,n) ((b) &= (~(1<<(n)))) 139 #define BITMAP_copy(b1,b2) ((b1) = (b2)) 140 #define BITMAP_intersection(b1,b2,b3) ((b1) = ((b2) & (b3))) 141 #define BITMAP_difference(b1,b2,b3) ((b1) = ((b2) & (~(b3)))) 142 143 # 144 //---------------------------------------------------------------- 145 typedef enum { TRUE=1, FALSE=0} BOOLEAN; 146 typedef enum { IN=1, OUT=0} STATUS; 147 148 // 149 #define BUFFER_SIZE 1000 150 /* ********************************************************************************** */ 151 /* API */ 152 RL_Tree* new_rl(NUM max_size); 153 RL_Tree* copy_rl(RL_Tree *tree); 154 void free_rl(RL_Tree* range); 155 156 void rl_all(RL_Tree* tree,STATUS status); 157 void display_tree(RL_Tree *tree); 158 RL_Tree* set_in_rl(RL_Tree* tree,NUM number,STATUS status); 159 BOOLEAN in_rl(RL_Tree* range,NUM number); 160 BOOLEAN freeze_rl(RL_Tree* tree); /* write operations on the range are finishe */ 161 RL_Tree* intersect_rl(RL_Tree* range1,RL_Tree* range2); 162 163 NUM rl_next_in_bigger(RL_Tree *tree,NUM min); /* Returns next number in tree bigger than min */ 164 165 #define IS_FREEZED(tree) (tree->mem_alloc!=0) 166 167