idep_LinkDep_i Struct Reference

List of all members.

Public Member Functions
	idep_LinkDep_i ()
	~idep_LinkDep_i ()
int	entry (const char *name, int suffixFlag)
void	loadDependencies (std::istream &in, int suffixFlag)
void	createCycleArray ()
int	calculate (std::ostream &orr, int canonicalFlag, int suffixFlag)
Public Attributes
idep_NameIndexMap	d_unaliases
idep_AliasTable	d_aliases
idep_NameArray	d_dependencyFiles
idep_NameIndexMap *	d_componentNames_p
idep_BinRel *	d_dependencies_p
int *	d_map_p
int *	d_levels_p
int *	d_levelNumbers_p
int *	d_cycles_p
int *	d_weights_p
int *	d_cycleIndices_p
int	d_numComponents
int	d_numLevels
int	d_numCycles
int	d_numMembers
int	d_ccd

---

Constructor & Destructor Documentation

idep_LinkDep_i::idep_LinkDep_i (   )

Definition at line 141 of file idep_ldep.cxx. : d_componentNames_p(0) , d_dependencies_p(0) , d_map_p(0) , d_levels_p(0) , d_levelNumbers_p(0) , d_cycles_p(0) , d_weights_p(0) , d_cycleIndices_p(0) , d_numComponents(-1) , d_numLevels(-1) , d_numCycles(-1) , d_numMembers(-1) , d_ccd(-1) { }

idep_LinkDep_i::~idep_LinkDep_i (   )

Definition at line 158 of file idep_ldep.cxx. { delete d_componentNames_p; delete d_dependencies_p; delete [] d_map_p; delete [] d_levels_p; delete [] d_levelNumbers_p; delete [] d_cycles_p; delete [] d_weights_p; delete [] d_cycleIndices_p; }

---

Member Function Documentation

int idep_LinkDep_i::calculate (  std::ostream &  orr, int  canonicalFlag, int  suffixFlag )

