diff options
| -rw-r--r-- | Source/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | Source/cmLinkedTree.h | 164 | ||||
| -rw-r--r-- | Source/cmState.cxx | 112 | ||||
| -rw-r--r-- | Source/cmState.h | 9 |
4 files changed, 211 insertions, 75 deletions
diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt index a7adb51..e8d5107 100644 --- a/Source/CMakeLists.txt +++ b/Source/CMakeLists.txt @@ -281,6 +281,7 @@ set(SRCS cmInstallTargetGenerator.cxx cmInstallDirectoryGenerator.h cmInstallDirectoryGenerator.cxx + cmLinkedTree.h cmListFileCache.cxx cmListFileCache.h cmListFileLexer.c diff --git a/Source/cmLinkedTree.h b/Source/cmLinkedTree.h new file mode 100644 index 0000000..d2339c4 --- /dev/null +++ b/Source/cmLinkedTree.h @@ -0,0 +1,164 @@ +/*============================================================================ + CMake - Cross Platform Makefile Generator + Copyright 2015 Stephen Kelly <steveire@gmail.com> + + Distributed under the OSI-approved BSD License (the "License"); + see accompanying file Copyright.txt for details. + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the License for more information. +============================================================================*/ +#ifndef cmLinkedTree_h +#define cmLinkedTree_h + +#include "cmStandardIncludes.h" + +#include <assert.h> + +/** + @brief A adaptor for traversing a tree structure in a vector + + This class is not intended to be wholly generic like a standard library + container adaptor. Mostly it exists to facilitate code sharing for the + needs of the cmState. For example, the Truncate() method is a specific + requirement of the cmState. + + An empty cmLinkedTree provides a Root() method, and an Extend() method, + each of which return iterators. A Tree can be built up by extending + from the root, and then extending from any other iterator. + + An iterator resulting from this tree construction can be + forward-only-iterated toward the root. Extending the tree never + invalidates existing iterators. + */ +template<typename T> +class cmLinkedTree +{ + typedef typename std::vector<T>::size_type PositionType; + typedef T* PointerType; + typedef T& ReferenceType; +public: + class iterator : public std::iterator<std::forward_iterator_tag, T> + { + friend class cmLinkedTree; + cmLinkedTree* Tree; + + // The Position is always 'one past the end'. + PositionType Position; + + iterator(cmLinkedTree* tree, PositionType pos) + : Tree(tree), Position(pos) + { + + } + + public: + iterator() + : Tree(0), Position(0) + { + + } + + void operator++() + { + assert(this->Tree); + assert(this->Tree->UpPositions.size() == this->Tree->Data.size()); + assert(this->Position <= this->Tree->Data.size()); + assert(this->Position > 0); + this->Position = this->Tree->UpPositions[this->Position - 1]; + } + + PointerType operator->() const + { + assert(this->Tree); + assert(this->Tree->UpPositions.size() == this->Tree->Data.size()); + assert(this->Position <= this->Tree->Data.size()); + assert(this->Position > 0); + return this->Tree->GetPointer(this->Position - 1); + } + + PointerType operator->() + { + assert(this->Tree); + assert(this->Tree->UpPositions.size() == this->Tree->Data.size()); + assert(this->Position <= this->Tree->Data.size()); + assert(this->Position > 0); + return this->Tree->GetPointer(this->Position - 1); + } + + bool operator==(iterator other) const + { + assert(this->Tree); + assert(this->Tree->UpPositions.size() == this->Tree->Data.size()); + assert(this->Tree == other.Tree); + return this->Position == other.Position; + } + + bool operator!=(iterator other) const + { + assert(this->Tree); + assert(this->Tree->UpPositions.size() == this->Tree->Data.size()); + return !(*this == other); + } + + bool IsValid() const + { + if (!this->Tree) + { + return false; + } + return this->Position <= this->Tree->Data.size(); + } + }; + + iterator Root() const + { + return iterator(const_cast<cmLinkedTree*>(this), 0); + } + + iterator Extend(iterator it) + { + return Extend_impl(it, T()); + } + + iterator Extend(iterator it, T t) + { + return Extend_impl(it, t); + } + + iterator Truncate() + { + assert(this->UpPositions.size() > 0); + this->UpPositions.erase(this->UpPositions.begin() + 1, + this->UpPositions.end()); + assert(this->Data.size() > 0); + this->Data.erase(this->Data.begin() + 1, this->Data.end()); + return iterator(this, 1); + } + +private: + T& GetReference(PositionType pos) + { + return this->Data[pos]; + } + + T* GetPointer(PositionType pos) + { + return &this->Data[pos]; + } + + iterator Extend_impl(iterator it, T t) + { + assert(this->UpPositions.size() == this->Data.size()); + assert(it.Position <= this->UpPositions.size()); + this->UpPositions.push_back(it.Position); + this->Data.push_back(t); + return iterator(this, this->UpPositions.size()); + } + + std::vector<T> Data; + std::vector<PositionType> UpPositions; +}; + +#endif diff --git a/Source/cmState.cxx b/Source/cmState.cxx index 161cee4..a2ebb24 100644 --- a/Source/cmState.cxx +++ b/Source/cmState.cxx @@ -22,8 +22,8 @@ struct cmState::SnapshotDataType { cmState::PositionType DirectoryParent; cmState::SnapshotType SnapshotType; - std::vector<cmState::BuildsystemDirectoryStateType>::size_type - BuildSystemDirectoryPosition; + cmLinkedTree<cmState::BuildsystemDirectoryStateType>::iterator + BuildSystemDirectory; }; struct cmState::BuildsystemDirectoryStateType @@ -224,13 +224,8 @@ void cmState::Reset() this->GlobalProperties.clear(); this->PropertyDefinitions.clear(); - assert(this->BuildsystemDirectory.size() > 0); - assert(this->SnapshotData.size() > 0); - - this->BuildsystemDirectory.erase(this->BuildsystemDirectory.begin() + 1, - this->BuildsystemDirectory.end()); - this->SnapshotData.erase(this->SnapshotData.begin() + 1, - this->SnapshotData.end()); + this->BuildsystemDirectory.Truncate(); + this->SnapshotData.Truncate(); this->DefineProperty ("RULE_LAUNCH_COMPILE", cmProperty::DIRECTORY, @@ -620,9 +615,7 @@ void cmState::Snapshot::ComputeRelativePathTopSource() result = currentSource; } } - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - this->State->BuildsystemDirectory[pos].RelativePathTopSource = result; + this->Position->BuildSystemDirectory->RelativePathTopSource = result; } void cmState::Snapshot::ComputeRelativePathTopBinary() @@ -656,30 +649,26 @@ void cmState::Snapshot::ComputeRelativePathTopBinary() } } - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; // The current working directory on Windows cannot be a network // path. Therefore relative paths cannot work when the binary tree // is a network path. if(result.size() < 2 || result.substr(0, 2) != "//") { - this->State->BuildsystemDirectory[pos].RelativePathTopBinary = result; + this->Position->BuildSystemDirectory->RelativePathTopBinary = result; } else { - this->State->BuildsystemDirectory[pos].RelativePathTopBinary = ""; + this->Position->BuildSystemDirectory->RelativePathTopBinary = ""; } } cmState::Snapshot cmState::CreateBaseSnapshot() { - PositionType pos = 0; - this->SnapshotData.resize(1); - SnapshotDataType& snp = this->SnapshotData.back(); - snp.DirectoryParent = 0; - snp.SnapshotType = BuildsystemDirectoryType; - snp.BuildSystemDirectoryPosition = 0; - this->BuildsystemDirectory.resize(1); + PositionType pos = this->SnapshotData.Extend(this->SnapshotData.Root()); + pos->DirectoryParent = this->SnapshotData.Root(); + pos->SnapshotType = BuildsystemDirectoryType; + pos->BuildSystemDirectory = + this->BuildsystemDirectory.Extend(this->BuildsystemDirectory.Root()); return cmState::Snapshot(this, pos); } @@ -687,13 +676,12 @@ cmState::Snapshot cmState::CreateBuildsystemDirectorySnapshot(Snapshot originSnapshot) { assert(originSnapshot.IsValid()); - PositionType pos = this->SnapshotData.size(); - this->SnapshotData.resize(this->SnapshotData.size() + 1); - SnapshotDataType& snp = this->SnapshotData.back(); - snp.DirectoryParent = originSnapshot.Position; - snp.SnapshotType = BuildsystemDirectoryType; - snp.BuildSystemDirectoryPosition = this->BuildsystemDirectory.size(); - this->BuildsystemDirectory.resize(this->BuildsystemDirectory.size() + 1); + PositionType pos = this->SnapshotData.Extend(originSnapshot.Position); + pos->DirectoryParent = originSnapshot.Position; + pos->SnapshotType = BuildsystemDirectoryType; + pos->BuildSystemDirectory = + this->BuildsystemDirectory.Extend( + originSnapshot.Position->BuildSystemDirectory); return cmState::Snapshot(this, pos); } @@ -706,112 +694,94 @@ cmState::Snapshot::Snapshot(cmState* state, PositionType position) const char* cmState::Snapshot::GetCurrentSourceDirectory() const { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State->BuildsystemDirectory[pos].Location.c_str(); + return this->Position->BuildSystemDirectory->Location.c_str(); } void cmState::Snapshot::SetCurrentSourceDirectory(std::string const& dir) { assert(this->State); - assert(this->State->SnapshotData.size() > this->Position); - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - std::string& loc = this->State->BuildsystemDirectory[pos].Location; + std::string& loc = this->Position->BuildSystemDirectory->Location; loc = dir; cmSystemTools::ConvertToUnixSlashes(loc); loc = cmSystemTools::CollapseFullPath(loc); cmSystemTools::SplitPath( loc, - this->State->BuildsystemDirectory[pos].CurrentSourceDirectoryComponents); + this->Position->BuildSystemDirectory->CurrentSourceDirectoryComponents); this->ComputeRelativePathTopSource(); } const char* cmState::Snapshot::GetCurrentBinaryDirectory() const { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State->BuildsystemDirectory[pos].OutputLocation.c_str(); + return this->Position->BuildSystemDirectory->OutputLocation.c_str(); } void cmState::Snapshot::SetCurrentBinaryDirectory(std::string const& dir) { - assert(this->State->SnapshotData.size() > this->Position); - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - std::string& loc = this->State->BuildsystemDirectory[pos].OutputLocation; + std::string& loc = this->Position->BuildSystemDirectory->OutputLocation; loc = dir; cmSystemTools::ConvertToUnixSlashes(loc); loc = cmSystemTools::CollapseFullPath(loc); cmSystemTools::SplitPath( loc, - this->State->BuildsystemDirectory[pos].CurrentBinaryDirectoryComponents); + this->Position->BuildSystemDirectory->CurrentBinaryDirectoryComponents); this->ComputeRelativePathTopBinary(); } std::vector<std::string> const& cmState::Snapshot::GetCurrentSourceDirectoryComponents() { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State - ->BuildsystemDirectory[pos].CurrentSourceDirectoryComponents; + return this->Position->BuildSystemDirectory + ->CurrentSourceDirectoryComponents; } std::vector<std::string> const& cmState::Snapshot::GetCurrentBinaryDirectoryComponents() { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State - ->BuildsystemDirectory[pos].CurrentBinaryDirectoryComponents; + return this->Position->BuildSystemDirectory + ->CurrentBinaryDirectoryComponents; } const char* cmState::Snapshot::GetRelativePathTopSource() const { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State->BuildsystemDirectory[pos].RelativePathTopSource.c_str(); + return this->Position->BuildSystemDirectory->RelativePathTopSource.c_str(); } const char* cmState::Snapshot::GetRelativePathTopBinary() const { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - return this->State->BuildsystemDirectory[pos].RelativePathTopBinary.c_str(); + return this->Position->BuildSystemDirectory->RelativePathTopBinary.c_str(); } void cmState::Snapshot::SetRelativePathTopSource(const char* dir) { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - this->State->BuildsystemDirectory[pos].RelativePathTopSource = dir; + this->Position->BuildSystemDirectory->RelativePathTopSource = dir; } void cmState::Snapshot::SetRelativePathTopBinary(const char* dir) { - PositionType pos = - this->State->SnapshotData[this->Position].BuildSystemDirectoryPosition; - this->State->BuildsystemDirectory[pos].RelativePathTopBinary = dir; + this->Position->BuildSystemDirectory->RelativePathTopBinary = dir; } bool cmState::Snapshot::IsValid() const { - return this->State ? true : false; + return this->State && this->Position.IsValid() + ? this->Position != this->State->SnapshotData.Root() + : false; } cmState::Snapshot cmState::Snapshot::GetBuildsystemDirectoryParent() const { Snapshot snapshot; - if (!this->State || this->Position == 0) + if (!this->State || this->Position == this->State->SnapshotData.Root()) { return snapshot; } - PositionType parentPos = - this->State->SnapshotData[this->Position].DirectoryParent; - snapshot = Snapshot(this->State, parentPos); + PositionType parentPos = this->Position->DirectoryParent; + if (parentPos != this->State->SnapshotData.Root()) + { + snapshot = Snapshot(this->State, parentPos); + } return snapshot; } diff --git a/Source/cmState.h b/Source/cmState.h index 4589a72..1411e2f 100644 --- a/Source/cmState.h +++ b/Source/cmState.h @@ -15,6 +15,7 @@ #include "cmStandardIncludes.h" #include "cmPropertyDefinitionMap.h" #include "cmPropertyMap.h" +#include "cmLinkedTree.h" class cmake; class cmCommand; @@ -22,7 +23,7 @@ class cmCommand; class cmState { struct SnapshotDataType; - typedef std::vector<std::string>::size_type PositionType; + typedef cmLinkedTree<SnapshotDataType>::iterator PositionType; friend class Snapshot; public: cmState(cmake* cm); @@ -35,7 +36,7 @@ public: class Snapshot { public: - Snapshot(cmState* state = 0, PositionType position = 0); + Snapshot(cmState* state = 0, PositionType position = PositionType()); const char* GetCurrentSourceDirectory() const; void SetCurrentSourceDirectory(std::string const& dir); @@ -166,9 +167,9 @@ private: cmake* CMakeInstance; struct BuildsystemDirectoryStateType; - std::vector<BuildsystemDirectoryStateType> BuildsystemDirectory; + cmLinkedTree<BuildsystemDirectoryStateType> BuildsystemDirectory; - std::vector<SnapshotDataType> SnapshotData; + cmLinkedTree<SnapshotDataType> SnapshotData; std::vector<std::string> SourceDirectoryComponents; std::vector<std::string> BinaryDirectoryComponents; |