Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

idep_BinRel Class Reference

#include <idep_binrel.h>

List of all members.

Public Member Functions

 idep_BinRel (int initialEntries=0, int maxEntriesHint=0)
 idep_BinRel (const idep_BinRel &rel)
 ~idep_BinRel ()
idep_BinRel & operator= (const idep_BinRel &rel)
void set (int row, int col, int bit)
void set (int row, int col)
void clr (int row, int col)
void makeTransitive ()
void makeNonTransitive ()
int appendEntry ()
int get (int row, int col) const
int cmp (const idep_BinRel &rel) const
int length () const

Private Member Functions

void grow ()
void compress ()
void warshall (int bit)

Private Attributes

char ** d_rel_p
int d_size
int d_length

Constructor & Destructor Documentation

idep_BinRel::idep_BinRel (  int  initialEntries = 0,
int  maxEntriesHint = 0
) 
 

Definition at line 85 of file idep_binrel.cxx.

References alloc(), clear(), d_rel_p, d_size, and START_SIZE.

00086 : d_size(maxEntriesHint > 0 ? maxEntriesHint : START_SIZE) 
00087 , d_length(initialEntries > 0 ? initialEntries : 0)
00088 {
00089     if (d_size < d_length) {
00090         d_size = d_length;
00091     }
00092     d_rel_p = alloc(d_size);
00093     clear(d_rel_p, d_size);
00094 }

idep_BinRel::idep_BinRel (  const idep_BinRel &  rel  ) 
 

Definition at line 96 of file idep_binrel.cxx.

References alloc(), copy(), d_rel_p, and d_size.

00097 : d_rel_p(alloc(rel.d_size)) 
00098 , d_size(rel.d_size)
00099 , d_length(rel.d_length)
00100 { 
00101     copy(d_rel_p, rel.d_rel_p, d_size);
00102 }

idep_BinRel::~idep_BinRel (   ) 
 

Definition at line 118 of file idep_binrel.cxx.

References clean(), and d_rel_p.

00119 {
00120     clean(d_rel_p);
00121 }

Member Function Documentation

int idep_BinRel::appendEntry (   )  [inline]
 

Definition at line 95 of file idep_binrel.h.

References d_length, and grow().

Referenced by idep_CompileDep::calculate(), idep_LinkDep_i::entry(), and getDep().

00096 {
00097     if (d_length >= d_size) {
00098         grow();
00099     }
00100     return d_length++;
00101 }

void idep_BinRel::clr (  int  row,
int  col
)  [inline]
 

Definition at line 116 of file idep_binrel.h.

References d_rel_p.

Referenced by idep_LinkDep_i::calculate().

00117 {
00118     d_rel_p[row][col] = 0;
00119 }

int idep_BinRel::cmp (  const idep_BinRel &  rel  )  const
 

Definition at line 123 of file idep_binrel.cxx.

References d_length, d_rel_p, and d_size.

Referenced by operator!=(), and operator==().

00124 {
00125     enum { SAME = 0, DIFFERENT = 1 };
00126 
00127     if (d_length != rel.d_length) {
00128         return DIFFERENT;
00129     }
00130 
00131     if (d_size == rel.d_size && 
00132                             memcmp(*d_rel_p, *rel.d_rel_p, d_size * d_size)) {
00133         return DIFFERENT;
00134     }
00135 
00136     for (int i = 0; i < d_length; ++i) {
00137         if (memcmp(d_rel_p[i], rel.d_rel_p[i], d_length)) {
00138             return DIFFERENT;
00139         }
00140     }
00141 
00142     return SAME;
00143 }

void idep_BinRel::compress (   )  [private]
 

Definition at line 69 of file idep_binrel.cxx.

References alloc(), clean(), clear(), d_length, d_rel_p, and d_size.

Referenced by warshall().

00070 {
00071     if (d_size > d_length && d_length > 0) {
00072         d_size = d_length;
00073         char **tmp = d_rel_p;
00074         d_rel_p = alloc(d_size);
00075         clear(d_rel_p, d_size);
00076         for (int i = 0; i < d_size; ++i) {
00077             memcpy(d_rel_p[i], tmp[i], d_size);
00078         }
00079         clean(tmp);
00080     }
00081 }

int idep_BinRel::get (  int  row,
int  col
)  const [inline]
 

Definition at line 122 of file idep_binrel.h.

References d_rel_p.

Referenced by idep_LinkDep_i::calculate(), idep_LinkDep_i::createCycleArray(), idep_DependencyIter::operator++(), idep_HeaderFileIter::operator++(), and operator<<().

00123 {
00124     return d_rel_p[row][col];
00125 }

void idep_BinRel::grow (   )  [private]
 

Definition at line 54 of file idep_binrel.cxx.

References alloc(), clean(), clear(), d_rel_p, and d_size.

Referenced by appendEntry().

00055 {
00056     int newSize = d_size * GROW_FACTOR;
00057     char **tmp = d_rel_p;
00058     d_rel_p = alloc(newSize);
00059     clear(d_rel_p, newSize);
00060 
00061     for (int i = 0; i < d_size; ++i) {
00062         memcpy(d_rel_p[i], tmp[i], d_size);
00063     }
00064 
00065     d_size = newSize;
00066     clean(tmp);
00067 }

