home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume7 / rvi / part1 / binsearch.c next >
Encoding:
Text File  |  1986-11-30  |  1.8 KB  |  67 lines
  1. /*        binsearch - do a binary search of a structure.
  2.         84/04/07.  A. E. Klietz.
  3. */
  4.  
  5. binsearch(match_string, structarray, size_struct, num_structs)
  6. /* Search an array of structures for the "match_string" and return
  7.             -2 if match_string is not unique
  8.             -1 if match_string was not found
  9.              i if ith structure matches match_string
  10.  
  11.    Each structure contains a string to be compared.
  12. The structure array must be alphabetized.  No error message is
  13. printed.
  14.     The structure must be aligned at least as well as a pointer. */
  15.  
  16. char    *match_string;    /* string to match */
  17. register char    *structarray;    /* array of structures to search */
  18. short     size_struct;    /* size of each structure element in bytes */
  19. short     num_structs;    /* number of structures in array */
  20. {
  21.  
  22. register short    pos, diff, lower, upper, indx;
  23.  
  24.     if (match_string[0] == '\0') /* if null string */
  25.         return(-1);  /* no match */
  26.  
  27.     lower = 0;
  28.     upper = num_structs - 1;
  29.     do {
  30.         pos = (lower + upper) / 2;
  31.         diff = strcmp(&structarray[indx = pos * size_struct], match_string);
  32.         if (diff <= 0) /* if match_string >= &structarray[pos] */
  33.             lower = pos + 1;
  34.         if (diff >= 0) /* if match_string <= &structarray[pos] */
  35.             upper = pos - 1;
  36.     } while (lower <= upper);
  37.  
  38.     if (strcmp(&structarray[indx], match_string) == 0) 
  39.         return(pos);
  40.  
  41.     if (!substring(match_string, &structarray[indx])) {
  42.         ++pos;
  43.         indx = pos * size_struct;
  44.         if (pos > num_structs - 1 || !substring(match_string, &structarray[indx]))
  45.             return(-1);
  46.     }
  47.     
  48.     if (pos < num_structs - 1)
  49.         if (substring(match_string, &structarray[(pos + 1) * size_struct]))
  50.             return(-2); /* not unique error. */
  51.  
  52.     return(pos);
  53. }
  54.  
  55.  
  56. substring(part, full)
  57. /* Returns TRUE if "part" is a left anchored substring of "full". */
  58.  
  59. register char    *part, *full;
  60. {
  61.     register    char    ch;
  62.  
  63.     while ((ch = *part++) == *full++ && ch != '\0')
  64.         ;
  65.     return(ch == '\0');    
  66. }
  67.