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 : :
|
