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 : : Only used during Compare.
34 : : Keeps track of a stack of two lists we're comparing.
35 : : Used for comparing, and so we don't get into an infinite loop.
36 : :
37 : : FUTURE: This can go away once we move things out of the library and into
38 : : Trot itself. Should we go ahead and remove it now?
39 : : */
40 : : #define TROT_FILE_NUMBER 10
41 : :
42 : : /******************************************************************************/
43 : : #include "trot.h"
44 : : #include "trotInternal.h"
45 : :
46 : : /******************************************************************************/
47 : : /*!
48 : : \brief Creates a new stack.
49 : : \param[out] stack The new stack.
50 : : \return TROT_RC
51 : : */
52 : 127830 : TROT_RC trotStackInit( TrotStack **stack )
53 : : {
54 : : /* DATA */
55 : 127830 : TROT_RC rc = TROT_RC_SUCCESS;
56 : :
57 : 127830 : TrotStack *newStack = NULL;
58 : :
59 : 127830 : TrotStackNode *newHead = NULL;
60 : 127830 : TrotStackNode *newTail = NULL;
61 : :
62 : :
63 : : /* CODE */
64 : : PARANOID_ERR_IF( stack == NULL );
65 : : PARANOID_ERR_IF( (*stack) != NULL );
66 : :
67 [ + + ]: 127830 : TROT_MALLOC( newHead, TrotStackNode, 1 );
68 [ + + ]: 127828 : TROT_MALLOC( newTail, TrotStackNode, 1 );
69 [ + + ]: 127826 : TROT_MALLOC( newStack, TrotStack, 1 );
70 : :
71 : 127824 : newHead->la1 = NULL;
72 : 127824 : newHead->la1Node = NULL;
73 : 127824 : newHead->la1Count = 0;
74 : 127824 : newHead->la2 = NULL;
75 : 127824 : newHead->la2Node = NULL;
76 : 127824 : newHead->la2Count = 0;
77 : 127824 : newHead->index = 0;
78 : 127824 : newHead->prev = newHead;
79 : 127824 : newHead->next = newTail;
80 : :
81 : 127824 : newTail->la1 = NULL;
82 : 127824 : newTail->la1Node = NULL;
83 : 127824 : newTail->la1Count = 0;
84 : 127824 : newTail->la2 = NULL;
85 : 127824 : newTail->la2Node = NULL;
86 : 127824 : newTail->la2Count = 0;
87 : 127824 : newTail->index = 0;
88 : 127824 : newTail->prev = newHead;
89 : 127824 : newTail->next = newTail;
90 : :
91 : 127824 : newStack->head = newHead;
92 : 127824 : newStack->tail = newTail;
93 : 127824 : newHead = NULL;
94 : 127824 : newTail = NULL;
95 : :
96 : : /* give back */
97 : 127824 : (*stack) = newStack;
98 : 127824 : newStack = NULL;
99 : :
100 : :
101 : : /* CLEANUP */
102 : : cleanup:
103 : :
104 : 127830 : trotHookFree( newHead );
105 : 127830 : trotHookFree( newTail );
106 : 127830 : trotHookFree( newStack );
107 : :
108 : 127830 : return rc;
109 : : }
110 : :
111 : : /******************************************************************************/
112 : : /*!
113 : : \brief Frees a stack.
114 : : \param[in] stack The stack.
115 : : \return void
116 : : */
117 : 127833 : void trotStackFree( TrotStack **stack )
118 : : {
119 : : /* DATA */
120 : 127833 : TrotStackNode *node = NULL;
121 : :
122 : :
123 : : /* CODE */
124 : : PARANOID_ERR_IF( stack == NULL );
125 : :
126 [ + + ]: 127833 : if ( (*stack) == NULL )
127 : : {
128 : 9 : return;
129 : : }
130 : :
131 : 127824 : node = (*stack)->head;
132 [ + + ]: 307624 : while ( node != (*stack)->tail )
133 : : {
134 : 179800 : node = node->next;
135 : :
136 : 179800 : trotHookFree( node->prev );
137 : : }
138 : :
139 : 127824 : trotHookFree( (*stack)->tail );
140 : :
141 : 127824 : trotHookFree( (*stack) );
142 : 127824 : (*stack) = NULL;
143 : :
144 : 127833 : return;
145 : : }
146 : :
147 : : /******************************************************************************/
148 : : /*!
149 : : \brief Pushes a new node on the stack .
150 : : \param[in] stack The stack.
151 : : \param[in] la1 The first list.
152 : : \param[in] la2 The second list.
153 : : \return TROT_RC
154 : : */
155 : 1509580 : TROT_RC trotStackPush( TrotStack *stack, TrotListActual *la1, TrotListActual *la2 )
156 : : {
157 : : /* DATA */
158 : 1509580 : TROT_RC rc = TROT_RC_SUCCESS;
159 : :
160 : 1509580 : TrotStackNode *node = NULL;
161 : :
162 : 1509580 : TrotStackNode *newNode = NULL;
163 : :
164 : :
165 : : /* CODE */
166 : : PARANOID_ERR_IF( stack == NULL );
167 : :
168 : : /* are these two lists already in the stack? */
169 : 1509580 : node = stack->head->next;
170 [ + + ]: 2890508 : while ( node != stack->tail )
171 : : {
172 [ + + ][ + + ]: 1381756 : if ( ( node->la1 == la1 && node->la2 == la2 )
173 [ + + ][ + + ]: 1381000 : || ( node->la1 == la2 && node->la2 == la1 )
174 : : )
175 : : {
176 : : /* yes, so nothing to do */
177 : 828 : return TROT_RC_SUCCESS;
178 : : }
179 : :
180 : 1380928 : node = node->next;
181 : : }
182 : :
183 : : /* not already in stack, so lets add */
184 [ + + ]: 1508752 : TROT_MALLOC( newNode, TrotStackNode, 1 );
185 : :
186 : 1508749 : newNode->la1 = la1;
187 : 1508749 : newNode->la1Node = la1->head;
188 : 1508749 : newNode->la1Count = 0;
189 : 1508749 : newNode->la2 = la2;
190 : 1508749 : newNode->la2Node = la2->head;
191 : 1508749 : newNode->la2Count = 0;
192 : 1508749 : newNode->index = 0;
193 : 1508749 : newNode->next = stack->tail;
194 : 1508749 : newNode->prev = stack->tail->prev;
195 : :
196 : 1508749 : stack->tail->prev->next = newNode;
197 : 1508749 : stack->tail->prev = newNode;
198 : :
199 : 1508749 : return TROT_RC_SUCCESS;
200 : :
201 : :
202 : : /* CLEANUP */
203 : : cleanup:
204 : :
205 : 1509580 : return rc;
206 : : }
207 : :
208 : : /******************************************************************************/
209 : : /*!
210 : : \brief Pops off the top of the stack.
211 : : \param[in] stack The stack.
212 : : \param[out] empty Will be 1 if stack is empty, or 0 if stack
213 : : has items still on it.
214 : : \return TROT_RC
215 : : */
216 : 1456773 : TROT_RC trotStackPop( TrotStack *stack, TROT_INT *empty )
217 : : {
218 : : /* DATA */
219 : 1456773 : TrotStackNode *node = NULL;
220 : :
221 : :
222 : : /* CODE */
223 : : PARANOID_ERR_IF( stack == NULL );
224 : : PARANOID_ERR_IF( empty == NULL );
225 : :
226 : : PARANOID_ERR_IF( stack->tail->prev == stack->head );
227 : :
228 : 1456773 : node = stack->tail->prev;
229 : :
230 : 1456773 : node->prev->next = node->next;
231 : 1456773 : node->next->prev = node->prev;
232 : :
233 : 1456773 : trotHookFree( node );
234 : :
235 [ + + ]: 1456773 : if ( stack->tail->prev == stack->head )
236 : : {
237 : 90519 : (*empty) = 1;
238 : : }
239 : : else
240 : : {
241 : 1366254 : (*empty) = 0;
242 : : }
243 : :
244 : 1456773 : return TROT_RC_SUCCESS;
245 : : }
246 : :
247 : : /******************************************************************************/
248 : : /*!
249 : : \brief Increments the data on top the stack.
250 : : \param[in] stack The stack.
251 : : \return TROT_RC
252 : : */
253 : 5629570 : TROT_RC trotStackIncrementTopIndex( TrotStack *stack )
254 : : {
255 : : /* DATA */
256 : 5629570 : TrotStackNode *stackNode = NULL;
257 : :
258 : : /* CODE */
259 : : PARANOID_ERR_IF( stack == NULL );
260 : :
261 : : PARANOID_ERR_IF( stack->tail->prev == stack->head );
262 : :
263 : 5629570 : stackNode = stack->tail->prev;
264 : :
265 : 5629570 : stackNode->index += 1;
266 : :
267 : 5629570 : stackNode->la1Count += 1;
268 [ + + ]: 5629570 : if ( stackNode->la1Count >= stackNode->la1Node->count )
269 : : {
270 : 3954638 : stackNode->la1Node = stackNode->la1Node->next;
271 : 3954638 : stackNode->la1Count = 0;
272 : : }
273 : :
274 : 5629570 : stackNode->la2Count += 1;
275 [ + + ]: 5629570 : if ( stackNode->la2Count >= stackNode->la2Node->count )
276 : : {
277 : 3954638 : stackNode->la2Node = stackNode->la2Node->next;
278 : 3954638 : stackNode->la2Count = 0;
279 : : }
280 : :
281 : 5629570 : return TROT_RC_SUCCESS;
282 : : }
283 : :
|
