00001 /* 00002 * BitmapDigest.h : part of the Mace toolkit for building distributed systems 00003 * 00004 * Copyright (c) 2007, Charles Killian, Dejan Kostic, Ryan Braud, James W. Anderson, John Fisher-Ogden, Calvin Hubble, Duy Nguyen, Justin Burke, David Oppenheimer, Amin Vahdat, Adolfo Rodriguez, Sooraj Bhat 00005 * All rights reserved. 00006 * 00007 * Redistribution and use in source and binary forms, with or without 00008 * modification, are permitted provided that the following conditions are met: 00009 * 00010 * * Redistributions of source code must retain the above copyright 00011 * notice, this list of conditions and the following disclaimer. 00012 * * Redistributions in binary form must reproduce the above copyright 00013 * notice, this list of conditions and the following disclaimer in 00014 * the documentation and/or other materials provided with the 00015 * distribution. 00016 * * Neither the names of Duke University nor The University of 00017 * California, San Diego, nor the names of the authors or contributors 00018 * may be used to endorse or promote products derived from 00019 * this software without specific prior written permission. 00020 * 00021 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00022 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00023 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 00024 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 00025 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00026 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 00027 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00028 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 00029 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 00030 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00031 * 00032 * ----END-OF-LEGAL-STUFF---- */ 00033 #include "Digest.h" 00034 00040 #ifndef __bitmap_digest 00041 #define __bitmap_digest 00042 //const static int BITMAP_SIZE = 1024*22; 00044 const static int BITMAP_SIZE = 1024*6; //was *4 00045 00049 typedef struct bitmapy { 00050 int tab_size; 00051 int start_bit; 00052 int start_seq; 00053 int last_seq; 00054 #if VARIABLE_BITMAP 00055 unsigned char* tab; 00056 bitmapy():tab( 0) {} 00057 int size_core_in_bytes (){sizeof(*this)-sizeof(unsigned char* );}; 00058 #else 00059 unsigned char tab[BITMAP_SIZE/8]; 00060 #endif 00061 } flat_bitmap; 00062 00076 class bitmap_digest : public digest 00077 { 00078 00079 public: 00080 bitmap_digest (int size = BITMAP_SIZE); 00081 ~bitmap_digest ( ); 00082 public: 00083 bool contains (int item); 00084 //insert returns the lowest sequence number remaining in the digest even after truncation 00085 int insert (int item, int suppress = 1); 00086 //returns 1 if it actually cleared the bit (i.e. it was in range) 00087 int remove_item (int item); 00088 void serialize (unsigned char* buffer); 00089 void import (unsigned char* buffer); 00090 int size_compacted_in_bytes (); 00091 /* int reset (); */ 00092 void reset (); 00093 int get_lowest_sequence (); 00094 int get_highest_sequence (); 00095 00096 flat_bitmap bm; 00097 protected: 00098 int in_table (int seq); 00099 int which_byte (int seq); 00100 int which_bit (int seq); 00101 void set_bit (int seq, int set_value); 00102 00103 private: 00104 }; 00106 #endif //__bitmap_digest