1/*
2 * Legal Notice
3 *
4 * This document and associated source code (the "Work") is a part of a
5 * benchmark specification maintained by the TPC.
6 *
7 * The TPC reserves all right, title, and interest to the Work as provided
8 * under U.S. and international laws, including without limitation all patent
9 * and trademark rights therein.
10 *
11 * No Warranty
12 *
13 * 1.1 TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, THE INFORMATION
14 * CONTAINED HEREIN IS PROVIDED "AS IS" AND WITH ALL FAULTS, AND THE
15 * AUTHORS AND DEVELOPERS OF THE WORK HEREBY DISCLAIM ALL OTHER
16 * WARRANTIES AND CONDITIONS, EITHER EXPRESS, IMPLIED OR STATUTORY,
17 * INCLUDING, BUT NOT LIMITED TO, ANY (IF ANY) IMPLIED WARRANTIES,
18 * DUTIES OR CONDITIONS OF MERCHANTABILITY, OF FITNESS FOR A PARTICULAR
19 * PURPOSE, OF ACCURACY OR COMPLETENESS OF RESPONSES, OF RESULTS, OF
20 * WORKMANLIKE EFFORT, OF LACK OF VIRUSES, AND OF LACK OF NEGLIGENCE.
21 * ALSO, THERE IS NO WARRANTY OR CONDITION OF TITLE, QUIET ENJOYMENT,
22 * QUIET POSSESSION, CORRESPONDENCE TO DESCRIPTION OR NON-INFRINGEMENT
23 * WITH REGARD TO THE WORK.
24 * 1.2 IN NO EVENT WILL ANY AUTHOR OR DEVELOPER OF THE WORK BE LIABLE TO
25 * ANY OTHER PARTY FOR ANY DAMAGES, INCLUDING BUT NOT LIMITED TO THE
26 * COST OF PROCURING SUBSTITUTE GOODS OR SERVICES, LOST PROFITS, LOSS
27 * OF USE, LOSS OF DATA, OR ANY INCIDENTAL, CONSEQUENTIAL, DIRECT,
28 * INDIRECT, OR SPECIAL DAMAGES WHETHER UNDER CONTRACT, TORT, WARRANTY,
29 * OR OTHERWISE, ARISING IN ANY WAY OUT OF THIS OR ANY OTHER AGREEMENT
30 * RELATING TO THE WORK, WHETHER OR NOT SUCH AUTHOR OR DEVELOPER HAD
31 * ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.
32 *
33 * Contributors:
34 * Gradient Systems
35 */
36#include "config.h"
37#include "porting.h"
38#include <stdio.h>
39#include <assert.h>
40#include "list.h"
41#include "error_msg.h"
42
43list_t *makeList(int nFlags, int (*SortFunc)(const void *d1, const void *d2)) {
44 list_t *pRes;
45
46 pRes = (list_t *)malloc(sizeof(list_t));
47 MALLOC_CHECK(pRes);
48 if (pRes == NULL)
49 ReportError(QERR_NO_MEMORY, "client list", 1);
50 memset(pRes, 0, sizeof(list_t));
51 pRes->nFlags = nFlags;
52 pRes->pSortFunc = SortFunc;
53
54 return (pRes);
55}
56
57list_t *addList(list_t *pList, void *pData) {
58 node_t *pNode;
59 node_t *pInsertPoint;
60 int bMoveForward = (pList->nFlags & L_FL_HEAD);
61
62 pNode = (node_t *)malloc(sizeof(node_t));
63 MALLOC_CHECK(pNode);
64 if (!pNode)
65 ReportErrorNoLine(QERR_NO_MEMORY, "client node", 1);
66 memset(pNode, 0, sizeof(node_t));
67 pNode->pData = pData;
68
69 if (pList->nMembers == 0) /* first node */
70 {
71 pList->head = pNode;
72 pList->tail = pNode;
73 pList->nMembers = 1;
74 return (pList);
75 }
76
77 if (pList->nFlags & L_FL_SORT) {
78 if (pList->pSortFunc(pData, pList->head->pData) <= 0) {
79 /* new node become list head */
80 pNode->pNext = pList->head;
81 pList->head->pPrev = pNode;
82 pList->head = pNode;
83 pList->nMembers += 1;
84 return (pList);
85 }
86 pInsertPoint = pList->head;
87
88 /* find the correct point to insert new node */
89 while (pInsertPoint) {
90 if (pList->pSortFunc(pInsertPoint->pData, pData) < 0)
91 break;
92 pInsertPoint = (bMoveForward) ? pInsertPoint->pNext : pInsertPoint->pPrev;
93 }
94 if (pInsertPoint) /* mid-list insert */
95 {
96 pNode->pNext = pInsertPoint->pNext;
97 pNode->pPrev = pInsertPoint;
98 pInsertPoint->pNext = pNode;
99 } else {
100 if (bMoveForward) {
101 /* new node becomes list tail */
102 pNode->pPrev = pList->tail;
103 pList->tail->pNext = pNode;
104 pList->tail = pNode;
105 } else {
106 /* new node become list head */
107 pNode->pNext = pList->head;
108 pList->head->pPrev = pNode;
109 pList->head = pNode;
110 }
111 }
112
113 pList->nMembers += 1;
114
115 return (pList);
116 }
117
118 if (pList->nFlags & L_FL_HEAD) {
119 pNode->pNext = pList->head;
120 pList->head->pPrev = pNode;
121 pList->head = pNode;
122 pList->nMembers += 1;
123 } else {
124 pNode->pPrev = pList->tail;
125 pList->tail->pNext = pNode;
126 pList->tail = pNode;
127 pList->nMembers += 1;
128 }
129
130 return (pList);
131}
132
133/*
134 * Routine:
135 * Purpose:
136 * Algorithm:
137 * Data Structures:
138 *
139 * Params:
140 * Returns:
141 * Called By:
142 * Calls:
143 * Assumptions:
144 * Side Effects:
145 * TODO: None
146 */
147void *removeItem(list_t *pList, int bHead) {
148 void *pResult;
149
150 if (pList->nMembers == 0)
151 return (NULL);
152
153 if (!bHead) {
154 pResult = pList->tail->pData;
155 pList->tail = pList->tail->pPrev;
156 pList->tail->pNext = NULL;
157 } else {
158 pResult = pList->head->pData;
159 pList->head = pList->head->pNext;
160 pList->head->pPrev = NULL;
161 }
162
163 pList->nMembers -= 1;
164
165 return (pResult);
166}
167
168/*
169 * Routine:
170 * Purpose:
171 * Algorithm:
172 * Data Structures:
173 *
174 * Params:
175 * Returns:
176 * Called By:
177 * Calls:
178 * Assumptions:
179 * Side Effects:
180 * TODO: None
181 */
182void *getHead(list_t *pList) {
183 assert(pList);
184
185 if (!pList->head)
186 return (NULL);
187
188 pList->pCurrent = pList->head;
189
190 return (pList->pCurrent->pData);
191}
192
193/*
194 * Routine:
195 * Purpose:
196 * Algorithm:
197 * Data Structures:
198 *
199 * Params:
200 * Returns:
201 * Called By:
202 * Calls:
203 * Assumptions:
204 * Side Effects:
205 * TODO: None
206 */
207void *getTail(list_t *pList) {
208 assert(pList);
209
210 if (!pList->tail)
211 return (NULL);
212
213 pList->pCurrent = pList->tail;
214
215 return (pList->pCurrent->pData);
216}
217
218/*
219 * Routine:
220 * Purpose:
221 * Algorithm:
222 * Data Structures:
223 *
224 * Params:
225 * Returns:
226 * Called By:
227 * Calls:
228 * Assumptions:
229 * Side Effects:
230 * TODO: None
231 */
232void *getNext(list_t *pList) {
233 assert(pList);
234
235 if (!pList->pCurrent->pNext)
236 return (NULL);
237
238 pList->pCurrent = pList->pCurrent->pNext;
239
240 return (pList->pCurrent->pData);
241}
242
243/*
244 * Routine:
245 * Purpose: findList(list_t *pList, void *pData)
246 * Algorithm:
247 * Data Structures:
248 *
249 * Params:
250 * Returns:
251 * Called By:
252 * Calls:
253 * Assumptions:
254 * Side Effects:
255 * TODO: None
256 */
257void *findList(list_t *pList, void *pData) {
258 void *pNode;
259 struct LIST_NODE_T *pOldCurrent = pList->pCurrent;
260
261 for (pNode = getHead(pList); pNode; pNode = getNext(pList))
262 if (pList->pSortFunc(pNode, pData) == 0) {
263 pList->pCurrent = pOldCurrent;
264 return (pNode);
265 }
266
267 pList->pCurrent = pOldCurrent;
268 return (NULL);
269}
270
271/*
272 * Routine:
273 * Purpose:
274 * Algorithm:
275 * Data Structures:
276 *
277 * Params:
278 * Returns:
279 * Called By:
280 * Calls:
281 * Assumptions:
282 * Side Effects:
283 * TODO: None
284 */
285void *getItem(list_t *pList, int nIndex) {
286 void *pResult;
287 struct LIST_NODE_T *pOldCurrent = pList->pCurrent;
288
289 if (nIndex > length(pList))
290 return (NULL);
291
292 for (pResult = getHead(pList); --nIndex; pResult = getNext(pList))
293 ;
294
295 pList->pCurrent = pOldCurrent;
296 return (pResult);
297}
298