LCOV - code coverage report
Current view: top level - source/trotLib - trotListSecondary.c (source / functions) Hit Total Coverage
Test: trot.info Lines: 299 299 100.0 %
Date: 2014-03-07 Functions: 6 6 100.0 %
Branches: 174 174 100.0 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            : Copyright (c) 2010-2014 Jeremiah Martell
       3                 :            : All rights reserved.
       4                 :            : 
       5                 :            : Redistribution and use in source and binary forms, with or without modification,
       6                 :            : are permitted provided that the following conditions are met:
       7                 :            : 
       8                 :            :     - Redistributions of source code must retain the above copyright notice,
       9                 :            :       this list of conditions and the following disclaimer.
      10                 :            :     - Redistributions in binary form must reproduce the above copyright notice,
      11                 :            :       this list of conditions and the following disclaimer in the documentation
      12                 :            :       and/or other materials provided with the distribution.
      13                 :            :     - Neither the name of Jeremiah Martell nor the name of GeekHorse nor the
      14                 :            :       name of Trot nor the names of its contributors may be used to endorse or
      15                 :            :       promote products derived from this software without specific prior written
      16                 :            :       permission.
      17                 :            : 
      18                 :            : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
      19                 :            : ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
      20                 :            : WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
      21                 :            : DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
      22                 :            : ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
      23                 :            : (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
      24                 :            : LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
      25                 :            : ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
      26                 :            : (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
      27                 :            : SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      28                 :            : */
      29                 :            : 
      30                 :            : /******************************************************************************/
      31                 :            : /*!
      32                 :            :         \file
      33                 :            :         Implements the secondary functionality for our lists.
      34                 :            : 
      35                 :            :         Secondary functionality includes:
      36                 :            :         - Deep list compare by value
      37                 :            :         - List copy (1 level deep only)
      38                 :            :         - Enlist
      39                 :            :         - Delist
      40                 :            :         - Copy Span
      41                 :            :         - Remove Span
      42                 :            : */
      43                 :            : #define TROT_FILE_NUMBER 2
      44                 :            : 
      45                 :            : /******************************************************************************/
      46                 :            : #include "trot.h"
      47                 :            : #include "trotInternal.h"
      48                 :            : 
      49                 :            : /******************************************************************************/
      50                 :            : /*!
      51                 :            :         \brief Does a full-depth compare of 2 lists by value. Does not compare tags.
      52                 :            :         \param[in] l The first list.
      53                 :            :         \param[in] lCompareTo The second list.
      54                 :            :         \param[out] compareResult Result of the comparison.
      55                 :            :         \return TROT_RC
      56                 :            : 
      57                 :            :         FUTURE: it doesnt compare references, just structure and values, which is ok,
      58                 :            :         just need to document it. if you want a "real" compare, you must encode
      59                 :            :         both lists, then compare the outputs.
      60                 :            :         maybe we just need a "string compare" that will only compare 1 level deep
      61                 :            :         and then a true compare that uses encoding. ... same with copy?
      62                 :            : 
      63                 :            :         FUTURE: need to remove this, and just implement it in Trot itself
      64                 :            :         that way, it will be easier, plus, people can modify it to suit their
      65                 :            :         needs. What if they want tags to match, but not usertags, etc.
      66                 :            : 
      67                 :            :         FUTURE: a true compare can be done by using encode, and comparing the
      68                 :            :         resulting character lists.
      69                 :            : */
      70                 :     128661 : TROT_RC trotListCompare( TrotList *l, TrotList *lCompareTo, TROT_LIST_COMPARE_RESULT *compareResult )
      71                 :            : {
      72                 :            :         /* DATA */
      73                 :     128661 :         TROT_RC rc = TROT_RC_SUCCESS;
      74                 :            : 
      75                 :     128661 :         TrotStack *stack = NULL;
      76                 :     128661 :         TrotStackNode *stackNode = NULL;
      77                 :     128661 :         TROT_INT stackEmpty = 0;
      78                 :            : 
      79                 :     128661 :         TrotListActual *la1 = NULL;
      80                 :     128661 :         TROT_INT count1 = 0;
      81                 :     128661 :         TROT_INT n1 = 0;
      82                 :     128661 :         TROT_INT kind1 = NODE_KIND_HEAD_OR_TAIL;
      83                 :     128661 :         TrotListActual *subLa1 = NULL;
      84                 :            : 
      85                 :     128661 :         TrotListActual *la2 = NULL;
      86                 :     128661 :         TROT_INT count2 = 0;
      87                 :     128661 :         TROT_INT n2 = 0;
      88                 :     128661 :         TROT_INT kind2 = NODE_KIND_HEAD_OR_TAIL;
      89                 :     128661 :         TrotListActual *subLa2 = NULL;
      90                 :            : 
      91                 :     128661 :         TROT_INT index = 0;
      92                 :            : 
      93                 :            : 
      94                 :            :         /* PRECOND */
      95         [ +  + ]:     128661 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
      96         [ +  + ]:     128660 :         ERR_IF( lCompareTo == NULL, TROT_RC_ERROR_PRECOND );
      97         [ +  + ]:     128659 :         ERR_IF( compareResult == NULL, TROT_RC_ERROR_PRECOND );
      98                 :            : 
      99                 :            : 
     100                 :            :         /* CODE */
     101                 :            :         /* we assume equal, and set this otherwise later */
     102                 :     128658 :         (*compareResult) = TROT_LIST_COMPARE_EQUAL;
     103                 :            : 
     104                 :            :         /* no need to test if they point to same list */
     105         [ +  + ]:     128658 :         if ( l->laPointsTo == lCompareTo->laPointsTo )
     106                 :            :         {
     107                 :        828 :                 return TROT_RC_SUCCESS;
     108                 :            :         }
     109                 :            : 
     110                 :            :         /* init stack */
     111                 :     127830 :         rc = trotStackInit( &stack );
     112         [ +  + ]:     127830 :         ERR_IF_PASSTHROUGH;
     113                 :            : 
     114                 :     127824 :         rc = trotStackPush( stack, l->laPointsTo, lCompareTo->laPointsTo );
     115         [ +  + ]:     127824 :         ERR_IF_PASSTHROUGH;
     116                 :            : 
     117                 :            :         /* compare loop */
     118                 :            :         while ( 1 )
     119                 :            :         {
     120                 :            :                 /* increment top of stack */
     121                 :    5629570 :                 rc = trotStackIncrementTopIndex( stack );
     122                 :            :                 PARANOID_ERR_IF( rc != TROT_RC_SUCCESS );
     123                 :            : 
     124                 :            :                 /* get both stack info */
     125                 :    5629570 :                 stackNode = stack->tail->prev;
     126                 :    5629570 :                 index = stackNode->index;
     127                 :    5629570 :                 la1 = stackNode->la1;
     128                 :    5629570 :                 la2 = stackNode->la2;
     129                 :            : 
     130                 :            :                 /* make sure we're in index */
     131                 :    5629570 :                 count1 = la1->childrenCount;
     132                 :    5629570 :                 count2 = la2->childrenCount;
     133                 :            : 
     134                 :            :                 /* if both are too big */
     135 [ +  + ][ +  + ]:    5629570 :                 if ( index > count1 && index > count2 )
     136                 :            :                 {
     137                 :    1456773 :                         rc = trotStackPop( stack, &stackEmpty );
     138                 :            :                         PARANOID_ERR_IF( rc != TROT_RC_SUCCESS );
     139                 :            : 
     140         [ +  + ]:    1456773 :                         if ( stackEmpty )
     141                 :            :                         {
     142                 :      90519 :                                 break;
     143                 :            :                         }
     144                 :            : 
     145                 :    1366254 :                         continue;
     146                 :            :                 }
     147                 :            : 
     148                 :            :                 /* if index is too big for list 1 */
     149         [ +  + ]:    4172797 :                 if ( index > count1 )
     150                 :            :                 {
     151                 :        756 :                         (*compareResult) = TROT_LIST_COMPARE_LESS_THAN;
     152                 :        756 :                         break;
     153                 :            :                 }
     154                 :            : 
     155                 :            :                 /* if index is too big for list 2 */
     156         [ +  + ]:    4172041 :                 if ( index > count2 )
     157                 :            :                 {
     158                 :       1253 :                         (*compareResult) = TROT_LIST_COMPARE_GREATER_THAN;
     159                 :       1253 :                         break;
     160                 :            :                 }
     161                 :            : 
     162                 :            :                 /* get kinds */
     163                 :    4170788 :                 kind1 = stackNode->la1Node->kind;
     164                 :    4170788 :                 kind2 = stackNode->la2Node->kind;
     165                 :            : 
     166                 :            :                 /* compare kinds */
     167                 :            :                 /* ints are considered smaller than lists */
     168 [ +  + ][ +  + ]:    4170788 :                 if ( kind1 == NODE_KIND_INT && kind2 == NODE_KIND_LIST )
     169                 :            :                 {
     170                 :      12055 :                         (*compareResult) = TROT_LIST_COMPARE_LESS_THAN;
     171                 :      12055 :                         break;
     172                 :            :                 }
     173 [ +  + ][ +  + ]:    4158733 :                 if ( kind1 == NODE_KIND_LIST && kind2 == NODE_KIND_INT )
     174                 :            :                 {
     175                 :      12055 :                         (*compareResult) = TROT_LIST_COMPARE_GREATER_THAN;
     176                 :      12055 :                         break;
     177                 :            :                 }
     178                 :            : 
     179                 :            :                 /* get and compare ints */
     180         [ +  + ]:    4146678 :                 if ( kind1 == NODE_KIND_INT )
     181                 :            :                 {
     182                 :            :                         PARANOID_ERR_IF( kind2 != NODE_KIND_INT );
     183                 :            : 
     184                 :    2755220 :                         n1 = stackNode->la1Node->n[ stackNode->la1Count ];
     185                 :    2755220 :                         n2 = stackNode->la2Node->n[ stackNode->la2Count ];
     186                 :            : 
     187         [ +  + ]:    2755220 :                         if ( n1 < n2 )
     188                 :            :                         {
     189                 :       5724 :                                 (*compareResult) = TROT_LIST_COMPARE_LESS_THAN;
     190                 :       5724 :                                 break;
     191                 :            :                         }
     192         [ +  + ]:    2749496 :                         else if ( n1 > n2 )
     193                 :            :                         {
     194                 :       5459 :                                 (*compareResult) = TROT_LIST_COMPARE_GREATER_THAN;
     195                 :       5459 :                                 break;
     196                 :            :                         }
     197                 :            : 
     198                 :    2744037 :                         continue;
     199                 :            :                 }
     200                 :            : 
     201                 :            :                 PARANOID_ERR_IF( kind1 != NODE_KIND_LIST );
     202                 :            :                 PARANOID_ERR_IF( kind2 != NODE_KIND_LIST );
     203                 :            : 
     204                 :            :                 /* get lists */
     205                 :    1391458 :                 subLa1 = stackNode->la1Node->l[ stackNode->la1Count ]->laPointsTo;
     206                 :    1391458 :                 subLa2 = stackNode->la2Node->l[ stackNode->la2Count ]->laPointsTo;
     207                 :            : 
     208                 :            :                 /* only add if different.
     209                 :            :                    if they point to same, there's no need to compare */
     210         [ +  + ]:    1391458 :                 if ( subLa1 != subLa2 )
     211                 :            :                 {
     212                 :    1381756 :                         rc = trotStackPush( stack, subLa1, subLa2 );
     213         [ +  + ]:    1381756 :                         ERR_IF_PASSTHROUGH;
     214                 :            :                 }
     215                 :    5501748 :         }
     216                 :            : 
     217                 :            : 
     218                 :            :         /* CLEANUP */
     219                 :            :         cleanup:
     220                 :            : 
     221                 :     127833 :         trotStackFree( &stack );
     222                 :            : 
     223                 :     128661 :         return rc;
     224                 :            : }
     225                 :            : 
     226                 :            : /******************************************************************************/
     227                 :            : /*!
     228                 :            :         \brief Copies a list.
     229                 :            :         \param[in] l The list.
     230                 :            :         \param[out] lCopy_A New copied list.
     231                 :            :         \return TROT_RC
     232                 :            : 
     233                 :            :         This only copies the 1st level, it does not recurse. If you want a "deep"
     234                 :            :         copy, then encode then decode a list.
     235                 :            : 
     236                 :            :         Tags are copied.
     237                 :            : */
     238                 :       1342 : TROT_RC trotListCopy( TrotList *l, TrotList **lCopy_A )
     239                 :            : {
     240                 :            :         /* DATA */
     241                 :       1342 :         TROT_RC rc = TROT_RC_SUCCESS;
     242                 :            : 
     243                 :            : 
     244                 :            :         /* PRECOND */
     245         [ +  + ]:       1342 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
     246         [ +  + ]:       1341 :         ERR_IF( lCopy_A == NULL, TROT_RC_ERROR_PRECOND );
     247         [ +  + ]:       1340 :         ERR_IF( (*lCopy_A) != NULL, TROT_RC_ERROR_PRECOND );
     248                 :            : 
     249                 :            : 
     250                 :            :         /* CODE */
     251                 :            :         /* if list is empty, just give back a new list */
     252         [ +  + ]:       1339 :         if ( l->laPointsTo->childrenCount == 0 )
     253                 :            :         {
     254                 :        428 :                 rc = trotListInit( lCopy_A );
     255         [ +  + ]:        428 :                 ERR_IF_PASSTHROUGH;
     256                 :            : 
     257                 :            :                 /* make sure copied list has same tags */
     258                 :        420 :                 (*lCopy_A)->laPointsTo->tag     = l->laPointsTo->tag;
     259                 :        420 :                 (*lCopy_A)->laPointsTo->userTag = l->laPointsTo->userTag;
     260                 :            :         }
     261                 :            :         /* else, use CopySpan */
     262                 :            :         else
     263                 :            :         {
     264                 :        911 :                 rc = trotListCopySpan( l, 1, -1, lCopy_A );
     265         [ +  + ]:        911 :                 ERR_IF_PASSTHROUGH;
     266                 :            : 
     267                 :            :                 /* copy span copys the tags too */
     268                 :            :         }
     269                 :            : 
     270                 :            : 
     271                 :            :         /* CLEANUP */
     272                 :            :         cleanup:
     273                 :            : 
     274                 :       1342 :         return rc;
     275                 :            : }
     276                 :            : 
     277                 :            : /******************************************************************************/
     278                 :            : /*!
     279                 :            :         \brief Takes a span of children and puts them into a list.
     280                 :            :         \param[in] l The list.
     281                 :            :         \param[in] indexStart Start index of items you want to enlist.
     282                 :            :         \param[in] indexEnd End index of items you want to enlist.
     283                 :            :         \return TROT_RC
     284                 :            : 
     285                 :            :         Example:
     286                 :            :         If list is [ 1 2 3 4 5 ], indexStart is 3, and indexEnd is 5 then list will
     287                 :            :         become:
     288                 :            :         [ 1 2 [ 3 4 5 ] ]
     289                 :            : */
     290                 :      16838 : TROT_RC trotListEnlist( TrotList *l, TROT_INT indexStart, TROT_INT indexEnd )
     291                 :            : {
     292                 :            :         /* DATA */
     293                 :      16838 :         TROT_RC rc = TROT_RC_SUCCESS;
     294                 :            : 
     295                 :      16838 :         TrotListActual *la = NULL;
     296                 :      16838 :         TROT_INT tempI = 0;
     297                 :            : 
     298                 :      16838 :         TrotListNode *node = NULL;
     299                 :            : 
     300                 :      16838 :         TROT_INT count = 0;
     301                 :            : 
     302                 :      16838 :         TrotListNode *startNode = NULL;
     303                 :            : 
     304                 :      16838 :         TrotList *newL = NULL;
     305                 :      16838 :         TrotListActual *newLa = NULL;
     306                 :            : 
     307                 :      16838 :         TrotListNode *newNode = NULL;
     308                 :            : 
     309                 :      16838 :         TROT_INT i = 0;
     310                 :            : 
     311                 :            : 
     312                 :            :         /* PRECOND */
     313         [ +  + ]:      16838 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
     314                 :            : 
     315                 :            : 
     316                 :            :         /* CODE */
     317                 :      16837 :         la = l->laPointsTo;
     318                 :            : 
     319                 :            :         /* Turn negative indices into positive equivalents. */
     320         [ +  + ]:      16837 :         if ( indexStart < 0 )
     321                 :            :         {
     322                 :       4030 :                 indexStart = (la->childrenCount) + indexStart + 1;
     323                 :            :         }
     324         [ +  + ]:      16837 :         if ( indexEnd < 0 )
     325                 :            :         {
     326                 :       4492 :                 indexEnd = (la->childrenCount) + indexEnd + 1;
     327                 :            :         }
     328                 :            : 
     329                 :            :         /* Make sure indices are in range */
     330         [ +  + ]:      16837 :         ERR_IF_1( indexStart <= 0, TROT_RC_ERROR_BAD_INDEX, indexStart );
     331         [ +  + ]:      16833 :         ERR_IF_1( indexStart > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, indexStart );
     332                 :            : 
     333         [ +  + ]:      16831 :         ERR_IF_1( indexEnd <= 0, TROT_RC_ERROR_BAD_INDEX, indexEnd );
     334         [ +  + ]:      16827 :         ERR_IF_1( indexEnd > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, indexEnd );
     335                 :            : 
     336                 :            :         /* swap indices if end is before start */
     337         [ +  + ]:      16825 :         if ( indexEnd < indexStart )
     338                 :            :         {
     339                 :       7812 :                 tempI = indexStart;
     340                 :       7812 :                 indexStart = indexEnd;
     341                 :       7812 :                 indexEnd = tempI;
     342                 :            :         }
     343                 :            : 
     344                 :            :         /* find start */
     345                 :      16825 :         node = la->head->next;
     346                 :            :         while ( 1 )
     347                 :            :         {
     348         [ +  + ]:      66457 :                 if ( count + (node->count) >= indexStart )
     349                 :            :                 {
     350                 :      16825 :                         break;
     351                 :            :                 }
     352                 :            : 
     353                 :      49632 :                 count += node->count;
     354                 :      49632 :                 node = node->next;
     355                 :            : 
     356                 :            :                 PARANOID_ERR_IF( node == la->tail );
     357                 :      49632 :         }
     358                 :            : 
     359                 :            :         /* split this node if necessary */
     360         [ +  + ]:      16825 :         if ( count + 1 != indexStart )
     361                 :            :         {
     362                 :      10053 :                 rc = trotListNodeSplit( node, indexStart - count - 1 );
     363         [ +  + ]:      10053 :                 ERR_IF_PASSTHROUGH;
     364                 :            : 
     365                 :      10051 :                 count += node->count;
     366                 :      10051 :                 node = node->next;
     367                 :            :         }
     368                 :            : 
     369                 :            :         /* mark startNode */
     370                 :      16823 :         startNode = node;
     371                 :            : 
     372                 :            :         /* find end */
     373                 :            :         while ( 1 )
     374                 :            :         {
     375         [ +  + ]:      75434 :                 if ( count + (node->count) >= indexEnd )
     376                 :            :                 {
     377                 :      16823 :                         break;
     378                 :            :                 }
     379                 :            : 
     380                 :      58611 :                 count += node->count;
     381                 :      58611 :                 node = node->next;
     382                 :            : 
     383                 :            :                 PARANOID_ERR_IF( node == la->tail );
     384                 :      58611 :         }
     385                 :            : 
     386                 :            :         /* split this node if necessary */
     387         [ +  + ]:      16823 :         if ( count + node->count != indexEnd )
     388                 :            :         {
     389                 :      10051 :                 rc = trotListNodeSplit( node, indexEnd - count );
     390         [ +  + ]:      10051 :                 ERR_IF_PASSTHROUGH;
     391                 :            :         }
     392                 :            : 
     393                 :            :         /* create our new node */
     394                 :      16821 :         rc = newListNode( &newNode );
     395         [ +  + ]:      16821 :         ERR_IF_PASSTHROUGH;
     396                 :            : 
     397                 :            :         /* create our new list */
     398                 :      16819 :         rc = trotListInit( &newL );
     399         [ +  + ]:      16819 :         ERR_IF_PASSTHROUGH;
     400                 :            : 
     401                 :            :         /* insert our new list into our node */
     402                 :      16811 :         newNode->l[ 0 ] = newL;
     403                 :      16811 :         newNode->count = 1;
     404                 :      16811 :         newL->laParent = la;
     405                 :            : 
     406                 :            :         /* get our new list */
     407                 :      16811 :         newLa = newL->laPointsTo;
     408                 :            : 
     409                 :            :         /* insert our new node into list */
     410                 :      16811 :         newNode->prev = startNode->prev;
     411                 :      16811 :         newNode->next = startNode;
     412                 :            : 
     413                 :      16811 :         startNode->prev->next = newNode;
     414                 :      16811 :         startNode->prev = newNode;
     415                 :            : 
     416                 :      16811 :         newNode = NULL;
     417                 :            : 
     418                 :            :         /* remove nodes from old list */
     419                 :      16811 :         startNode->prev->next = node->next;
     420                 :      16811 :         node->next->prev = startNode->prev;
     421                 :            : 
     422                 :            :         /* insert nodes into new list */
     423                 :      16811 :         newLa->head->next = startNode;
     424                 :      16811 :         startNode->prev = newLa->head;
     425                 :            : 
     426                 :      16811 :         newLa->tail->prev = node;
     427                 :      16811 :         node->next = newLa->tail;
     428                 :            : 
     429                 :            : 
     430                 :            :         /* adjust counts in both lists */
     431                 :      16811 :         count = 0;
     432                 :      16811 :         node = newLa->head->next;
     433         [ +  + ]:      92125 :         while ( node != newLa->tail )
     434                 :            :         {
     435                 :      75314 :                 count += node->count;
     436                 :      75314 :                 node = node->next;
     437                 :            :         }
     438                 :            : 
     439                 :            :         /* we subtract one from count because we're adding
     440                 :            :            the new "enlist" list too */
     441                 :      16811 :         la->childrenCount -= (count - 1); 
     442                 :      16811 :         newLa->childrenCount = count;
     443                 :            : 
     444                 :            :         /* adjust references in newList */
     445                 :      16811 :         node = newLa->head->next;
     446         [ +  + ]:      92125 :         while ( node != newLa->tail )
     447                 :            :         {
     448         [ +  + ]:      75314 :                 if ( node->kind == NODE_KIND_LIST )
     449                 :            :                 {
     450                 :      37657 :                         i = 0;
     451         [ +  + ]:     129670 :                         while ( i < node->count )
     452                 :            :                         {
     453                 :      92013 :                                 node->l[ i ]->laParent = newLa;
     454                 :            : 
     455                 :      92013 :                                 i += 1;
     456                 :            :                         }
     457                 :            :                 }
     458                 :            : 
     459                 :      75314 :                 node = node->next;
     460                 :            :         }
     461                 :            : 
     462                 :            : 
     463                 :            :         /* CLEANUP */
     464                 :            :         cleanup:
     465                 :            : 
     466         [ +  + ]:      16838 :         if ( newNode != NULL )
     467                 :            :         {
     468                 :          8 :                 trotHookFree( newNode->l );
     469                 :          8 :                 trotHookFree( newNode );
     470                 :            :         }
     471                 :            : 
     472                 :      16838 :         return rc;
     473                 :            : }
     474                 :            : 
     475                 :            : /******************************************************************************/
     476                 :            : /*!
     477                 :            :         \brief Removes a list and puts it's children in it's place.
     478                 :            :         \param[in] l The list.
     479                 :            :         \param[in] index Index of list you want to delist.
     480                 :            :         \return TROT_RC
     481                 :            : 
     482                 :            :         Example:
     483                 :            :         If list is [ 1 2 [ 3 4 5 ] ] and index is 3 then list will become:
     484                 :            :         [ 1 2 3 4 5 ]
     485                 :            : */
     486                 :      25338 : TROT_RC trotListDelist( TrotList *l, TROT_INT index )
     487                 :            : {
     488                 :            :         /* DATA */
     489                 :      25338 :         TROT_RC rc = TROT_RC_SUCCESS;
     490                 :            : 
     491                 :      25338 :         TrotListActual *la = NULL;
     492                 :            : 
     493                 :      25338 :         TROT_INT count = 0;
     494                 :            : 
     495                 :      25338 :         TrotListNode *node = NULL;
     496                 :      25338 :         TrotListNode *insertBeforeThisNode = NULL;
     497                 :            : 
     498                 :      25338 :         TrotList *delistL = NULL;
     499                 :      25338 :         TrotList *copiedL = NULL;
     500                 :            : 
     501                 :      25338 :         TROT_INT i = 0;
     502                 :            : 
     503                 :            : 
     504                 :            :         /* PRECOND */
     505         [ +  + ]:      25338 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
     506                 :            : 
     507                 :            : 
     508                 :            :         /* CODE */
     509                 :      25337 :         la = l->laPointsTo;
     510                 :            : 
     511                 :            :         /* Turn negative index into positive equivalent. */
     512         [ +  + ]:      25337 :         if ( index < 0 )
     513                 :            :         {
     514                 :       8377 :                 index = (la->childrenCount) + index + 1;
     515                 :            :         }
     516                 :            : 
     517                 :            :         /* Make sure index is in range */
     518         [ +  + ]:      25337 :         ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
     519         [ +  + ]:      25335 :         ERR_IF_1( index > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, index );
     520                 :            : 
     521                 :            :         /* find index */
     522                 :      25334 :         node = la->head->next;
     523                 :            :         while ( 1 )
     524                 :            :         {
     525         [ +  + ]:      86085 :                 if ( count + (node->count) >= index )
     526                 :            :                 {
     527                 :      25334 :                         break;
     528                 :            :                 }
     529                 :            : 
     530                 :      60751 :                 count += node->count;
     531                 :      60751 :                 node = node->next;
     532                 :            : 
     533                 :            :                 PARANOID_ERR_IF( node == la->tail );
     534                 :      60751 :         }
     535                 :            : 
     536                 :            :         /* check kind */
     537         [ +  + ]:      25334 :         ERR_IF_1( node->kind != NODE_KIND_LIST, TROT_RC_ERROR_WRONG_KIND, node->kind );
     538                 :            : 
     539                 :            :         /* split this node if necessary */
     540         [ +  + ]:      25333 :         if ( count + 1 != index )
     541                 :            :         {
     542                 :       1856 :                 rc = trotListNodeSplit( node, index - count - 1 );
     543         [ +  + ]:       1856 :                 ERR_IF_PASSTHROUGH;
     544                 :            : 
     545                 :       1854 :                 node = node->next;
     546                 :            :         }
     547                 :            : 
     548                 :            :         /* save our spot */
     549                 :      25331 :         insertBeforeThisNode = node;
     550                 :            : 
     551                 :            :         /* get our delist list */
     552                 :      25331 :         delistL = node->l[ 0 ];
     553                 :            : 
     554                 :            :         /* lists cannot hold more than TROT_MAX_CHILDREN, so make sure we have room */
     555                 :            :         /* plus 1 because when you delist, you're removing a list, and then adding the children */
     556         [ +  + ]:      25331 :         ERR_IF( TROT_MAX_CHILDREN - la->childrenCount + 1 < delistL->laPointsTo->childrenCount, TROT_RC_ERROR_LIST_OVERFLOW );
     557                 :            : 
     558                 :            :         /* copy our delist (only if it contains something) */
     559         [ +  + ]:      25330 :         if ( delistL->laPointsTo->childrenCount > 0 )
     560                 :            :         {
     561                 :      16812 :                 rc = trotListCopySpan( delistL, 1, -1, &copiedL );
     562         [ +  + ]:      16812 :                 ERR_IF_PASSTHROUGH;
     563                 :            :         }
     564                 :            : 
     565                 :            :         /* if this node contains more, the move the others over */
     566         [ +  + ]:      25279 :         if ( node->count > 1 )
     567                 :            :         {
     568                 :       8158 :                 delistL = node->l[ 0 ];
     569                 :            : 
     570                 :       8158 :                 i = 0;
     571         [ +  + ]:      45779 :                 while ( i < ( node->count - 1 ) )
     572                 :            :                 {
     573                 :      37621 :                         node->l[ i ] = node->l[ i + 1 ];
     574                 :            : 
     575                 :      37621 :                         i += 1;
     576                 :            :                 }
     577                 :       8158 :                 node->l[ i ] = NULL;
     578                 :       8158 :                 node->count -= 1;
     579                 :            :         }
     580                 :            :         /* else, remove node from list */
     581                 :            :         else
     582                 :            :         {
     583                 :      17121 :                 insertBeforeThisNode = insertBeforeThisNode->next;
     584                 :            : 
     585                 :      17121 :                 node->prev->next = node->next;
     586                 :      17121 :                 node->next->prev = node->prev;
     587                 :            : 
     588                 :      17121 :                 trotHookFree( node->l );
     589                 :      17121 :                 trotHookFree( node );
     590                 :            :         }
     591                 :            : 
     592                 :            :         /* adjust count */
     593                 :      25279 :         la->childrenCount -= 1;
     594                 :            : 
     595                 :            :         /* free our delistL */
     596                 :      25279 :         delistL->laParent = NULL;
     597                 :      25279 :         trotListFree( &delistL );
     598                 :            : 
     599                 :            :         /* was the delist empty? */
     600         [ +  + ]:      25279 :         if ( copiedL == NULL )
     601                 :            :         {
     602                 :       8518 :                 goto cleanup;
     603                 :            :         }
     604                 :            : 
     605                 :            :         /* adjust count */
     606                 :      16761 :         la->childrenCount += copiedL->laPointsTo->childrenCount;
     607                 :            : 
     608                 :            :         /* go ahead and adjust all ref's "parents" */
     609                 :      16761 :         node = copiedL->laPointsTo->head;
     610         [ +  + ]:     107367 :         while ( node != copiedL->laPointsTo->tail )
     611                 :            :         {
     612         [ +  + ]:      90606 :                 if ( node->kind == NODE_KIND_LIST )
     613                 :            :                 {
     614                 :      36922 :                         i = 0;
     615         [ +  + ]:     127864 :                         while ( i < node->count )
     616                 :            :                         {
     617                 :      90942 :                                 node->l[ i ]->laParent = la;
     618                 :            : 
     619                 :      90942 :                                 i += 1;
     620                 :            :                         }
     621                 :            :                 }
     622                 :            : 
     623                 :      90606 :                 node = node->next;
     624                 :            :         }
     625                 :            : 
     626                 :            :         /* move copied list contents into our list */
     627                 :      16761 :         copiedL->laPointsTo->head->next->prev = insertBeforeThisNode->prev;
     628                 :      16761 :         copiedL->laPointsTo->tail->prev->next = insertBeforeThisNode;
     629                 :            : 
     630                 :      16761 :         insertBeforeThisNode->prev->next = copiedL->laPointsTo->head->next;
     631                 :      16761 :         insertBeforeThisNode->prev = copiedL->laPointsTo->tail->prev;
     632                 :            : 
     633                 :      16761 :         copiedL->laPointsTo->childrenCount = 0;
     634                 :      16761 :         copiedL->laPointsTo->head->next = copiedL->laPointsTo->tail;
     635                 :      16761 :         copiedL->laPointsTo->tail->prev = copiedL->laPointsTo->head;
     636                 :            : 
     637                 :            :         /* free our copied list */
     638                 :      16761 :         trotListFree( &copiedL );
     639                 :            : 
     640                 :            : 
     641                 :            :         /* CLEANUP */
     642                 :            :         cleanup:
     643                 :            : 
     644                 :      25338 :         return rc;
     645                 :            : }
     646                 :            : 
     647                 :            : /******************************************************************************/
     648                 :            : /*!
     649                 :            :         \brief Makes a copy of a span in a list.
     650                 :            :         \param[in] l The list.
     651                 :            :         \param[in] indexStart Index of start of span.
     652                 :            :         \param[in] indexEnd Index of end of span.
     653                 :            :         \param[out] lCopy_A Copy of span.
     654                 :            :         \return TROT_RC
     655                 :            : 
     656                 :            :         l is not modified.
     657                 :            : 
     658                 :            :         Example:
     659                 :            :         If list is [ 1 2 3 4 5 ], indexStart is 3, and indexEnd is 5, then the new
     660                 :            :         list will contain:
     661                 :            :         [ 3 4 5 ]
     662                 :            : 
     663                 :            :         FUTURE: This could potentially be removed and reimplemented when the Trot
     664                 :            :         virtual machine is finished. Which would make it slower, but would make
     665                 :            :         the trot library smaller. Do we want to eliminate everything from the
     666                 :            :         library that can be implemented in Trot?
     667                 :            : */
     668                 :      26338 : TROT_RC trotListCopySpan( TrotList *l, TROT_INT indexStart, TROT_INT indexEnd, TrotList **lCopy_A )
     669                 :            : {
     670                 :            :         /* DATA */
     671                 :      26338 :         TROT_RC rc = TROT_RC_SUCCESS;
     672                 :            : 
     673                 :      26338 :         TrotListActual *la = NULL;
     674                 :            : 
     675                 :      26338 :         TROT_INT tempI = 0;
     676                 :            : 
     677                 :      26338 :         TrotList *newL = NULL;
     678                 :            : 
     679                 :      26338 :         TrotListNode *node = NULL;
     680                 :      26338 :         TrotListNode *tail = NULL;
     681                 :            : 
     682                 :      26338 :         TROT_INT count = 0;
     683                 :            : 
     684                 :      26338 :         TROT_INT i = 0;
     685                 :            : 
     686                 :            : 
     687                 :            :         /* PRECOND */
     688         [ +  + ]:      26338 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
     689         [ +  + ]:      26337 :         ERR_IF( lCopy_A == NULL, TROT_RC_ERROR_PRECOND );
     690         [ +  + ]:      26336 :         ERR_IF( (*lCopy_A) != NULL, TROT_RC_ERROR_PRECOND );
     691                 :            : 
     692                 :            : 
     693                 :            :         /* CODE */
     694                 :      26335 :         la = l->laPointsTo;
     695                 :            : 
     696                 :            :         /* Turn negative indices into positive equivalents. */
     697         [ +  + ]:      26335 :         if ( indexStart < 0 )
     698                 :            :         {
     699                 :       4067 :                 indexStart = (la->childrenCount) + indexStart + 1;
     700                 :            :         }
     701         [ +  + ]:      26335 :         if ( indexEnd < 0 )
     702                 :            :         {
     703                 :      22122 :                 indexEnd = (la->childrenCount) + indexEnd + 1;
     704                 :            :         }
     705                 :            : 
     706                 :            :         /* Make sure indices are in range */
     707         [ +  + ]:      26335 :         ERR_IF_1( indexStart <= 0, TROT_RC_ERROR_BAD_INDEX, indexStart );
     708         [ +  + ]:      26333 :         ERR_IF_1( indexStart > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, indexStart );
     709                 :            : 
     710         [ +  + ]:      26332 :         ERR_IF_1( indexEnd <= 0, TROT_RC_ERROR_BAD_INDEX, indexEnd );
     711         [ +  + ]:      26330 :         ERR_IF_1( indexEnd > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, indexEnd );
     712                 :            : 
     713                 :            :         /* swap indices if end is before start */
     714         [ +  + ]:      26329 :         if ( indexEnd < indexStart )
     715                 :            :         {
     716                 :       3924 :                 tempI = indexStart;
     717                 :       3924 :                 indexStart = indexEnd;
     718                 :       3924 :                 indexEnd = tempI;
     719                 :            :         }
     720                 :            : 
     721                 :            :         /* make our new list */
     722                 :      26329 :         rc = trotListInit( &newL );
     723         [ +  + ]:      26329 :         ERR_IF_PASSTHROUGH;
     724                 :            : 
     725                 :            :         /* *** */
     726                 :      26305 :         tail = la->tail;
     727                 :      26305 :         node = la->head->next;
     728                 :            : 
     729                 :            :         /* find node that contain indexStart */
     730                 :            :         while ( 1 )
     731                 :            :         {
     732                 :            :                 /* if we haven't reached the startIndex, continue */
     733         [ +  + ]:      51162 :                 if ( count + node->count >= indexStart )
     734                 :            :                 {
     735                 :      26305 :                         break;
     736                 :            :                 }
     737                 :            : 
     738                 :      24857 :                 count += node->count;
     739                 :      24857 :                 node = node->next;
     740                 :            : 
     741                 :            :                 PARANOID_ERR_IF( node == tail );
     742                 :      24857 :         }
     743                 :            : 
     744                 :            :         /* begin to copy */
     745                 :      26305 :         i = indexStart - count - 1;
     746 [ +  + ][ +  + ]:     148273 :         while ( node != tail && count < indexEnd )
     747                 :            :         {
     748                 :            :                 /* copy */
     749 [ +  + ][ +  + ]:     431325 :                 while ( i < node->count && ( i + count ) < indexEnd )
     750                 :            :                 {
     751         [ +  + ]:     309357 :                         if ( node->kind == NODE_KIND_INT )
     752                 :            :                         {
     753                 :     154164 :                                 rc = trotListAppendInt( newL, node->n[ i ] );
     754         [ +  + ]:     154164 :                                 ERR_IF_PASSTHROUGH;
     755                 :            :                         }
     756                 :            :                         else
     757                 :            :                         {
     758                 :     155193 :                                 rc = trotListAppendList( newL, node->l[ i ] );
     759         [ +  + ]:     155193 :                                 ERR_IF_PASSTHROUGH;
     760                 :            :                         }
     761                 :            : 
     762                 :     309228 :                         i += 1;
     763                 :            :                 }
     764                 :            : 
     765                 :     121968 :                 i = 0;
     766                 :     121968 :                 count += node->count;
     767                 :     121968 :                 node = node->next;
     768                 :            :         }
     769                 :            : 
     770                 :            :         /* make sure copied span has same tag */
     771                 :      26176 :         newL->laPointsTo->tag     = l->laPointsTo->tag;
     772                 :      26176 :         newL->laPointsTo->userTag = l->laPointsTo->userTag;
     773                 :            : 
     774                 :            : 
     775                 :            :         /* give back */
     776                 :      26176 :         (*lCopy_A) = newL;
     777                 :      26176 :         newL = NULL;
     778                 :            : 
     779                 :            : 
     780                 :            :         /* CLEANUP */
     781                 :            :         cleanup:
     782                 :            : 
     783                 :      26338 :         trotListFree( &newL );
     784                 :            : 
     785                 :      26338 :         return rc;
     786                 :            : }
     787                 :            : 
     788                 :            : /******************************************************************************/
     789                 :            : /*!
     790                 :            :         \brief Removes a span in a list.
     791                 :            :         \param[in] l The list.
     792                 :            :         \param[in] indexStart Index of start of span.
     793                 :            :         \param[in] indexEnd Index of end of span.
     794                 :            :         \return TROT_RC
     795                 :            : 
     796                 :            :         Example:
     797                 :            :         If list is [ 1 2 3 4 5 ], indexStart is 3, and indexEnd is 5, then list will
     798                 :            :         become:
     799                 :            :         [ 1 2 ]
     800                 :            : */
     801                 :       8197 : TROT_RC trotListRemoveSpan( TrotList *l, TROT_INT indexStart, TROT_INT indexEnd )
     802                 :            : {
     803                 :            :         /* DATA */
     804                 :       8197 :         TROT_RC rc = TROT_RC_SUCCESS;
     805                 :            : 
     806                 :       8197 :         TrotList *lRemoved = NULL;
     807                 :            : 
     808                 :            : 
     809                 :            :         /* PRECOND */
     810         [ +  + ]:       8197 :         ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
     811                 :            : 
     812                 :            : 
     813                 :            :         /* CODE */
     814                 :            :         /* Turn negative indices into positive equivalents. */
     815         [ +  + ]:       8196 :         if ( indexStart < 0 )
     816                 :            :         {
     817                 :       4067 :                 indexStart = (l->laPointsTo->childrenCount) + indexStart + 1;
     818                 :            :         }
     819         [ +  + ]:       8196 :         if ( indexEnd < 0 )
     820                 :            :         {
     821                 :       4019 :                 indexEnd = (l->laPointsTo->childrenCount) + indexEnd + 1;
     822                 :            :         }
     823                 :            : 
     824                 :            :         /* enlist */
     825                 :       8196 :         rc = trotListEnlist( l, indexStart, indexEnd );
     826         [ +  + ]:       8196 :         ERR_IF_PASSTHROUGH;
     827                 :            : 
     828                 :            :         /* remove list */
     829                 :       8190 :         rc = trotListRemoveList( l, indexStart < indexEnd ? indexStart : indexEnd, &lRemoved );
     830                 :            :         PARANOID_ERR_IF( rc != TROT_RC_SUCCESS );
     831                 :            : 
     832                 :            :         /* free removed list */
     833                 :       8190 :         trotListFree( &lRemoved );
     834                 :            : 
     835                 :            : 
     836                 :            :         /* CLEANUP */
     837                 :            :         cleanup:
     838                 :            : 
     839                 :       8197 :         return rc;
     840                 :            : }
     841                 :            : 

Generated by: LCOV version 1.9