"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "src/iptree.h" between
tcpflow-1.5.0.tar.gz and tcpflow-1.6.1.tar.gz

About: tcpflow is a TCP/IP packet demultiplexer that captures data transmitted as part of TCP connections (flows), and stores the data in a way that is convenient for protocol analysis and debugging.

iptree.h  (tcpflow-1.5.0)	:	iptree.h  (tcpflow-1.6.1)
skipping to change at line 89		skipping to change at line 89
public:;		public:;
TYPE tsum; // this node and pruned children.		TYPE tsum; // this node and pruned children.
/* Caching system */		/* Caching system */
mutable bool dirty; // add() has been called and cac hed data is no longer valid		mutable bool dirty; // add() has been called and cac hed data is no longer valid
mutable best cached_best;		mutable best cached_best;
public:		public:
node(node *p):parent(p),ptr0(0),ptr1(0),tsum(),dirty(false),cached_best( ){ }		node(node *p):parent(p),ptr0(0),ptr1(0),tsum(),dirty(false),cached_best( ){ }
int children() const {return (ptr0 ? 1 : 0) + (ptr1 ? 1 : 0);}		int children() const {return (ptr0 ? 1 : 0) + (ptr1 ? 1 : 0);}
~node(){		~node(){
if(ptr0){ delete ptr0; ptr0 = 0; }		delete ptr0; ptr0 = 0;
if(ptr1){ delete ptr1; ptr1 = 0; }		delete ptr1; ptr1 = 0;
};		};
// a node is leaf if tsum>0 and both ptrs are 0.		// a node is leaf if tsum>0 and both ptrs are 0.
bool isLeaf() const {		bool isLeaf() const {
if(tsum>0 && ptr0==0 && ptr1==0) return true;		if(tsum>0 && ptr0==0 && ptr1==0) return true;
return false;		return false;
}		}
/**		/**
* prune():		* prune():
* Cut this node's children off the tree.		* Cut this node's children off the tree.
* Returns the number removed, which should be larger than 0 (or we shou ldn't have been called).		* Returns the number removed, which should be larger than 0 (or we shou ldn't have been called).
skipping to change at line 114		skipping to change at line 114
/* If prune() on a node is called, then both ptr0 and ptr1 nodes, if present,		/* If prune() on a node is called, then both ptr0 and ptr1 nodes, if present,
* must not have children.		* must not have children.
* Now delete those that we counted out		* Now delete those that we counted out
*/		*/
int removed = 0;		int removed = 0;
if(ptr0){		if(ptr0){
assert(ptr0->isLeaf()); // only prune leaf nodes		assert(ptr0->isLeaf()); // only prune leaf nodes
tsum += ptr0->tsum;		tsum += ptr0->tsum;
tree.cache_remove(ptr0); // remove it from the cache		tree.cache_remove(ptr0); // remove it from the cache
tree.pruned++;		tree.pruned++;
delete ptr0;		delete ptr0; ptr0=0;
ptr0=0;
tree.nodes--;		tree.nodes--;
removed++;		removed++;
}		}
if(ptr1){		if(ptr1){
assert(ptr1->isLeaf());		assert(ptr1->isLeaf());
tsum += ptr1->tsum;		tsum += ptr1->tsum;
tree.cache_remove(ptr1);		tree.cache_remove(ptr1);
tree.pruned++;		tree.pruned++;
delete ptr1;		delete ptr1;
ptr1=0;		ptr1=0;
skipping to change at line 243		skipping to change at line 242
/****************************************************************		/****************************************************************
*** static member service routines		*** static member service routines
****************************************************************/		****************************************************************/
/* get the ith bit; 0 is the MSB */		/* get the ith bit; 0 is the MSB */
static bool bit(const uint8_t *addr,size_t i){		static bool bit(const uint8_t *addr,size_t i){
return (addr[i / 8]) & (1<<((7-i)&7));		return (addr[i / 8]) & (1<<((7-i)&7));
}		}
/* set the ith bit to 1 */		/* set the ith bit to 1 */
static void setbit(uint8_t *addr,size_t i){		static void setbit(uint8_t *addr,size_t addrlen, size_t i){
addr[i / 8] |= (1<<((7-i)&7));		if ( i/8 < addrlen) {
		addr[i / 8] |= (1<<((7-i)&7));
		}
}		}
virtual ~iptreet(){} // required per compiler warnings		virtual ~iptreet(){} // required per compiler warnings
/* copy is a deep copy */		/* copy is a deep copy */
iptreet(const iptreet &n):root(n.root ? new node(*n.root) : 0),		iptreet(const iptreet &n):root(n.root ? new node(*n.root) : 0),
nodes(n.nodes),maxnodes(n.maxnodes),ctr_added(),pr uned(),cache(),cachenext(),cache_hits(),cache_misses(){};		nodes(n.nodes),maxnodes(n.maxnodes),ctr_added(),pr uned(),cache(),cachenext(),cache_hits(),cache_misses(){};
/* create an empty tree */		/* create an empty tree */
iptreet(int maxnodes_):root(new node(0)),nodes(0),maxnodes(maxnodes_),		iptreet(int maxnodes_):root(new node(0)),nodes(0),maxnodes(maxnodes_),
ctr_added(),pruned(),cache(),cachenext(),cache_hits() ,cache_misses(){		ctr_added(),pruned(),cache(),cachenext(),cache_hits() ,cache_misses(){
skipping to change at line 389		skipping to change at line 390
histogram.push_back(addr_elem(addr,depth,ptr->nodesum()));		histogram.push_back(addr_elem(addr,depth,ptr->nodesum()));
//return;		//return;
}		}
if(depth>max_histogram_depth) return; // can't go deeper t han this now		if(depth>max_histogram_depth) return; // can't go deeper t han this now
/* create address with 0 and 1 added */		/* create address with 0 and 1 added */
uint8_t addr0[ADDRBYTES];		uint8_t addr0[ADDRBYTES];
uint8_t addr1[ADDRBYTES];		uint8_t addr1[ADDRBYTES];
memset(addr0,0,sizeof(addr0)); memcpy(addr0,addr,(depth+7)/8);		memset(addr0,0,sizeof(addr0)); memcpy(addr0,addr,(depth+7)/8);
memset(addr1,0,sizeof(addr1)); memcpy(addr1,addr,(depth+7)/8); setbit(ad		memset(addr1,0,sizeof(addr1)); memcpy(addr1,addr,(depth+7)/8);
dr1,depth);		setbit(addr1,sizeof(addr1),depth);
if(ptr->ptr0) get_histogram(depth+1,addr0,ptr->ptr0,histogram);		if(ptr->ptr0) get_histogram(depth+1,addr0,ptr->ptr0,histogram);
if(ptr->ptr1) get_histogram(depth+1,addr1,ptr->ptr1,histogram);		if(ptr->ptr1) get_histogram(depth+1,addr1,ptr->ptr1,histogram);
}		}
void get_histogram(histogram_t &histogram) const { // adds the histogram to the passed in vector		void get_histogram(histogram_t &histogram) const { // adds the histogram to the passed in vector
uint8_t addr[ADDRBYTES];		uint8_t addr[ADDRBYTES];
memset(addr,0,sizeof(addr));		memset(addr,0,sizeof(addr));
get_histogram(0,addr,root,histogram);		get_histogram(0,addr,root,histogram);
}		}
skipping to change at line 525		skipping to change at line 527
}		}
assert(0); // should never happen		assert(0); // should never happen
}		}
/* a structure for a pair of IP addresses */		/* a structure for a pair of IP addresses */
class ip2tree:public iptreet<uint64_t,32> {		class ip2tree:public iptreet<uint64_t,32> {
public:		public:
/* de-interleave a pair of addresses */		/* de-interleave a pair of addresses */
static void un_pair(uint8_t *addr1,uint8_t *addr2,size_t addr12len,size_t *d epth1,size_t *depth2,const uint8_t *addr,size_t addrlen,size_t depth){		static void un_pair(uint8_t *addr1,uint8_t *addr2,size_t addr12len,size_t *d epth1,size_t *depth2,const uint8_t *addr,size_t addrlen,size_t depth){
for(size_t i=0;i<addrlen*8/2;i++){		for(size_t i=0;i<addrlen*8/2;i++){
if(iptreet<uint64_t,32>::bit(addr,i*2)) iptreet<uint64_t,32>::setb		if(iptreet<uint64_t,32>::bit(addr,i*2))
it(addr1,i);		iptreet<uint64_t,32>::setbit(addr1, addr12len, i);
if(iptreet<uint64_t,32>::bit(addr,i*2+1)) iptreet<uint64_t,32>::setb		if(iptreet<uint64_t,32>::bit(addr,i*2+1))
it(addr2,i);		iptreet<uint64_t,32>::setbit(addr2, addr12len, i);
}		}
*depth1 = (depth+1)/2;		*depth1 = (depth+1)/2;
*depth2 = (depth)/2;		*depth2 = (depth)/2;
}		}
ip2tree(int maxnodes_):iptreet<uint64_t,32>(maxnodes_){}		ip2tree(int maxnodes_):iptreet<uint64_t,32>(maxnodes_){}
virtual ~ip2tree(){};		virtual ~ip2tree(){};
/* str requires more work */		/* str requires more work */
static std::string ip2str(const uint8_t *addr,size_t addrlen,size_t depth){		static std::string ip2str(const uint8_t *addr,size_t addrlen,size_t depth){
uint8_t addr1[16];memset(addr1,0,sizeof(addr1));		uint8_t addr1[16];memset(addr1,0,sizeof(addr1));
skipping to change at line 561		skipping to change at line 565
}		}
return os;		return os;
}		}
/* Add a pair of addresses by interleaving them */		/* Add a pair of addresses by interleaving them */
void add_pair(const uint8_t *addr1,const uint8_t *addr2,size_t addrlen,uint6 4_t val){		void add_pair(const uint8_t *addr1,const uint8_t *addr2,size_t addrlen,uint6 4_t val){
uint8_t addr[32];		uint8_t addr[32];
memset(addr,0,sizeof(addr));		memset(addr,0,sizeof(addr));
/* Interleave on the bit by bit level */		/* Interleave on the bit by bit level */
for(size_t i=0;i<addrlen*8;i++){		for(size_t i=0;i<addrlen*8;i++){
if(iptreet<uint64_t,32>::bit(addr1,i)) iptreet<uint64_t,32>::setbit(		if(iptreet<uint64_t,32>::bit(addr1,i))
addr,i*2);		iptreet<uint64_t,32>::setbit(addr,sizeof(addr),i*2);
if(iptreet<uint64_t,32>::bit(addr2,i)) iptreet<uint64_t,32>::setbit(		if(iptreet<uint64_t,32>::bit(addr2,i))
addr,i*2+1);		iptreet<uint64_t,32>::setbit(addr,sizeof(addr),i*2+1);
}		}
add(addr,addrlen*2,val); /* Add it */		add(addr,addrlen*2,val); /* Add it */
}		}
};		};
typedef iptreet<uint64_t,16> iptree; // simple tree for counting; reimplem ent so val is tcount		typedef iptreet<uint64_t,16> iptree; // simple tree for counting; reimplem ent so val is tcount
template <typename T,size_t ADDRBYTES> std::ostream & operator <<(std::ostream & os,const iptreet<T,ADDRBYTES> &ipt) {		template <typename T,size_t ADDRBYTES> std::ostream & operator <<(std::ostream & os,const iptreet<T,ADDRBYTES> &ipt) {
return ipt.dump(os);		return ipt.dump(os);
}		}
End of changes. 6 change blocks.
16 lines changed or deleted		17 lines changed or added

---