"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

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)