#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. */ LONG DSRCHGE(ULONG *key, CHAR *key_base, int *entry_length, int *nentries) #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. */ int dir_search_GE_file(FILE *fp, ULONG key, ULONG key_base, int entry_length, int nentries, int from, int to) { 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 */ void DSORTAS(CHAR *dir_base, CHAR *key_base, int *entry_length, int *nentries) { 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 This is an auxiliary function to DSORTAS that finds the sorted order of the directory using insertion sort. An index array is used to store the order in which the elements should be sorted. The insertion sort is a stable algorithm (preserves original order of equal entries) that is very fast in the most typical use case here, where the table is already sorted. 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 */ void sort_dir_index(int n, int *indx, CHAR *key_base, int entry_length) #define _key(ii) ( *( (LONG *) (key_base+(entry_length)*(ii)) ) ) { int i, j; LONG q; /* Initialize the index array */ for (j=0; j=0 && _key(indx[j]) > q) { indx[j+1] = indx[j]; j--; } indx[j+1] = i; } } /*----------------------------------------------------------------------------- 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 */ LONG read_long(FILE *fp, long ofs, int from, int to) { 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); }