| 1 | /* PROGRAM: Hybrid sort (polyphase merge with quicksort presorter) */ |
|---|
| 2 | /* AUTHOR: Kelly McTiernan, Feb. 4, 1990 */ |
|---|
| 3 | /* USAGE: psort reclen src dest: reclen--record length in bytes; */ |
|---|
| 4 | /* src--source file name; dest--destination file name */ |
|---|
| 5 | /* NOTES: Sort routine is attached to a test driver for your con- */ |
|---|
| 6 | /* venience. Functions main() and compare() illustrate calling */ |
|---|
| 7 | /* conventions. This test driver is not very forgiving, the sort */ |
|---|
| 8 | /* is intended for more flexible usage as part of a larger */ |
|---|
| 9 | /* package. This has been implemented in Turbo C. This is */ |
|---|
| 10 | /* configured for large memory model. */ |
|---|
| 11 | /* |
|---|
| 12 | Changed in may/2001 for CISIS Interface purposes. |
|---|
| 13 | AOT, 19/05/2001 |
|---|
| 14 | */ |
|---|
| 15 | |
|---|
| 16 | #include <stdio.h> |
|---|
| 17 | #include <string.h> |
|---|
| 18 | |
|---|
| 19 | #if CIAPI |
|---|
| 20 | #include "ciapi.h" |
|---|
| 21 | #else /* CIAPI */ |
|---|
| 22 | #include "cisis.h" /* CISIS Interface header file */ |
|---|
| 23 | #endif /* CIAPI */ |
|---|
| 24 | |
|---|
| 25 | #define MAX_STK 512 /*128*/ /* Local stack size */ |
|---|
| 26 | #define TMP_FILES 33 /*9*/ /* Maximum number of merge files */ |
|---|
| 27 | #define HEAP_SAVE 8192 /* Amount to save for FILE'S */ |
|---|
| 28 | #define MAX_BUF (unsigned) 0xFFFF /* largest possible buffer */ |
|---|
| 29 | |
|---|
| 30 | #define OPEN_ERR 1 /* Local error codes */ |
|---|
| 31 | #define OPEN_ERR_OUT 11 /* cannot create output file */ |
|---|
| 32 | #define OPEN_ERR_INP 12 /* cannot read input file */ |
|---|
| 33 | #define OPEN_ERR_TMP 13 /* cannot create tmp file */ |
|---|
| 34 | #define READ_ERR 2 |
|---|
| 35 | #define WRITE_ERR 3 |
|---|
| 36 | #define ALLOC_ERR 4 |
|---|
| 37 | /* #define DATA_ERR 5 */ |
|---|
| 38 | #define PARM_ERR 6 |
|---|
| 39 | #define MOVE_ERR 998 |
|---|
| 40 | #define PROG_ERR 999 |
|---|
| 41 | |
|---|
| 42 | |
|---|
| 43 | typedef struct mys_stru { |
|---|
| 44 | int last_file; /* Actual number of files */ |
|---|
| 45 | int last_minus_one; /* Eliminates major invariant */ |
|---|
| 46 | int actual_run_count[TMP_FILES]; /* Ideal number of runs */ |
|---|
| 47 | int dummy_run_count[TMP_FILES]; /* Difference from ideal */ |
|---|
| 48 | int least_runs; /* Number of runs at a level */ |
|---|
| 49 | int select; /* Next file to receive run */ |
|---|
| 50 | int level; /* Number of passes needed */ |
|---|
| 51 | void *last_item[TMP_FILES]; /* Buffered I/O variables */ |
|---|
| 52 | void *next; |
|---|
| 53 | FILE *tmp_files[TMP_FILES]; |
|---|
| 54 | char fnames[TMP_FILES][FILENAME_MAX+1]; /* Filenames for temp files */ |
|---|
| 55 | int end_data[TMP_FILES]; /* EOF for local buffers */ |
|---|
| 56 | int end_of_data; |
|---|
| 57 | size_t max_items; /* Maximum records a buffer can hold */ |
|---|
| 58 | size_t num_ptrs; /* Number of items for presort */ |
|---|
| 59 | void *buf; /* R/W pointer */ |
|---|
| 60 | void *bs; /* last item read */ |
|---|
| 61 | void **buf_ptrs; /* Array of pointers to records */ |
|---|
| 62 | size_t rd_count; /* Static read counter, last number read */ |
|---|
| 63 | size_t rsize; /* Global for record size */ |
|---|
| 64 | void *spos[TMP_FILES]; /* Store position in buffer */ |
|---|
| 65 | void *rpos[TMP_FILES]; /* Retrieve position pointer */ |
|---|
| 66 | void *top[TMP_FILES]; /* Buffer tops */ |
|---|
| 67 | void *next_item[TMP_FILES]; /* Next item to be read */ |
|---|
| 68 | size_t buf_cnt[TMP_FILES]; /* Buffer counter */ |
|---|
| 69 | int myserror; /* program error set by funserror(xmysp, ) */ |
|---|
| 70 | int rec_len; /* For our driver routine */ |
|---|
| 71 | int index[TMP_FILES]; /* Index to merge file buffers */ |
|---|
| 72 | char *gidbnp; /* dbn.par */ |
|---|
| 73 | FILE *src; /* now global and fclose(src) in funserror() - AOT 19/09/2001 */ |
|---|
| 74 | #if CIAPI |
|---|
| 75 | void *ciapip; |
|---|
| 76 | #endif /* CIAPI */ |
|---|
| 77 | } MYS_STRU; |
|---|
| 78 | |
|---|
| 79 | /* MYS_STRU */ |
|---|
| 80 | #define last_file xmysp->last_file |
|---|
| 81 | #define last_minus_one xmysp->last_minus_one |
|---|
| 82 | #define actual_run_count xmysp->actual_run_count |
|---|
| 83 | #define dummy_run_count xmysp->dummy_run_count |
|---|
| 84 | #define least_runs xmysp->least_runs |
|---|
| 85 | #define select xmysp->select |
|---|
| 86 | #define level xmysp->level |
|---|
| 87 | #define last_item xmysp->last_item |
|---|
| 88 | #define next xmysp->next |
|---|
| 89 | #define tmp_files xmysp->tmp_files |
|---|
| 90 | #define fnames xmysp->fnames |
|---|
| 91 | #define end_data xmysp->end_data |
|---|
| 92 | #define end_of_data xmysp->end_of_data |
|---|
| 93 | #define max_items xmysp->max_items |
|---|
| 94 | #define num_ptrs xmysp->num_ptrs |
|---|
| 95 | #define buf xmysp->buf |
|---|
| 96 | #define bs xmysp->bs |
|---|
| 97 | #define buf_ptrs xmysp->buf_ptrs |
|---|
| 98 | #define rd_count xmysp->rd_count |
|---|
| 99 | #define rsize xmysp->rsize |
|---|
| 100 | #define spos xmysp->spos |
|---|
| 101 | #define rpos xmysp->rpos |
|---|
| 102 | #define top xmysp->top |
|---|
| 103 | #define next_item xmysp->next_item |
|---|
| 104 | #define buf_cnt xmysp->buf_cnt |
|---|
| 105 | #define myserror xmysp->myserror |
|---|
| 106 | #define rec_len xmysp->rec_len |
|---|
| 107 | #define index xmysp->index |
|---|
| 108 | #define gidbnp xmysp->gidbnp |
|---|
| 109 | #define src xmysp->src |
|---|
| 110 | #define ciapip xmysp->ciapip |
|---|
| 111 | |
|---|
| 112 | #define serror(x) { funserror(xmysp,x); return; } |
|---|
| 113 | #define serrorX(x) { funserror(xmysp,x); return(x); } |
|---|
| 114 | |
|---|
| 115 | int funserror(MYS_STRU *xmysp, int e); |
|---|
| 116 | void select_file(MYS_STRU *xmysp); |
|---|
| 117 | void generate_run(MYS_STRU *xmysp, FILE *fp); |
|---|
| 118 | void b_set_rd(MYS_STRU *xmysp, int n); |
|---|
| 119 | void b_set_wr(MYS_STRU *xmysp, int b); |
|---|
| 120 | void bflush(MYS_STRU *xmysp, int b); |
|---|
| 121 | void buf_free(MYS_STRU *xmysp); |
|---|
| 122 | void fill_buffer(MYS_STRU *xmysp, FILE *fp); |
|---|
| 123 | void quick_sort(MYS_STRU *xmysp, void *a[], int l, int r); |
|---|
| 124 | void bmove(MYS_STRU *xmysp, int n, int m); |
|---|
| 125 | void bfill(MYS_STRU *xmysp, int n); |
|---|
| 126 | void buf_init(MYS_STRU *xmysp, FILE *fp); |
|---|
| 127 | int poly_sort(MYS_STRU *xmysp, char *srcname, int rec_size, char *name); |
|---|
| 128 | |
|---|
| 129 | |
|---|
| 130 | int poly_sort(xmysp, srcname,rec_size,name) |
|---|
| 131 | MYS_STRU *xmysp; |
|---|
| 132 | char *srcname; /* File to sort, open for reading */ |
|---|
| 133 | int rec_size; /* Length of records in bytes */ |
|---|
| 134 | char *name; /* Name of sorted file */ |
|---|
| 135 | { |
|---|
| 136 | #if BEFORE20010919 |
|---|
| 137 | FILE *src; /* File to sort, open for reading */ |
|---|
| 138 | #endif |
|---|
| 139 | /*register*/ int i; |
|---|
| 140 | int tmp_idx, tmp_d; |
|---|
| 141 | int min_index; |
|---|
| 142 | int active_index[TMP_FILES]; /* Index to active files in merge */ |
|---|
| 143 | void *min; |
|---|
| 144 | int active_count; /* Number files currently active */ |
|---|
| 145 | void *tmp; |
|---|
| 146 | /* MYSFUN */ |
|---|
| 147 | /* FILE *fp; */ |
|---|
| 148 | int wffd; |
|---|
| 149 | if (!srcname || !name || rec_size < 0) /* Parse command line */ |
|---|
| 150 | return(PARM_ERR); |
|---|
| 151 | /* create empty output file */ |
|---|
| 152 | #if 0 |
|---|
| 153 | /* remove(name); */ |
|---|
| 154 | fp=fopen(name, "wb"); |
|---|
| 155 | if (fp) fclose(fp); else return(OPEN_ERR_OUT); |
|---|
| 156 | if((src = fopen(srcname,"rb")) == NULL) |
|---|
| 157 | #endif |
|---|
| 158 | dbxopenc(gidbnp,dbxcipar(gidbnp,name,'='),&wffd,NULL,NULL,1,0); /*..force create= */ |
|---|
| 159 | if (wffd <= 0) return(OPEN_ERR_OUT); else CLOSE(wffd); |
|---|
| 160 | if((src = fopen(dbxcipar(gidbnp,srcname,'='),"rb")) == NULL) |
|---|
| 161 | return(OPEN_ERR_INP); |
|---|
| 162 | /* MYSFUN */ |
|---|
| 163 | rec_len = rec_size; |
|---|
| 164 | rsize = rec_size; |
|---|
| 165 | rewind(src); |
|---|
| 166 | buf_init(xmysp, src); /* Allocate memory, init buffer */ |
|---|
| 167 | if (end_of_data) |
|---|
| 168 | serrorX(0/*DATA_ERR*/); |
|---|
| 169 | /* Initialize, distribute one run to each merge file */ |
|---|
| 170 | for (i = 0; i < last_minus_one; i++) { |
|---|
| 171 | actual_run_count[i] = 1; |
|---|
| 172 | dummy_run_count[i] = 1; |
|---|
| 173 | tmpnam(fnames[i]); |
|---|
| 174 | tmp_files[i] = fopen(fnames[i], "wb+"); |
|---|
| 175 | if (tmp_files[i] == NULL) |
|---|
| 176 | serrorX(OPEN_ERR_TMP); |
|---|
| 177 | } |
|---|
| 178 | level = 1; |
|---|
| 179 | select = 0; |
|---|
| 180 | actual_run_count[last_minus_one] = 0; |
|---|
| 181 | dummy_run_count[last_minus_one] = 0; |
|---|
| 182 | do { |
|---|
| 183 | select_file(xmysp); |
|---|
| 184 | generate_run(xmysp, src); |
|---|
| 185 | } while (!end_of_data && select != last_file - 2); |
|---|
| 186 | /* Distribute runs, account for next run being continuation of the */ |
|---|
| 187 | /* previous run or an out-of-data condition */ |
|---|
| 188 | while (!end_of_data) { |
|---|
| 189 | select_file(xmysp); |
|---|
| 190 | while (memcmp(last_item[select], next, rec_len) <= 0) { |
|---|
| 191 | generate_run(xmysp, src); /* Continue old run */ |
|---|
| 192 | if (end_of_data) |
|---|
| 193 | break; |
|---|
| 194 | } |
|---|
| 195 | if (end_of_data) /* Then use a null run */ |
|---|
| 196 | dummy_run_count[select]++; |
|---|
| 197 | else |
|---|
| 198 | generate_run(xmysp, src); /* Otherwise generate new run */ |
|---|
| 199 | } |
|---|
| 200 | |
|---|
| 201 | for (i = 0; i < last_minus_one; i++) { |
|---|
| 202 | b_set_rd(xmysp, i); |
|---|
| 203 | index[i] = i; |
|---|
| 204 | } |
|---|
| 205 | index[last_minus_one] = last_minus_one; |
|---|
| 206 | tmpnam(fnames[last_minus_one]); |
|---|
| 207 | tmp_files[last_minus_one] = fopen(fnames[last_minus_one], "wb+"); |
|---|
| 208 | if (tmp_files[last_minus_one] == NULL) |
|---|
| 209 | serrorX(OPEN_ERR_TMP); |
|---|
| 210 | do { /* Begin merge operation */ |
|---|
| 211 | least_runs = actual_run_count[last_file - 2]; |
|---|
| 212 | dummy_run_count[last_minus_one] = 0; |
|---|
| 213 | b_set_wr(xmysp, index[last_minus_one]); |
|---|
| 214 | do { /* Merge one run */ |
|---|
| 215 | active_count = 0; |
|---|
| 216 | for (i = 0; i < last_minus_one; i++){ |
|---|
| 217 | if (dummy_run_count[i] > 0) |
|---|
| 218 | dummy_run_count[i]--; /* Exclude from merge */ |
|---|
| 219 | else { /* Participate in merge */ |
|---|
| 220 | active_index[active_count] = index[i]; |
|---|
| 221 | active_count++; |
|---|
| 222 | } |
|---|
| 223 | } |
|---|
| 224 | if (!active_count) /* All dummy runs, do dummy merge */ |
|---|
| 225 | dummy_run_count[last_minus_one]++; |
|---|
| 226 | else /* Do real merge */ |
|---|
| 227 | do { /* Find smallest item */ |
|---|
| 228 | min_index = 0; |
|---|
| 229 | min = next_item[active_index[0]]; |
|---|
| 230 | for (i = 1; i < active_count; i++) { |
|---|
| 231 | tmp = next_item[active_index[i]]; |
|---|
| 232 | if (memcmp(tmp, min, rec_len) < 0) { |
|---|
| 233 | min = tmp; |
|---|
| 234 | min_index = i; |
|---|
| 235 | } |
|---|
| 236 | } |
|---|
| 237 | /* Move min item to test buffer */ |
|---|
| 238 | tmp_idx = active_index[min_index]; |
|---|
| 239 | bmove(xmysp, index[last_minus_one], tmp_idx); |
|---|
| 240 | if (memcmp(buf, next_item[tmp_idx], rec_len) > 0 || end_data[tmp_idx]) { |
|---|
| 241 | active_count--; |
|---|
| 242 | active_index[min_index] = active_index[active_count]; |
|---|
| 243 | } |
|---|
| 244 | } while (active_count); /* Do until one run from each merged */ |
|---|
| 245 | /* Continue merging until file with least runs is empty */ |
|---|
| 246 | } while (--least_runs); |
|---|
| 247 | bflush(xmysp, index[last_minus_one]); /* Rotate files */ |
|---|
| 248 | b_set_rd(xmysp, index[last_minus_one]); |
|---|
| 249 | tmp_idx = index[last_minus_one]; |
|---|
| 250 | tmp_d = dummy_run_count[last_minus_one]; |
|---|
| 251 | least_runs = actual_run_count[last_file - 2]; |
|---|
| 252 | for (i = last_minus_one; i > 0; i--) { |
|---|
| 253 | dummy_run_count[i] = dummy_run_count[i - 1]; |
|---|
| 254 | actual_run_count[i] = actual_run_count[i - 1] - least_runs; |
|---|
| 255 | index[i] = index[i - 1]; |
|---|
| 256 | } |
|---|
| 257 | index[0] = tmp_idx; |
|---|
| 258 | dummy_run_count[0] = tmp_d; |
|---|
| 259 | actual_run_count[0] = least_runs; |
|---|
| 260 | } while (--level); /* Do until all runs merge to one */ |
|---|
| 261 | /* Merge sort complete, index[0] is sorted file */ |
|---|
| 262 | /* Delete all temporary files and rename sorted file */ |
|---|
| 263 | for (i = 1; i < last_file; i++) { |
|---|
| 264 | fclose(tmp_files[index[i]]); tmp_files[index[i]]=NULL; |
|---|
| 265 | remove(fnames[index[i]]); |
|---|
| 266 | } |
|---|
| 267 | fclose(tmp_files[index[0]]); tmp_files[index[0]]=NULL; |
|---|
| 268 | fclose(src); src=NULL; /* AOT 19/09/2001 */ |
|---|
| 269 | |
|---|
| 270 | name=dbxcipar(gidbnp,name,'='); |
|---|
| 271 | remove(name); |
|---|
| 272 | #if UNIX |
|---|
| 273 | sprintf(fnames[0],"mv %s %s",fnames[index[0]],name); |
|---|
| 274 | if (system(fnames[0])) serrorX(MOVE_ERR); |
|---|
| 275 | #else |
|---|
| 276 | if (rename(fnames[index[0]],name)) serrorX(MOVE_ERR); |
|---|
| 277 | #endif |
|---|
| 278 | buf_free(xmysp); |
|---|
| 279 | /* |
|---|
| 280 | fp = fopen(name, "r+"); |
|---|
| 281 | if (fp == NULL) |
|---|
| 282 | return(OPEN_ERR_END); |
|---|
| 283 | fclose(fp); |
|---|
| 284 | */ |
|---|
| 285 | return(0); |
|---|
| 286 | } |
|---|
| 287 | |
|---|
| 288 | void select_file(xmysp) |
|---|
| 289 | MYS_STRU *xmysp; |
|---|
| 290 | { /* Selects file for run distribution */ |
|---|
| 291 | int i, mn; |
|---|
| 292 | if (dummy_run_count[select] < dummy_run_count[select + 1]) |
|---|
| 293 | select++; /* Select next file */ |
|---|
| 294 | else { |
|---|
| 295 | if (dummy_run_count[select] == 0) { /* Ideal reached */ |
|---|
| 296 | level++; /* Generate next level */ |
|---|
| 297 | mn = actual_run_count[0]; |
|---|
| 298 | for (i = 0; i < last_minus_one; i++) { |
|---|
| 299 | dummy_run_count[i] = mn + actual_run_count[i + 1] - actual_run_count[i]; |
|---|
| 300 | actual_run_count[i] = mn + actual_run_count[i + 1]; |
|---|
| 301 | } /* Actual run count = ideal, dummy runs = number to add */ |
|---|
| 302 | } /* to the previous level to reach that ideal */ |
|---|
| 303 | select = 0; /* Select for a run */ |
|---|
| 304 | } |
|---|
| 305 | dummy_run_count[select]--; |
|---|
| 306 | } |
|---|
| 307 | void buf_init(xmysp, fp) |
|---|
| 308 | MYS_STRU *xmysp; |
|---|
| 309 | FILE *fp; /* Get memory, init buffers for generate_run(xmysp, ) */ |
|---|
| 310 | { |
|---|
| 311 | void *tmp; /* Allocate, then free to save */ |
|---|
| 312 | int i; |
|---|
| 313 | tmp = malloc(HEAP_SAVE); |
|---|
| 314 | bs = malloc(rsize); /* Emergency item save buffer */ |
|---|
| 315 | for (i = 0; i < TMP_FILES; i++) { |
|---|
| 316 | last_item[i] = malloc(rsize); |
|---|
| 317 | if (!last_item[i]) |
|---|
| 318 | serror(ALLOC_ERR); |
|---|
| 319 | } |
|---|
| 320 | max_items = MAX_BUF/rsize; |
|---|
| 321 | num_ptrs = MAX_BUF/sizeof(void *); |
|---|
| 322 | buf_ptrs = (void **)malloc(MAX_BUF); |
|---|
| 323 | if (!(buf_ptrs && bs)) |
|---|
| 324 | serror(ALLOC_ERR); |
|---|
| 325 | for (i = 0; i < TMP_FILES - 1; i++) { |
|---|
| 326 | top[i] = malloc(MAX_BUF); |
|---|
| 327 | if (top[i] == NULL) |
|---|
| 328 | break; |
|---|
| 329 | } |
|---|
| 330 | top[i=TMP_FILES - 1] = (void *)buf_ptrs; /* Gets us an extra buffer without realloc */ |
|---|
| 331 | last_minus_one = i; |
|---|
| 332 | i++; |
|---|
| 333 | if (i < 3) /* At least three files needed to merge */ |
|---|
| 334 | serror(ALLOC_ERR); |
|---|
| 335 | free(tmp); /* Return to system rool */ |
|---|
| 336 | last_file = i; |
|---|
| 337 | fill_buffer(xmysp, fp); |
|---|
| 338 | --rd_count; |
|---|
| 339 | switch (rd_count) { |
|---|
| 340 | case -1: |
|---|
| 341 | end_of_data = 1; |
|---|
| 342 | return; |
|---|
| 343 | case 0: |
|---|
| 344 | break; |
|---|
| 345 | default: |
|---|
| 346 | quick_sort(xmysp, buf_ptrs, 0, rd_count); |
|---|
| 347 | break; |
|---|
| 348 | } |
|---|
| 349 | next = buf_ptrs[0]; |
|---|
| 350 | end_of_data = 0; |
|---|
| 351 | } |
|---|
| 352 | void generate_run(xmysp, srcx) |
|---|
| 353 | MYS_STRU *xmysp; |
|---|
| 354 | FILE *srcx; /* Use avail memory to gen maximally large runs */ |
|---|
| 355 | { /* init_buf() loaded and presorted buffer */ |
|---|
| 356 | size_t i; |
|---|
| 357 | size_t w; |
|---|
| 358 | if (end_of_data) |
|---|
| 359 | return; |
|---|
| 360 | memmove(last_item[select], buf_ptrs[rd_count], rsize); |
|---|
| 361 | for (i = 0; i <= rd_count; i++) { |
|---|
| 362 | w = fwrite(buf_ptrs[i],rsize,(size_t)1,tmp_files[select]); |
|---|
| 363 | if (w != 1) |
|---|
| 364 | serror(WRITE_ERR); |
|---|
| 365 | } |
|---|
| 366 | fflush(tmp_files[select]); |
|---|
| 367 | fill_buffer(xmysp, srcx); |
|---|
| 368 | --rd_count; |
|---|
| 369 | switch (rd_count) { |
|---|
| 370 | case -1: /* Nothing read */ |
|---|
| 371 | end_of_data = 1; |
|---|
| 372 | break; |
|---|
| 373 | case 0: /* One item read */ |
|---|
| 374 | break; |
|---|
| 375 | default: |
|---|
| 376 | quick_sort(xmysp, buf_ptrs, 0, rd_count); |
|---|
| 377 | break; |
|---|
| 378 | } |
|---|
| 379 | next = buf_ptrs[0]; |
|---|
| 380 | } |
|---|
| 381 | void fill_buffer(xmysp, fp) |
|---|
| 382 | MYS_STRU *xmysp; |
|---|
| 383 | FILE *fp; /* Fill sort buffer from source file */ |
|---|
| 384 | { |
|---|
| 385 | void **p; |
|---|
| 386 | void *bp; |
|---|
| 387 | int i; |
|---|
| 388 | size_t j, cnt, num_to_read; |
|---|
| 389 | if (feof(fp)) { |
|---|
| 390 | rd_count = 0; |
|---|
| 391 | return; |
|---|
| 392 | } |
|---|
| 393 | p = buf_ptrs; |
|---|
| 394 | rd_count = 0; |
|---|
| 395 | num_to_read = max_items; /* Try for a full buffer */ |
|---|
| 396 | for (i = 0; i < last_minus_one; i++) { /* Read across boundaries */ |
|---|
| 397 | cnt = fread(top[i], rsize, num_to_read, fp); |
|---|
| 398 | rd_count += cnt; |
|---|
| 399 | bp = top[i]; |
|---|
| 400 | for (j = 0; j < cnt; j++) { /* Set pointers to items for sort */ |
|---|
| 401 | *p++ = bp; |
|---|
| 402 | /* (char *)bp += rsize; */ |
|---|
| 403 | bp = (void *)((char *)bp + rsize); |
|---|
| 404 | |
|---|
| 405 | } |
|---|
| 406 | if (cnt < max_items) /* EOF */ |
|---|
| 407 | break; |
|---|
| 408 | if (rd_count + max_items >= num_ptrs) /* Don't read too much */ |
|---|
| 409 | num_to_read = num_ptrs - rd_count; |
|---|
| 410 | } |
|---|
| 411 | } |
|---|
| 412 | void b_set_rd(xmysp, n) |
|---|
| 413 | MYS_STRU *xmysp; |
|---|
| 414 | int n; |
|---|
| 415 | { |
|---|
| 416 | rewind(tmp_files[n]); |
|---|
| 417 | bfill(xmysp, n); /* Fill buffer */ |
|---|
| 418 | } |
|---|
| 419 | void bfill(xmysp, n) |
|---|
| 420 | MYS_STRU *xmysp; |
|---|
| 421 | int n; |
|---|
| 422 | { |
|---|
| 423 | size_t cnt; |
|---|
| 424 | rpos[n] = spos[n] = top[n]; |
|---|
| 425 | if (feof(tmp_files[n])) { |
|---|
| 426 | end_data[n] = 1; |
|---|
| 427 | return; |
|---|
| 428 | } |
|---|
| 429 | cnt = fread(top[n], rsize, max_items, tmp_files[n]); |
|---|
| 430 | if (cnt == 0) { |
|---|
| 431 | end_data[n] = 1; |
|---|
| 432 | return; |
|---|
| 433 | } |
|---|
| 434 | /* (char *)spos[n] += cnt * rsize; */ |
|---|
| 435 | spos[n] = (char *)spos[n] + cnt * rsize; |
|---|
| 436 | buf_cnt[n] = 0; |
|---|
| 437 | end_data[n] = 0; |
|---|
| 438 | next_item[n] = top[n]; |
|---|
| 439 | } |
|---|
| 440 | void b_set_wr(xmysp, n) |
|---|
| 441 | MYS_STRU *xmysp; |
|---|
| 442 | int n; |
|---|
| 443 | { |
|---|
| 444 | spos[n] = rpos[n] = top[n]; |
|---|
| 445 | fclose(tmp_files[n]); /* Truncate file */ |
|---|
| 446 | tmp_files[n] = fopen(fnames[n], "wb+"); |
|---|
| 447 | if (tmp_files[n] == NULL) |
|---|
| 448 | serror(OPEN_ERR); |
|---|
| 449 | buf_cnt[n] = 0; |
|---|
| 450 | } |
|---|
| 451 | void bflush(xmysp, n) |
|---|
| 452 | MYS_STRU *xmysp; |
|---|
| 453 | int n; /* Flush write buffer */ |
|---|
| 454 | { |
|---|
| 455 | size_t w; |
|---|
| 456 | memmove(bs, buf, rsize); /* Save! We are going to flush */ |
|---|
| 457 | buf = bs; |
|---|
| 458 | w = fwrite(rpos[n], rsize, buf_cnt[n], tmp_files[n]); |
|---|
| 459 | if (w != buf_cnt[n]) |
|---|
| 460 | serror(WRITE_ERR); |
|---|
| 461 | fflush(tmp_files[n]); |
|---|
| 462 | buf_cnt[n] = 0; |
|---|
| 463 | spos[n] = rpos[n] = top[n]; /* Buffer empty */ |
|---|
| 464 | } |
|---|
| 465 | void bmove(xmysp, n, m) |
|---|
| 466 | MYS_STRU *xmysp; |
|---|
| 467 | int n; /* Index of destination buffer */ |
|---|
| 468 | int m; /* Index of source buffer */ |
|---|
| 469 | { |
|---|
| 470 | if (end_data[m]) |
|---|
| 471 | return; |
|---|
| 472 | memmove(spos[n], next_item[m], rsize); |
|---|
| 473 | buf = spos[n]; |
|---|
| 474 | /* (char *)spos[n] += rsize; */ |
|---|
| 475 | spos[n] = (char *)spos[n] + rsize; |
|---|
| 476 | buf_cnt[n]++; |
|---|
| 477 | if (buf_cnt[n] == max_items) |
|---|
| 478 | bflush(xmysp, n); |
|---|
| 479 | /* (char *)rpos[m] += rsize; */ |
|---|
| 480 | rpos[m] = (char *)rpos[m] + rsize; |
|---|
| 481 | buf_cnt[m]++; |
|---|
| 482 | if(rpos[m] >= spos[m]) |
|---|
| 483 | bfill(xmysp, m); |
|---|
| 484 | else |
|---|
| 485 | next_item[m] = rpos[m]; |
|---|
| 486 | } |
|---|
| 487 | |
|---|
| 488 | int funserror(xmysp, e) |
|---|
| 489 | MYS_STRU *xmysp; |
|---|
| 490 | int e; /* Minimal error handler */ |
|---|
| 491 | { |
|---|
| 492 | int i; |
|---|
| 493 | myserror=e; |
|---|
| 494 | if (src) { |
|---|
| 495 | fclose(src); src=NULL; /* AOT 19/09/2001 */ |
|---|
| 496 | } |
|---|
| 497 | for (i = 0; i < last_file; i++) { |
|---|
| 498 | if (tmp_files[index[i]]) { |
|---|
| 499 | fclose(tmp_files[index[i]]); tmp_files[index[i]]=NULL; |
|---|
| 500 | remove(fnames[index[i]]); |
|---|
| 501 | } |
|---|
| 502 | } |
|---|
| 503 | buf_free(xmysp); |
|---|
| 504 | return(e); |
|---|
| 505 | } |
|---|
| 506 | |
|---|
| 507 | void buf_free(xmysp) |
|---|
| 508 | MYS_STRU *xmysp; |
|---|
| 509 | { |
|---|
| 510 | /*register*/ int i; |
|---|
| 511 | if (bs) { free(bs); bs=NULL; } |
|---|
| 512 | for (i = 0; i < TMP_FILES; i++) |
|---|
| 513 | if (last_item[i]) { free(last_item[i]); last_item[i]=NULL; } |
|---|
| 514 | for (i = 0; i < TMP_FILES - 1; i++) /* MYSFUN !! */ |
|---|
| 515 | if (top[i]) { free(top[i]); top[i]=NULL; } |
|---|
| 516 | |
|---|
| 517 | if (buf_ptrs) { free(buf_ptrs); buf_ptrs=NULL; } |
|---|
| 518 | } |
|---|
| 519 | void quick_sort(xmysp, a, l, r) |
|---|
| 520 | MYS_STRU *xmysp; |
|---|
| 521 | void *a[]; /* Array of pointers to sort */ |
|---|
| 522 | int l, r; /* Left and right index */ |
|---|
| 523 | { |
|---|
| 524 | /*register*/ int i; |
|---|
| 525 | /*register*/ int j; |
|---|
| 526 | void *mid; |
|---|
| 527 | void *tmp; |
|---|
| 528 | struct stack { |
|---|
| 529 | int l; |
|---|
| 530 | int r; |
|---|
| 531 | }; |
|---|
| 532 | struct stack s[MAX_STK]; /* Local stack variable */ |
|---|
| 533 | struct stack *sp; |
|---|
| 534 | if (xmysp) if (!xmysp) return; /* no warning */ |
|---|
| 535 | sp = s; |
|---|
| 536 | sp->l = l; /* Stack initial request */ |
|---|
| 537 | (sp++)->r = r; |
|---|
| 538 | do { |
|---|
| 539 | l = (--sp)->l; /* Retrieve partition bounds from stack */ |
|---|
| 540 | r = sp->r; |
|---|
| 541 | do { |
|---|
| 542 | i = l; /* Split into two halves */ |
|---|
| 543 | j = r; |
|---|
| 544 | mid = a[(l + r)/2]; |
|---|
| 545 | do { |
|---|
| 546 | while(memcmp(a[i], mid, rec_len) < 0) i++; |
|---|
| 547 | while(memcmp(a[j], mid, rec_len) > 0) j--; |
|---|
| 548 | if (i <= j) { /* Swap */ |
|---|
| 549 | tmp = a[i]; |
|---|
| 550 | a[i++] = a[j]; |
|---|
| 551 | a[j--] = tmp; |
|---|
| 552 | } |
|---|
| 553 | } while (i <= j); |
|---|
| 554 | if (j - l < r - i) { /* Left partition smaller? */ |
|---|
| 555 | if (i < r) { /* And bigger than one item? */ |
|---|
| 556 | sp->l = i; /* Stack right partition */ |
|---|
| 557 | (sp++)->r = r; |
|---|
| 558 | } |
|---|
| 559 | r = j; /* Sort left partition */ |
|---|
| 560 | } else { /* Right partition = left */ |
|---|
| 561 | if (l < j) { /* Bigger than one item? */ |
|---|
| 562 | sp->l = l; /* Stack left partition */ |
|---|
| 563 | (sp++)->r = j; |
|---|
| 564 | } |
|---|
| 565 | l = i; /* Sort right partition */ |
|---|
| 566 | } |
|---|
| 567 | } while (l < r); /* Repeat until partition size is zero */ |
|---|
| 568 | } while (sp != s); /* Continue until stack is empty */ |
|---|
| 569 | } |
|---|
| 570 | |
|---|
| 571 | |
|---|
| 572 | #if !MYSFUN |
|---|
| 573 | int cisis_mysfunc(char *xgidbnp, int xparmlen, char *xparmin, char *xparmout, LONGX xparmtell); |
|---|
| 574 | #endif /* MYSFUN */ |
|---|
| 575 | |
|---|
| 576 | /* MYSFUN */ |
|---|
| 577 | int cisis_mysfunc(parmgidbnp, parmlen, parmin, parmout, parmtell) |
|---|
| 578 | char *parmgidbnp; /* dbn.par */ |
|---|
| 579 | int parmlen; |
|---|
| 580 | char *parmin; |
|---|
| 581 | char *parmout; |
|---|
| 582 | LONGX parmtell; |
|---|
| 583 | { |
|---|
| 584 | MYS_STRU *xmysp; |
|---|
| 585 | int rc; |
|---|
| 586 | |
|---|
| 587 | /* |
|---|
| 588 | #if CICPP |
|---|
| 589 | xmysp=(MYS_STRU *)new char[sizeof(MYS_STRU)]; |
|---|
| 590 | #else |
|---|
| 591 | */ |
|---|
| 592 | xmysp=(MYS_STRU *)ALLOC((ALLOPARM)sizeof(MYS_STRU)); |
|---|
| 593 | /* |
|---|
| 594 | #endif |
|---|
| 595 | */ |
|---|
| 596 | if (xmysp == (MYS_STRU *)NULL) return(PROG_ERR); |
|---|
| 597 | memset(xmysp,0x00,sizeof(MYS_STRU)); |
|---|
| 598 | gidbnp=parmgidbnp; |
|---|
| 599 | |
|---|
| 600 | if (parmtell) printf("starting sort.. (%d,%s,%s)\n",rec_len,parmin,parmout); |
|---|
| 601 | |
|---|
| 602 | #if CIAPI |
|---|
| 603 | ciapip = cisisApplication( MAXNREC,MAXNTRM );/* mandatory for CIAPI definitions */ |
|---|
| 604 | #endif /* CIAPI */ |
|---|
| 605 | |
|---|
| 606 | rc=poly_sort(xmysp, parmin, parmlen, parmout); |
|---|
| 607 | |
|---|
| 608 | #if CIAPI |
|---|
| 609 | cisisApplicationDelete( ciapip ); |
|---|
| 610 | #endif /* CIAPI */ |
|---|
| 611 | |
|---|
| 612 | if (parmtell) |
|---|
| 613 | if (rc) |
|---|
| 614 | printf("sort error #%d\n",rc); |
|---|
| 615 | else |
|---|
| 616 | printf("sort completed (files used: %d)\n",last_file); |
|---|
| 617 | |
|---|
| 618 | /* |
|---|
| 619 | #if CICPP |
|---|
| 620 | delete [] (char *)xmysp; |
|---|
| 621 | #else |
|---|
| 622 | */ |
|---|
| 623 | FREE(xmysp); |
|---|
| 624 | /* |
|---|
| 625 | #endif |
|---|
| 626 | */ |
|---|
| 627 | return(rc); |
|---|
| 628 | } |
|---|
| 629 | /* MYSFUN */ |
|---|
| 630 | |
|---|
| 631 | |
|---|
| 632 | #if MYSMAIN || !MYSFUN |
|---|
| 633 | #include "cirun.h" |
|---|
| 634 | void main(argc, argv) |
|---|
| 635 | int argc; |
|---|
| 636 | char *argv[]; |
|---|
| 637 | { |
|---|
| 638 | int parmlen; |
|---|
| 639 | char *parmin=argv[2]; |
|---|
| 640 | char *parmout=argv[3]; |
|---|
| 641 | LONGX parmtell=1; |
|---|
| 642 | int rc; |
|---|
| 643 | |
|---|
| 644 | int link1len=LE1+1+8+(LIND||ciiflfim?0:1+5+1+4+1+4)+(CRLF?2:1); /* 27: key %8ld %5d %4d %4d */ |
|---|
| 645 | int link2len=LE2+1+8+(LIND||ciiflfim?0:1+5+1+4+1+4)+(CRLF?2:1); /* 57: key %8ld %5d %4d %4d */ |
|---|
| 646 | |
|---|
| 647 | if (argc < 4) { /* Parse command line */ |
|---|
| 648 | printf("%s",cicopyr("Utility MYS")); |
|---|
| 649 | printf("\n"); |
|---|
| 650 | printf("mys {link1|link2|<preclen>} <fileln> <filelk> [<option> [...]] \n"); |
|---|
| 651 | printf("\n"); |
|---|
| 652 | printf("options: tell=<n> \n"); |
|---|
| 653 | /*printf(" +fix/m \n");*/ |
|---|
| 654 | printf("\n"); |
|---|
| 655 | printf("\n"); |
|---|
| 656 | printf(" Ex: mys %d x.ln1 x.lk1 \n",link1len); |
|---|
| 657 | printf(" mys link1 x.ln1 x.lk1 tell=0 \n"); |
|---|
| 658 | printf(" \n"); |
|---|
| 659 | printf(" Ex: mys %d x.ln1 x.lk1 \n",link2len); |
|---|
| 660 | printf(" mys link2 x.ln2 x.lk2 tell=0 \n"); |
|---|
| 661 | printf("\n"); |
|---|
| 662 | exit(0); |
|---|
| 663 | } |
|---|
| 664 | |
|---|
| 665 | parmlen = atoi(argv[1]); |
|---|
| 666 | if (strcmp(argv[1],"link1") == 0) parmlen=link1len; |
|---|
| 667 | if (strcmp(argv[1],"link2") == 0) parmlen=link2len; |
|---|
| 668 | |
|---|
| 669 | if (argc > 4) { |
|---|
| 670 | if (strncmp(argv[4],"tell=",5) == 0) { |
|---|
| 671 | if (sscanf(argv[4]+5,"%ld",&parmtell) != 1) exit(PARM_ERR); |
|---|
| 672 | } |
|---|
| 673 | else exit(PARM_ERR); |
|---|
| 674 | } |
|---|
| 675 | |
|---|
| 676 | rc=cisis_mysfunc(NULL,parmlen,parmin,parmout,parmtell); |
|---|
| 677 | exit(rc); |
|---|
| 678 | } |
|---|
| 679 | #endif /* MYSMAIN || !MYSFUN*/ |
|---|