int idep_BinRel::length (   )  const [inline]
 

Definition at line 128 of file idep_binrel.h.

Referenced by idep_LinkDep_i::calculate(), makeNonTransitive(), idep_HeaderFileIter::operator const void *(), idep_HeaderFileIter::operator++(), and operator<<().

00129 {
00130     return d_length;
00131 }

void idep_BinRel::makeNonTransitive (   ) 
 

Definition at line 197 of file idep_binrel.cxx.

References d_rel_p, length(), and warshall().

Referenced by idep_LinkDep_i::calculate().

00198 {
00199     warshall(0);
00200     // make non-reflexive too -- i.e., subtract the identity matrix.
00201     for (int i = 0; i < length(); ++i) {
00202         d_rel_p[i][i] = 0;
00203     }
00204 }

void idep_BinRel::makeTransitive (   ) 
 

Definition at line 192 of file idep_binrel.cxx.

References warshall().

Referenced by idep_LinkDep_i::calculate(), and idep_CompileDep::calculate().

00193 {
00194     warshall(1);
00195 }

idep_BinRel & idep_BinRel::operator= (  const idep_BinRel &  rel  ) 
 

Definition at line 104 of file idep_binrel.cxx.

References alloc(), clean(), copy(), d_length, d_rel_p, and d_size.

00105 {  
00106     if (&rel != this) {
00107         if (d_size != rel.d_size) { 
00108             clean(d_rel_p);
00109             d_size = rel.d_size;
00110             d_rel_p = alloc(d_size);
00111         }
00112         copy(d_rel_p, rel.d_rel_p, d_size);
00113         d_length = rel.d_length;
00114     }
00115     return *this;
00116 }

void idep_BinRel::set (  int  row,
int  col
)  [inline]
 

Definition at line 110 of file idep_binrel.h.

References d_rel_p.

00111 {
00112     d_rel_p[row][col] = 1;
00113 }

void idep_BinRel::set (  int  row,
int  col,
int  bit
)  [inline]
 

Definition at line 104 of file idep_binrel.h.

References d_rel_p.

Referenced by idep_LinkDep_i::calculate(), getDep(), and idep_LinkDep_i::loadDependencies().

00105 {
00106     d_rel_p[row][col] = !!bit;
00107 }

void idep_BinRel::warshall (  int  bit  )  [private]
 

Definition at line 145 of file idep_binrel.cxx.

References compress(), d_length, d_rel_p, d_size, and s().

Referenced by makeNonTransitive(), and makeTransitive().

00146 {
00147     // DEFINITION: Transitive Closure
00148     //
00149     // Given: R is a relation (matrix) indicating transitions in 1 step.
00150     // TransitiveClosure(R) = R + R^2 + R^3 + ... + R^N 
00151     //      where N is the number of rows and columns in the square matrix R.
00152     //
00153     // Warshall's algorithm to construct the transitive closure:
00154     // foreach index k
00155     //     foreach row i
00156     //         foreach column j
00157     //             if (A[i][k] && A[k][j]) 
00158     //                 A[i][j] = 1;      
00159     // 
00160     // See Aho, Hopcroft, & Ullman, "Data Structures And Algorithms,"
00161     // Addison-Wesley, Reading MA, pp. 212-213.  Also see, Warshall, S. [1962].
00162     // "A theorem on Boolean matrices," Journal of the ACM, 9:1, pp. 11-12.
00163 
00164     compress();
00165     assert(d_size == d_length || 0 == d_length);
00166 
00167     register const int VALUE = !!bit;
00168     register int s = d_length;  // size and length are the same or length is 0
00169     register char *top_row = d_rel_p[0] + s * s;
00170 
00171     for (int k = 0; k < s; ++k) {
00172         register char *row_k = d_rel_p[k];
00173         for (register char *row_r = d_rel_p[0]; row_r < top_row; row_r += s) {
00174             if (!row_r[k]) { 
00175                 continue;                   // huge optimization
00176             }
00177             if (d_rel_p[k] == row_r) {  
00178                 continue;                   // note: ignore self dependency
00179             }
00180             for (register int c = 0; c < s; ++c) {
00181                 if (row_k[c] && row_r[k]) { // note: both conditions are needed
00182                                             // in reverse (consider k == c).
00183                     if (c != k) {           // note: ignore self dependency
00184                         row_r[c] = VALUE;   
00185                     }
00186                 }
00187             }
00188         }
00189     }
00190 }

Member Data Documentation

int idep_BinRel::d_length [private]
 

Definition at line 13 of file idep_binrel.h.

Referenced by appendEntry(), cmp(), compress(), operator=(), and warshall().

char** idep_BinRel::d_rel_p [private]
 

Definition at line 11 of file idep_binrel.h.

Referenced by clr(), cmp(), compress(), get(), grow(), idep_BinRel(), makeNonTransitive(), operator=(), set(), warshall(), and ~idep_BinRel().

int idep_BinRel::d_size [private]
 

Definition at line 12 of file idep_binrel.h.

Referenced by cmp(), compress(), grow(), idep_BinRel(), operator=(), and warshall().

The documentation for this class was generated from the following files:
Generated on Mon Feb 15 11:09:19 2010 for loon by  doxygen 1.3.9.1