src/TortoiseProc/RevisionGraph/VisibleGraphNode.cpp

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