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 primary funcitonality of our lists.
34 : :
35 : : Primary functionality includes:
36 : : - List Init
37 : : - List Twin (create another reference to a list, all lists are
38 : : manipulated by reference)
39 : : - List Free
40 : : - Get Count (how many children does the list have?)
41 : : - Get Kind (is child at index N an int or list?)
42 : : - Append Int
43 : : - Append List Twin
44 : : - Get Int
45 : : - Get List Twin
46 : : - Remove Int
47 : : - Remove List Twin
48 : : - Remove
49 : : */
50 : : #define TROT_FILE_NUMBER 1
51 : :
52 : : /******************************************************************************/
53 : : #include "trot.h"
54 : : #include "trotInternal.h"
55 : :
56 : : /******************************************************************************/
57 : : static TROT_RC refListAdd( TrotListActual *la, TrotList *l );
58 : : static void refListRemove( TrotListActual *la, TrotList *l );
59 : :
60 : : static void isListReachable( TrotListActual *la );
61 : : static TROT_INT findNextParent( TrotListActual *la, TROT_INT queryVisited, TrotListActual **parent );
62 : :
63 : : /******************************************************************************/
64 : : /*!
65 : : \brief Allocates a new list and new reference to the list.
66 : : \param[out] l_A On success, will be new reference to a new list.
67 : : \return TROT_RC
68 : : */
69 : 4953459 : TROT_RC trotListInit( TrotList **l_A )
70 : : {
71 : : /* DATA */
72 : 4953459 : TROT_RC rc = TROT_RC_SUCCESS;
73 : :
74 : 4953459 : TrotListRefListNode *newRefHead = NULL;
75 : 4953459 : TrotListRefListNode *newRefTail = NULL;
76 : :
77 : 4953459 : TrotListNode *newHead = NULL;
78 : 4953459 : TrotListNode *newTail = NULL;
79 : 4953459 : TrotListActual *newLa = NULL;
80 : :
81 : 4953459 : TrotList *newL = NULL;
82 : :
83 : :
84 : : /* PRECOND */
85 [ + + ]: 4953459 : ERR_IF( l_A == NULL, TROT_RC_ERROR_PRECOND );
86 [ + + ]: 4953458 : ERR_IF( (*l_A) != NULL, TROT_RC_ERROR_PRECOND );
87 : :
88 : :
89 : : /* CODE */
90 : : /* create list of refs that point to this list */
91 [ + + ]: 4953457 : TROT_MALLOC( newRefHead, TrotListRefListNode, 1 );
92 [ + + ]: 4952532 : TROT_MALLOC( newRefTail, TrotListRefListNode, 1 );
93 : :
94 : 4951607 : newRefHead->count = 0;
95 : 4951607 : newRefHead->l = NULL;
96 : 4951607 : newRefHead->next = newRefTail;
97 : 4951607 : newRefHead->prev = newRefHead;
98 : :
99 : 4951607 : newRefTail->count = 0;
100 : 4951607 : newRefTail->l = NULL;
101 : 4951607 : newRefTail->next = newRefTail;
102 : 4951607 : newRefTail->prev = newRefHead;
103 : :
104 : : /* create the data list */
105 [ + + ]: 4951607 : TROT_MALLOC( newHead, TrotListNode, 1 );
106 [ + + ]: 4950682 : TROT_MALLOC( newTail, TrotListNode, 1 );
107 : :
108 : 4949757 : newHead->kind = NODE_KIND_HEAD_OR_TAIL;
109 : 4949757 : newHead->count = 0;
110 : 4949757 : newHead->n = NULL;
111 : 4949757 : newHead->l = NULL;
112 : 4949757 : newHead->prev = newHead;
113 : 4949757 : newHead->next = newTail;
114 : :
115 : 4949757 : newTail->kind = NODE_KIND_HEAD_OR_TAIL;
116 : 4949757 : newTail->count = 0;
117 : 4949757 : newTail->n = NULL;
118 : 4949757 : newTail->l = NULL;
119 : 4949757 : newTail->prev = newHead;
120 : 4949757 : newTail->next = newTail;
121 : :
122 : : /* create actual list structure */
123 [ + + ]: 4949757 : TROT_MALLOC( newLa, TrotListActual, 1 );
124 : :
125 : 4948832 : newLa->reachable = 1;
126 : 4948832 : newLa->flagVisited = 0;
127 : 4948832 : newLa->previous = NULL;
128 : 4948832 : newLa->nextToFree = NULL;
129 : :
130 : 4948832 : newLa->encodingParent = NULL;
131 : 4948832 : newLa->encodingChildNumber = 0;
132 : :
133 : 4948832 : newLa->tag = TROT_TAG_DATA;
134 : 4948832 : newLa->userTag = 0;
135 : :
136 : 4948832 : newLa->childrenCount = 0;
137 : :
138 : 4948832 : newLa->refListHead = newRefHead;
139 : 4948832 : newLa->refListTail = newRefTail;
140 : 4948832 : newRefHead = NULL;
141 : 4948832 : newRefTail = NULL;
142 : :
143 : 4948832 : newLa->head = newHead;
144 : 4948832 : newLa->tail = newTail;
145 : 4948832 : newHead = NULL;
146 : 4948832 : newTail = NULL;
147 : :
148 : : /* create the first ref to this list */
149 [ + + ]: 4948832 : TROT_MALLOC( newL, TrotList, 1 );
150 : :
151 : 4947907 : newL->laParent = NULL;
152 : :
153 : 4947907 : newL->laPointsTo = newLa;
154 : 4947907 : newLa = NULL;
155 : :
156 : : /* add first ref to list's ref list */
157 : 4947907 : rc = refListAdd( newL->laPointsTo, newL );
158 [ + + ]: 4947907 : ERR_IF_PASSTHROUGH;
159 : :
160 : : /* give back */
161 : 4946057 : (*l_A) = newL;
162 : 4946057 : newL = NULL;
163 : :
164 : : /* special case where we return success here instead of going through cleanup. */
165 : 4946057 : return TROT_RC_SUCCESS;
166 : :
167 : :
168 : : /* CLEANUP */
169 : : cleanup:
170 : :
171 : 7402 : trotHookFree( newRefHead );
172 : 7402 : trotHookFree( newRefTail );
173 : 7402 : trotHookFree( newHead );
174 : 7402 : trotHookFree( newTail );
175 [ + + ]: 7402 : if ( newLa != NULL )
176 : : {
177 : 925 : trotHookFree( newLa->refListHead );
178 : 925 : trotHookFree( newLa->refListTail );
179 : 925 : trotHookFree( newLa->head );
180 : 925 : trotHookFree( newLa->tail );
181 : 925 : trotHookFree( newLa );
182 : : }
183 [ + + ]: 7402 : if ( newL != NULL )
184 : : {
185 : 1850 : trotHookFree( newL->laPointsTo->refListHead );
186 : 1850 : trotHookFree( newL->laPointsTo->refListTail );
187 : 1850 : trotHookFree( newL->laPointsTo->head );
188 : 1850 : trotHookFree( newL->laPointsTo->tail );
189 : 1850 : trotHookFree( newL->laPointsTo );
190 : 1850 : trotHookFree( newL );
191 : : }
192 : :
193 : 4953459 : return rc;
194 : : }
195 : :
196 : : /******************************************************************************/
197 : : /*!
198 : : \brief Creates a new reference to a list.
199 : : \param[in] l List to create a new reference to.
200 : : \param[out] l_A On success, new reference to the list.
201 : : \return TROT_RC
202 : : */
203 : 11120757 : TROT_RC trotListTwin( TrotList *l, TrotList **l_A )
204 : : {
205 : : /* DATA */
206 : 11120757 : TROT_RC rc = TROT_RC_SUCCESS;
207 : :
208 : 11120757 : TrotList *newL = NULL;
209 : :
210 : :
211 : : /* PRECOND */
212 [ + + ]: 11120757 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
213 [ + + ]: 11120756 : ERR_IF( l_A == NULL, TROT_RC_ERROR_PRECOND );
214 [ + + ]: 11120755 : ERR_IF( (*l_A) != NULL, TROT_RC_ERROR_PRECOND );
215 : :
216 : :
217 : : /* CODE */
218 [ + + ]: 11120754 : TROT_MALLOC( newL, TrotList, 1 );
219 : :
220 : 11119171 : newL->laParent = NULL;
221 : 11119171 : newL->laPointsTo = l->laPointsTo;
222 : :
223 : 11119171 : rc = refListAdd( newL->laPointsTo, newL );
224 [ + + ]: 11119171 : ERR_IF_PASSTHROUGH;
225 : :
226 : :
227 : : /* give back */
228 : 11119145 : (*l_A) = newL;
229 : 11119145 : newL = NULL;
230 : :
231 : 11119145 : return TROT_RC_SUCCESS;
232 : :
233 : :
234 : : /* CLEANUP */
235 : : cleanup:
236 : :
237 : 1612 : trotHookFree( newL );
238 : :
239 : 11120757 : return rc;
240 : : }
241 : :
242 : : /******************************************************************************/
243 : : /*!
244 : : \brief Frees a list reference. Actual list will be freed if the list is no
245 : : longer reachable.
246 : : \param[in] l_F Address of list reference to free.
247 : : \return void
248 : :
249 : : l_F can be NULL, or the address of a NULL pointer, and this will be a noop.
250 : : */
251 : 24559319 : void trotListFree( TrotList **l_F )
252 : : {
253 : : /* DATA */
254 : 24559319 : TrotListActual *la = NULL;
255 : :
256 : 24559319 : TrotListNode *node = NULL;
257 : :
258 : 24559319 : TROT_INT j = 0;
259 : 24559319 : TrotListActual *laTemp = NULL;
260 : :
261 : 24559319 : TrotListActual *laNext = NULL;
262 : 24559319 : TrotListActual *laCurrent = NULL;
263 : :
264 : :
265 : : /* CODE */
266 [ + + ][ + + ]: 24559319 : if ( l_F == NULL || (*l_F) == NULL )
267 : : {
268 : 9852241 : return;
269 : : }
270 : :
271 : : PARANOID_ERR_IF( (*l_F)->laParent != NULL );
272 : :
273 : 14707078 : la = (*l_F)->laPointsTo;
274 : :
275 : : /* remove ref from list's ref list */
276 : 14707078 : refListRemove( la, (*l_F) );
277 : :
278 : : /* free ref */
279 : 14707078 : trotHookFree( (*l_F) );
280 : 14707078 : (*l_F) = NULL;
281 : :
282 : : /* is list reachable? */
283 : 14707078 : isListReachable( la );
284 [ + + ]: 14707078 : if ( la->reachable )
285 : : {
286 : 10570622 : return;
287 : : }
288 : :
289 : : /* we need to free it */
290 : :
291 : : /* go through stack */
292 : 4136456 : laCurrent = la;
293 [ + + ]: 9082513 : while ( laCurrent != NULL )
294 : : {
295 : : /* free data */
296 : 4946057 : node = laCurrent->head->next;
297 [ + + ]: 10591293 : while ( node != laCurrent->tail )
298 : : {
299 [ + + ]: 5645236 : if ( node->kind == NODE_KIND_INT )
300 : : {
301 : 5052200 : trotHookFree( node->n );
302 : : }
303 : : else /* NODE_KIND_LIST */
304 : : {
305 [ + + ]: 1951160 : for ( j = 0; j < node->count; j += 1 )
306 : : {
307 : 1358124 : laTemp = node->l[ j ]->laPointsTo;
308 : :
309 : 1358124 : refListRemove( laTemp, node->l[ j ] );
310 : :
311 : 1358124 : trotHookFree( node->l[ j ] );
312 : 1358124 : node->l[ j ] = NULL;
313 : :
314 [ + + ]: 1358124 : if ( laTemp->reachable == 1 )
315 : : {
316 : 1049077 : isListReachable( laTemp );
317 [ + + ]: 1049077 : if ( laTemp->reachable == 0 )
318 : : {
319 : : /* need to free this list too */
320 : 809601 : laTemp->nextToFree = laCurrent->nextToFree;
321 : 809601 : laCurrent->nextToFree = laTemp;
322 : : }
323 : : }
324 : : }
325 : :
326 : 593036 : trotHookFree( node->l );
327 : : }
328 : :
329 : 5645236 : node = node->next;
330 : 5645236 : trotHookFree( node->prev );
331 : : }
332 : :
333 : 4946057 : laCurrent = laCurrent->nextToFree;
334 : : }
335 : :
336 : : /* *** */
337 : 4136456 : laNext = la;
338 [ + + ]: 9082513 : while ( laNext != NULL )
339 : : {
340 : : /* *** */
341 : 4946057 : laCurrent = laNext;
342 : :
343 : : /* *** */
344 : 4946057 : laNext = laNext->nextToFree;
345 : :
346 : : /* *** */
347 : 4946057 : trotHookFree( laCurrent->head );
348 : 4946057 : trotHookFree( laCurrent->tail );
349 : 4946057 : trotHookFree( laCurrent->refListHead );
350 : 4946057 : trotHookFree( laCurrent->refListTail );
351 : 4946057 : trotHookFree( laCurrent );
352 : : }
353 : :
354 : 24559319 : return;
355 : : }
356 : :
357 : : /******************************************************************************/
358 : : /*!
359 : : \brief Compares list references to see if they point to the same list.
360 : : \param[in] l1 First reference.
361 : : \param[in] l2 Second reference.
362 : : \param[out] isSame 0 if refs point to different lists, 1 if they point to
363 : : the same lists.
364 : : \return TROT_RC
365 : : */
366 : 6 : TROT_RC trotListRefCompare( TrotList *l1, TrotList *l2, TROT_INT *isSame )
367 : : {
368 : : /* DATA */
369 : 6 : TROT_RC rc = TROT_RC_SUCCESS;
370 : :
371 : :
372 : : /* PRECOND */
373 [ + + ]: 6 : ERR_IF( l1 == NULL, TROT_RC_ERROR_PRECOND );
374 [ + + ]: 5 : ERR_IF( l2 == NULL, TROT_RC_ERROR_PRECOND );
375 [ + + ]: 4 : ERR_IF( isSame == NULL, TROT_RC_ERROR_PRECOND );
376 : :
377 : :
378 : : /* CODE */
379 : 3 : (*isSame) = 0;
380 : :
381 [ + + ]: 3 : if ( l1->laPointsTo == l2->laPointsTo )
382 : : {
383 : 2 : (*isSame) = 1;
384 : : }
385 : :
386 : :
387 : : /* CLEANUP */
388 : : cleanup:
389 : :
390 : 6 : return rc;
391 : : }
392 : :
393 : : /******************************************************************************/
394 : : /*!
395 : : \brief Gets the count of items in the list.
396 : : \param[in] l Pointer to a TrotList pointer.
397 : : \param[out] count On success, will contain the count of this list.
398 : : \return TROT_RC
399 : : */
400 : 6713144 : TROT_RC trotListGetCount( TrotList *l, TROT_INT *count )
401 : : {
402 : : /* DATA */
403 : 6713144 : TROT_RC rc = TROT_RC_SUCCESS;
404 : :
405 : : /* PRECOND */
406 [ + + ]: 6713144 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
407 [ + + ]: 6713143 : ERR_IF( count == NULL, TROT_RC_ERROR_PRECOND );
408 : :
409 : :
410 : : /* CODE */
411 : 6713142 : (*count) = l->laPointsTo->childrenCount;
412 : :
413 : : PARANOID_ERR_IF( (*count) > TROT_MAX_CHILDREN );
414 : :
415 : :
416 : : /* CLEANUP */
417 : : cleanup:
418 : :
419 : 6713144 : return rc;
420 : : }
421 : :
422 : : /******************************************************************************/
423 : : /*!
424 : : \brief Gets the kind of an item in the list.
425 : : \param[in] l The list.
426 : : \param[in] index Index of the item in the list to ge the kind of.
427 : : \param[out] kind On success, will contain the kind of the item.
428 : : \return TROT_RC
429 : : */
430 : 17719458 : TROT_RC trotListGetKind( TrotList *l, TROT_INT index, TROT_INT *kind )
431 : : {
432 : : /* DATA */
433 : 17719458 : TROT_RC rc = TROT_RC_SUCCESS;
434 : :
435 : 17719458 : TrotListActual *la = NULL;
436 : :
437 : 17719458 : TrotListNode *node = NULL;
438 : :
439 : 17719458 : TROT_INT count = 0;
440 : :
441 : :
442 : : /* PRECOND */
443 [ + + ]: 17719458 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
444 [ + + ]: 17719457 : ERR_IF( kind == NULL, TROT_RC_ERROR_PRECOND );
445 : :
446 : :
447 : : /* CODE */
448 : 17719456 : la = l->laPointsTo;
449 : :
450 : : /* Turn negative index into positive equivalent. */
451 [ + + ]: 17719456 : if ( index < 0 )
452 : : {
453 : 8057317 : index = (la->childrenCount) + index + 1;
454 : : }
455 : :
456 : : /* Make sure index is in range */
457 [ + + ]: 17719456 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
458 [ + + ]: 17719454 : ERR_IF_1( index > (la->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
459 : :
460 : : /* *** */
461 : 17719453 : node = la->head->next;
462 : : while ( 1 )
463 : : {
464 : 154216779 : count += node->count;
465 [ + + ]: 154216779 : if ( count >= index )
466 : : {
467 : 17719453 : break;
468 : : }
469 : :
470 : 136497326 : node = node->next;
471 : :
472 : : PARANOID_ERR_IF( node == la->tail );
473 : 136497326 : }
474 : :
475 : 17719453 : (*kind) = node->kind;
476 : :
477 : 17719453 : return TROT_RC_SUCCESS;
478 : :
479 : :
480 : : /* CLEANUP */
481 : : cleanup:
482 : :
483 : 17719458 : return rc;
484 : : }
485 : :
486 : : /******************************************************************************/
487 : : /*!
488 : : \brief Appends an int to the end of the list.
489 : : \param[in] l The list.
490 : : \param[in] n The int to append.
491 : : \return TROT_RC
492 : : */
493 : 11473423 : TROT_RC trotListAppendInt( TrotList *l, TROT_INT n )
494 : : {
495 : : /* DATA */
496 : 11473423 : TROT_RC rc = TROT_RC_SUCCESS;
497 : :
498 : 11473423 : TrotListActual *la = NULL;
499 : 11473423 : TrotListNode *node = NULL;
500 : :
501 : 11473423 : TrotListNode *newNode = NULL;
502 : :
503 : :
504 : : /* PRECOND */
505 [ + + ]: 11473423 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
506 : :
507 : :
508 : : /* CODE */
509 : 11473422 : la = l->laPointsTo;
510 : :
511 : : /* lists cannot hold more than TROT_MAX_CHILDREN, so make sure we have room */
512 [ + + ]: 11473422 : ERR_IF( TROT_MAX_CHILDREN - la->childrenCount < 1, TROT_RC_ERROR_LIST_OVERFLOW );
513 : :
514 : : /* *** */
515 : 11473421 : node = la->tail->prev;
516 : :
517 : : /* special cases to create new node */
518 [ + + ]: 11473421 : if ( node == la->head /* empty list */
519 [ + + ]: 6840084 : || node->kind != NODE_KIND_INT /* last node is not int kind */
520 [ + + ]: 6498322 : || node->count == NODE_SIZE /* last node is full */
521 : : )
522 : : {
523 : 5124084 : rc = newIntNode( &newNode );
524 [ + + ]: 5124084 : ERR_IF_PASSTHROUGH;
525 : :
526 : 5121734 : newNode->next = la->tail;
527 : 5121734 : newNode->prev = la->tail->prev;
528 : :
529 : 5121734 : la->tail->prev->next = newNode;
530 : 5121734 : la->tail->prev = newNode;
531 : :
532 : 5121734 : node = newNode;
533 : 5121734 : newNode = NULL;
534 : : }
535 : :
536 : : /* append */
537 : 11471071 : node->n[ node->count ] = n;
538 : 11471071 : node->count += 1;
539 : :
540 : 11471071 : la->childrenCount += 1;
541 : :
542 : 11471071 : return TROT_RC_SUCCESS;
543 : :
544 : :
545 : : /* CLEANUP */
546 : : cleanup:
547 : :
548 : 11473423 : return rc;
549 : : }
550 : :
551 : : /******************************************************************************/
552 : : /*!
553 : : \brief Appends a list to the end of the list.
554 : : \param[in] l The list to append to.
555 : : \param[in] lToAppend The list to append.
556 : : \return TROT_RC
557 : : */
558 : 1291895 : TROT_RC trotListAppendList( TrotList *l, TrotList *lToAppend )
559 : : {
560 : : /* DATA */
561 : 1291895 : TROT_RC rc = TROT_RC_SUCCESS;
562 : :
563 : 1291895 : TrotListActual *la = NULL;
564 : 1291895 : TrotListNode *node = NULL;
565 : :
566 : 1291895 : TrotListNode *newNode = NULL;
567 : :
568 : 1291895 : TrotList *newL = NULL;
569 : :
570 : :
571 : : /* PRECOND */
572 [ + + ]: 1291895 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
573 [ + + ]: 1291894 : ERR_IF( lToAppend == NULL, TROT_RC_ERROR_PRECOND );
574 : :
575 : :
576 : : /* CODE */
577 : 1291893 : la = l->laPointsTo;
578 : :
579 : : /* lists cannot hold more than TROT_MAX_CHILDREN, so make sure we have room */
580 [ + + ]: 1291893 : ERR_IF( TROT_MAX_CHILDREN - la->childrenCount < 1, TROT_RC_ERROR_LIST_OVERFLOW );
581 : :
582 : : /* *** */
583 : 1291892 : node = la->tail->prev;
584 : :
585 : : /* special cases to create new node */
586 [ + + ]: 1291892 : if ( node == la->head /* empty list */
587 [ + + ]: 940701 : || node->kind != NODE_KIND_LIST /* last node is not list kind */
588 [ + + ]: 603566 : || node->count == NODE_SIZE /* last node is full */
589 : : )
590 : : {
591 : 699127 : rc = newListNode( &newNode );
592 [ + + ]: 699127 : ERR_IF_PASSTHROUGH;
593 : :
594 : 698095 : newNode->next = la->tail;
595 : 698095 : newNode->prev = la->tail->prev;
596 : :
597 : 698095 : la->tail->prev->next = newNode;
598 : 698095 : la->tail->prev = newNode;
599 : :
600 : 698095 : node = newNode;
601 : 698095 : newNode = NULL;
602 : : }
603 : :
604 : : /* append */
605 : 1290860 : rc = trotListTwin( lToAppend, &newL );
606 [ + + ]: 1290860 : ERR_IF_PASSTHROUGH;
607 : :
608 : 1290049 : node->l[ node->count ] = newL;
609 : 1290049 : newL->laParent = la;
610 : 1290049 : newL = NULL;
611 : :
612 : 1290049 : node->count += 1;
613 : :
614 : 1290049 : la->childrenCount += 1;
615 : :
616 : 1290049 : return TROT_RC_SUCCESS;
617 : :
618 : :
619 : : /* CLEANUP */
620 : : cleanup:
621 : :
622 : 1846 : trotListFree( &newL );
623 : :
624 : 1291895 : return rc;
625 : : }
626 : :
627 : : /******************************************************************************/
628 : : /*!
629 : : \brief Inserts an int into the list.
630 : : \param[in] l The list to insert into.
631 : : \param[in] index Where to insert.
632 : : \param[in] n The int to insert.
633 : : \return TROT_RC
634 : : */
635 : 85312 : TROT_RC trotListInsertInt( TrotList *l, TROT_INT index, TROT_INT n )
636 : : {
637 : : /* DATA */
638 : 85312 : TROT_RC rc = TROT_RC_SUCCESS;
639 : :
640 : 85312 : TrotListActual *la = NULL;
641 : :
642 : 85312 : TrotListNode *node = NULL;
643 : :
644 : 85312 : TROT_INT count = 0;
645 : :
646 : 85312 : TROT_INT i = 0;
647 : 85312 : TROT_INT j = 0;
648 : :
649 : 85312 : TrotListNode *newNode = NULL;
650 : :
651 : :
652 : : /* PRECOND */
653 [ + + ]: 85312 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
654 : :
655 : :
656 : : /* CODE */
657 : 85311 : la = l->laPointsTo;
658 : :
659 : : /* lists cannot hold more than TROT_MAX_CHILDREN, so make sure we have room */
660 [ + + ]: 85311 : ERR_IF( TROT_MAX_CHILDREN - la->childrenCount < 1, TROT_RC_ERROR_LIST_OVERFLOW );
661 : :
662 : : /* Turn negative index into positive equivalent. */
663 [ + + ]: 85310 : if ( index < 0 )
664 : : {
665 : 20853 : index = (la->childrenCount) + index + 2;
666 : : }
667 : :
668 : : /* This handles two special cases. One, if they want to add to the end of the
669 : : list. And two, if they want to add to an empty list. */
670 [ + + ]: 85310 : if ( index == (la->childrenCount) + 1 )
671 : : {
672 : 50438 : rc = trotListAppendInt( l, n );
673 [ + + ]: 50438 : ERR_IF_PASSTHROUGH;
674 : :
675 : 50356 : return TROT_RC_SUCCESS;
676 : : }
677 : :
678 : : /* Make sure index is in range */
679 [ + + ]: 34872 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
680 [ + + ]: 34870 : ERR_IF_1( index > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, index );
681 : :
682 : : /* Find node where int needs to be added into */
683 : 34869 : node = la->head->next;
684 : : while ( 1 )
685 : : {
686 [ + + ]: 198585 : if ( count + (node->count) >= index )
687 : : {
688 : 34869 : break;
689 : : }
690 : :
691 : 163716 : count += node->count;
692 : 163716 : node = node->next;
693 : :
694 : : PARANOID_ERR_IF( node == la->tail );
695 : 163716 : }
696 : :
697 : : /* *** */
698 [ + + ]: 34869 : if ( node->kind == NODE_KIND_INT )
699 : : {
700 : : /* If node is full */
701 [ + + ]: 21535 : if ( node->count == NODE_SIZE )
702 : : {
703 : 2028 : rc = trotListNodeSplit( node, NODE_SIZE / 2 );
704 [ + + ]: 2028 : ERR_IF_PASSTHROUGH;
705 : :
706 : : /* Since node has been split, we may need to go to next
707 : : node. */
708 [ + + ]: 2026 : if ( count + (node->count) < index )
709 : : {
710 : 1328 : count += node->count;
711 : 1328 : node = node->next;
712 : : }
713 : : }
714 : :
715 : : /* We now have the node where the int needs to be inserted.
716 : : We've made sure there is space to insert.
717 : : (count + 1) is the beginning index of the node */
718 : : /* Now let's move any ints over to make room */
719 : 21533 : i = index - count - 1;
720 : 21533 : j = node->count;
721 [ + + ]: 124722 : while ( j != i )
722 : : {
723 : 103189 : node->n[ j ] = node->n[ j - 1 ];
724 : 103189 : j -= 1;
725 : : }
726 : :
727 : : /* Insert int into node */
728 : 21533 : node->n[ i ] = n;
729 : 21533 : node->count += 1;
730 : :
731 : 21533 : la->childrenCount += 1;
732 : :
733 : 21533 : return TROT_RC_SUCCESS;
734 : : }
735 : : else /* node->kind == NODE_KIND_LIST */
736 : : {
737 : 13334 : i = index - count - 1;
738 : :
739 : : /* If we need to insert at spot 0, we see if the previous node
740 : : is an int node with room. If so, we can just append to that
741 : : node. */
742 [ + + ]: 13334 : if ( i == 0
743 [ + + ]: 11654 : && node->prev->kind == NODE_KIND_INT
744 [ + + ]: 11400 : && node->prev->count != NODE_SIZE
745 : : )
746 : : {
747 : 10714 : node = node->prev;
748 : :
749 : : /* Insert int into node */
750 : 10714 : node->n[ node->count ] = n;
751 : 10714 : node->count += 1;
752 : :
753 : 10714 : la->childrenCount += 1;
754 : :
755 : 10714 : return TROT_RC_SUCCESS;
756 : : }
757 : :
758 : : /* if not at beginning, we'll have to split the node */
759 [ + + ]: 2620 : if ( i != 0 )
760 : : {
761 : 1680 : rc = trotListNodeSplit( node, i );
762 [ + + ]: 1680 : ERR_IF_PASSTHROUGH;
763 : :
764 : 1678 : node = node->next;
765 : : }
766 : :
767 : : /* *** */
768 : 2618 : rc = newIntNode( &newNode ); /* FUTURE: newNode functions may be able to also place themselves in the list too, to consolidate some code */
769 [ + + ]: 2618 : ERR_IF_PASSTHROUGH;
770 : :
771 : 2616 : newNode->n[ 0 ] = n;
772 : 2616 : newNode->count = 1;
773 : :
774 : : /* Insert node into list */
775 : 2616 : newNode->next = node;
776 : 2616 : newNode->prev = node->prev;
777 : :
778 : 2616 : node->prev->next = newNode;
779 : 2616 : node->prev = newNode;
780 : :
781 : 2616 : la->childrenCount += 1;
782 : :
783 : 2616 : return TROT_RC_SUCCESS;
784 : : }
785 : :
786 : :
787 : : /* CLEANUP */
788 : : cleanup:
789 : :
790 : 85312 : return rc;
791 : : }
792 : :
793 : : /******************************************************************************/
794 : : /*!
795 : : \brief Inserts a list into the list.
796 : : \param[in] l The list to insert into.
797 : : \param[in] index Where to insert.
798 : : \param[in] lToInsert The list to insert.
799 : : \return TROT_RC
800 : : */
801 : 992677 : TROT_RC trotListInsertList( TrotList *l, TROT_INT index, TrotList *lToInsert )
802 : : {
803 : : /* DATA */
804 : 992677 : TROT_RC rc = TROT_RC_SUCCESS;
805 : :
806 : 992677 : TrotListActual *la = NULL;
807 : :
808 : 992677 : TrotListNode *node = NULL;
809 : :
810 : 992677 : TROT_INT count = 0;
811 : :
812 : 992677 : TROT_INT i = 0;
813 : 992677 : TROT_INT j = 0;
814 : :
815 : 992677 : TrotListNode *newNode = NULL;
816 : :
817 : 992677 : TrotList *newL = NULL;
818 : :
819 : :
820 : : /* PRECOND */
821 [ + + ]: 992677 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
822 [ + + ]: 992676 : ERR_IF( lToInsert == NULL, TROT_RC_ERROR_PRECOND );
823 : :
824 : :
825 : : /* CODE */
826 : 992675 : la = l->laPointsTo;
827 : :
828 : : /* lists cannot hold more than TROT_MAX_CHILDREN, so make sure we have room */
829 [ + + ]: 992675 : ERR_IF( TROT_MAX_CHILDREN - la->childrenCount < 1, TROT_RC_ERROR_LIST_OVERFLOW );
830 : :
831 : : /* Turn negative index into positive equivalent. */
832 [ + + ]: 992674 : if ( index < 0 )
833 : : {
834 : 33976 : index = (la->childrenCount) + index + 2;
835 : : }
836 : :
837 : : /* This handles two special cases. One, if they want to add to the end of the
838 : : list. And two, if they want to add to an empty list. */
839 [ + + ]: 992674 : if ( index == (la->childrenCount) + 1 )
840 : : {
841 : 492458 : rc = trotListAppendList( l, lToInsert );
842 [ + + ]: 492458 : ERR_IF_PASSTHROUGH;
843 : :
844 : 492455 : return TROT_RC_SUCCESS;
845 : : }
846 : :
847 : : /* Make sure index is in range */
848 [ + + ]: 500216 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
849 [ + + ]: 500214 : ERR_IF_1( index > (la->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
850 : :
851 : : /* Find node where list needs to be added into */
852 : 500213 : node = la->head->next;
853 : : while ( 1 )
854 : : {
855 [ + + ]: 14914113 : if ( count + (node->count) >= index )
856 : : {
857 : 500213 : break;
858 : : }
859 : :
860 : 14413900 : count += node->count;
861 : 14413900 : node = node->next;
862 : :
863 : : PARANOID_ERR_IF( node == la->tail );
864 : 14413900 : }
865 : :
866 : : /* *** */
867 [ + + ]: 500213 : if ( node->kind == NODE_KIND_LIST )
868 : : {
869 : : /* If node is full */
870 [ + + ]: 477262 : if ( node->count == NODE_SIZE )
871 : : {
872 : 41817 : rc = trotListNodeSplit( node, NODE_SIZE / 2 );
873 [ + + ]: 41817 : ERR_IF_PASSTHROUGH;
874 : :
875 : : /* Since node has been split, we may need to go to next
876 : : node. */
877 [ + + ]: 41815 : if ( count + (node->count) < index )
878 : : {
879 : 21387 : count += node->count;
880 : 21387 : node = node->next;
881 : : }
882 : : }
883 : :
884 : : /* We now have the node where the list needs to be inserted.
885 : : We've made sure there is space to insert.
886 : : (count + 1) is the beginning index of the node */
887 : :
888 : : /* *** */
889 : 477260 : rc = trotListTwin( lToInsert, &newL );
890 [ + + ]: 477260 : ERR_IF_PASSTHROUGH;
891 : :
892 : : /* Now let's move any lists over to make room */
893 : 477241 : i = index - count - 1;
894 : 477241 : j = node->count;
895 [ + + ]: 3241771 : while ( j != i )
896 : : {
897 : 2764530 : node->l[ j ] = node->l[ j - 1 ];
898 : 2764530 : j -= 1;
899 : : }
900 : :
901 : : /* Insert list into node */
902 : 477241 : node->l[ i ] = newL;
903 : 477241 : newL->laParent = la;
904 : 477241 : newL = NULL;
905 : :
906 : 477241 : node->count += 1;
907 : :
908 : 477241 : la->childrenCount += 1;
909 : :
910 : 477241 : return TROT_RC_SUCCESS;
911 : : }
912 : : else /* node->kind == NODE_KIND_INT */
913 : : {
914 : 22951 : i = index - count - 1;
915 : :
916 : : /* If we need to insert at spot 0, we see if the previous node
917 : : is an list node with room. If so, we can just append to that
918 : : node. */
919 [ + + ]: 22951 : if ( i == 0
920 [ + + ]: 21264 : && node->prev->kind == NODE_KIND_LIST
921 [ + + ]: 13385 : && node->prev->count != NODE_SIZE
922 : : )
923 : : {
924 : 12666 : node = node->prev;
925 : :
926 : : /* Insert list into node */
927 : 12666 : rc = trotListTwin( lToInsert, &newL );
928 [ + + ]: 12666 : ERR_IF_PASSTHROUGH;
929 : :
930 : 12665 : node->l[ node->count ] = newL;
931 : 12665 : newL->laParent = la;
932 : 12665 : newL = NULL;
933 : :
934 : 12665 : node->count += 1;
935 : :
936 : 12665 : la->childrenCount += 1;
937 : :
938 : 12665 : return TROT_RC_SUCCESS;
939 : : }
940 : :
941 : : /* if not at beginning, we'll have to split the node */
942 [ + + ]: 10285 : if ( i != 0 )
943 : : {
944 : 1687 : rc = trotListNodeSplit( node, i );
945 [ + + ]: 1687 : ERR_IF_PASSTHROUGH;
946 : :
947 : 1685 : node = node->next;
948 : : }
949 : :
950 : : /* *** */
951 : 10283 : rc = newListNode( &newNode );
952 [ + + ]: 10283 : ERR_IF_PASSTHROUGH;
953 : :
954 : : /* *** */
955 : 10279 : rc = trotListTwin( lToInsert, &newL );
956 [ + + ]: 10279 : ERR_IF_PASSTHROUGH;
957 : :
958 : : /* Insert node into list */ /* FUTURE: inserting a node into a list should be a function */
959 : 10277 : newNode->l[ 0 ] = newL;
960 : 10277 : newL->laParent = la;
961 : 10277 : newL = NULL;
962 : :
963 : 10277 : newNode->count = 1;
964 : :
965 : 10277 : newNode->next = node;
966 : 10277 : newNode->prev = node->prev;
967 : :
968 : 10277 : node->prev->next = newNode;
969 : 10277 : node->prev = newNode;
970 : :
971 : 10277 : la->childrenCount += 1;
972 : :
973 : 10277 : return TROT_RC_SUCCESS;
974 : : }
975 : :
976 : :
977 : : /* CLEANUP */
978 : : cleanup:
979 : :
980 : 39 : trotListFree( &newL );
981 : :
982 [ + + ]: 39 : if ( newNode != NULL )
983 : : {
984 : 2 : trotHookFree( newNode->l );
985 : 2 : trotHookFree( newNode );
986 : : }
987 : :
988 : 992677 : return rc;
989 : : }
990 : :
991 : : /******************************************************************************/
992 : : /*!
993 : : \brief Get int at index in list.
994 : : \param[in] l The list.
995 : : \param[in] index Which int to get.
996 : : \param[out] n On success, the int that was at index in l.
997 : : \return TROT_RC
998 : : */
999 : 28694387 : TROT_RC trotListGetInt( TrotList *l, TROT_INT index, TROT_INT *n )
1000 : : {
1001 : : /* DATA */
1002 : 28694387 : TROT_RC rc = TROT_RC_SUCCESS;
1003 : :
1004 : 28694387 : TrotListActual *la = NULL;
1005 : :
1006 : 28694387 : TrotListNode *node = NULL;
1007 : :
1008 : 28694387 : TROT_INT count = 0;
1009 : :
1010 : :
1011 : : /* PRECOND */
1012 [ + + ]: 28694387 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1013 [ + + ]: 28694386 : ERR_IF( n == NULL, TROT_RC_ERROR_PRECOND );
1014 : :
1015 : :
1016 : : /* CODE */
1017 : 28694385 : la = l->laPointsTo;
1018 : :
1019 : : /* Turn negative index into positive equivalent. */
1020 [ + + ]: 28694385 : if ( index < 0 )
1021 : : {
1022 : 4028257 : index = (la->childrenCount) + index + 1;
1023 : : }
1024 : :
1025 : : /* Make sure index is in range */
1026 [ + + ]: 28694385 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1027 [ + + ]: 28694383 : ERR_IF_1( index > (la->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
1028 : :
1029 : : /* *** */
1030 : 28694369 : node = la->head->next;
1031 : : while ( 1 )
1032 : : {
1033 : 103202171 : count += node->count;
1034 [ + + ]: 103202171 : if ( count >= index )
1035 : : {
1036 : 28694369 : break;
1037 : : }
1038 : :
1039 : 74507802 : node = node->next;
1040 : :
1041 : : PARANOID_ERR_IF( node == la->tail );
1042 : 74507802 : }
1043 : :
1044 [ + + ]: 28694369 : ERR_IF_1( node->kind != NODE_KIND_INT, TROT_RC_ERROR_WRONG_KIND, node->kind );
1045 : :
1046 : : /* give back */
1047 : 28694346 : (*n) = node->n[ (node->count) - 1 - (count - index) ];
1048 : :
1049 : 28694346 : return TROT_RC_SUCCESS;
1050 : :
1051 : :
1052 : : /* CLEANUP */
1053 : : cleanup:
1054 : :
1055 : 28694387 : return rc;
1056 : : }
1057 : :
1058 : : /******************************************************************************/
1059 : : /*!
1060 : : \brief Gets list at index in list.
1061 : : \param[in] l The list.
1062 : : \param[in] index Which list to get.
1063 : : \param[out] lTwin_A On success, the list that was at index in l.
1064 : : \return TROT_RC
1065 : : */
1066 : 9130161 : TROT_RC trotListGetList( TrotList *l, TROT_INT index, TrotList **lTwin_A )
1067 : : {
1068 : : /* DATA */
1069 : 9130161 : TROT_RC rc = TROT_RC_SUCCESS;
1070 : :
1071 : 9130161 : TrotListNode *node = NULL;
1072 : :
1073 : 9130161 : TROT_INT count = 0;
1074 : :
1075 : 9130161 : TrotList *newL = NULL;
1076 : :
1077 : :
1078 : : /* PRECOND */
1079 [ + + ]: 9130161 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1080 [ + + ]: 9130160 : ERR_IF( lTwin_A == NULL, TROT_RC_ERROR_PRECOND );
1081 [ + + ]: 9130159 : ERR_IF( (*lTwin_A) != NULL, TROT_RC_ERROR_PRECOND );
1082 : :
1083 : :
1084 : : /* CODE */
1085 : : /* Turn negative index into positive equivalent. */
1086 [ + + ]: 9130158 : if ( index < 0 )
1087 : : {
1088 : 4028401 : index = (l->laPointsTo->childrenCount) + index + 1;
1089 : : }
1090 : :
1091 : : /* Make sure index is in range */
1092 [ + + ]: 9130158 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1093 [ + + ]: 9130156 : ERR_IF_1( index > (l->laPointsTo->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
1094 : :
1095 : : /* *** */
1096 : 9130155 : node = l->laPointsTo->head->next;
1097 : : while ( 1 )
1098 : : {
1099 : 77451724 : count += node->count;
1100 [ + + ]: 77451724 : if ( count >= index )
1101 : : {
1102 : 9130155 : break;
1103 : : }
1104 : :
1105 : 68321569 : node = node->next;
1106 : :
1107 : : PARANOID_ERR_IF( node == l->laPointsTo->tail );
1108 : 68321569 : }
1109 : :
1110 [ + + ]: 9130155 : ERR_IF_1( node->kind != NODE_KIND_LIST, TROT_RC_ERROR_WRONG_KIND, node->kind );
1111 : :
1112 : 9130154 : rc = trotListTwin( node->l[ (node->count) - 1 - (count - index) ], &newL );
1113 [ + + ]: 9130154 : ERR_IF_PASSTHROUGH;
1114 : :
1115 : : /* give back */
1116 : 9129541 : (*lTwin_A) = newL;
1117 : 9129541 : newL = NULL;
1118 : :
1119 : 9129541 : return TROT_RC_SUCCESS;
1120 : :
1121 : :
1122 : : /* CLEANUP */
1123 : : cleanup:
1124 : :
1125 : 9130161 : return rc;
1126 : : }
1127 : :
1128 : : /******************************************************************************/
1129 : : /*!
1130 : : \brief Gets and removes int in list.
1131 : : \param[in] l The list.
1132 : : \param[in] index Which int to get and remove.
1133 : : \param[out] n On success, the int that was at index in l.
1134 : : \return TROT_RC
1135 : : */
1136 : 104150 : TROT_RC trotListRemoveInt( TrotList *l, TROT_INT index, TROT_INT *n )
1137 : : {
1138 : : /* DATA */
1139 : 104150 : TROT_RC rc = TROT_RC_SUCCESS;
1140 : :
1141 : 104150 : TrotListNode *node = NULL;
1142 : :
1143 : 104150 : TROT_INT count = 0;
1144 : :
1145 : 104150 : TROT_INT giveBackN = 0;
1146 : :
1147 : 104150 : TROT_INT i = 0;
1148 : :
1149 : :
1150 : : /* PRECOND */
1151 [ + + ]: 104150 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1152 [ + + ]: 104149 : ERR_IF( n == NULL, TROT_RC_ERROR_PRECOND );
1153 : :
1154 : :
1155 : : /* CODE */
1156 : : /* Turn negative index into positive equivalent. */
1157 [ + + ]: 104148 : if ( index < 0 )
1158 : : {
1159 : 93975 : index = (l->laPointsTo->childrenCount) + index + 1;
1160 : : }
1161 : :
1162 : : /* Make sure index is in range */
1163 [ + + ]: 104148 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1164 [ + + ]: 104146 : ERR_IF_1( index > (l->laPointsTo->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
1165 : :
1166 : : /* *** */
1167 : 104145 : node = l->laPointsTo->head->next;
1168 : : while ( 1 )
1169 : : {
1170 : 234028 : count += node->count;
1171 [ + + ]: 234028 : if ( count >= index )
1172 : : {
1173 : 104145 : break;
1174 : : }
1175 : :
1176 : 129883 : node = node->next;
1177 : :
1178 : : PARANOID_ERR_IF( node == l->laPointsTo->tail );
1179 : 129883 : }
1180 : :
1181 [ + + ]: 104145 : ERR_IF_1( node->kind != NODE_KIND_INT, TROT_RC_ERROR_WRONG_KIND, node->kind );
1182 : :
1183 : 104144 : i = (node->count) - 1 - (count - index);
1184 : 104144 : giveBackN = node->n[ i ];
1185 [ + + ]: 107536 : while ( i < ( (node->count) - 1 ) )
1186 : : {
1187 : 3392 : node->n[ i ] = node->n[ i + 1 ];
1188 : 3392 : i += 1;
1189 : : }
1190 : 104144 : node->count -= 1;
1191 : 104144 : l->laPointsTo->childrenCount -= 1;
1192 : :
1193 [ + + ]: 104144 : if ( node->count == 0 ) /* FUTURE: this code may be able to be factored out into a function */
1194 : : {
1195 : 85857 : node->prev->next = node->next;
1196 : 85857 : node->next->prev = node->prev;
1197 : :
1198 : 85857 : trotHookFree( node->n );
1199 : 85857 : trotHookFree( node );
1200 : : }
1201 : :
1202 : : /* give back */
1203 : 104144 : (*n) = giveBackN;
1204 : :
1205 : 104144 : return TROT_RC_SUCCESS;
1206 : :
1207 : :
1208 : : /* CLEANUP */
1209 : : cleanup:
1210 : :
1211 : 104150 : return rc;
1212 : : }
1213 : :
1214 : : /******************************************************************************/
1215 : : /*!
1216 : : \brief Gets and removes list in list.
1217 : : \param[in] l The list.
1218 : : \param[in] index Which list to get.
1219 : : \param[out] lRemoved_A On success, list that was at index in l.
1220 : : \return TROT_RC
1221 : : */
1222 : 293282 : TROT_RC trotListRemoveList( TrotList *l, TROT_INT index, TrotList **lRemoved_A )
1223 : : {
1224 : : /* DATA */
1225 : 293282 : TROT_RC rc = TROT_RC_SUCCESS;
1226 : :
1227 : 293282 : TrotListNode *node = NULL;
1228 : :
1229 : 293282 : TROT_INT count = 0;
1230 : :
1231 : 293282 : TrotList *giveBackL = NULL;
1232 : :
1233 : 293282 : TROT_INT i = 0;
1234 : :
1235 : :
1236 : : /* PRECOND */
1237 [ + + ]: 293282 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1238 [ + + ]: 293281 : ERR_IF( lRemoved_A == NULL, TROT_RC_ERROR_PRECOND );
1239 [ + + ]: 293280 : ERR_IF( (*lRemoved_A) != NULL, TROT_RC_ERROR_PRECOND );
1240 : :
1241 : :
1242 : : /* CODE */
1243 : : /* Turn negative index into positive equivalent. */
1244 [ + + ]: 293279 : if ( index < 0 )
1245 : : {
1246 : 167156 : index = (l->laPointsTo->childrenCount) + index + 1;
1247 : : }
1248 : :
1249 : : /* Make sure index is in range */
1250 [ + + ]: 293279 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1251 [ + + ]: 293277 : ERR_IF_1( index > (l->laPointsTo->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
1252 : :
1253 : : /* *** */
1254 : 293276 : node = l->laPointsTo->head->next;
1255 : : while ( 1 )
1256 : : {
1257 : 7180760 : count += node->count;
1258 [ + + ]: 7180760 : if ( count >= index )
1259 : : {
1260 : 293276 : break;
1261 : : }
1262 : :
1263 : 6887484 : node = node->next;
1264 : :
1265 : : PARANOID_ERR_IF( node == l->laPointsTo->tail );
1266 : 6887484 : }
1267 : :
1268 [ + + ]: 293276 : ERR_IF_1( node->kind != NODE_KIND_LIST, TROT_RC_ERROR_WRONG_KIND, node->kind );
1269 : :
1270 : 293275 : i = (node->count) - 1 - (count - index);
1271 : 293275 : giveBackL = node->l[ i ];
1272 : 293275 : giveBackL->laParent = NULL;
1273 [ + + ]: 690403 : while ( i < ( (node->count) - 1 ) )
1274 : : {
1275 : 397128 : node->l[ i ] = node->l[ i + 1 ];
1276 : 397128 : i += 1;
1277 : : }
1278 : 293275 : node->l[ i ] = NULL;
1279 : 293275 : node->count -= 1;
1280 : 293275 : l->laPointsTo->childrenCount -= 1;
1281 : :
1282 [ + + ]: 293275 : if ( node->count == 0 )
1283 : : {
1284 : 168437 : node->prev->next = node->next;
1285 : 168437 : node->next->prev = node->prev;
1286 : :
1287 : 168437 : trotHookFree( node->l );
1288 : 168437 : trotHookFree( node );
1289 : : }
1290 : :
1291 : : /* give back */
1292 : 293275 : (*lRemoved_A) = giveBackL;
1293 : :
1294 : 293275 : return TROT_RC_SUCCESS;
1295 : :
1296 : :
1297 : : /* CLEANUP */
1298 : : cleanup:
1299 : :
1300 : 293282 : return rc;
1301 : : }
1302 : :
1303 : : /******************************************************************************/
1304 : : /*!
1305 : : \brief Removes whatever is at index in list.
1306 : : \param[in] l The list.
1307 : : \param[in] index What to remove.
1308 : : \return TROT_RC
1309 : : */
1310 : 151858 : TROT_RC trotListRemove( TrotList *l, TROT_INT index )
1311 : : {
1312 : : /* DATA */
1313 : 151858 : TROT_RC rc = TROT_RC_SUCCESS;
1314 : :
1315 : 151858 : TrotListNode *node = NULL;
1316 : :
1317 : 151858 : TROT_INT count = 0;
1318 : :
1319 : 151858 : TrotList *tempL = NULL;
1320 : :
1321 : 151858 : TROT_INT i = 0;
1322 : :
1323 : :
1324 : : /* PRECOND */
1325 [ + + ]: 151858 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1326 : :
1327 : :
1328 : : /* CODE */
1329 : : /* Turn negative index into positive equivalent. */
1330 [ + + ]: 151857 : if ( index < 0 )
1331 : : {
1332 : 20686 : index = (l->laPointsTo->childrenCount) + index + 1;
1333 : : }
1334 : :
1335 : : /* Make sure index is in range */
1336 [ + + ]: 151857 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1337 [ + + ]: 151855 : ERR_IF_1( index > (l->laPointsTo->childrenCount ), TROT_RC_ERROR_BAD_INDEX, index );
1338 : :
1339 : : /* *** */
1340 : 151854 : node = l->laPointsTo->head->next;
1341 : : while ( 1 )
1342 : : {
1343 : 7132612 : count += node->count;
1344 [ + + ]: 7132612 : if ( count >= index )
1345 : : {
1346 : 151854 : break;
1347 : : }
1348 : :
1349 : 6980758 : node = node->next;
1350 : :
1351 : : PARANOID_ERR_IF( node == l->laPointsTo->tail );
1352 : 6980758 : }
1353 : :
1354 : 151854 : i = (node->count) - 1 - (count - index);
1355 [ + + ]: 151854 : if ( node->kind == NODE_KIND_INT )
1356 : : {
1357 [ + + ]: 27129 : while ( i < ( (node->count) - 1 ) )
1358 : : {
1359 : 5310 : node->n[ i ] = node->n[ i + 1 ];
1360 : 5310 : i += 1;
1361 : : }
1362 : : }
1363 : : else
1364 : : {
1365 : 130035 : tempL = node->l[ i ];
1366 : 130035 : tempL->laParent = NULL;
1367 : 130035 : trotListFree( &tempL );
1368 [ + + ]: 529792 : while ( i < ( (node->count) - 1 ) )
1369 : : {
1370 : 399757 : node->l[ i ] = node->l[ i + 1 ];
1371 : 399757 : i += 1;
1372 : : }
1373 : 130035 : node->l[ i ] = NULL;
1374 : : }
1375 : :
1376 : 151854 : node->count -= 1;
1377 : 151854 : l->laPointsTo->childrenCount -= 1;
1378 : :
1379 [ + + ]: 151854 : if ( node->count == 0 )
1380 : : {
1381 : 6948 : node->prev->next = node->next;
1382 : 6948 : node->next->prev = node->prev;
1383 : :
1384 [ + + ]: 6948 : if ( node->kind == NODE_KIND_INT )
1385 : : {
1386 : 2587 : trotHookFree( node->n );
1387 : : }
1388 : : else
1389 : : {
1390 : 4361 : trotHookFree( node->l );
1391 : : }
1392 : 6948 : trotHookFree( node );
1393 : : }
1394 : :
1395 : 151854 : return TROT_RC_SUCCESS;
1396 : :
1397 : :
1398 : : /* CLEANUP */
1399 : : cleanup:
1400 : :
1401 : 151858 : return rc;
1402 : : }
1403 : :
1404 : : /******************************************************************************/
1405 : : /*!
1406 : : \brief Replaces whatever is at index in l with an int.
1407 : : \param[in] l The list.
1408 : : \param[in] index Which item to replace.
1409 : : \param[in] n The int to put at index in l.
1410 : : \return TROT_RC
1411 : : */
1412 : 5089 : TROT_RC trotListReplaceWithInt( TrotList *l, TROT_INT index, TROT_INT n )
1413 : : {
1414 : : /* DATA */
1415 : 5089 : TROT_RC rc = TROT_RC_SUCCESS;
1416 : :
1417 : 5089 : TrotListActual *la = NULL;
1418 : :
1419 : 5089 : TrotListNode *node = NULL;
1420 : :
1421 : 5089 : TROT_INT count = 0;
1422 : :
1423 : 5089 : TrotList *tempL = NULL;
1424 : :
1425 : 5089 : TROT_INT i = 0;
1426 : 5089 : TROT_INT j = 0;
1427 : :
1428 : 5089 : TrotListNode *newNode = NULL;
1429 : :
1430 : :
1431 : : /* PRECOND */
1432 [ + + ]: 5089 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1433 : :
1434 : :
1435 : : /* CODE */
1436 : 5088 : la = l->laPointsTo;
1437 : :
1438 : : /* FUTURE: turn negative into positive, make sure in range, and find node could
1439 : : all be factored out into a function.
1440 : : as well as other code, to make this file smaller */
1441 : : /* Turn negative index into positive equivalent. */
1442 [ + + ]: 5088 : if ( index < 0 )
1443 : : {
1444 : 1525 : index = (la->childrenCount) + index + 1;
1445 : : }
1446 : :
1447 : : /* Make sure index is in range */
1448 [ + + ]: 5088 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1449 [ + + ]: 5086 : ERR_IF_1( index > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, index );
1450 : :
1451 : : /* Find node where int needs to be replaced into */
1452 : 5085 : node = la->head->next;
1453 : : while ( 1 )
1454 : : {
1455 [ + + ]: 35777 : if ( count + (node->count) >= index )
1456 : : {
1457 : 5085 : break;
1458 : : }
1459 : :
1460 : 30692 : count += node->count;
1461 : 30692 : node = node->next;
1462 : :
1463 : : PARANOID_ERR_IF( node == la->tail );
1464 : 30692 : }
1465 : :
1466 : : /* *** */
1467 [ + + ]: 5085 : if ( node->kind == NODE_KIND_INT )
1468 : : {
1469 : 1524 : i = index - count - 1;
1470 : :
1471 : : /* replace int into node */
1472 : 1524 : node->n[ i ] = n;
1473 : : }
1474 : : else /* node->kind == NODE_KIND_LIST */
1475 : : {
1476 : 3561 : i = index - count - 1;
1477 : :
1478 : : /* If at beginning of node */
1479 [ + + ]: 3561 : if ( i == 0 )
1480 : : {
1481 : : /* If the previous node is an int node with space, we
1482 : : can just append in that node. */
1483 [ + + ]: 1951 : if ( node->prev->kind == NODE_KIND_INT
1484 [ + + ]: 1401 : && node->prev->count != NODE_SIZE
1485 : : )
1486 : : {
1487 : : /* append int into prev node */
1488 : 704 : node->prev->n[ node->prev->count ] = n;
1489 : :
1490 : 704 : node->prev->count += 1;
1491 : : }
1492 : : else
1493 : : {
1494 : : /* *** */
1495 : 1247 : rc = newIntNode( &newNode );
1496 [ + + ]: 1247 : ERR_IF_PASSTHROUGH;
1497 : :
1498 : 1245 : newNode->n[ 0 ] = n;
1499 : 1245 : newNode->count = 1;
1500 : :
1501 : : /* Insert node into list */
1502 : 1245 : newNode->next = node;
1503 : 1245 : newNode->prev = node->prev;
1504 : :
1505 : 1245 : node->prev->next = newNode;
1506 : 1949 : node->prev = newNode;
1507 : : }
1508 : : }
1509 : : /* else if end of node */
1510 [ + + ]: 1610 : else if ( i == (node->count) - 1 )
1511 : : {
1512 : : /* if the next node is an int node with room, we can just prepend to
1513 : : that node. */
1514 [ + + ]: 929 : if ( node->next->kind == NODE_KIND_INT
1515 [ + + ]: 685 : && node->next->count != NODE_SIZE
1516 : : )
1517 : : {
1518 : : /* prepend int */
1519 : 6 : j = node->next->count;
1520 [ + + ]: 28 : while ( j != 0 )
1521 : : {
1522 : 22 : node->next->n[ j ] = node->next->n[ j - 1 ];
1523 : 22 : j -= 1;
1524 : : }
1525 : :
1526 : 6 : node->next->n[ 0 ] = n;
1527 : :
1528 : 6 : node->next->count += 1;
1529 : : }
1530 : : else
1531 : : {
1532 : : /* *** */
1533 : 923 : rc = newIntNode( &newNode );
1534 [ + + ]: 923 : ERR_IF_PASSTHROUGH;
1535 : :
1536 : 921 : newNode->n[ 0 ] = n;
1537 : 921 : newNode->count = 1;
1538 : :
1539 : : /* Insert node into list */
1540 : 921 : newNode->prev = node;
1541 : 921 : newNode->next = node->next;
1542 : :
1543 : 921 : node->next->prev = newNode;
1544 : 927 : node->next = newNode;
1545 : : }
1546 : : }
1547 : : /* we'll have to split the node */
1548 : : else
1549 : : {
1550 : 681 : rc = trotListNodeSplit( node, i + 1 );
1551 [ + + ]: 681 : ERR_IF_PASSTHROUGH;
1552 : :
1553 : : /* *** */
1554 : 679 : rc = newIntNode( &newNode );
1555 [ + + ]: 679 : ERR_IF_PASSTHROUGH;
1556 : :
1557 : 677 : newNode->n[ 0 ] = n;
1558 : 677 : newNode->count = 1;
1559 : :
1560 : : /* Insert node into list */
1561 : 677 : newNode->prev = node;
1562 : 677 : newNode->next = node->next;
1563 : :
1564 : 677 : node->next->prev = newNode;
1565 : 677 : node->next = newNode;
1566 : : }
1567 : :
1568 : : /* we've put in our int, now we need to remove a list */
1569 : 3553 : tempL = node->l[ i ];
1570 : 3553 : tempL->laParent = NULL;
1571 : 3553 : trotListFree( &tempL );
1572 [ + + ]: 17052 : while ( i < ( (node->count) - 1 ) )
1573 : : {
1574 : 13499 : node->l[ i ] = node->l[ i + 1 ];
1575 : 13499 : i += 1;
1576 : : }
1577 : 3553 : node->l[ i ] = NULL;
1578 : :
1579 : 3553 : node->count -= 1;
1580 [ + + ]: 3553 : if ( node->count == 0 )
1581 : : {
1582 : 818 : node->prev->next = node->next;
1583 : 818 : node->next->prev = node->prev;
1584 : :
1585 : 818 : trotHookFree( node->l );
1586 : 818 : trotHookFree( node );
1587 : : }
1588 : : }
1589 : :
1590 : :
1591 : : /* CLEANUP */
1592 : : cleanup:
1593 : :
1594 : 5089 : return rc;
1595 : : }
1596 : :
1597 : : /******************************************************************************/
1598 : : /*!
1599 : : \brief Replaces whatever is at index in l with a list.
1600 : : \param[in] l The list.
1601 : : \param[in] index Which item to replace.
1602 : : \param[in[ lToInsert The list to put at index in l.
1603 : : \return TROT_RC
1604 : : */
1605 : 4763 : TROT_RC trotListReplaceWithList( TrotList *l, TROT_INT index, TrotList *lToInsert )
1606 : : {
1607 : : /* DATA */
1608 : 4763 : TROT_RC rc = TROT_RC_SUCCESS;
1609 : :
1610 : 4763 : TrotListActual *la = NULL;
1611 : :
1612 : 4763 : TrotListNode *node = NULL;
1613 : :
1614 : 4763 : TROT_INT count = 0;
1615 : :
1616 : 4763 : TrotList *tempL = NULL;
1617 : :
1618 : 4763 : TrotList *newL = NULL;
1619 : :
1620 : 4763 : TROT_INT i = 0;
1621 : 4763 : TROT_INT j = 0;
1622 : :
1623 : 4763 : TrotListNode *newNode = NULL;
1624 : :
1625 : :
1626 : : /* PRECOND */
1627 [ + + ]: 4763 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1628 [ + + ]: 4762 : ERR_IF( lToInsert == NULL, TROT_RC_ERROR_PRECOND );
1629 : :
1630 : :
1631 : : /* CODE */
1632 : 4761 : la = l->laPointsTo;
1633 : :
1634 : : /* Turn negative index into positive equivalent. */
1635 [ + + ]: 4761 : if ( index < 0 )
1636 : : {
1637 : 1525 : index = (la->childrenCount) + index + 1;
1638 : : }
1639 : :
1640 : : /* Make sure index is in range */
1641 [ + + ]: 4761 : ERR_IF_1( index <= 0, TROT_RC_ERROR_BAD_INDEX, index );
1642 [ + + ]: 4759 : ERR_IF_1( index > (la->childrenCount), TROT_RC_ERROR_BAD_INDEX, index );
1643 : :
1644 : : /* Find node where list needs to be replaced into */
1645 : 4758 : node = la->head->next;
1646 : : while ( 1 )
1647 : : {
1648 [ + + ]: 34358 : if ( count + (node->count) >= index )
1649 : : {
1650 : 4758 : break;
1651 : : }
1652 : :
1653 : 29600 : count += node->count;
1654 : 29600 : node = node->next;
1655 : :
1656 : : PARANOID_ERR_IF( node == la->tail );
1657 : 29600 : }
1658 : :
1659 : : /* create our new twin */
1660 : 4758 : rc = trotListTwin( lToInsert, &newL );
1661 [ + + ]: 4758 : ERR_IF_PASSTHROUGH;
1662 : :
1663 : : /* *** */
1664 [ + + ]: 4755 : if ( node->kind == NODE_KIND_LIST )
1665 : : {
1666 : 1524 : i = index - count - 1;
1667 : :
1668 : : /* free old */
1669 : 1524 : tempL = node->l[ i ];
1670 : 1524 : tempL->laParent = NULL;
1671 : 1524 : trotListFree( &tempL );
1672 : :
1673 : : /* replace with new */
1674 : 1524 : node->l[ i ] = newL;
1675 : 1524 : newL->laParent = la;
1676 : 1524 : newL = NULL;
1677 : : }
1678 : : else /* node->kind == NODE_KIND_INT */
1679 : : {
1680 : 3231 : i = index - count - 1;
1681 : :
1682 : : /* If at beginning of node */
1683 [ + + ]: 3231 : if ( i == 0 )
1684 : : {
1685 : : /* If the previous node is a list node with space, we
1686 : : can just append in that node. */
1687 [ + + ]: 1842 : if ( node->prev->kind == NODE_KIND_LIST
1688 [ + + ]: 1292 : && node->prev->count != NODE_SIZE
1689 : : )
1690 : : {
1691 : : /* append into prev node */
1692 : 704 : node->prev->l[ node->prev->count ] = newL;
1693 : 704 : newL->laParent = la;
1694 : 704 : newL = NULL;
1695 : :
1696 : 704 : node->prev->count += 1;
1697 : : }
1698 : : else
1699 : : {
1700 : : /* *** */
1701 : 1138 : rc = newListNode( &newNode );
1702 [ + + ]: 1138 : ERR_IF_PASSTHROUGH;
1703 : :
1704 : 1136 : newNode->l[ 0 ] = newL;
1705 : 1136 : newL->laParent = la;
1706 : 1136 : newL = NULL;
1707 : :
1708 : 1136 : newNode->count = 1;
1709 : :
1710 : : /* Insert node into list */
1711 : 1136 : newNode->next = node;
1712 : 1136 : newNode->prev = node->prev;
1713 : :
1714 : 1136 : node->prev->next = newNode;
1715 : 1840 : node->prev = newNode;
1716 : : }
1717 : : }
1718 : : /* else if end of node */
1719 [ + + ]: 1389 : else if ( i == (node->count) - 1 )
1720 : : {
1721 : : /* if the next node is a list node with room, we can just prepend to
1722 : : that node. */
1723 [ + + ]: 819 : if ( node->next->kind == NODE_KIND_LIST
1724 [ + + ]: 575 : && node->next->count != NODE_SIZE
1725 : : )
1726 : : {
1727 : : /* prepend int */
1728 : 6 : j = node->next->count;
1729 [ + + ]: 28 : while ( j != 0 )
1730 : : {
1731 : 22 : node->next->l[ j ] = node->next->l[ j - 1 ];
1732 : 22 : j -= 1;
1733 : : }
1734 : :
1735 : 6 : node->next->l[ 0 ] = newL;
1736 : 6 : newL->laParent = la;
1737 : 6 : newL = NULL;
1738 : :
1739 : 6 : node->next->count += 1;
1740 : : }
1741 : : else
1742 : : {
1743 : : /* *** */
1744 : 813 : rc = newListNode( &newNode );
1745 [ + + ]: 813 : ERR_IF_PASSTHROUGH;
1746 : :
1747 : 811 : newNode->l[ 0 ] = newL;
1748 : 811 : newL->laParent = la;
1749 : 811 : newL = NULL;
1750 : :
1751 : 811 : newNode->count = 1;
1752 : :
1753 : : /* Insert node into list */
1754 : 811 : newNode->prev = node;
1755 : 811 : newNode->next = node->next;
1756 : :
1757 : 811 : node->next->prev = newNode;
1758 : 817 : node->next = newNode;
1759 : : }
1760 : : }
1761 : : /* we'll have to split the node */
1762 : : else
1763 : : {
1764 : 570 : rc = trotListNodeSplit( node, i + 1 );
1765 [ + + ]: 570 : ERR_IF_PASSTHROUGH;
1766 : :
1767 : : /* *** */
1768 : 568 : rc = newListNode( &newNode );
1769 [ + + ]: 568 : ERR_IF_PASSTHROUGH;
1770 : :
1771 : 566 : newNode->l[ 0 ] = newL;
1772 : 566 : newL->laParent = la;
1773 : 566 : newL = NULL;
1774 : :
1775 : 566 : newNode->count = 1;
1776 : :
1777 : : /* Insert node into list */
1778 : 566 : newNode->prev = node;
1779 : 566 : newNode->next = node->next;
1780 : :
1781 : 566 : node->next->prev = newNode;
1782 : 566 : node->next = newNode;
1783 : : }
1784 : :
1785 : : /* we've put in our list, now we need to remove an int */
1786 [ + + ]: 15087 : while ( i < ( (node->count) - 1 ) )
1787 : : {
1788 : 11864 : node->n[ i ] = node->n[ i + 1 ];
1789 : 11864 : i += 1;
1790 : : }
1791 : :
1792 : 3223 : node->count -= 1;
1793 [ + + ]: 3223 : if ( node->count == 0 )
1794 : : {
1795 : 818 : node->prev->next = node->next;
1796 : 818 : node->next->prev = node->prev;
1797 : :
1798 : 818 : trotHookFree( node->n );
1799 : 818 : trotHookFree( node );
1800 : : }
1801 : : }
1802 : :
1803 : :
1804 : : /* CLEANUP */
1805 : : cleanup:
1806 : :
1807 : 4763 : trotListFree( &newL );
1808 : :
1809 : 4763 : return rc;
1810 : : }
1811 : :
1812 : : /******************************************************************************/
1813 : : /*!
1814 : : \brief Gets tag of list.
1815 : : \param[in] l The list.
1816 : : \param[out] tag The tag of the list.
1817 : : \return TROT_RC
1818 : : */
1819 : 102034 : TROT_RC trotListGetTag( TrotList *l, TROT_INT *tag )
1820 : : {
1821 : : /* DATA */
1822 : 102034 : TROT_RC rc = TROT_RC_SUCCESS;
1823 : :
1824 : :
1825 : : /* PRECOND */
1826 [ + + ]: 102034 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1827 [ + + ]: 102033 : ERR_IF( tag == NULL, TROT_RC_ERROR_PRECOND );
1828 : :
1829 : :
1830 : : /* CODE */
1831 : 102032 : (*tag) = l->laPointsTo->tag;
1832 : :
1833 : :
1834 : : /* CLEANUP */
1835 : : cleanup:
1836 : :
1837 : 102034 : return rc;
1838 : : }
1839 : :
1840 : : /******************************************************************************/
1841 : : /*!
1842 : : \brief Sets tag of list.
1843 : : \param[in] l The list.
1844 : : \param[in] tag Tag value to set.
1845 : : \return TROT_RC
1846 : : */
1847 : 21951 : TROT_RC trotListSetTag( TrotList *l, TROT_INT tag )
1848 : : {
1849 : : /* DATA */
1850 : 21951 : TROT_RC rc = TROT_RC_SUCCESS;
1851 : :
1852 : :
1853 : : /* PRECOND */
1854 [ + + ]: 21951 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1855 : :
1856 : :
1857 : : /* CODE */
1858 [ + + ][ + + ]: 21950 : ERR_IF_1( tag < TROT_TAG_MIN || tag > TROT_TAG_MAX, TROT_RC_ERROR_BAD_TAG, tag );
1859 : :
1860 : 21946 : l->laPointsTo->tag = tag;
1861 : :
1862 : :
1863 : : /* CLEANUP */
1864 : : cleanup:
1865 : :
1866 : 21951 : return rc;
1867 : : }
1868 : :
1869 : : /******************************************************************************/
1870 : : /*!
1871 : : \brief Gets user tag of list.
1872 : : \param[in] l The list.
1873 : : \param[out] tag The user tag of the list.
1874 : : \return TROT_RC
1875 : : */
1876 : 220 : TROT_RC trotListGetUserTag( TrotList *l, TROT_INT *tag )
1877 : : {
1878 : : /* DATA */
1879 : 220 : TROT_RC rc = TROT_RC_SUCCESS;
1880 : :
1881 : :
1882 : : /* PRECOND */
1883 [ + + ]: 220 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1884 [ + + ]: 219 : ERR_IF( tag == NULL, TROT_RC_ERROR_PRECOND );
1885 : :
1886 : :
1887 : : /* CODE */
1888 : 218 : (*tag) = l->laPointsTo->userTag;
1889 : :
1890 : :
1891 : : /* CLEANUP */
1892 : : cleanup:
1893 : :
1894 : 220 : return rc;
1895 : : }
1896 : :
1897 : : /******************************************************************************/
1898 : : /*!
1899 : : \brief Sets the uer tag of a list.
1900 : : \param[in] l The list.
1901 : : \param[in] tag The tag value to set.
1902 : : \return TROT_RC
1903 : : */
1904 : 20637 : TROT_RC trotListSetUserTag( TrotList *l, TROT_INT tag )
1905 : : {
1906 : : /* DATA */
1907 : 20637 : TROT_RC rc = TROT_RC_SUCCESS;
1908 : :
1909 : :
1910 : : /* PRECOND */
1911 [ + + ]: 20637 : ERR_IF( l == NULL, TROT_RC_ERROR_PRECOND );
1912 : :
1913 : :
1914 : : /* CODE */
1915 : 20636 : l->laPointsTo->userTag = tag;
1916 : :
1917 : :
1918 : : /* CLEANUP */
1919 : : cleanup:
1920 : :
1921 : 20637 : return rc;
1922 : : }
1923 : :
1924 : : /******************************************************************************/
1925 : : /*!
1926 : : \brief Splits a node, leaving keepInLeft into the left/prev node, and
1927 : : moving the rest into the new right/next node.
1928 : : \param[in] n Node to split.
1929 : : \param[in] keepInLeft How many items to keep in n.
1930 : : \return TROT_RC
1931 : : */
1932 : 70423 : TROT_RC trotListNodeSplit( TrotListNode *n, TROT_INT keepInLeft )
1933 : : {
1934 : : /* DATA */
1935 : 70423 : TROT_RC rc = TROT_RC_SUCCESS;
1936 : :
1937 : 70423 : TrotListNode *newNode = NULL;
1938 : :
1939 : 70423 : TROT_INT i = 0;
1940 : :
1941 : :
1942 : : /* PRECOND */
1943 : : PARANOID_ERR_IF( n == NULL );
1944 : :
1945 : :
1946 : : /* CODE */
1947 [ + + ]: 70423 : TROT_MALLOC( newNode, TrotListNode, 1 );
1948 : :
1949 [ + + ]: 70414 : if ( n->kind == NODE_KIND_INT )
1950 : : {
1951 : 14332 : newNode->kind = NODE_KIND_INT;
1952 : 14332 : newNode->count = (n->count) - keepInLeft;
1953 : :
1954 : 14332 : newNode->l = NULL;
1955 [ + + ]: 14332 : TROT_MALLOC( newNode->n, TROT_INT, NODE_SIZE );
1956 : :
1957 : 14328 : i = keepInLeft;
1958 [ + + ]: 121349 : while ( i < (n->count) )
1959 : : {
1960 : 107021 : newNode->n[ i - keepInLeft ] = n->n[ i ];
1961 : :
1962 : 107021 : i += 1;
1963 : : }
1964 : :
1965 : 14328 : n->count = keepInLeft;
1966 : : }
1967 : : else /* n->kind == NODE_KIND_LIST */
1968 : : {
1969 : 56082 : newNode->kind = NODE_KIND_LIST;
1970 : 56082 : newNode->count = (n->count) - keepInLeft;
1971 : :
1972 : 56082 : newNode->n = NULL;
1973 [ + + ]: 56082 : TROT_CALLOC( newNode->l, TrotList *, NODE_SIZE );
1974 : :
1975 : 56077 : i = keepInLeft;
1976 [ + + ]: 482645 : while ( i < (n->count) )
1977 : : {
1978 : 426568 : newNode->l[ i - keepInLeft ] = n->l[ i ];
1979 : 426568 : n->l[ i ] = NULL;
1980 : :
1981 : 426568 : i += 1;
1982 : : }
1983 : :
1984 : 56077 : n->count = keepInLeft;
1985 : : }
1986 : :
1987 : 70405 : newNode->prev = n;
1988 : 70405 : newNode->next = n->next;
1989 : :
1990 : 70405 : n->next->prev = newNode;
1991 : 70405 : n->next = newNode;
1992 : :
1993 : 70405 : return TROT_RC_SUCCESS;
1994 : :
1995 : :
1996 : : /* CLEANUP */
1997 : : cleanup:
1998 : :
1999 : 18 : trotHookFree( newNode );
2000 : :
2001 : 70423 : return rc;
2002 : : }
2003 : :
2004 : : /******************************************************************************/
2005 : : /*!
2006 : : \brief Creates a new TrotListNode for Int.
2007 : : \param[out] n_A On success, the new node.
2008 : : \return TROT_RC
2009 : : */
2010 : 5129551 : TROT_RC newIntNode( TrotListNode **n_A )
2011 : : {
2012 : : /* DATA */
2013 : 5129551 : TROT_RC rc = TROT_RC_SUCCESS;
2014 : :
2015 : 5129551 : TrotListNode *newNode = NULL;
2016 : :
2017 : :
2018 : : /* PRECOND */
2019 : : PARANOID_ERR_IF( n_A == NULL );
2020 : : PARANOID_ERR_IF( (*n_A) != NULL );
2021 : :
2022 : :
2023 : : /* CODE */
2024 [ + + ]: 5129551 : TROT_MALLOC( newNode, TrotListNode, 1 );
2025 : :
2026 : 5128372 : newNode->kind = NODE_KIND_INT;
2027 : 5128372 : newNode->count = 0;
2028 : :
2029 : 5128372 : newNode->l = NULL;
2030 [ + + ]: 5128372 : TROT_MALLOC( newNode->n, TROT_INT, NODE_SIZE );
2031 : :
2032 : : /* give back */
2033 : 5127193 : (*n_A) = newNode;
2034 : 5127193 : newNode = NULL;
2035 : :
2036 : 5127193 : return TROT_RC_SUCCESS;
2037 : :
2038 : :
2039 : : /* CLEANUP */
2040 : : cleanup:
2041 : :
2042 : 2358 : trotHookFree( newNode );
2043 : :
2044 : 5129551 : return rc;
2045 : : }
2046 : :
2047 : : /******************************************************************************/
2048 : : /*!
2049 : : \brief Creates a new TrotListNode for List.
2050 : : \param[out] n_A On success, the new node.
2051 : : \return TROT_RC
2052 : : */
2053 : 728750 : TROT_RC newListNode( TrotListNode **n_A )
2054 : : {
2055 : : /* DATA */
2056 : 728750 : TROT_RC rc = TROT_RC_SUCCESS;
2057 : :
2058 : 728750 : TrotListNode *newNode = NULL;
2059 : :
2060 : :
2061 : : /* PRECOND */
2062 : : PARANOID_ERR_IF( n_A == NULL );
2063 : : PARANOID_ERR_IF( (*n_A) != NULL );
2064 : :
2065 : :
2066 : : /* CODE */
2067 [ + + ]: 728750 : TROT_MALLOC( newNode, TrotListNode, 1 );
2068 : :
2069 : 728228 : newNode->kind = NODE_KIND_LIST;
2070 : 728228 : newNode->count = 0;
2071 : :
2072 : 728228 : newNode->n = NULL;
2073 [ + + ]: 728228 : TROT_CALLOC( newNode->l, TrotList *, NODE_SIZE );
2074 : :
2075 : : /* give back */
2076 : 727706 : (*n_A) = newNode;
2077 : 727706 : newNode = NULL;
2078 : :
2079 : 727706 : return TROT_RC_SUCCESS;
2080 : :
2081 : :
2082 : : /* CLEANUP */
2083 : : cleanup:
2084 : :
2085 : 1044 : trotHookFree( newNode );
2086 : :
2087 : 728750 : return rc;
2088 : : }
2089 : :
2090 : : /******************************************************************************/
2091 : 16067078 : static TROT_RC refListAdd( TrotListActual *la, TrotList *l )
2092 : : {
2093 : : /* DATA */
2094 : 16067078 : TROT_RC rc = TROT_RC_SUCCESS;
2095 : :
2096 : 16067078 : TrotListRefListNode *refNode = NULL;
2097 : :
2098 : 16067078 : TrotListRefListNode *newRefNode = NULL;
2099 : :
2100 : :
2101 : : /* PRECOND */
2102 : : PARANOID_ERR_IF( la == NULL );
2103 : : PARANOID_ERR_IF( l == NULL );
2104 : :
2105 : :
2106 : : /* CODE */
2107 : 16067078 : refNode = la->refListHead->next;
2108 [ + + ]: 17002180 : while ( refNode != la->refListTail )
2109 : : {
2110 [ + + ]: 12038115 : if ( refNode->count < REF_LIST_NODE_SIZE )
2111 : : {
2112 : 11103013 : refNode->l[ refNode->count ] = l;
2113 : 11103013 : refNode->count += 1;
2114 : :
2115 : 11103013 : return TROT_RC_SUCCESS;
2116 : : }
2117 : :
2118 : 935102 : refNode = refNode->next;
2119 : : }
2120 : :
2121 : : /* there was no room in list, so create new node, insert ref into new
2122 : : node, and insert node into list */
2123 [ + + ]: 4964065 : TROT_MALLOC( newRefNode, TrotListRefListNode, 1 );
2124 : :
2125 [ + + ]: 4963127 : TROT_CALLOC( newRefNode->l, TrotList *, REF_LIST_NODE_SIZE );
2126 : :
2127 : 4962189 : newRefNode->count = 1;
2128 : 4962189 : newRefNode->l[ 0 ] = l;
2129 : :
2130 : 4962189 : newRefNode->prev = la->refListTail->prev;
2131 : 4962189 : newRefNode->next = la->refListTail;
2132 : 4962189 : la->refListTail->prev->next = newRefNode;
2133 : 4962189 : la->refListTail->prev = newRefNode;
2134 : :
2135 : 4962189 : return TROT_RC_SUCCESS;
2136 : :
2137 : :
2138 : : /* CLEANUP */
2139 : : cleanup:
2140 : :
2141 : 1876 : trotHookFree( newRefNode );
2142 : :
2143 : 16067078 : return rc;
2144 : : }
2145 : :
2146 : : /******************************************************************************/
2147 : 16065202 : static void refListRemove( TrotListActual *la, TrotList *l )
2148 : : {
2149 : : /* DATA */
2150 : 16065202 : TrotListRefListNode *refNode = NULL;
2151 : :
2152 : 16065202 : TROT_INT i = 0;
2153 : :
2154 : :
2155 : : /* PRECOND */
2156 : : PARANOID_ERR_IF( la == NULL );
2157 : : PARANOID_ERR_IF( l == NULL );
2158 : :
2159 : :
2160 : : /* CODE */
2161 : : /* foreach refNode */
2162 : 16065202 : refNode = la->refListHead->next;
2163 : : while ( 1 )
2164 : : {
2165 : : /* foreach pointer in this node */
2166 : 16872474 : i = 0;
2167 [ + + ]: 38217108 : while ( i < refNode->count )
2168 : : {
2169 : : /* is this the ref we're looking for? */
2170 [ + + ]: 37409836 : if ( refNode->l[ i ] == l )
2171 : : {
2172 : : /* found, now remove it */
2173 [ + + ]: 20023192 : while ( i < ( ( refNode->count ) - 1 ) )
2174 : : {
2175 : 3957990 : refNode->l[ i ] = refNode->l[ i + 1 ];
2176 : :
2177 : 3957990 : i += 1;
2178 : : }
2179 : :
2180 : 16065202 : refNode->l[ i ] = NULL;
2181 : :
2182 : 16065202 : refNode->count -= 1;
2183 : :
2184 : : /* remove node if node is empty */
2185 [ + + ]: 16065202 : if ( refNode->count == 0 )
2186 : : {
2187 : 4962189 : refNode->prev->next = refNode->next;
2188 : 4962189 : refNode->next->prev = refNode->prev;
2189 : :
2190 : 4962189 : trotHookFree( refNode->l );
2191 : 4962189 : trotHookFree( refNode );
2192 : : }
2193 : :
2194 : 16065202 : return;
2195 : : }
2196 : :
2197 : 21344634 : i += 1;
2198 : : }
2199 : :
2200 : 807272 : refNode = refNode->next;
2201 : :
2202 : : PARANOID_ERR_IF( refNode == la->refListTail );
2203 : 807272 : }
2204 : :
2205 : : PARANOID_ERR_IF( 1 );
2206 : :
2207 : : return;
2208 : : }
2209 : :
2210 : : /******************************************************************************/
2211 : 15756155 : static void isListReachable( TrotListActual *la )
2212 : : {
2213 : : /* DATA */
2214 : 15756155 : int flagFoundClientRef = 0;
2215 : :
2216 : 15756155 : TrotListActual *currentLa = NULL;
2217 : :
2218 : 15756155 : TrotListActual *parent = NULL;
2219 : :
2220 : 15756155 : TrotListActual *tempLa = NULL;
2221 : :
2222 : :
2223 : : /* PRECOND */
2224 : : PARANOID_ERR_IF( la == NULL );
2225 : : PARANOID_ERR_IF( la->reachable == 0 );
2226 : :
2227 : :
2228 : : /* CODE */
2229 : : /* go "up" trying to find a client ref */
2230 : 15756155 : currentLa = la;
2231 : 15756155 : currentLa->flagVisited = 1;
2232 : :
2233 : : while ( 1 )
2234 : : {
2235 [ + + ]: 26879858 : if ( findNextParent( currentLa, 0, &parent ) != 0 )
2236 : : {
2237 [ + + ]: 5164969 : if ( currentLa->previous != NULL )
2238 : : {
2239 : 218912 : tempLa = currentLa;
2240 : 218912 : currentLa = currentLa->previous;
2241 : 218912 : tempLa->previous = NULL;
2242 : :
2243 : 218912 : continue;
2244 : : }
2245 : :
2246 : 4946057 : break;
2247 : : }
2248 : :
2249 : : /* did we find a client ref? */
2250 [ + + ]: 21714889 : if ( parent == NULL )
2251 : : {
2252 : 10810098 : flagFoundClientRef = 1;
2253 : 10810098 : break;
2254 : : }
2255 : :
2256 : 10904791 : parent->previous = currentLa;
2257 : 10904791 : currentLa = parent;
2258 : 10904791 : currentLa->flagVisited = 1;
2259 : 11123703 : }
2260 : :
2261 [ + + ]: 15756155 : if ( ! flagFoundClientRef )
2262 : : {
2263 : 4946057 : la->reachable = 0;
2264 : : }
2265 : :
2266 : : /* restart, go "up", resetting all the flagVisited flags to 0 */
2267 : 15756155 : currentLa = la;
2268 : 15756155 : currentLa->flagVisited = 0;
2269 : :
2270 : : while ( 1 )
2271 : : {
2272 [ + + ]: 37565737 : if ( findNextParent( currentLa, 1, &parent ) != 0 )
2273 : : {
2274 [ + + ]: 26660946 : if ( currentLa->previous != NULL )
2275 : : {
2276 : 10904791 : tempLa = currentLa;
2277 : 10904791 : currentLa = currentLa->previous;
2278 : 10904791 : tempLa->previous = NULL;
2279 : :
2280 : 10904791 : continue;
2281 : : }
2282 : :
2283 : 15756155 : break;
2284 : : }
2285 : :
2286 : 10904791 : parent->previous = currentLa;
2287 : 10904791 : currentLa = parent;
2288 : 10904791 : currentLa->flagVisited = 0;
2289 : 37565737 : }
2290 : :
2291 : 15756155 : return;
2292 : : }
2293 : :
2294 : : /******************************************************************************/
2295 : 64445595 : static TROT_INT findNextParent( TrotListActual *la, TROT_INT queryVisited, TrotListActual **parent )
2296 : : {
2297 : : /* DATA */
2298 : 64445595 : TrotListRefListNode *refNode = NULL;
2299 : :
2300 : 64445595 : TROT_INT i = 0;
2301 : :
2302 : 64445595 : TrotListActual *tempParent = NULL;
2303 : :
2304 : :
2305 : : /* PRECOND */
2306 : : PARANOID_ERR_IF( la == NULL );
2307 : : PARANOID_ERR_IF( parent == NULL );
2308 : :
2309 : :
2310 : : /* CODE */
2311 : : /* for each reference that points to this list */
2312 : 64445595 : refNode = la->refListHead;
2313 [ + + ]: 159801787 : while ( refNode != la->refListTail )
2314 : : {
2315 : 127975872 : i = 0;
2316 [ + + ]: 251480400 : while ( i < refNode->count )
2317 : : {
2318 : : /* get list this ref is in */
2319 : 156124208 : tempParent = refNode->l[ i ]->laParent;
2320 : :
2321 : : /* if ref has no parent, it means it's a client
2322 : : reference, and so the list is reachable, but we only
2323 : : care if our caller is looking for not visited
2324 : : parents */
2325 [ + + ]: 156124208 : if ( tempParent == NULL )
2326 : : {
2327 [ + + ]: 22647572 : if ( queryVisited == 0 )
2328 : : {
2329 : 10810098 : (*parent) = NULL;
2330 : 10810098 : return 0;
2331 : : }
2332 : : }
2333 : : /* if this matches our 'visit' query, then return it */
2334 [ + + ]: 133476636 : else if ( tempParent->flagVisited == queryVisited )
2335 : : {
2336 : 21809582 : (*parent) = tempParent;
2337 : 21809582 : return 0;
2338 : : }
2339 : :
2340 : 123504528 : i += 1;
2341 : : }
2342 : :
2343 : 95356192 : refNode = refNode->next;
2344 : : }
2345 : :
2346 : 64445595 : return -1;
2347 : : }
2348 : :
2349 : : /******************************************************************************/
2350 : : /*!
2351 : : \brief Provides a const char string representation for a TROT_RC
2352 : : \param[in] rc A TROT_RC value.
2353 : : \return A const char representation of the passed in TROT_RC.
2354 : : */
2355 : 11 : const char *trotRCToString( TROT_RC rc )
2356 : : {
2357 : : static const char *_rcStrings[] =
2358 : : {
2359 : : "Success",
2360 : :
2361 : : "Precondition Error",
2362 : : "Memory Allocation Error",
2363 : : "Standard Library Error",
2364 : :
2365 : : "Bad Index Error",
2366 : : "Wrong Kind Error",
2367 : : "List Overflow Error",
2368 : : "Invalid Op Error",
2369 : : "Bad Tag Error",
2370 : : "Divide By Zero Error",
2371 : : "Unicode Error",
2372 : : "Decode Error"
2373 : : };
2374 : :
2375 : : static const char *_rcUnknown = "Unknown Error";
2376 : :
2377 [ + + ][ + + ]: 11 : if ( rc >= 0 && rc <= TROT_RC_STANDARD_ERRORS_MAX )
2378 : : {
2379 : 4 : return _rcStrings[ rc ];
2380 : : }
2381 [ + + ][ + + ]: 7 : else if ( rc >= TROT_RC_TROT_ERRORS_MIN && rc <= TROT_RC_TROT_ERRORS_MAX )
2382 : : {
2383 : 2 : return _rcStrings[ TROT_RC_STANDARD_ERRORS_MAX + rc - TROT_RC_TROT_ERRORS_MIN + 1 ];
2384 : : }
2385 : :
2386 : 11 : return _rcUnknown;
2387 : : }
2388 : :
|
