bullet-summary_ticket.cc

这是一个著名的应用层组播中间件的源码

//Copyright (c) 2004, Charles Killian, Adolfo Rodriguez, Dejan Kostic, Sooraj Bhat, and Amin Vahdat
//All rights reserved.
//
//Redistribution and use in source and binary forms, with or without
//modification, are permitted provided that the following conditions are met:
//
//   * Redistributions of source code must retain the above copyright
//     notice, this list of conditions and the following disclaimer.
//   * Redistributions in binary form must reproduce the above copyright
//     notice, this list of conditions and the following disclaimer in
//     the documentation and/or other materials provided with the
//     distribution.
//   * Neither the names of Duke University nor The University of
//     California, San Diego, nor the names of its contributors
//     may be used to endorse or promote products derived from
//     this software without specific prior written permission.
//
//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
//AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
//IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
//DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
//FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
//DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
//SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
//CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
//OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
//USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "bullet-summary_ticket.h"
#include "stdio.h"
// these are random numbers drawn from [1..100]
int bullet_summary_ticket::permutation_multipliers[NUM_SUM_TIX_FUNCS]={79,57,69,87,44,73,39,84,71,45};

int bullet_summary_ticket::permutation_additives[NUM_SUM_TIX_FUNCS]={87,78,36,74,35,26,77,57,8,10};

bullet_summary_ticket::bullet_summary_ticket(int universe)
  : universe_size(universe)
{
  st.address = 0;
  if (NUM_SUM_TIX_FUNCS>sizeof(permutation_multipliers)/sizeof(int))
    {
      printf("NUM_SUM_TIX_FUNCS: %d is too big, exiting\n", NUM_SUM_TIX_FUNCS);
      exit(1);
    }
  reset ();
}
bullet_summary_ticket::~bullet_summary_ticket()
{
}

// ---------------------------------------------- 
// reset
// ---------------------------------------------- 

void  bullet_summary_ticket::reset ()
{

  for (int counter = 0; counter < NUM_SUM_TIX_FUNCS; counter++ )
    {
      st.table[counter]= universe_size + 1; 
      origin[counter]= -1; 
    }
  for (int counter = 0; counter < NUM_HANDLES; counter++ )
    {
      st.handles[counter]= 0;
      st.handle_percentage[counter]= 0;
    }
}


// ---------------------------------------------- 
// empty
// ---------------------------------------------- 

int  bullet_summary_ticket::empty ()
{

  for (int counter = 0; counter < NUM_SUM_TIX_FUNCS; counter++ )
    {
      if (st.table[counter]== (universe_size + 1)) return 0;
    }
  return 1;
}
// ---------------------------------------------- 
// insert
// ---------------------------------------------- 

void  bullet_summary_ticket::insert (int key)
{
  for (int counter = 0; counter < NUM_SUM_TIX_FUNCS ;counter++ )
    {
      int value = (key*permutation_multipliers[counter] + permutation_additives[counter])%universe_size;
      if (value  < st.table[counter])
	{
	  st.table[counter]= value; 
	  origin[counter]= key; 
	}
    }
}
// ---------------------------------------------- 
// remove
// ---------------------------------------------- 

void  bullet_summary_ticket::remove (int key, map <int, message*, less<int> >& contents)
{
//    printf("removing key: %d\n", key);

  for (int counter = 0; counter < NUM_SUM_TIX_FUNCS ;counter++ )
    {
      if (origin[counter] == key)
	{
//  	  printf("recomputing: %d minimum: %d key: %d\n", counter,st.table[counter],key);
	  st.table[counter]=universe_size+1;
	  origin[counter]= -1; 

	  map <int, message*, less<int> >::const_iterator element;
  
	  for(element=contents.begin();element!=contents.end();element++)
	    {
	      int vk= (*element).first;
	      if (vk== key)
		{
		  printf("encountered same key as the one being removed: %d\n", key);
		  continue;
		}

	      int value = (vk*permutation_multipliers[counter] + permutation_additives[counter])%universe_size;
	      if (value  < st.table[counter])
		{
		  st.table[counter]= value; 
		  origin[counter]= vk; 
		}
 	    }
//  	  printf("recomputed: %d minimum: %d from key: %d\n",  counter,st.table[counter],origin[counter]);
	}
    }

}


// ---------------------------------------------- 
// serialize
// ---------------------------------------------- 

void  bullet_summary_ticket::serialize (unsigned char*buffer)
{
  cand_bullet_summary_ticket *out =  (cand_bullet_summary_ticket*)buffer;
  
  *out = st;
}

// ---------------------------------------------- 
// import
// ---------------------------------------------- 

int  bullet_summary_ticket::import (unsigned char*buffer)
{
  cand_bullet_summary_ticket *intic =  (cand_bullet_summary_ticket*)buffer;

  st = *intic;

  return size_compacted_in_bytes ();
}

// ---------------------------------------------- 
// size_compacted
// ---------------------------------------------- 

int  bullet_summary_ticket::size_compacted_in_bytes ()
{
  return sizeof(cand_bullet_summary_ticket);
}

// ---------------------------------------------- 
// operator % 
// ---------------------------------------------- 

 double  bullet_summary_ticket::operator %  ( const bullet_summary_ticket& ticket)
 {
   int same = 0;
   for (int counter = 0; counter < NUM_SUM_TIX_FUNCS ;counter++ )
     {
       for (int other = 0; other < NUM_SUM_TIX_FUNCS ;other++ )
 	{
 	  if (st.table[counter] == ticket.st.table[other])
 	    {
	      same++;
	      break;
	    }
	}
    }
  return same/(double) NUM_SUM_TIX_FUNCS;
}

bool  operator ==  ( const cand_bullet_summary_ticket& ticket1, const cand_bullet_summary_ticket& ticket2)
 {
   if (ticket1.address == ticket2.address)
     return 1;
   else 
     return 0;
}



// ---------------------------------------------- 
// dump_state
// ---------------------------------------------- 

void  bullet_summary_ticket::dump_state ()
{
  printf("bullet_summary_ticket address: %x ", st.address);
  
  for (int i = 0; i < NUM_SUM_TIX_FUNCS ;i++ )
    {
      printf("%d ",st.table[i]);
    }
  
  printf("\n");
  
}

// ---------------------------------------------- 
// range_overlap
// ---------------------------------------------- 

 double  bullet_summary_ticket::range_overlap ( const bullet_summary_ticket& ticket)
{
if (st.low  == 0 && 
    st.high  == 0)
{
  return 0;
}

if (st.low  >  ticket.st.high || 
    st.high  <  ticket.st.low)
{
  return 0;
}
 int lower = st.low;
if (st.low  <  ticket.st.low)
{
  lower =ticket.st.low;
}

int higher  = st.high;
if (st.high  > ticket.st.high)
{
  higher = ticket.st.high;
}

return (( higher - lower)/( double)(st.high-st.low));
}