Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Compound Members | File Members

HitCountList Class Reference

#include <mcache.h>

Inheritance diagram for HitCountList:

Inheritance graph
[legend]
Collaboration diagram for HitCountList:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 HitCountList ()
void update (HitCount *h)
void add (HitCount *h)
HitCount * detach_tail ()
void print ()
void check_integrity ()
virtual void destroy ()
DoubleListElem * head ()
DoubleListElem * tail ()
void detach (DoubleListElem *e)
void insert (DoubleListElem *src, DoubleListElem *dst)
void append (DoubleListElem *src, DoubleListElem *dst)

Protected Attributes

DoubleListElem * head_
DoubleListElem * tail_

Constructor & Destructor Documentation

HitCountList::HitCountList (   )  [inline]
 

Definition at line 66 of file mcache.h. 

00066 : DoubleList() {}

Member Function Documentation

void HitCountList::add (  HitCount *  h  ) 
 

Definition at line 209 of file mcache.cc.

References DoubleList::append(), HitCount::hc(), DoubleList::head_, DoubleList::insert(), HitCount::layer(), HitCount::next(), HitCount::page(), and DoubleList::tail_.

Referenced by MClientPagePool::add_segment(). 

00210 {
00211         HitCount *tmp = (HitCount*)head_;
00212 
00213         // XXX First, ensure that the layer ordering within the same page
00214         // is not violated!!
00215         while ((tmp != NULL) && (tmp->hc() > h->hc())) {
00216                 if ((tmp->page() == h->page()) && (tmp->layer() > h->layer()))
00217                         break;
00218                 tmp = tmp->next();
00219         }
00220         // Then order according to layer number
00221         while ((tmp != NULL) && (tmp->hc() == h->hc()) && 
00222                (tmp->layer() < h->layer()))
00223                 tmp = tmp->next();
00224 
00225         if (tmp == NULL) {
00226                 if (head_ == NULL) 
00227                         head_ = tail_ = h;
00228                 else
00229                         append(h, tail_);
00230                 return;
00231         } else if ((tmp == head_) && 
00232                    ((tmp->hc() < h->hc()) || (tmp->layer() > h->layer()))) {
00233                 insert(h, head_);
00234                 return;
00235         }
00236 
00237         // Now tmp->hc()<=h->hc(), or tmp->hc()>h->hc() but 
00238         // tmp->layer()>h->layer(), insert h BEFORE tmp
00239         insert(h, tmp);
00240 }

Here is the call graph for this function:

void DoubleList::append (  DoubleListElem *  src,
DoubleListElem *  dst
)  [inline, inherited]
 

Definition at line 111 of file utilities.h.

References DoubleListElem::append(), and DoubleList::tail_.

Referenced by MediaSegmentList::add(), add(), and update(). 

00111                                                               {
00112                 dst->append(src);
00113                 if (dst == tail_)
00114                         tail_ = src;
00115         }

Here is the call graph for this function:

void HitCountList::check_integrity (   ) 
 

Definition at line 191 of file mcache.cc.

References abort(), DoubleList::head_, HitCount::layer(), HitCount::next(), and HitCount::page().

Referenced by MClientPagePool::hc_update(). 

00192 {
00193         HitCount *p = (HitCount*)head_, *q;
00194         while (p != NULL) {
00195                 q = p->next();
00196                 while (q != NULL) {
00197                         // Check layer ordering 
00198                         if ((p->page() == q->page()) && 
00199                             (p->layer() > q->layer())) {
00200                                 fprintf(stderr, "Wrong hit count list.\n");
00201                                 abort();
00202                         }
00203                         q = q->next();
00204                 }
00205                 p = p->next();
00206         }
00207 }

Here is the call graph for this function:

void DoubleList::destroy (   )  [virtual, inherited]
 

Reimplemented in MediaSegmentList.

Definition at line 81 of file utilities.cc.

References DoubleList::head_, DoubleListElem::next(), and DoubleList::tail_.

Referenced by MediaSegmentList::destroy(). 

00082 {
00083         DoubleListElem *p = head_, *q;
00084         while (p != NULL) {
00085                 q = p;
00086                 p = p->next();
00087                 delete q;
00088         }
00089         head_ = tail_ = NULL;
00090 }

Here is the call graph for this function:

void DoubleList::detach (  DoubleListElem *  e  )  [inline, inherited]
 

Definition at line 99 of file utilities.h.

References DoubleListElem::detach(), DoubleList::head_, DoubleListElem::next(), DoubleListElem::prev(), and DoubleList::tail_.

Referenced by MediaSegmentList::evict_head(), MediaSegmentList::evict_head_offset(), MediaSegmentList::evict_tail(), MClientPagePool::force_remove(), MediaSegmentList::merge_seg(), MClientPagePool::repl_atomic(), MClientPagePool::repl_finegrain(), and update(). 

00099                                        {
00100                 if (head_ == e)
00101                         head_ = e->next();
00102                 if (tail_ == e)
00103                         tail_ = e->prev();
00104                 e->detach();
00105         }

Here is the call graph for this function:

HitCount* HitCountList::detach_tail (   )  [inline]
 

Definition at line 71 of file mcache.h.

References DoubleListElem::detach(), DoubleListElem::prev(), and DoubleList::tail_. 

00071                                 {
00072                 HitCount* tmp = (HitCount *)tail_;
00073                 if (tmp) {
00074                         tail_ = tail_->prev();
00075                         tmp->detach();
00076                 }
00077                 return tmp;
00078         }

Here is the call graph for this function:

DoubleListElem* DoubleList::head (   )  [inline, inherited]
 

