#include "geninc.h" /* LONG, etc. */ /***************************************************************************** * * * COMMON OCEANOGRAPHIC DATA ACCESS SYSTEM (CODAS) * * * * WRITTEN BY: RAMON CABRERA, ERIC FIRING, and JULIE RANADA * * JOINT INSTITUTE FOR MARINE AND ATMOSPHERIC RESEARCH * * 1000 POPE ROAD MSB 312 * * HONOLULU, HI 96822 * * * * VERSION: 3.10 * * * * DATE: APRIL 1989, AUGUST 1995 * * * *****************************************************************************/ /* FILE: sort.c Sorting functions. */ /*----------------------------------------------------------------------------- FUNCTION: DSRCHGE Given a key it returns the index to the first entry in the directory with key greater than or equal to the one given. PARAMETERS: key = pointer to ULONG variable where the key to search for is stored key_base = pointer to the first key in the directory entry_length = pointer to variable containing the size in BYTEs of directory entries nentries = pointer to variable containing the number of entries in the directory RETURNS: the index to the first entry found with key >= key 0 if all entries in directory have keys > key -1 if all entries have keys < key CALLED FROM: C, FORTRAN Modified 8/15/89 - J.R. to return -1 only if all entries have keys < key (rather than <=). This allows calling function search_for_profile_by_time to distinguish between these two conditions and signal the difference. */ #if PROTOTYPE_ALLOWED LONG DSRCHGE(ULONG *key, CHAR *key_base, int *entry_length, int *nentries) #else LONG DSRCHGE(key, key_base, entry_length, nentries) ULONG *key; CHAR *key_base; int *entry_length, *nentries; #endif #define KEY(x) *( (ULONG *) (key_base + (x) * (*entry_length)) ) { int i1, i2, im, il; if (* (ULONG *) key_base >= *key) return(0); if (KEY(*nentries - 1) < *key) return(-1); /* jr- */ if (KEY(*nentries - 1) == *key) return(*nentries - 1); /* jr+ */ i1 = il = 0; i2 = *nentries - 1; im = (i1 + i2) / 2; while (il != im) /* binary search */ { if (KEY(im) >= *key) if (KEY(im - 1) < *key) return(im); else im = ((i2 = il = im) + i1) / 2; /* search top half */ else im = ((i1 = il = im) + i2) / 2; /* search bottom half */ } return(i2); } /*----------------------------------------------------------------------------- FUNCTION: dir_search_GE_file Given a key it returns the index to the first entry in the directory with key greater or equal than the one given. This function differs from DSRCHGE in that the directory is in a file, not in memory. PARAMETERS: fp = file pointer for directory file key = key to search for key_base = offset from beginning of file of first key in the directory entry_length = size in BYTEs of a directory entry nentries = number of entries in directory RETURNS: the index to the first entry found with key >= key 0 if all entries in directory have keys > key -1 if all entries have keys < key <-1 if an i/o error occurs CALLED FROM: C, FORTRAN Modified 8/15/89 - J.R. to return -1 only if all entries have keys < key (rather than <=). This allows calling function search_for_profile_by_time to distinguish between these two conditions and signal the difference. */ #if PROTOTYPE_ALLOWED int dir_search_GE_file(FILE *fp, ULONG key, ULONG key_base, int entry_length, int nentries, int from, int to) #else int dir_search_GE_file(fp, key, key_base, entry_length, nentries, from, to) FILE *fp; int entry_length, nentries, from, to; ULONG key, key_base; #endif { int i1, i2, im, il; ULONG ofs; if (read_long(fp, key_base, from, to) >= key) return(0); i2 = nentries - 1; if (read_long(fp, key_base + i2 * entry_length, from, to) < key) return(-1); /* jr- */ if (read_long(fp, key_base + i2 * entry_length, from, to) == key) return(i2); /* jr+ */ i1 = il = 0; im = (i1 + i2) / 2; while (il != im) { if (read_long(fp, (ofs = key_base + im * entry_length), from, to) >= key) if (read_long(fp, ofs - entry_length, from, to) < key) return(im); else im = ((i2 = il = im) + i1) / 2; else im = ((i1 = il = im) + i2) / 2; } return(i2); } /*----------------------------------------------------------------------------- FUNCTION: DSORTAS It sorts a directory into ascending order by time using the heapsort algorithm. PARAMETERS: dir_base = pointer to directory structure (not necessarily the same as key_base) key_base = pointer to the first key in the directory entry_length = pointer to ULONG variable containing the size in BYTEs of a directory entry nentries = pointer to ULONG variable containing the number of entries in the directory RETURNS: VOID CALLED FROM: C, FORTRAN */ #if PROTOTYPE_ALLOWED void DSORTAS(CHAR *dir_base, CHAR *key_base, int *entry_length, int *nentries) #else void DSORTAS(dir_base, key_base, entry_length, nentries) CHAR *dir_base, *key_base; int *entry_length, *nentries; #endif { int i, i1, j, n, *ind; CHAR *e1, *e2, *temp_entry; if ((*nentries) < 2) return; ind = (int *) malloc( (*nentries) * sizeof(int)); temp_entry = (CHAR *) malloc( (*entry_length) ); sort_dir_index((*nentries), ind, key_base, (*entry_length) ); n = 0; for (i1=0; i1<(*nentries); i1++) { j = ind[(i = i1)]; if (j >= 0) { if (i != j) { while (ind[j] >= 0) { e1 = dir_base + i * (*entry_length); e2 = dir_base + j * (*entry_length); move_byte(e1, temp_entry, (*entry_length) ); move_byte(e2, e1, (*entry_length) ); move_byte(temp_entry, e2, (*entry_length) ); ind[i] = -1; i = j; j = ind[i]; n++; } ind[i] = -1; n++; } if (n >= (*nentries)) { free(ind); free(temp_entry); return; } } } free(ind); free(temp_entry); return; } /*----------------------------------------------------------------------------- FUNCTION: sort_dir_index It is an auxiliary function to DSORTAS and does the actual sorting of the directory using the heapsort algorithm. An index array is used to store the order in which the elements should be sorted. (c) 1986 Numerical Recipes Software Reproduced by permission, from the book Numerical Recipes: The Art of Scientific Computing, published by Cambridge University Press This routine is translated from the Pascal routine given in Numerical Recipes: PROCEDURE indexx(n: integer; arrin: glsarray; VAR indx: gliarray); (* Programs using routine INDEXX must define the types TYPE glsarray = ARRAY [1..np] OF real; gliarray = ARRAY [1..np] OF integer; in the main routine, with np >= n. *) l,j,ir,indxt,i: integer; q: real; Translation by Eric Firing, Sept. 13, 1987. indexx() is based on the heapsort algorithm. The calling routine supplies pointers to the start of an array of numbers to be sorted, and to the start of an integer index array. indexx() fills the index array, and then rearranges it so that it contains the indices, in order of the sorted elements in arrin. sort_dir_index() is a simple adaptation of indexx(), using the definition _key(i) in place of the key array. PARAMETERS: n = the number of entries in the directory indx = the index array in which the correct order of directory entries will be stored key_base = pointer to first key in the directory entry_length = size in bytes of a directory entry */ #if PROTOTYPE_ALLOWED void sort_dir_index(int n, int *indx, CHAR *key_base, int entry_length) #else void sort_dir_index(n, indx, key_base, entry_length) int n, *indx, entry_length; CHAR *key_base; #endif #define _key(ii) ( *( (LONG *) (key_base+(entry_length)*(ii)) ) ) { int l,j,ir,indxt,i; LONG q; /* ef: used to be float */ for (j=0; j 0) { indxt = indx[--l]; q = _key(indxt); } else { indxt = indx[ir]; q = _key(indxt); indx[ir--] = indx[0]; if (ir == 0) { indx[0] = indxt; return; /* This is the only exit. */ } } i = l; j = l+l+1; while (j <= ir) { if (j < ir) if (_key(indx[j]) < _key(indx[j+1])) j++; if (q < _key(indx[j])) { indx[i] = indx[j]; i = j; j += j+1; } else j = ir + 1; } indx[i] = indxt; } } /*----------------------------------------------------------------------------- FUNCTION: read_long It returns a long integer read at a given offset into a file. PARAMETERS: fp = pointer to file to read from ofs = offset into file from which to start reading long integer RETURNS: the long integer read, if successful SEEK_ERROR or READ_ERROR otherwise NOTE: there is really no way that the calling function would be able to distinguish from the return value whether a SEEK or READ error has occurred--we could change this to read_ulong (since the calling f'n above dir_srch_GE_file really wants a ULONG) if a problem ever arises CALLED FROM: C */ #if PROTOTYPE_ALLOWED LONG read_long(FILE *fp, long ofs, int from, int to) #else LONG read_long(fp, ofs, from, to) FILE *fp; long ofs; int from, to; #endif { LONG long_value; if (fseek(fp, ofs, 0)) return(SEEK_ERROR); if ((fread((char *)&long_value, 1, sizeof(LONG), fp)) != sizeof(LONG)) return(READ_ERROR); if (from != to) convert_array_long((char *)&long_value, (char *)&long_value, from, to, 1); return(long_value); }