1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*
fcs_dm.c - Freecell Solver's data management routines.
Written by Shlomi Fish, 2000
This file is distributed under the public domain.
(It's not copyrighted)
*/
#include <stddef.h>
#include <string.h>
#include "fcs_dm.h"
#ifdef DMALLOC
#include "dmalloc.h"
#endif
/*
freecell_solver_bsearch - an improved binary search function. Highlights:
* The comparison function accepts a common context argument that
is passed to SFO_bsearch.
* If the item was not found the function returns the place in which
it should be placed, while setting *found to 0. If it was found
(*found) is set to 1.
*/
void * freecell_solver_bsearch
(
void * key,
void * void_array,
size_t len,
size_t width,
int (* compare)(const void *, const void *, void *),
void * context,
int * found
)
{
int low = 0;
int high = len-1;
int mid;
int result;
char * array = void_array;
while (low <= high)
{
mid = ((low+high)>>1);
result = compare(key, (void*)(array+mid*width), context);
if (result < 0)
{
high = mid-1;
}
else if (result > 0)
{
low = mid+1;
}
else
{
*found = 1;
return (void*)(array+mid*width);
}
}
*found = 0;
return ((void*)(array+(high+1)*width));
}
/*
freecell_solver_merge_large_and_small_sorted_array - merges a large sorted
array with a small sorted array. The arrays could be of any length
whatsoever, but it works faster if the first is significantly bigger
than the second.
This function assumes that big_array is allocated with enough
space to hold the extra elements.
The array should be distinct or else there would be unexpected
results.
*/
int freecell_solver_merge_large_and_small_sorted_arrays
(
void * void_big_array,
size_t size_big_array,
void * void_small_array,
size_t size_small_array,
size_t width,
int (*compare) (const void *, const void *, void *),
void * context
)
{
int item_to_move, num_big_items_moved, pos;
char * pos_ptr;
char * big_array;
char * small_array;
int found;
int start_offset, end_offset;
big_array = (char*)void_big_array;
small_array = (char*)void_small_array;
num_big_items_moved = 0;
for(item_to_move = size_small_array-1 ; item_to_move>=0; item_to_move--)
{
pos_ptr = freecell_solver_bsearch (
small_array+item_to_move*width,
big_array,
size_big_array-num_big_items_moved,
width,
compare,
context,
&found
);
pos = (pos_ptr-big_array)/width;
end_offset = size_big_array + size_small_array -
num_big_items_moved -
(size_small_array-item_to_move-1);
start_offset = end_offset + pos -
(size_big_array - num_big_items_moved);
memmove(
big_array+start_offset*width,
big_array+pos*width,
(end_offset-start_offset)*width
);
memcpy(
big_array+(start_offset-1)*width,
small_array+item_to_move*width,
width
);
num_big_items_moved += (end_offset - start_offset);
}
return 1;
}
|