Definition at line 96 of file utilities.h.

References DoubleList::head_. 

00096 { return head_; }

void DoubleList::insert (  DoubleListElem *  src,
DoubleListElem *  dst
)  [inline, inherited]
 

Definition at line 106 of file utilities.h.

References DoubleList::head_, and DoubleListElem::insert().

Referenced by MediaSegmentList::add(), add(), and update(). 

00106                                                               {
00107                 dst->insert(src);
00108                 if (dst == head_)
00109                         head_ = src;
00110         }

Here is the call graph for this function:

void HitCountList::print (   ) 
 

Definition at line 243 of file mcache.cc.

References HitCount::hc(), DoubleList::head_, HitCount::layer(), ClientPage::name(), HitCount::next(), and HitCount::page().

Referenced by MClientPagePool::dump_hclist(), MClientPagePool::repl_atomic(), and MClientPagePool::repl_finegrain(). 

00244 {
00245         HitCount *p = (HitCount *)head_;
00246         int i = 0;
00247         char buf[20];
00248         while (p != NULL) {
00249                 p->page()->name(buf);
00250                 fprintf(stderr, "(%s %d %f) ", buf, p->layer(), p->hc());
00251                 if (++i % 4 == 0)
00252                         printf("\n");
00253                 p = p->next();
00254         }
00255         if (i % 4 != 0)
00256                 fprintf(stderr, "\n");
00257 }

Here is the call graph for this function:

DoubleListElem* DoubleList::tail (   )  [inline, inherited]
 

Definition at line 97 of file utilities.h.

References DoubleList::tail_.

Referenced by MClientPagePool::repl_atomic(), and MClientPagePool::repl_finegrain(). 

00097 { return tail_; }

void HitCountList::update (  HitCount *  h  ) 
 

Definition at line 138 of file mcache.cc.

References DoubleList::append(), DoubleList::detach(), HitCount::hc(), DoubleList::head_, DoubleList::insert(), HitCount::layer(), HitCount::next(), HitCount::page(), HitCount::prev(), and DoubleList::tail_.

Referenced by MClientPagePool::hc_update(). 

00139 {
00140         HitCount *tmp = h->prev();
00141         if ((tmp != NULL) && (tmp->hc() < h->hc())) {
00142                 // Hit count increased, need to move this one up
00143                 detach(h);
00144                 while ((tmp != NULL) && (tmp->hc() < h->hc())) {
00145                         if ((tmp->page() == h->page()) &&
00146                             (tmp->layer() < h->layer()))
00147                                 // XXX Don't violate layer encoding within the
00148                                 // same page!
00149                                 break;
00150                         tmp = tmp->prev();
00151                 }
00152                 if (tmp == NULL) 
00153                         // Insert it at the head
00154                         insert(h, head_);
00155                 else 
00156                         append(h, tmp);
00157         } else if ((h->next() != NULL) && (h->hc() < h->next()->hc())) {
00158                 // Hit count decreased, need to move this one down
00159                 tmp = h->next();
00160                 detach(h);
00161                 while ((tmp != NULL) && (h->hc() < tmp->hc())) {
00162                         if ((h->page() == tmp->page()) && 
00163                             (h->layer() < tmp->layer()))
00164                                 // XXX Don't violate layer encoding within 
00165                                 // the same page!
00166                                 break;
00167                         tmp = tmp->next();
00168                 }
00169                 if (tmp == NULL)
00170                         // At the tail
00171                         append(h, tail_);
00172                 else
00173                         insert(h, tmp);
00174         }
00175         // We may end up with two cases here:
00176         //
00177         // (1) tmp->hc()>h->hc() && tmp->layer()<h->layer(). This is
00178         // the normal case, where both hit count ordering and layer 
00179         // ordering are preserved;
00180         //
00181         // (2) tmp->hc()>h->hc() && tmp->layer()>h->layer(). In this
00182         // case, we should move h BEFORE tmp so that the layer 
00183         // ordering is not violated. We basically order the list using 
00184         // layer number as primary key, and use hit count as secondary
00185         // key. 
00186         // Note that the hit count ordering is only violated when more packets 
00187         // in layer i are dropped than those in layer i+1.
00188 }

Here is the call graph for this function:

Member Data Documentation

DoubleListElem* DoubleList::head_ [protected, inherited]
 

Definition at line 117 of file utilities.h.

Referenced by MediaSegmentList::add(), add(), MediaSegmentList::check_holes(), MediaSegmentList::check_integrity(), check_integrity(), DoubleList::destroy(), DoubleList::detach(), DoubleList::DoubleList(), MediaSegmentList::dump2buf(), MediaSegmentList::evict_head(), MediaSegmentList::evict_head_offset(), MediaSegmentList::get_nextseg(), MediaSegmentList::getsize(), DoubleList::head(), MediaSegmentList::in(), DoubleList::insert(), MediaSegmentList::overlap_size(), MediaSegmentList::print(), print(), and update().

DoubleListElem * DoubleList::tail_ [protected, inherited]
 

Definition at line 117 of file utilities.h.

Referenced by MediaSegmentList::add(), add(), DoubleList::append(), DoubleList::destroy(), DoubleList::detach(), detach_tail(), DoubleList::DoubleList(), MediaSegmentList::evict_head_offset(), MediaSegmentList::evict_tail(), MediaSegmentList::merge_seg(), DoubleList::tail(), and update().

The documentation for this class was generated from the following files:
Generated on Tue Apr 20 12:51:07 2004 for NS2.26SourcesOriginal by doxygen 1.3.3