Definition at line 331 of file idep_ldep.cxx. References idep_BinRel::clr(), createCycleArray(), d_ccd, d_componentNames_p, d_cycleIndices_p, d_cycles_p, d_dependencies_p, d_dependencyFiles, d_levelNumbers_p, d_levels_p, d_map_p, d_numComponents, d_numCycles, d_numLevels, d_numMembers, d_weights_p, err(), idep_BinRel::get(), IOERROR, idep_NameIndexMap::length(), idep_BinRel::length(), idep_NameArray::length(), loadDependencies(), idep_BinRel::makeNonTransitive(), idep_BinRel::makeTransitive(), and idep_BinRel::set(). Referenced by idep_LinkDep::calculate(). { enum { IOERRR = -1 }; // clean up any previous calculation artifacts delete d_componentNames_p; delete d_dependencies_p; delete [] d_map_p; delete [] d_levels_p; delete [] d_levelNumbers_p; delete [] d_cycles_p; delete [] d_weights_p; delete [] d_cycleIndices_p; // allocate new data structures for this calculation d_componentNames_p = new idep_NameIndexMap; d_dependencies_p = new idep_BinRel; d_map_p = 0; // allocated later when length is known d_levels_p = 0; // allocated later when length is known d_levelNumbers_p = 0; // allocated later when length is known d_cycles_p = 0; // allocated later when length is known d_numLevels = -1; // invalidate for now d_numComponents = -1; // invalidate for now (-1 value is important) d_numCycles = -1; // invalidate for now d_numMembers = -1; // invalidate for now d_ccd = -1; // invalidate for now // Now try to read dependencies from specified set of files. // If an I/O error occurs, abort; otherwise keep on processing. int i; for (i = 0; i < d_dependencyFiles.length(); ++i) { const int INSANITY = 1000; if (d_dependencies_p->length() > INSANITY) { orr << "SANITY CHECK: Number of components is currently " << d_dependencies_p->length() << " !!!!" << std::endl; } enum { IOERROR = -1 }; const char *file = d_dependencyFiles[i]; if ('\0' == *file) { loadDependencies(std::cin, suffixFlag); // reset eof for standard input std::cin.clear(std::ios::iostate(0)); } else { std::ifstream in(file); if (!in) { err(orr) << "dependency file \"" << file << "\" not found." << std::endl; return IOERROR; } loadDependencies(in, suffixFlag); } } // We can now allocate fixed size arrays: d_numComponents = d_dependencies_p->length(); assert (d_componentNames_p->length() == d_numComponents); // Create the level array for component name indices. We will fill in the // level array with the number of components on each level. d_levels_p = new int[d_numComponents]; // will holds # of components/level d_numLevels = 0; // initially there are no levels // Create the level number array to hold the level number for each // component. This array will be filled in at the end of this function. d_levelNumbers_p = new int[d_numComponents]; // will holds level #'s // Create the mapping array for component name indices. This array // will hold the sorted indices of the original component names. d_map_p = new int[d_numComponents]; // array of levelized component indices int pIndex = 0; // current length of mapping // Create an array of byte vectors. Each byte vector identifies the // components that are below the indicated level index. The rows are // allocated as the levels in the system are defined, beginning with level // corresponding to d_numLevels = 0. At the end of this calculation, the // first d_numLevels + 1 byte vectors in this array must be deleted // explicitly. // // level // index // +-------+ // N | ? | // +-------+ // N-1 | ? | +----------------------------------+ // +-------+ | `i' is defined to be d_numLevels | // : : +----------------------------------+---+ // : : | `N' is defined to be d_numComponents | // +-------+ +--------------------------------------+ // i+1 | ? | // +-------+ // i | o---|--->[ 1 ][ 1 ][ 0 ][ 1 ][ 1 ][ 1 ][ 0 ] ... [ 0 ] // +-------+ // : : // : : // +-------+ // 1 | o---|--->[ 0 ][ 1 ][ 0 ][ 0 ][ 1 ][ 0 ][ 0 ] ... [ 0 ] // +-------+ // 0 | o---|--->[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ] ... [ 0 ] // +-------+ // component index: 0 1 2 3 4 5 6 N-1 char **lowerThan = new char *[d_numComponents + 1]; // array of byte sets lowerThan[0] = new char[d_numComponents]; // set of lower-level components memset(lowerThan[0], 0, d_numComponents); // initially this set is empty char *current = new char[d_numComponents]; // components on current level d_dependencies_p->makeTransitive(); // perform transitive closure algorithm createCycleArray(); // determine and label members of all cycles // We can now use the transitive dependency relation to sort the // components in this system into levelized order (provided the // graph is asyclic). In order to facilitate the levelization // algorithm, the principal members of each cycle will be temporarily // stripped of their dependency on the other members of that cycle. // All of the remaining members will be ignored by the levelization // algorithm (by marking them as already belonging to a lower level). for (i = 0; i < d_numComponents; ++i) { if (d_cycles_p[i] == i) { int j; for (j = i + 1; j < d_numComponents; ++j) { if (d_cycles_p[j] == i) { assert(d_dependencies_p->get(i,j)); d_dependencies_p->clr(i,j); // strip cyclic dependency lowerThan[0][j] = 1; // ignore other members in algorithm } } } } // We will now construct the levelized array of component indices. For // each level in this system, we will examine each component in the system // to see if it depends on any higher level components. Note that we have // already stripped out cyclic dependencies as described above. If a // component is part of a lower level we will ignore it. Otherwise, we // will check to see if that component depends on any other components // that are _not_ at a lower level. If so, the component is skipped over; // otherwise the component index is added to the current level and // appended to the end of the levelized list. If this index corresponds // to the principal member of a cycle, we use the weight of the cycle to // determine the level below the current level to use to to check // dependencies. If the principal member of the cycle depends only on // components at a level "weight" (or more) lower than the current level, // all other members are immediately appended to the list in their // original order. At this point, we restore the cyclic dependencies of // that principal component on the other members of its cycle. After // iterating through all of the components, the number of components on // the current level is appended to the level array and the current level // set is united with the lower level set. This process repeats until all // components are assigned a level. while (pIndex < d_numComponents) { // not all components assigned a level int componentCount = 0; // number of components on this level memset(current, 0, d_numComponents); // initially current level empty int i; for (i = 0; i < d_numComponents; ++i) { if (d_cycles_p[i] >= 0 && d_cycles_p[i] != i) { continue; // component is non principal member of a cycle } if (lowerThan[d_numLevels][i]) { continue; // already at a lower level; } int weight = 1; // weight of non-cyclically dependent component if (d_cycles_p[i] == i) { // if principal member of cycle weight = d_weights_p[i]; if (d_weights_p[i] > d_numLevels + 1) { continue; // weight of cycle two heigh for current level } } int searchLevel = d_numLevels + 1 - weight; // allowed dependencies int j; for (j = 0; j < d_numComponents; ++j) { if (i == j) { continue; } if (d_dependencies_p->get(i,j) && !lowerThan[searchLevel][j]) { break; // depends on component not at or below search level } } if (j < d_numComponents) { continue; // consider next candidate i } current[i] = 1; // record component as being at the current level d_map_p[pIndex++] = i; // append component in levelized order ++componentCount; if (d_cycles_p[i] == i) { // if principal member of a cycle for (j = i + 1; j < d_numComponents; ++j) { if (d_cycles_p[j] == i) { // if other member of this cycle d_map_p[pIndex++] = j; // append it to current level ++componentCount; d_dependencies_p->set(i,j); // restore dependencies } } } } // advance to next level for (i = 0; i < d_numComponents; ++i) { current[i] |= lowerThan[d_numLevels][i]; } d_levels_p[d_numLevels++] = componentCount; // components per level lowerThan[d_numLevels] = current; // attach new lower level current = new char[d_numComponents]; // reallocate current array } assert (pIndex == d_numComponents); // at this point we can load the level number array int start = 0; for (i = 0; i < d_numLevels; ++i) { int top = start + d_levels_p[i]; int j; for (j = start; j < top; ++j) { d_levelNumbers_p[d_map_p[j]] = i; } start = top; } // Sort components within each level lexicographically to make names // easier to find and to provide a canonical order to facilitate finding // differences as software is modified (e.g., via the Unix diff command). start = 0; int k; for (k = 0; k < d_numLevels; ++k) { int top = start + d_levels_p[k]; int i; for (i = start + 1; i < top; ++i) { int j; for (j = start; j < i; ++j) { if (strcmp((*d_componentNames_p)[d_map_p[i]], (*d_componentNames_p)[d_map_p[j]]) < 0) { int tmp = d_map_p[i]; d_map_p[i] = d_map_p[j]; d_map_p[j] = tmp; } } } start = top; } // We can now uses the cycles array and the level map to create the // cycleIndex array. This array assigns all components of each cycle // a unique cycle index (in increasing order w.r.t. level). int cycleCount = 0; for (i = 0; i < d_numComponents; ++i) { const int label = d_cycles_p[d_map_p[i]]; if (label < 0) { continue; // not part of any cycle } const int index = d_cycleIndices_p[d_map_p[i]]; if (index >= 0 && index < cycleCount) { continue; // part of lower level cycle } // Found the next cycle, go through the remander of the sequence and // annotate each correspondingly labeled component with current cycle // index in the cycleIndices array. int j; for (j = i; j < d_numComponents; ++j) { if (label == d_cycles_p[d_map_p[j]]) { d_cycleIndices_p[d_map_p[j]] = cycleCount; } } ++cycleCount; } assert(cycleCount == d_numCycles); // Now sort components within each level again, but this time // group cyclically dependent components together in order of // cycle index to facilitate understanding of cycle composition. // The previous sort ensured that cycle indices will be in the // order of the lexicographically smallest member of the cycle // on a given level. start = 0; for (k = 0; k < d_numLevels; ++k) { int top = start + d_levels_p[k]; int i; for (i = start + 1; i < top; ++i) { int j; for (j = start; j < i; ++j) { int ci = d_cycleIndices_p[d_map_p[i]]; int cj = d_cycleIndices_p[d_map_p[j]]; if (ci < cj || ci == cj && strcmp((*d_componentNames_p)[d_map_p[i]], (*d_componentNames_p)[d_map_p[j]]) < 0) { int tmp = d_map_p[i]; d_map_p[i] = d_map_p[j]; d_map_p[j] = tmp; } } } start = top; } // Clean up local data structures. for (i = 0; i <= d_numLevels; ++i) { delete [] lowerThan[i]; } delete [] lowerThan; delete [] current; // Calculate CCD and cache the value in a data member of the object. idep_BinRel tmp = *d_dependencies_p; // temporary for calculating CCD for (i = 0; i < d_numComponents; ++i) { if (0 == d_levelNumbers_p[i]) { for (int j = 0; j < d_numComponents; ++j) { tmp.clr(j, i); // ignore dependencies on all level 0 components } } else { tmp.set(i, i); // each component itself contributes unit weight } } int sum = 0; for (i = 0; i < d_numComponents; ++i) { for (int j = 0; j < d_numComponents; ++j) { if (tmp.get(i,j)) { ++sum; } } } d_ccd = sum; // Cache this value -- too hard to calculate later. if (canonicalFlag) { // In order to ensure a canonical representations with redundant // dependencies removed, it is necessary to create a canonical // sorted binary relation based on the d_map_p array. After removing // transitive entries from that relation, the results are then mapped // back to the d_dependencies_p relation. idep_BinRel tmp(d_numComponents); int i; for (i = 0; i < d_numComponents; ++i) { int u = d_map_p[i]; for (int j = 0; j < d_numComponents; ++j) { int v = d_map_p[j]; int bit = d_dependencies_p->get(u, v); tmp.set(i, j, bit); } } tmp.makeNonTransitive(); for (i = 0; i < d_numComponents; ++i) { int u = d_map_p[i]; for (int j = 0; j < d_numComponents; ++j) { int v = d_map_p[j]; int bit = tmp.get(i, j); d_dependencies_p->set(u, v, bit); } } } return d_numMembers; }

void idep_LinkDep_i::createCycleArray (   )

Definition at line 255 of file idep_ldep.cxx. References d_cycleIndices_p, d_cycles_p, d_dependencies_p, d_numComponents, d_numCycles, d_numMembers, d_weights_p, and idep_BinRel::get(). Referenced by calculate(). { assert (!d_cycles_p); // should not already exist assert (!d_weights_p); // should not already exist assert (!d_cycleIndices_p); // should not already exist assert (d_numComponents >= 0); // should be valid // Create the cycle array used to detect and identify potential cycles. d_cycles_p = new int[d_numComponents]; // identifies members of cycles d_weights_p = new int[d_numComponents]; // identifies weights of cycles d_cycleIndices_p = new int[d_numComponents]; // consecutive indices // Members of each cycle are identified by the index of their first member. enum { NO_CYCLE = -1 }; int i; for (i = 0; i < d_numComponents; ++i) { d_cycles_p[i] = NO_CYCLE; // Initially each entry is invalid. d_weights_p[i] = 0; // Initially weight of each cycle is 0. d_cycleIndices_p[i] = NO_CYCLE; // Initially each entry is invalid. // These indices will be determined // after levelization has occurred. } d_numCycles = 0; // # of unique design cycles d_numMembers = 0; // # of cyclicly-dependent components // Load the cycle array. For each cycle detected, the non-negative // index of the lowest participating component is used as a tag to // identify that cycle. For each component we will scan ahead to see // on what other components this component is mutually dependent. // If one or more is found, each of these locations will be set to // the index value of the first (primary) component in the cycle. // Ideally there will be no cycles, in which case each entry in the // array will be left set to -1. We will use the cycle array initially // to report all cyclic dependencies and again later to facilitate // the levelization algorithm in the presence of cycles. for (i = 0; i < d_numComponents; ++i) { if (d_cycles_p[i] >= 0) { continue; // part of a previously reported cycle } int cycleFound = 0; d_cycles_p[i] = i; // first component in potential cycle int j; for (j = i + 1; j < d_numComponents; ++j) { if (d_cycles_p[j] >= 0) { continue; // part of a previously reported cycle } if (d_dependencies_p->get(i, j) && d_dependencies_p->get(j, i)) { cycleFound = 1; // record that we have a cycle d_cycles_p[j] = i; // record index of first component } } if (cycleFound) { // if cycle found involving component `i' int weight = 0; for (j = i; j < d_numComponents; ++j) { // find each cycle member if (d_cycles_p[j] == i) { ++weight; // # members in this cycle } } for (j = i; j < d_numComponents; ++j) { // find each cycle member if (d_cycles_p[j] == i) { d_weights_p[j] = weight; // store weight for each member } } d_numMembers += weight; // total # of members in cycles ++d_numCycles; } else { d_cycles_p[i] = NO_CYCLE; // component `i' is not part of a cycle } } }

int idep_LinkDep_i::entry (  const char *  name, int  suffixFlag )

Definition at line 170 of file idep_ldep.cxx. References idep_BinRel::appendEntry(), d_aliases, d_componentNames_p, d_dependencies_p, d_unaliases, idep_NameIndexMap::entry(), isLocal(), len, idep_NameIndexMap::length(), idep_AliasTable::lookup(), idep_NameIndexMap::lookup(), NULL_CHAR, removeFileName(), and removeSuffix(). Referenced by loadDependencies(). { int size = strlen(name) + 1; char *buf = new char[size]; memcpy(buf, name, size); if (!isLocal(buf)) { removeFileName(buf); if (d_unaliases.lookup(buf) >= 0) { // found unalias memcpy(buf, name, size); // restore buffer } } if (suffixFlag) { removeSuffix(buf); } const char *componentName = d_aliases.lookup(buf); if (!componentName) { const char SLASH_CHAR = '/'; const char NULL_CHAR = '\0'; int len = strlen(buf); int last = len - 1; if (SLASH_CHAR == buf[last]) { // If the input ends in '/' buf[last] = NULL_CHAR; // try removing the '/' and componentName = d_aliases.lookup(buf); // checking for that alias. if (!componentName) { buf[last] = SLASH_CHAR; // restore } } } if (!componentName) { componentName = buf; } int length = d_componentNames_p->length(); int index = d_componentNames_p->entry(componentName); if (d_componentNames_p->length() > length) { d_dependencies_p->appendEntry(); } delete [] buf; return index; }

void idep_LinkDep_i::loadDependencies (  std::istream &  in, int  suffixFlag )

Definition at line 217 of file idep_ldep.cxx. References d_dependencies_p, entry(), NEWLINE_CHAR, and idep_BinRel::set(). Referenced by calculate(). { enum { INVALID_INDEX = -1 }; const char NEWLINE_CHAR = '\n'; int lineno = 1; int fromIndex = INVALID_INDEX; int lastTokenWasNewline = 1; for (idep_TokenIter it(in); it; ++it) { if ('#' == *it()) { // strip comment if any while (it && '\n' != *it()) { ++it; } if (!it) { // either !it or '\n' continue; } } if (NEWLINE_CHAR == *it()) { ++lineno; // end of line if (lastTokenWasNewline) { fromIndex = INVALID_INDEX; // end of current sequence } lastTokenWasNewline = 1; // record newline state } else { if (INVALID_INDEX == fromIndex) { fromIndex = entry(it(), suffixFlag); // start of new sequence } else { // found a dependency int toIndex = entry(it(), suffixFlag); d_dependencies_p->set(fromIndex, toIndex); } lastTokenWasNewline = 0; // record newline state } } }

---

Member Data Documentation

idep_AliasTable idep_LinkDep_i::d_aliases

Definition at line 115 of file idep_ldep.cxx. Referenced by idep_LinkDep::addAlias(), entry(), and idep_LinkDep::readAliases().

int idep_LinkDep_i::d_ccd

Definition at line 130 of file idep_ldep.cxx. Referenced by calculate(), and idep_LinkDep::ccd().

idep_NameIndexMap* idep_LinkDep_i::d_componentNames_p

Definition at line 118 of file idep_ldep.cxx. Referenced by calculate(), entry(), idep_DependencyIter::operator()(), idep_ComponentIter::operator()(), and idep_MemberIter::operator()().

int* idep_LinkDep_i::d_cycleIndices_p

Definition at line 125 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), idep_DependencyIter::cycle(), idep_ComponentIter::cycle(), idep_MemberIter::operator++(), and idep_CycleIter::operator++().

int* idep_LinkDep_i::d_cycles_p

Definition at line 123 of file idep_ldep.cxx. Referenced by calculate(), and createCycleArray().

idep_BinRel* idep_LinkDep_i::d_dependencies_p

Definition at line 119 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), entry(), loadDependencies(), and idep_DependencyIter::operator++().

idep_NameArray idep_LinkDep_i::d_dependencyFiles

Definition at line 116 of file idep_ldep.cxx. Referenced by idep_LinkDep::addDependencyFile(), and calculate().

int* idep_LinkDep_i::d_levelNumbers_p

Definition at line 122 of file idep_ldep.cxx. Referenced by calculate(), and idep_DependencyIter::level().

int* idep_LinkDep_i::d_levels_p

Definition at line 121 of file idep_ldep.cxx. Referenced by calculate(), idep_LinkDep::numPackages(), and idep_LevelIter::operator++().

int* idep_LinkDep_i::d_map_p

Definition at line 120 of file idep_ldep.cxx. Referenced by calculate(), idep_DependencyIter::cycle(), idep_ComponentIter::cycle(), idep_DependencyIter::level(), idep_DependencyIter::operator()(), idep_ComponentIter::operator()(), idep_MemberIter::operator()(), idep_DependencyIter::operator++(), idep_MemberIter::operator++(), idep_CycleIter::operator++(), and idep_CycleIter::weight().

int idep_LinkDep_i::d_numComponents

Definition at line 126 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), idep_LinkDep::numComponents(), idep_DependencyIter::operator const void *(), idep_MemberIter::operator const void *(), and idep_CycleIter::operator const void *().

int idep_LinkDep_i::d_numCycles

Definition at line 128 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), and idep_LinkDep::numCycles().

int idep_LinkDep_i::d_numLevels

Definition at line 127 of file idep_ldep.cxx. Referenced by calculate(), idep_LinkDep::numLevels(), and idep_LevelIter::operator const void *().

int idep_LinkDep_i::d_numMembers

Definition at line 129 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), and idep_LinkDep::numMembers().

idep_NameIndexMap idep_LinkDep_i::d_unaliases

Definition at line 114 of file idep_ldep.cxx. Referenced by idep_LinkDep::addUnaliasDirectory(), entry(), and idep_LinkDep::readUnaliasDirectories().

int* idep_LinkDep_i::d_weights_p

Definition at line 124 of file idep_ldep.cxx. Referenced by calculate(), createCycleArray(), and idep_CycleIter::weight().

---

The documentation for this struct was generated from the following file:

• idep_ldep.cxx

---