Siena Fast Forwarding Documentation

00001 // -*- C++ -*-
00002 //
00003 //  This file is part of Siena, a wide-area event notification system.
00004 //  See http://www.cs.colorado.edu/serl/siena/
00005 //
00006 //  Authors: Antonio Carzaniga <[email protected]>
00007 //  See the file AUTHORS for full details. 
00008 //
00009 //  Copyright (C) 2002 University of Colorado
00010 //
00011 //  This program is free software; you can redistribute it and/or
00012 //  modify it under the terms of the GNU General Public License
00013 //  as published by the Free Software Foundation; either version 2
00014 //  of the License, or (at your option) any later version.
00015 //
00016 //  This program is distributed in the hope that it will be useful,
00017 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019 //  GNU General Public License for more details.
00020 //
00021 //  You should have received a copy of the GNU General Public License
00022 //  along with this program; if not, write to the Free Software
00023 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
00024 //  USA, or send email to [email protected].
00025 //
00026 //
00027 // $Id: bitvector.h,v 1.5 2002/09/30 04:51:48 carzanig Exp $
00028 //
00029 #ifndef BITVECTOR_H
00030 #define BITVECTOR_H
00031 
00032 #include <cstddef> /* for size_t */
00033 
00034 #include "fwdconf.h"
00035 #include "ft_allocator.h"
00036 
00037 class bitvector;
00038 class ibitvector;
00039 
00040 typedef unsigned long           bv_atom_t;
00041 //
00042 // hopefully this stuff is statically optimized by the compiler
00043 //
00044 static const unsigned char      bv_atom_bits = sizeof(bv_atom_t) * 8;
00045 static const unsigned char      bv_atom_bits_mask = bv_atom_bits - 1;
00046 static const unsigned char      bv_atom_bits_shift 
00047 = (bv_atom_bits == 32 ? 5 : 
00048    (bv_atom_bits == 64 ? 6 :
00049     (bv_atom_bits == 16 ? 4 : 
00050      /* bv_atom_bits == 16 */ 2)));
00051 
00056 class bitvector {
00057 public:
00060                                 bitvector(size_t size);
00061                                 ~bitvector();
00062     
00063     bool                        test(size_t pos)                        const;
00064     bool                        set(size_t pos);
00065 
00066     void                        set(const ibitvector & x);
00067 
00068     void                        clear();
00070     size_t                      get_count()                             const;
00072     size_t                      get_size()                              const;
00073 
00074 private:
00075     bv_atom_t *                 elements; 
00076     const size_t                size;           // number of bits
00077     size_t                      count;          // number of bits set to 1
00078 
00079     size_t                      element_size()                          const;
00080 
00081     static size_t               set(bv_atom_t * x, bv_atom_t * xe, 
00082                                     const bv_atom_t * y, const bv_atom_t *ye);
00083 };
00084 
00089 class ibitvector {
00090 public:
00091                                 ibitvector();
00092     
00093     bool                        test(size_t pos)                        const;
00094     bool                        set(size_t pos, FTAllocator &);
00095 
00096     void                        clear();
00097     size_t                      get_count()                             const;
00098     size_t                      get_size()                              const;
00099 
00100 private:
00101     struct index;
00102     struct block;
00103 
00104     static const unsigned int   block_size = 16;
00105     static const unsigned int   block_shift = 4;
00106     static const unsigned int   block_mask = block_size - 1;
00107 
00108     static const unsigned int   index_size = 16;
00109     static const unsigned int   index_shift = 4;
00110     static const unsigned int   index_mask = index_size - 1;
00111 
00112     union index_or_block {
00113         block *         b;
00114         index *         i;
00115     };
00116 
00117     struct block {
00118         index *         up;
00119         bv_atom_t       elements[block_size];
00120         
00121         block(index *);
00122     };
00123 
00124     struct index {
00125         index *         up;
00126         index_or_block  down[index_size];
00127 
00128         index(index *);
00129     };
00130 
00131     class iterator {
00132     public:
00133                         iterator(const block &);
00134 
00135         size_t          element_address() const;
00136         const block *   next_block();
00137 
00138     private:
00139         index *         bi;
00140         size_t          addr;
00141         unsigned char   level;
00142     };
00143 
00144     size_t count;
00145     size_t size;
00146     block  first_block;
00147 
00148     friend class bitvector;
00149 };
00150 
00151 #ifdef HAVE_INLINE
00152 #include "bitvector.icc"
00153 #endif
00154 
00155 #endif