src/libswift/availability.cpp

   1 /*
   2  *  availability.h
   3  *  Tree keeping track of the  availability of each bin in a swarm
   4  *
   5  *  Created by Riccardo Petrocco
   6  *  Copyright 2009-2012 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9 #include "availability.h"
  10
  11 using namespace swift;
  12
  13 #define DEBUGAVAILABILITY       0
  14
  15
  16 uint8_t Availability::get(const bin_t bin)
  17 {
  18         if (bin.is_none())
  19                 return 255;
  20         else if (size_)
  21                 return avail_[bin.toUInt()];
  22
  23         return 0;
  24 }
  25
  26
  27 void Availability::setBin(bin_t bin)
  28 {
  29         if (bin != bin_t::NONE)
  30         {
  31                 bin_t beg = bin.base_left();
  32                 bin_t end = bin.base_right();
  33
  34                 for (int i = beg.toUInt(); i<=end.toUInt(); i++)
  35                 {
  36                         // for the moment keep a counter
  37                         // TODO make it percentage
  38                         avail_[i]++;
  39                 }
  40         }
  41
  42 }
  43
  44
  45 void Availability::removeBin(bin_t bin)
  46 {
  47         bin_t beg = bin.base_left();
  48         bin_t end = bin.base_right();
  49
  50         for (int i = beg.toUInt(); i<=end.toUInt(); i++)
  51         {
  52                 avail_[i]--;
  53         }
  54 }
  55
  56
  57 void Availability::setBinmap(binmap_t * binmap)
  58 {
  59
  60         if (binmap->is_filled())
  61                 for (int i=0; i<size_; i++)
  62                         avail_[i]++;
  63         else
  64                 if (!binmap->is_empty())
  65                 {
  66                         //status();
  67                         bin_t tmp_b;
  68                         binmap_t tmp_bm;
  69                         tmp_b = binmap_t::find_complement(tmp_bm, *binmap, 0);
  70
  71                         while (tmp_b != bin_t::NONE)
  72                         {
  73                                 setBin(tmp_b);
  74                                 //binmap_t::copy(tmp_bm, *binmap, tmp_b);
  75                                 tmp_bm.set(tmp_b);
  76                                 tmp_b = binmap_t::find_complement(tmp_bm, *binmap, 0);
  77                         }
  78                         //status();
  79
  80                 }
  81
  82         return;
  83 }
  84
  85 void Availability::removeBinmap(binmap_t &binmap)
  86 {
  87         if (binmap.is_filled())
  88                 for (int i=0; i<size_; i++)
  89                         avail_[i]--;
  90         else
  91                 if (!binmap.is_empty())
  92                 {
  93                         bin_t tmp_b;
  94                         binmap_t tmp_bm;
  95                         tmp_b = binmap_t::find_complement(tmp_bm, binmap, 0);
  96                         while (tmp_b != bin_t::NONE)
  97                         {
  98                                 removeBin(tmp_b);
  99                                 tmp_bm.set(tmp_b);
 100                                 tmp_b = binmap_t::find_complement(tmp_bm, binmap, 0);
 101                         }
 102                 }
 103
 104         return;
 105 }
 106
 107 void Availability::set(uint32_t channel_id, binmap_t& binmap, bin_t target)
 108 {
 109         if (DEBUGAVAILABILITY)
 110         {
 111                 char bin_name_buf[32];
 112                 dprintf("%s #%u Availability -> setting %s (%llu)\n",tintstr(),channel_id,target.str(bin_name_buf),target.toUInt());
 113         }
 114
 115         if (size_>0 && !binmap.is_filled(target))
 116         {
 117                 bin_t beg = target.base_left();
 118                 bin_t end = target.base_right();
 119
 120                 for (int i = beg.toUInt(); i<=end.toUInt(); i++)
 121                 {
 122                         // for the moment keep a counter
 123                         // TODO make it percentage
 124                         if (!binmap.is_filled(bin_t(i)))
 125                                 avail_[i]++;
 126                         //TODO avoid running into sub-trees that r filled
 127                 }
 128         }
 129         // keep track of the incoming have msgs
 130         else
 131         {
 132
 133                 for (WaitingPeers::iterator vpci = waiting_peers_.begin(); vpci != waiting_peers_.end(); ++vpci)
 134                 {
 135                     if (vpci->first == channel_id)
 136                     {
 137                         waiting_peers_.erase(vpci);
 138                         break;
 139                 }
 140                 }
 141
 142         waiting_peers_.push_back(std::make_pair(channel_id, &binmap));
 143         }
 144 }
 145
 146
 147 void Availability::remove(uint32_t channel_id, binmap_t& binmap)
 148 {
 149         if (DEBUGAVAILABILITY)
 150         {
 151                 dprintf("%s #%u Availability -> removing peer\n",tintstr(),channel_id);
 152         }
 153         if (size_<=0)
 154         {
 155                 WaitingPeers::iterator vpci = waiting_peers_.begin();
 156                 for(; vpci != waiting_peers_.end(); ++vpci)
 157                 {
 158                         if (vpci->first == channel_id)
 159                         {
 160                             waiting_peers_.erase(vpci);
 161                                 break;
 162                         }
 163                 }
 164         }
 165
 166         else
 167                 removeBinmap(binmap);
 168         // remove the binmap from the availability
 169
 170         return;
 171 }
 172
 173
 174 void Availability::setSize(uint64_t size)
 175 {
 176         if (size && !size_)
 177         {
 178                 // TODO can be optimized (bithacks)
 179                 uint64_t r = 0;
 180                 uint64_t s = size;
 181
 182                 // check if the binmap is not complete
 183                 if (s & (s-1))
 184                 {
 185                         while (s >>= 1)
 186                         {
 187                                 r++;
 188                         }
 189                         s = 1<<(r+1);
 190                 }
 191                 // consider higher layers
 192                 s += s-1;
 193                 size_ = s;
 194                 avail_ = new uint8_t[s]();
 195
 196                 // Initialize with the binmaps we already received
 197                 for(WaitingPeers::iterator vpci = waiting_peers_.begin(); vpci != waiting_peers_.end(); ++vpci)
 198                 {
 199                         setBinmap(vpci->second);
 200                 }
 201
 202
 203                 if (DEBUGAVAILABILITY)
 204                 {
 205                         char bin_name_buf[32];
 206                         dprintf("%s #1 Availability -> setting size in chunk %lu \t avail size %u\n",tintstr(), size, s);
 207                 }
 208         }
 209 }
 210
 211 bin_t Availability::getRarest(const bin_t range, int width)
 212 {
 213         assert(range.toUInt()<size_);
 214         bin_t curr = range;
 215         bin_t::uint_t idx = range.toUInt();
 216
 217         while (curr.base_length()>width)
 218         {
 219                 idx = curr.toUInt();
 220                 if ( avail_[curr.left().toUInt()] <= avail_[curr.right().toUInt()] )
 221                         curr.to_left();
 222                 else
 223                         curr.to_right();
 224         }
 225         return curr;
 226 }
 227
 228 void Availability::status() const
 229 {
 230     printf("availability:\n");
 231
 232     if (size_ > 0)
 233     {
 234                 for (int i = 0; i < size_; i++)
 235                         printf("%d", avail_[i]);
 236     }
 237
 238     printf("\n");
 239 }
 240
 241
 242