1 |
2 |
zero_gravi |
/*
|
2 |
|
|
Copyright 2018 Embedded Microprocessor Benchmark Consortium (EEMBC)
|
3 |
|
|
|
4 |
|
|
Licensed under the Apache License, Version 2.0 (the "License");
|
5 |
|
|
you may not use this file except in compliance with the License.
|
6 |
|
|
You may obtain a copy of the License at
|
7 |
|
|
|
8 |
|
|
http://www.apache.org/licenses/LICENSE-2.0
|
9 |
|
|
|
10 |
|
|
Unless required by applicable law or agreed to in writing, software
|
11 |
|
|
distributed under the License is distributed on an "AS IS" BASIS,
|
12 |
|
|
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
13 |
|
|
See the License for the specific language governing permissions and
|
14 |
|
|
limitations under the License.
|
15 |
|
|
|
16 |
|
|
Original Author: Shay Gal-on
|
17 |
|
|
*/
|
18 |
|
|
|
19 |
|
|
#include "coremark.h"
|
20 |
|
|
/*
|
21 |
|
|
Topic: Description
|
22 |
|
|
Benchmark using a linked list.
|
23 |
|
|
|
24 |
|
|
Linked list is a common data structure used in many applications.
|
25 |
|
|
|
26 |
|
|
For our purposes, this will excercise the memory units of the processor.
|
27 |
|
|
In particular, usage of the list pointers to find and alter data.
|
28 |
|
|
|
29 |
|
|
We are not using Malloc since some platforms do not support this library.
|
30 |
|
|
|
31 |
|
|
Instead, the memory block being passed in is used to create a list,
|
32 |
|
|
and the benchmark takes care not to add more items then can be
|
33 |
|
|
accomodated by the memory block. The porting layer will make sure
|
34 |
|
|
that we have a valid memory block.
|
35 |
|
|
|
36 |
|
|
All operations are done in place, without using any extra memory.
|
37 |
|
|
|
38 |
|
|
The list itself contains list pointers and pointers to data items.
|
39 |
|
|
Data items contain the following:
|
40 |
|
|
|
41 |
|
|
idx - An index that captures the initial order of the list.
|
42 |
|
|
data - Variable data initialized based on the input parameters. The 16b are divided as follows:
|
43 |
|
|
o Upper 8b are backup of original data.
|
44 |
|
|
o Bit 7 indicates if the lower 7 bits are to be used as is or calculated.
|
45 |
|
|
o Bits 0-2 indicate type of operation to perform to get a 7b value.
|
46 |
|
|
o Bits 3-6 provide input for the operation.
|
47 |
|
|
|
48 |
|
|
*/
|
49 |
|
|
|
50 |
|
|
/* local functions */
|
51 |
|
|
|
52 |
|
|
list_head *core_list_find(list_head *list,list_data *info);
|
53 |
|
|
list_head *core_list_reverse(list_head *list);
|
54 |
|
|
list_head *core_list_remove(list_head *item);
|
55 |
|
|
list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified);
|
56 |
|
|
list_head *core_list_insert_new(list_head *insert_point
|
57 |
|
|
, list_data *info, list_head **memblock, list_data **datablock
|
58 |
|
|
, list_head *memblock_end, list_data *datablock_end);
|
59 |
|
|
typedef ee_s32(*list_cmp)(list_data *a, list_data *b, core_results *res);
|
60 |
|
|
list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res);
|
61 |
|
|
|
62 |
|
|
ee_s16 calc_func(ee_s16 *pdata, core_results *res) {
|
63 |
|
|
ee_s16 data=*pdata;
|
64 |
|
|
ee_s16 retval;
|
65 |
|
|
ee_u8 optype=(data>>7) & 1; /* bit 7 indicates if the function result has been cached */
|
66 |
|
|
if (optype) /* if cached, use cache */
|
67 |
|
|
return (data & 0x007f);
|
68 |
|
|
else { /* otherwise calculate and cache the result */
|
69 |
|
|
ee_s16 flag=data & 0x7; /* bits 0-2 is type of function to perform */
|
70 |
|
|
ee_s16 dtype=((data>>3) & 0xf); /* bits 3-6 is specific data for the operation */
|
71 |
|
|
dtype |= dtype << 4; /* replicate the lower 4 bits to get an 8b value */
|
72 |
|
|
switch (flag) {
|
73 |
|
|
case 0:
|
74 |
|
|
if (dtype<0x22) /* set min period for bit corruption */
|
75 |
|
|
dtype=0x22;
|
76 |
|
|
retval=core_bench_state(res->size,res->memblock[3],res->seed1,res->seed2,dtype,res->crc);
|
77 |
|
|
if (res->crcstate==0)
|
78 |
|
|
res->crcstate=retval;
|
79 |
|
|
break;
|
80 |
|
|
case 1:
|
81 |
|
|
retval=core_bench_matrix(&(res->mat),dtype,res->crc);
|
82 |
|
|
if (res->crcmatrix==0)
|
83 |
|
|
res->crcmatrix=retval;
|
84 |
|
|
break;
|
85 |
|
|
default:
|
86 |
|
|
retval=data;
|
87 |
|
|
break;
|
88 |
|
|
}
|
89 |
|
|
res->crc=crcu16(retval,res->crc);
|
90 |
|
|
retval &= 0x007f;
|
91 |
|
|
*pdata = (data & 0xff00) | 0x0080 | retval; /* cache the result */
|
92 |
|
|
return retval;
|
93 |
|
|
}
|
94 |
|
|
}
|
95 |
|
|
/* Function: cmp_complex
|
96 |
|
|
Compare the data item in a list cell.
|
97 |
|
|
|
98 |
|
|
Can be used by mergesort.
|
99 |
|
|
*/
|
100 |
|
|
ee_s32 cmp_complex(list_data *a, list_data *b, core_results *res) {
|
101 |
|
|
ee_s16 val1=calc_func(&(a->data16),res);
|
102 |
|
|
ee_s16 val2=calc_func(&(b->data16),res);
|
103 |
|
|
return val1 - val2;
|
104 |
|
|
}
|
105 |
|
|
|
106 |
|
|
/* Function: cmp_idx
|
107 |
|
|
Compare the idx item in a list cell, and regen the data.
|
108 |
|
|
|
109 |
|
|
Can be used by mergesort.
|
110 |
|
|
*/
|
111 |
|
|
ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
|
112 |
|
|
if (res==NULL) {
|
113 |
|
|
a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
|
114 |
|
|
b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
|
115 |
|
|
}
|
116 |
|
|
return a->idx - b->idx;
|
117 |
|
|
}
|
118 |
|
|
|
119 |
|
|
void copy_info(list_data *to,list_data *from) {
|
120 |
|
|
to->data16=from->data16;
|
121 |
|
|
to->idx=from->idx;
|
122 |
|
|
}
|
123 |
|
|
|
124 |
|
|
/* Benchmark for linked list:
|
125 |
|
|
- Try to find multiple data items.
|
126 |
|
|
- List sort
|
127 |
|
|
- Operate on data from list (crc)
|
128 |
|
|
- Single remove/reinsert
|
129 |
|
|
* At the end of this function, the list is back to original state
|
130 |
|
|
*/
|
131 |
|
|
ee_u16 core_bench_list(core_results *res, ee_s16 finder_idx) {
|
132 |
|
|
ee_u16 retval=0;
|
133 |
|
|
ee_u16 found=0,missed=0;
|
134 |
|
|
list_head *list=res->list;
|
135 |
|
|
ee_s16 find_num=res->seed3;
|
136 |
|
|
list_head *this_find;
|
137 |
|
|
list_head *finder, *remover;
|
138 |
|
|
list_data info;
|
139 |
|
|
ee_s16 i;
|
140 |
|
|
|
141 |
|
|
info.idx=finder_idx;
|
142 |
|
|
/* find <find_num> values in the list, and change the list each time (reverse and cache if value found) */
|
143 |
|
|
for (i=0; i<find_num; i++) {
|
144 |
|
|
info.data16= (i & 0xff) ;
|
145 |
|
|
this_find=core_list_find(list,&info);
|
146 |
|
|
list=core_list_reverse(list);
|
147 |
|
|
if (this_find==NULL) {
|
148 |
|
|
missed++;
|
149 |
|
|
retval+=(list->next->info->data16 >> 8) & 1;
|
150 |
|
|
}
|
151 |
|
|
else {
|
152 |
|
|
found++;
|
153 |
|
|
if (this_find->info->data16 & 0x1) /* use found value */
|
154 |
|
|
retval+=(this_find->info->data16 >> 9) & 1;
|
155 |
|
|
/* and cache next item at the head of the list (if any) */
|
156 |
|
|
if (this_find->next != NULL) {
|
157 |
|
|
finder = this_find->next;
|
158 |
|
|
this_find->next = finder->next;
|
159 |
|
|
finder->next=list->next;
|
160 |
|
|
list->next=finder;
|
161 |
|
|
}
|
162 |
|
|
}
|
163 |
|
|
if (info.idx>=0)
|
164 |
|
|
info.idx++;
|
165 |
|
|
#if CORE_DEBUG
|
166 |
|
|
ee_printf("List find %d: [%d,%d,%d]\n",i,retval,missed,found);
|
167 |
|
|
#endif
|
168 |
|
|
}
|
169 |
|
|
retval+=found*4-missed;
|
170 |
|
|
/* sort the list by data content and remove one item*/
|
171 |
|
|
if (finder_idx>0)
|
172 |
|
|
list=core_list_mergesort(list,cmp_complex,res);
|
173 |
|
|
remover=core_list_remove(list->next);
|
174 |
|
|
/* CRC data content of list from location of index N forward, and then undo remove */
|
175 |
|
|
finder=core_list_find(list,&info);
|
176 |
|
|
if (!finder)
|
177 |
|
|
finder=list->next;
|
178 |
|
|
while (finder) {
|
179 |
|
|
retval=crc16(list->info->data16,retval);
|
180 |
|
|
finder=finder->next;
|
181 |
|
|
}
|
182 |
|
|
#if CORE_DEBUG
|
183 |
|
|
ee_printf("List sort 1: %04x\n",retval);
|
184 |
|
|
#endif
|
185 |
|
|
remover=core_list_undo_remove(remover,list->next);
|
186 |
|
|
/* sort the list by index, in effect returning the list to original state */
|
187 |
|
|
list=core_list_mergesort(list,cmp_idx,NULL);
|
188 |
|
|
/* CRC data content of list */
|
189 |
|
|
finder=list->next;
|
190 |
|
|
while (finder) {
|
191 |
|
|
retval=crc16(list->info->data16,retval);
|
192 |
|
|
finder=finder->next;
|
193 |
|
|
}
|
194 |
|
|
#if CORE_DEBUG
|
195 |
|
|
ee_printf("List sort 2: %04x\n",retval);
|
196 |
|
|
#endif
|
197 |
|
|
return retval;
|
198 |
|
|
}
|
199 |
|
|
/* Function: core_list_init
|
200 |
|
|
Initialize list with data.
|
201 |
|
|
|
202 |
|
|
Parameters:
|
203 |
|
|
blksize - Size of memory to be initialized.
|
204 |
|
|
memblock - Pointer to memory block.
|
205 |
|
|
seed - Actual values chosen depend on the seed parameter.
|
206 |
|
|
The seed parameter MUST be supplied from a source that cannot be determined at compile time
|
207 |
|
|
|
208 |
|
|
Returns:
|
209 |
|
|
Pointer to the head of the list.
|
210 |
|
|
|
211 |
|
|
*/
|
212 |
|
|
list_head *core_list_init(ee_u32 blksize, list_head *memblock, ee_s16 seed) {
|
213 |
|
|
/* calculated pointers for the list */
|
214 |
|
|
ee_u32 per_item=16+sizeof(struct list_data_s);
|
215 |
|
|
ee_u32 size=(blksize/per_item)-2; /* to accomodate systems with 64b pointers, and make sure same code is executed, set max list elements */
|
216 |
|
|
list_head *memblock_end=memblock+size;
|
217 |
|
|
list_data *datablock=(list_data *)(memblock_end);
|
218 |
|
|
list_data *datablock_end=datablock+size;
|
219 |
|
|
/* some useful variables */
|
220 |
|
|
ee_u32 i;
|
221 |
|
|
list_head *finder,*list=memblock;
|
222 |
|
|
list_data info;
|
223 |
|
|
|
224 |
|
|
/* create a fake items for the list head and tail */
|
225 |
|
|
list->next=NULL;
|
226 |
|
|
list->info=datablock;
|
227 |
|
|
list->info->idx=0x0000;
|
228 |
|
|
list->info->data16=(ee_s16)0x8080;
|
229 |
|
|
memblock++;
|
230 |
|
|
datablock++;
|
231 |
|
|
info.idx=0x7fff;
|
232 |
|
|
info.data16=(ee_s16)0xffff;
|
233 |
|
|
core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
|
234 |
|
|
|
235 |
|
|
/* then insert size items */
|
236 |
|
|
for (i=0; i<size; i++) {
|
237 |
|
|
ee_u16 datpat=((ee_u16)(seed^i) & 0xf);
|
238 |
|
|
ee_u16 dat=(datpat<<3) | (i&0x7); /* alternate between algorithms */
|
239 |
|
|
info.data16=(dat<<8) | dat; /* fill the data with actual data and upper bits with rebuild value */
|
240 |
|
|
core_list_insert_new(list,&info,&memblock,&datablock,memblock_end,datablock_end);
|
241 |
|
|
}
|
242 |
|
|
/* and now index the list so we know initial seed order of the list */
|
243 |
|
|
finder=list->next;
|
244 |
|
|
i=1;
|
245 |
|
|
while (finder->next!=NULL) {
|
246 |
|
|
if (i<size/5) /* first 20% of the list in order */
|
247 |
|
|
finder->info->idx=i++;
|
248 |
|
|
else {
|
249 |
|
|
ee_u16 pat=(ee_u16)(i++ ^ seed); /* get a pseudo random number */
|
250 |
|
|
finder->info->idx=0x3fff & (((i & 0x07) << 8) | pat); /* make sure the mixed items end up after the ones in sequence */
|
251 |
|
|
}
|
252 |
|
|
finder=finder->next;
|
253 |
|
|
}
|
254 |
|
|
list = core_list_mergesort(list,cmp_idx,NULL);
|
255 |
|
|
#if CORE_DEBUG
|
256 |
|
|
ee_printf("Initialized list:\n");
|
257 |
|
|
finder=list;
|
258 |
|
|
while (finder) {
|
259 |
|
|
ee_printf("[%04x,%04x]",finder->info->idx,(ee_u16)finder->info->data16);
|
260 |
|
|
finder=finder->next;
|
261 |
|
|
}
|
262 |
|
|
ee_printf("\n");
|
263 |
|
|
#endif
|
264 |
|
|
return list;
|
265 |
|
|
}
|
266 |
|
|
|
267 |
|
|
/* Function: core_list_insert
|
268 |
|
|
Insert an item to the list
|
269 |
|
|
|
270 |
|
|
Parameters:
|
271 |
|
|
insert_point - where to insert the item.
|
272 |
|
|
info - data for the cell.
|
273 |
|
|
memblock - pointer for the list header
|
274 |
|
|
datablock - pointer for the list data
|
275 |
|
|
memblock_end - end of region for list headers
|
276 |
|
|
datablock_end - end of region for list data
|
277 |
|
|
|
278 |
|
|
Returns:
|
279 |
|
|
Pointer to new item.
|
280 |
|
|
*/
|
281 |
|
|
list_head *core_list_insert_new(list_head *insert_point, list_data *info, list_head **memblock, list_data **datablock
|
282 |
|
|
, list_head *memblock_end, list_data *datablock_end) {
|
283 |
|
|
list_head *newitem;
|
284 |
|
|
|
285 |
|
|
if ((*memblock+1) >= memblock_end)
|
286 |
|
|
return NULL;
|
287 |
|
|
if ((*datablock+1) >= datablock_end)
|
288 |
|
|
return NULL;
|
289 |
|
|
|
290 |
|
|
newitem=*memblock;
|
291 |
|
|
(*memblock)++;
|
292 |
|
|
newitem->next=insert_point->next;
|
293 |
|
|
insert_point->next=newitem;
|
294 |
|
|
|
295 |
|
|
newitem->info=*datablock;
|
296 |
|
|
(*datablock)++;
|
297 |
|
|
copy_info(newitem->info,info);
|
298 |
|
|
|
299 |
|
|
return newitem;
|
300 |
|
|
}
|
301 |
|
|
|
302 |
|
|
/* Function: core_list_remove
|
303 |
|
|
Remove an item from the list.
|
304 |
|
|
|
305 |
|
|
Operation:
|
306 |
|
|
For a singly linked list, remove by copying the data from the next item
|
307 |
|
|
over to the current cell, and unlinking the next item.
|
308 |
|
|
|
309 |
|
|
Note:
|
310 |
|
|
since there is always a fake item at the end of the list, no need to check for NULL.
|
311 |
|
|
|
312 |
|
|
Returns:
|
313 |
|
|
Removed item.
|
314 |
|
|
*/
|
315 |
|
|
list_head *core_list_remove(list_head *item) {
|
316 |
|
|
list_data *tmp;
|
317 |
|
|
list_head *ret=item->next;
|
318 |
|
|
/* swap data pointers */
|
319 |
|
|
tmp=item->info;
|
320 |
|
|
item->info=ret->info;
|
321 |
|
|
ret->info=tmp;
|
322 |
|
|
/* and eliminate item */
|
323 |
|
|
item->next=item->next->next;
|
324 |
|
|
ret->next=NULL;
|
325 |
|
|
return ret;
|
326 |
|
|
}
|
327 |
|
|
|
328 |
|
|
/* Function: core_list_undo_remove
|
329 |
|
|
Undo a remove operation.
|
330 |
|
|
|
331 |
|
|
Operation:
|
332 |
|
|
Since we want each iteration of the benchmark to be exactly the same,
|
333 |
|
|
we need to be able to undo a remove.
|
334 |
|
|
Link the removed item back into the list, and switch the info items.
|
335 |
|
|
|
336 |
|
|
Parameters:
|
337 |
|
|
item_removed - Return value from the <core_list_remove>
|
338 |
|
|
item_modified - List item that was modified during <core_list_remove>
|
339 |
|
|
|
340 |
|
|
Returns:
|
341 |
|
|
The item that was linked back to the list.
|
342 |
|
|
|
343 |
|
|
*/
|
344 |
|
|
list_head *core_list_undo_remove(list_head *item_removed, list_head *item_modified) {
|
345 |
|
|
list_data *tmp;
|
346 |
|
|
/* swap data pointers */
|
347 |
|
|
tmp=item_removed->info;
|
348 |
|
|
item_removed->info=item_modified->info;
|
349 |
|
|
item_modified->info=tmp;
|
350 |
|
|
/* and insert item */
|
351 |
|
|
item_removed->next=item_modified->next;
|
352 |
|
|
item_modified->next=item_removed;
|
353 |
|
|
return item_removed;
|
354 |
|
|
}
|
355 |
|
|
|
356 |
|
|
/* Function: core_list_find
|
357 |
|
|
Find an item in the list
|
358 |
|
|
|
359 |
|
|
Operation:
|
360 |
|
|
Find an item by idx (if not 0) or specific data value
|
361 |
|
|
|
362 |
|
|
Parameters:
|
363 |
|
|
list - list head
|
364 |
|
|
info - idx or data to find
|
365 |
|
|
|
366 |
|
|
Returns:
|
367 |
|
|
Found item, or NULL if not found.
|
368 |
|
|
*/
|
369 |
|
|
list_head *core_list_find(list_head *list,list_data *info) {
|
370 |
|
|
if (info->idx>=0) {
|
371 |
|
|
while (list && (list->info->idx != info->idx))
|
372 |
|
|
list=list->next;
|
373 |
|
|
return list;
|
374 |
|
|
} else {
|
375 |
|
|
while (list && ((list->info->data16 & 0xff) != info->data16))
|
376 |
|
|
list=list->next;
|
377 |
|
|
return list;
|
378 |
|
|
}
|
379 |
|
|
}
|
380 |
|
|
/* Function: core_list_reverse
|
381 |
|
|
Reverse a list
|
382 |
|
|
|
383 |
|
|
Operation:
|
384 |
|
|
Rearrange the pointers so the list is reversed.
|
385 |
|
|
|
386 |
|
|
Parameters:
|
387 |
|
|
list - list head
|
388 |
|
|
info - idx or data to find
|
389 |
|
|
|
390 |
|
|
Returns:
|
391 |
|
|
Found item, or NULL if not found.
|
392 |
|
|
*/
|
393 |
|
|
|
394 |
|
|
list_head *core_list_reverse(list_head *list) {
|
395 |
|
|
list_head *next=NULL, *tmp;
|
396 |
|
|
while (list) {
|
397 |
|
|
tmp=list->next;
|
398 |
|
|
list->next=next;
|
399 |
|
|
next=list;
|
400 |
|
|
list=tmp;
|
401 |
|
|
}
|
402 |
|
|
return next;
|
403 |
|
|
}
|
404 |
|
|
/* Function: core_list_mergesort
|
405 |
|
|
Sort the list in place without recursion.
|
406 |
|
|
|
407 |
|
|
Description:
|
408 |
|
|
Use mergesort, as for linked list this is a realistic solution.
|
409 |
|
|
Also, since this is aimed at embedded, care was taken to use iterative rather then recursive algorithm.
|
410 |
|
|
The sort can either return the list to original order (by idx) ,
|
411 |
|
|
or use the data item to invoke other other algorithms and change the order of the list.
|
412 |
|
|
|
413 |
|
|
Parameters:
|
414 |
|
|
list - list to be sorted.
|
415 |
|
|
cmp - cmp function to use
|
416 |
|
|
|
417 |
|
|
Returns:
|
418 |
|
|
New head of the list.
|
419 |
|
|
|
420 |
|
|
Note:
|
421 |
|
|
We have a special header for the list that will always be first,
|
422 |
|
|
but the algorithm could theoretically modify where the list starts.
|
423 |
|
|
|
424 |
|
|
*/
|
425 |
|
|
list_head *core_list_mergesort(list_head *list, list_cmp cmp, core_results *res) {
|
426 |
|
|
list_head *p, *q, *e, *tail;
|
427 |
|
|
ee_s32 insize, nmerges, psize, qsize, i;
|
428 |
|
|
|
429 |
|
|
insize = 1;
|
430 |
|
|
|
431 |
|
|
while (1) {
|
432 |
|
|
p = list;
|
433 |
|
|
list = NULL;
|
434 |
|
|
tail = NULL;
|
435 |
|
|
|
436 |
|
|
nmerges = 0; /* count number of merges we do in this pass */
|
437 |
|
|
|
438 |
|
|
while (p) {
|
439 |
|
|
nmerges++; /* there exists a merge to be done */
|
440 |
|
|
/* step `insize' places along from p */
|
441 |
|
|
q = p;
|
442 |
|
|
psize = 0;
|
443 |
|
|
for (i = 0; i < insize; i++) {
|
444 |
|
|
psize++;
|
445 |
|
|
q = q->next;
|
446 |
|
|
if (!q) break;
|
447 |
|
|
}
|
448 |
|
|
|
449 |
|
|
/* if q hasn't fallen off end, we have two lists to merge */
|
450 |
|
|
qsize = insize;
|
451 |
|
|
|
452 |
|
|
/* now we have two lists; merge them */
|
453 |
|
|
while (psize > 0 || (qsize > 0 && q)) {
|
454 |
|
|
|
455 |
|
|
/* decide whether next element of merge comes from p or q */
|
456 |
|
|
if (psize == 0) {
|
457 |
|
|
/* p is empty; e must come from q. */
|
458 |
|
|
e = q; q = q->next; qsize--;
|
459 |
|
|
} else if (qsize == 0 || !q) {
|
460 |
|
|
/* q is empty; e must come from p. */
|
461 |
|
|
e = p; p = p->next; psize--;
|
462 |
|
|
} else if (cmp(p->info,q->info,res) <= 0) {
|
463 |
|
|
/* First element of p is lower (or same); e must come from p. */
|
464 |
|
|
e = p; p = p->next; psize--;
|
465 |
|
|
} else {
|
466 |
|
|
/* First element of q is lower; e must come from q. */
|
467 |
|
|
e = q; q = q->next; qsize--;
|
468 |
|
|
}
|
469 |
|
|
|
470 |
|
|
/* add the next element to the merged list */
|
471 |
|
|
if (tail) {
|
472 |
|
|
tail->next = e;
|
473 |
|
|
} else {
|
474 |
|
|
list = e;
|
475 |
|
|
}
|
476 |
|
|
tail = e;
|
477 |
|
|
}
|
478 |
|
|
|
479 |
|
|
/* now p has stepped `insize' places along, and q has too */
|
480 |
|
|
p = q;
|
481 |
|
|
}
|
482 |
|
|
|
483 |
|
|
tail->next = NULL;
|
484 |
|
|
|
485 |
|
|
/* If we have done only one merge, we're finished. */
|
486 |
|
|
if (nmerges <= 1) /* allow for nmerges==0, the empty list case */
|
487 |
|
|
return list;
|
488 |
|
|
|
489 |
|
|
/* Otherwise repeat, merging lists twice the size */
|
490 |
|
|
insize *= 2;
|
491 |
|
|
}
|
492 |
|
|
#if COMPILER_REQUIRES_SORT_RETURN
|
493 |
|
|
return list;
|
494 |
|
|
#endif
|
495 |
|
|
}
|