src/TortoiseProc/RevisionGraph/VisibleGraphNode.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2003-2008 - TortoiseSVN\r
   4 \r
   5 // This program is free software; you can redistribute it and/or\r
   6 // modify it under the terms of the GNU General Public License\r
   7 // as published by the Free Software Foundation; either version 2\r
   8 // of the License, or (at your option) any later version.\r
   9 \r
  10 // This program is distributed in the hope that it will be useful,\r
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13 // GNU General Public License for more details.\r
  14 \r
  15 // You should have received a copy of the GNU General Public License\r
  16 // along with this program; if not, write to the Free Software Foundation,\r
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
  18 //\r
  19 \r
  20 #include "StdAfx.h"\r
  21 #include "VisibleGraphNode.h"\r
  22 #include "VisibleGraph.h"\r
  23 \r
  24 // CVisibleGraphNode::CFoldedTag methods\r
  25 \r
  26 bool CVisibleGraphNode::CFoldedTag::IsAlias() const\r
  27 {\r
  28     const CFullGraphNode* prev \r
  29         = tagNode->GetPrevious() == NULL\r
  30             ? tagNode->GetCopySource()\r
  31             : tagNode->GetPrevious();\r
  32 \r
  33     // skip all non-modifying nodes and make prev point to\r
  34     // either the copy node or the last modification\r
  35 \r
  36     while (   (prev != NULL) \r
  37            && (!prev->GetClassification().IsAnyOf \r
  38                   (CNodeClassification::IS_OPERATION_MASK)))\r
  39     {\r
  40         prev = prev->GetPrevious();\r
  41     }\r
  42 \r
  43     // it's an alias if the previous node is a tag and has\r
  44     // not been modified since\r
  45 \r
  46     return    (prev != NULL) \r
  47            && prev->GetClassification().Is (CNodeClassification::IS_TAG)\r
  48            && prev->GetClassification().IsAnyOf (  CNodeClassification::IS_ADDED\r
  49                                                  + CNodeClassification::IS_RENAMED);\r
  50 }\r
  51 \r
  52 // CVisibleGraphNode::CFactory methods\r
  53 \r
  54 CVisibleGraphNode::CFactory::CFactory()\r
  55     : nodePool (sizeof (CVisibleGraphNode), 1024)\r
  56     , tagPool (sizeof (CFoldedTag), 1024)\r
  57     , copyTargetFactory()\r
  58     , nodeCount (0)\r
  59 {\r
  60 }\r
  61 \r
  62 // factory interface\r
  63 \r
  64 CVisibleGraphNode* CVisibleGraphNode::CFactory::Create \r
  65     ( const CFullGraphNode* base\r
  66     , CVisibleGraphNode* prev\r
  67     , bool preserveNode)\r
  68 {\r
  69     CVisibleGraphNode * result = static_cast<CVisibleGraphNode *>(nodePool.malloc());\r
  70     new (result) CVisibleGraphNode (base, prev, copyTargetFactory, preserveNode);\r
  71 \r
  72     ++nodeCount;\r
  73     return result;\r
  74 }\r
  75 \r
  76 void CVisibleGraphNode::CFactory::Destroy (CVisibleGraphNode* node)\r
  77 {\r
  78     node->DestroySubNodes (*this, copyTargetFactory);\r
  79     node->DestroyTags (*this);\r
  80 \r
  81     node->~CVisibleGraphNode();\r
  82     nodePool.free (node);\r
  83 \r
  84     --nodeCount;\r
  85 }\r
  86 \r
  87 CVisibleGraphNode::CFoldedTag* CVisibleGraphNode::CFactory::Create \r
  88     ( const CFullGraphNode* tagNode\r
  89     , size_t depth\r
  90     , CFoldedTag* next)\r
  91 {\r
  92     CFoldedTag * result = static_cast<CFoldedTag *>(tagPool.malloc());\r
  93     new (result) CFoldedTag (tagNode, depth, next);\r
  94     return result;\r
  95 }\r
  96 \r
  97 void CVisibleGraphNode::CFactory::Destroy (CFoldedTag* tag)\r
  98 {\r
  99     tag->~CFoldedTag();\r
 100     tagPool.free (tag);\r
 101 }\r
 102 \r
 103 // CVisibleGraphNode construction / destruction \r
 104 \r
 105 CVisibleGraphNode::CVisibleGraphNode \r
 106     ( const CFullGraphNode* base\r
 107     , CVisibleGraphNode* prev\r
 108     , CCopyTarget::factory& copyTargetFactory\r
 109     , bool preserveNode)\r
 110         : base (base)\r
 111         , firstCopyTarget (NULL), firstTag (NULL)\r
 112         , prev (NULL), next (NULL), copySource (NULL)\r
 113     , classification (  preserveNode \r
 114                       ? base->GetClassification().GetFlags()\r
 115                       : (   base->GetClassification().GetFlags() \r
 116                           | CNodeClassification::MUST_BE_PRESERVED))\r
 117         , index ((index_t)NO_INDEX) \r
 118 {\r
 119     if (prev != NULL)\r
 120         if (classification.Is (CNodeClassification::IS_COPY_TARGET))\r
 121         {\r
 122             copySource = prev;\r
 123             copyTargetFactory.insert (this, prev->firstCopyTarget);\r
 124         }\r
 125         else\r
 126         {\r
 127             assert (prev->next == NULL);\r
 128 \r
 129             prev->next = this;\r
 130             this->prev = prev;\r
 131         }\r
 132 }\r
 133 \r
 134 CVisibleGraphNode::~CVisibleGraphNode() \r
 135 {\r
 136     assert (next == NULL);\r
 137     assert (firstCopyTarget == NULL);\r
 138     assert (firstTag == NULL);\r
 139 };\r
 140 \r
 141 // destruction utilities\r
 142 \r
 143 void CVisibleGraphNode::DestroySubNodes \r
 144     ( CFactory& factory\r
 145     , CCopyTarget::factory& copyTargetFactory)\r
 146 {\r
 147     while (next != NULL)\r
 148     {\r
 149         CVisibleGraphNode* toDestroy = next; \r
 150         next = toDestroy->next;\r
 151         toDestroy->next = NULL;\r
 152 \r
 153         factory.Destroy (toDestroy);\r
 154     }\r
 155 \r
 156     while (firstCopyTarget)\r
 157     {\r
 158         CVisibleGraphNode* target = copyTargetFactory.remove (firstCopyTarget);\r
 159         if (target != NULL)\r
 160             factory.Destroy (target);\r
 161     }\r
 162 }\r
 163 \r
 164 void CVisibleGraphNode::DestroyTags (CFactory& factory)\r
 165 {\r
 166     while (firstTag != NULL)\r
 167     {\r
 168         CFoldedTag* toDestroy = firstTag; \r
 169         firstTag = toDestroy->next;\r
 170         factory.Destroy (toDestroy);\r
 171     }\r
 172 }\r
 173 \r
 174 // set index members within the whole sub-tree\r
 175 \r
 176 index_t CVisibleGraphNode::InitIndex (index_t startIndex)\r
 177 {\r
 178     for (CVisibleGraphNode* node = this; node != NULL; node = node->next)\r
 179     {\r
 180         node->index = startIndex;\r
 181         ++startIndex;\r
 182 \r
 183         for ( CCopyTarget* target = node->firstCopyTarget\r
 184             ; target != NULL\r
 185             ; target = target->next())\r
 186         {\r
 187             startIndex = target->value()->InitIndex (startIndex);\r
 188         }\r
 189     }\r
 190 \r
 191     return startIndex;\r
 192 }\r
 193 \r
 194 // remove node and move links to pre-decessor\r
 195 \r
 196 void CVisibleGraphNode::DropNode (CVisibleGraph* graph)\r
 197 {\r
 198     // previous node to receive all our links\r
 199 \r
 200     CVisibleGraphNode* target = copySource == NULL\r
 201                               ? prev\r
 202                               : copySource;\r
 203 \r
 204     // special case: remove one of the roots\r
 205 \r
 206     if (target == NULL)\r
 207     {\r
 208         // handle this branch\r
 209 \r
 210         if (next)\r
 211         {\r
 212             next->prev = NULL;\r
 213             graph->ReplaceRoot (this, next);\r
 214         }\r
 215         else\r
 216         {\r
 217             graph->RemoveRoot (this);\r
 218         }\r
 219 \r
 220         // add sub-branches as new roots\r
 221 \r
 222         for (; firstCopyTarget != NULL; firstCopyTarget = firstCopyTarget->next())\r
 223         {\r
 224             firstCopyTarget->value()->copySource = NULL;\r
 225             graph->AddRoot (firstCopyTarget->value());\r
 226         }\r
 227 \r
 228         // no tag-folding supported here\r
 229 \r
 230         assert (firstTag == NULL);\r
 231     }\r
 232     else\r
 233     {\r
 234         // move all branches\r
 235 \r
 236         if (firstCopyTarget != NULL)\r
 237         {\r
 238             // find insertion point\r
 239 \r
 240             CCopyTarget** targetFirstCopyTarget = &target->firstCopyTarget;\r
 241             while (*targetFirstCopyTarget != NULL)\r
 242                 targetFirstCopyTarget = &(*targetFirstCopyTarget)->next();\r
 243 \r
 244             // concatenate list\r
 245 \r
 246             *targetFirstCopyTarget = firstCopyTarget;\r
 247 \r
 248             // adjust copy sources and reset firstCopyTarget\r
 249 \r
 250             for (; firstCopyTarget != NULL; firstCopyTarget = firstCopyTarget->next())\r
 251                 firstCopyTarget->value()->copySource = target;\r
 252         }\r
 253 \r
 254         // move all tags\r
 255 \r
 256         if (firstTag != NULL)\r
 257         {\r
 258             // find insertion point\r
 259 \r
 260             CFoldedTag** targetFirstTag = &target->firstTag;\r
 261             while (*targetFirstTag != NULL)\r
 262                 targetFirstTag = &(*targetFirstTag)->next;\r
 263 \r
 264             // concatenate list and reset firstTag\r
 265 \r
 266             *targetFirstTag = firstTag;\r
 267             firstTag = NULL;\r
 268         }\r
 269 \r
 270         // de-link this node\r
 271 \r
 272         if (prev != NULL)\r
 273         {\r
 274             prev->next = next;\r
 275             if (next)\r
 276                 next->prev = prev;\r
 277         }\r
 278         else\r
 279         {\r
 280             // find the copy struct that links to *this\r
 281 \r
 282             CCopyTarget** copy = &target->firstCopyTarget;\r
 283             for (\r
 284                 ; (*copy != NULL) && ((*copy)->value() != this)\r
 285                 ; copy = &(*copy)->next())\r
 286             {\r
 287             }\r
 288 \r
 289             assert (*copy != NULL);\r
 290 \r
 291             // make it point to next or remove it\r
 292 \r
 293             if (next)\r
 294             {\r
 295                 (*copy)->value() = next;\r
 296                 next->prev = NULL;\r
 297                 next->copySource = target;\r
 298             }\r
 299             else\r
 300             {\r
 301                 // remove from original list and attach it to *this for destruction\r
 302 \r
 303                 firstCopyTarget = *copy;\r
 304                 *copy = (*copy)->next();\r
 305 \r
 306                 firstCopyTarget->next() = NULL;\r
 307                 firstCopyTarget->value() = NULL;\r
 308             }\r
 309         }\r
 310     }\r
 311 \r
 312     // destruct this\r
 313 \r
 314     next = NULL;\r
 315     graph->GetFactory().Destroy (this);\r
 316 }\r
 317 \r
 318 // remove node and add it as folded tag to the parent\r
 319 \r
 320 void CVisibleGraphNode::FoldTag (CVisibleGraph* graph)\r
 321 {\r
 322     assert ((copySource || classification.Is (CNodeClassification::IS_RENAMED))\r
 323             && "This operation is only valid for copy nodes!");\r
 324 \r
 325     // fold the whole branch into this node.\r
 326     // Handle renames as sub-tags\r
 327 \r
 328     CVisibleGraphNode* node = this;\r
 329     while (node->next)\r
 330         node = node->next;\r
 331 \r
 332     while (node != this)\r
 333     {\r
 334         CVisibleGraphNode* previous = node->prev;\r
 335         if (node->classification.Is (CNodeClassification::IS_RENAMED))\r
 336             node->FoldTag (graph);\r
 337         else\r
 338             node->DropNode (graph);\r
 339 \r
 340         node = previous;\r
 341     }\r
 342 \r
 343     // fold all sub-branches as tags into this node\r
 344 \r
 345     while (firstCopyTarget != NULL)\r
 346         firstCopyTarget->value()->FoldTag (graph);\r
 347 \r
 348     // move tags to parent\r
 349 \r
 350     CVisibleGraphNode* source = copySource == NULL ? prev : copySource;\r
 351     if (firstTag != NULL)\r
 352     {\r
 353         CFoldedTag* lastTag = NULL;\r
 354         for (CFoldedTag* tag = firstTag; tag != NULL; tag = tag->next)\r
 355         {\r
 356             tag->depth++;\r
 357             lastTag = tag;\r
 358         }\r
 359 \r
 360         lastTag->next = source->firstTag;\r
 361         source->firstTag = firstTag;\r
 362         firstTag = NULL;\r
 363     }\r
 364 \r
 365     // create a tag for this node\r
 366 \r
 367     CFoldedTag* newTag \r
 368         = graph->GetFactory().Create (base, 0, source->firstTag);\r
 369     source->firstTag = newTag;\r
 370 \r
 371     // remove this node\r
 372 \r
 373     DropNode (graph);\r
 374 }\r