home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 2 / RISC_DISC_2.iso / pd_share / utilities / cli / gnuinfo / Source / c / search < prev    next >
Encoding:
Text File  |  1994-10-01  |  14.2 KB  |  570 lines
  1. #include "defines.h"
  2. /* search.c -- How to search large bodies of text. */
  3.  
  4. /* This file is part of GNU Info, a program for reading online documentation
  5.    stored in Info format.
  6.  
  7.    Copyright (C) 1993 Free Software Foundation, Inc.
  8.  
  9.    This program is free software; you can redistribute it and/or modify
  10.    it under the terms of the GNU General Public License as published by
  11.    the Free Software Foundation; either version 2, or (at your option)
  12.    any later version.
  13.  
  14.    This program is distributed in the hope that it will be useful,
  15.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.    GNU General Public License for more details.
  18.  
  19.    You should have received a copy of the GNU General Public License
  20.    along with this program; if not, write to the Free Software
  21.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22.  
  23.    Written by Brian Fox (bfox@ai.mit.edu). */
  24.  
  25. #include <ctype.h>
  26. #include <sys/types.h>
  27. #include <sys/stat.h>
  28. #include "general.h"
  29. #include "search.h"
  30. #include "nodes.h"
  31.  
  32. #if !defined (NULL)
  33. #  define NULL 0x0
  34. #endif /* !NULL */
  35.  
  36. /* The search functions take two arguments:
  37.  
  38.      1) a string to search for, and
  39.  
  40.      2) a pointer to a SEARCH_BINDING which contains the buffer, start,
  41.         and end of the search.
  42.  
  43.    They return a long, which is the offset from the start of the buffer
  44.    at which the match was found.  An offset of -1 indicates failure. */
  45.  
  46. /* A function which makes a binding with buffer and bounds. */
  47. SEARCH_BINDING *
  48. make_binding (buffer, start, end)
  49.      char *buffer;
  50.      long start, end;
  51. {
  52.   SEARCH_BINDING *binding;
  53.  
  54.   binding = (SEARCH_BINDING *)xmalloc (sizeof (SEARCH_BINDING));
  55.   binding->buffer = buffer;
  56.   binding->start = start;
  57.   binding->end = end;
  58.   binding->flags = 0;
  59.  
  60.   return (binding);
  61. }
  62.  
  63. /* Make a copy of BINDING without duplicating the data. */
  64. SEARCH_BINDING *
  65. copy_binding (binding)
  66.      SEARCH_BINDING *binding;
  67. {
  68.   SEARCH_BINDING *copy;
  69.  
  70.   copy = make_binding (binding->buffer, binding->start, binding->end);
  71.   copy->flags = binding->flags;
  72.   return (copy);
  73. }
  74.  
  75.  
  76. /* **************************************************************** */
  77. /*                                    */
  78. /*           The Actual Searching Functions            */
  79. /*                                    */
  80. /* **************************************************************** */
  81.  
  82. /* Search forwards or backwards for the text delimited by BINDING.
  83.    The search is forwards if BINDING->start is greater than BINDING->end. */
  84. long
  85. search (string, binding)
  86.      char *string;
  87.      SEARCH_BINDING *binding;
  88. {
  89.   long result;
  90.  
  91.   /* If the search is backwards, then search backwards, otherwise forwards. */
  92.   if (binding->start > binding->end)
  93.     result = search_backward (string, binding);
  94.   else
  95.     result = search_forward (string, binding);
  96.  
  97.   return (result);
  98. }
  99.  
  100. /* Search forwards for STRING through the text delimited in BINDING. */
  101. long
  102. search_forward (string, binding)
  103.      char *string;
  104.      SEARCH_BINDING *binding;
  105. {
  106.   register int c, i, len;
  107.   register char *buff, *end;
  108.   char *alternate = (char *)NULL;
  109.  
  110.   len = strlen (string);
  111.  
  112.   /* We match characters in the search buffer against STRING and ALTERNATE.
  113.      ALTERNATE is a case reversed version of STRING; this is cheaper than
  114.      case folding each character before comparison.   Alternate is only
  115.      used if the case folding bit is turned on in the passed BINDING. */
  116.  
  117.   if (binding->flags & S_FoldCase)
  118.     {
  119.       alternate = savestring (string);
  120.  
  121.       for (i = 0; i < len; i++)
  122.     {
  123.       if (islower (alternate[i]))
  124.         alternate[i] = toupper (alternate[i]);
  125.       else if (isupper (alternate[i]))
  126.         alternate[i] = tolower (alternate[i]);
  127.     }
  128.     }
  129.  
  130.   buff = binding->buffer + binding->start;
  131.   end = binding->buffer + binding->end + 1;
  132.  
  133.   while (buff < (end - len))
  134.     {
  135.       for (i = 0; i < len; i++)
  136.     {
  137.       c = buff[i];
  138.  
  139.       if ((c != string[i]) && (!alternate || c != alternate[i]))
  140.         break;
  141.     }
  142.  
  143.       if (!string[i])
  144.     {
  145.       if (alternate)
  146.         free (alternate);
  147.       if (binding->flags & S_SkipDest)
  148.         buff += len;
  149.       return ((long) (buff - binding->buffer));
  150.     }
  151.  
  152.       buff++;
  153.     }
  154.  
  155.   if (alternate)
  156.     free (alternate);
  157.  
  158.   return ((long) -1);
  159. }
  160.  
  161. /* Search for STRING backwards through the text delimited in BINDING. */
  162. long
  163. search_backward (input_string, binding)
  164.      char *input_string;
  165.      SEARCH_BINDING *binding;
  166. {
  167.   register int c, i, len;
  168.   register char *buff, *end;
  169.   char *string;
  170.   char *alternate = (char *)NULL;
  171.  
  172.   len = strlen (input_string);
  173.  
  174.   /* Reverse the characters in the search string. */
  175.   string = (char *)xmalloc (1 + len);
  176.   for (c = 0, i = len - 1; input_string[c]; c++, i--)
  177.     string[i] = input_string[c];
  178.  
  179.   string[c] = '\0';
  180.  
  181.   /* We match characters in the search buffer against STRING and ALTERNATE.
  182.      ALTERNATE is a case reversed version of STRING; this is cheaper than
  183.      case folding each character before comparison.   ALTERNATE is only
  184.      used if the case folding bit is turned on in the passed BINDING. */
  185.  
  186.   if (binding->flags & S_FoldCase)
  187.     {
  188.       alternate = savestring (string);
  189.  
  190.       for (i = 0; i < len; i++)
  191.     {
  192.       if (islower (alternate[i]))
  193.         alternate[i] = toupper (alternate[i]);
  194.       else if (isupper (alternate[i]))
  195.         alternate[i] = tolower (alternate[i]);
  196.     }
  197.     }
  198.  
  199.   buff = binding->buffer + binding->start;
  200.   end = binding->buffer + binding->end;
  201.  
  202.   while (buff > end + len)
  203.     {
  204.       for (i = 0; i < len; i++)
  205.     {
  206.       c = *(buff - i);
  207.  
  208.       if (c != string[i] && (alternate && c != alternate[i]))
  209.         break;
  210.     }
  211.  
  212.       if (!string[i])
  213.     {
  214.       free (string);
  215.       if (alternate)
  216.         free (alternate);
  217.  
  218.       if (binding->flags & S_SkipDest)
  219.         buff -= len;
  220.       return ((long) (1 + (buff - binding->buffer)));
  221.     }
  222.  
  223.       buff--;
  224.     }
  225.  
  226.   free (string);
  227.   if (alternate)
  228.     free (alternate);
  229.  
  230.   return ((long) -1);
  231. }
  232.  
  233. /* Find STRING in LINE, returning the offset of the end of the string.
  234.    Return an offset of -1 if STRING does not appear in LINE.  The search
  235.    is bound by the end of the line (i.e., either NEWLINE or 0). */
  236. int
  237. string_in_line (string, line)
  238.      char *string, *line;
  239. {
  240.   register int end;
  241.   SEARCH_BINDING binding;
  242.  
  243.   /* Find the end of the line. */
  244.   for (end = 0; line[end] && line[end] != '\n'; end++);
  245.  
  246.   /* Search for STRING within these confines. */
  247.   binding.buffer = line;
  248.   binding.start = 0;
  249.   binding.end = end;
  250.   binding.flags = S_FoldCase | S_SkipDest;
  251.  
  252.   return (search_forward (string, &binding));
  253. }
  254.  
  255. /* Return non-zero if STRING is the first text to appear at BINDING. */
  256. int
  257. looking_at (string, binding)
  258.      char *string;
  259.      SEARCH_BINDING *binding;
  260. {
  261.   long search_end;
  262.  
  263.   search_end = search (string, binding);
  264.  
  265.   /* If the string was not found, SEARCH_END is -1.  If the string was found,
  266.      but not right away, SEARCH_END is != binding->start.  Otherwise, the
  267.      string was found at binding->start. */
  268.   return (search_end == binding->start);
  269. }
  270.  
  271. /* **************************************************************** */
  272. /*                                    */
  273. /*              Small String Searches                */
  274. /*                                    */
  275. /* **************************************************************** */
  276.  
  277. /* Function names that start with "skip" are passed a string, and return
  278.    an offset from the start of that string.  Function names that start
  279.    with "find" are passed a SEARCH_BINDING, and return an absolute position
  280.    marker of the item being searched for.  "Find" functions return a value
  281.    of -1 if the item being looked for couldn't be found. */
  282.  
  283. /* Return the index of the first non-whitespace character in STRING. */
  284. int
  285. skip_whitespace (string)
  286.      char *string;
  287. {
  288.   register int i;
  289.  
  290.   for (i = 0; string && whitespace (string[i]); i++);
  291.   return (i);
  292. }
  293.  
  294. /* Return the index of the first non-whitespace or newline character in
  295.    STRING. */
  296. int
  297. skip_whitespace_and_newlines (string)
  298.      char *string;
  299. {
  300.   register int i;
  301.  
  302.   for (i = 0; string && (whitespace (string[i]) || string[i] == '\n'); i++);
  303.   return (i);
  304. }
  305.  
  306. /* Return the index of the first whitespace character in STRING. */
  307. int
  308. skip_non_whitespace (string)
  309.      char *string;
  310. {
  311.   register int i;
  312.  
  313.   for (i = 0; string && !whitespace (string[i]); i++);
  314.   return (i);
  315. }
  316.  
  317. /* Return the index of the first non-node character in STRING.  Note that
  318.    this function contains quite a bit of hair to ignore periods in some
  319.    special cases.  This is because we here at GNU ship some info files which
  320.    contain nodenames that contain periods.  No such nodename can start with
  321.    a period, or continue with whitespace, newline, or ')' immediately following
  322.    the period.  If second argument NEWLINES_OKAY is non-zero, newlines should
  323.    be skipped while parsing out the nodename specification. */
  324. int
  325. skip_node_characters (string, newlines_okay)
  326.      char *string;
  327.      int newlines_okay;
  328. {
  329.   register int c, i = 0;
  330.   int paren_seen = 0;
  331.   int paren = 0;
  332.  
  333.   /* Handle special case.  This is when another function has parsed out the
  334.      filename component of the node name, and we just want to parse out the
  335.      nodename proper.  In that case, a period at the start of the nodename
  336.      indicates an empty nodename. */
  337.   if (string && *string == '.')
  338.     return (0);
  339.  
  340.   if (string && *string == '(')
  341.     {
  342.       paren++;
  343.       paren_seen++;
  344.       i++;
  345.     }
  346.  
  347.   for (; string && (c = string[i]); i++)
  348.     {
  349.       if (paren)
  350.     {
  351.       if (c == '(')
  352.         paren++;
  353.       else if (c == ')')
  354.         paren--;
  355.  
  356.       continue;
  357.     }
  358.       
  359.       /* If the character following the close paren is a space or period,
  360.      then this node name has no more characters associated with it. */
  361.       if (c == '\t' ||
  362.       c == ','  ||
  363.       c == INFO_TAGSEP ||
  364.       ((!newlines_okay) && (c == '\n')) ||
  365.       ((paren_seen && string[i - 1] == ')') &&
  366.        (c == ' ' || c == '.')) ||
  367.       (c == '.' &&
  368.        ((!string[i + 1]) ||
  369.         (whitespace_or_newline (string[i + 1])) ||
  370.         (string[i + 1] == ')'))))
  371.     break;
  372.     }
  373.   return (i);
  374. }
  375.  
  376. #if 0
  377. /* Unix doesn't have stricmp () functions. */
  378. int
  379. stricmp (string1, string2)
  380.      char *string1, *string2;
  381. {
  382.   char ch1, ch2;
  383.  
  384.   for (;;)
  385.     {
  386.       ch1 = *string1++;
  387.       ch2 = *string2++;
  388.  
  389.       if (!(ch1 | ch2))
  390.     return (0);
  391.  
  392.       ch1 = info_toupper (ch1);
  393.       ch2 = info_toupper (ch2);
  394.  
  395.       if (ch1 != ch2)
  396.     return (ch1 - ch2);
  397.     }
  398. }
  399.  
  400. /* Compare at most COUNT characters from string1 to string2.  Case
  401.    doesn't matter. */
  402. int
  403. strnicmp (string1, string2, count)
  404.      char *string1, *string2;
  405.      int count;
  406. {
  407.   register char ch1, ch2;
  408.  
  409.   while (count)
  410.     {
  411.       ch1 = *string1++;
  412.       ch2 = *string2++;
  413.  
  414.       ch1 = info_toupper (ch1);
  415.       ch2 = info_toupper (ch2);
  416.  
  417.       if (ch1 == ch2)
  418.     count--;
  419.       else
  420.     break;
  421.     }
  422.   return (count);
  423. }
  424. #endif
  425.  
  426. /* **************************************************************** */
  427. /*                                    */
  428. /*             Searching FILE_BUFFER's                */
  429. /*                                    */
  430. /* **************************************************************** */
  431.  
  432. /* Return the absolute position of the first occurence of a node separator in
  433.    BINDING-buffer.  The search starts at BINDING->start.  Return -1 if no node
  434.    separator was found. */
  435. long
  436. find_node_separator (binding)
  437.      SEARCH_BINDING *binding;
  438. {
  439.   register long i;
  440.   char *body;
  441.  
  442.   body = binding->buffer;
  443.  
  444.   /* A node is started by [^L]^_[^L]\n.  That is to say, the C-l's are
  445.      optional, but the DELETE and NEWLINE are not.  This separator holds
  446.      true for all separated elements in an Info file, including the tags
  447.      table (if present) and the indirect tags table (if present). */
  448.   for (i = binding->start; i < binding->end - 1; i++)
  449.     if (((body[i] == INFO_FF && body[i + 1] == INFO_COOKIE) &&
  450.      (body[i + 2] == '\n' ||
  451.       (body[i + 2] == INFO_FF && body[i + 3] == '\n'))) ||
  452.     ((body[i] == INFO_COOKIE) &&
  453.      (body[i + 1] == '\n' ||
  454.       (body[i + 1] == INFO_FF && body[i + 2] == '\n'))))
  455.       return (i);
  456.   return (-1);
  457. }
  458.  
  459. /* Return the length of the node separator characters that BODY is
  460.    currently pointing at. */
  461. int
  462. skip_node_separator (body)
  463.      char *body;
  464. {
  465.   register int i;
  466.  
  467.   i = 0;
  468.  
  469.   if (body[i] == INFO_FF)
  470.     i++;
  471.  
  472.   if (body[i++] != INFO_COOKIE)
  473.     return (0);
  474.  
  475.   if (body[i] == INFO_FF)
  476.     i++;
  477.  
  478.   if (body[i++] != '\n')
  479.     return (0);
  480.  
  481.   return (i);
  482. }
  483.  
  484. /* Return the number of characters from STRING to the start of
  485.    the next line. */
  486. int
  487. skip_line (string)
  488.      char *string;
  489. {
  490.   register int i;
  491.  
  492.   for (i = 0; string && string[i] && string[i] != '\n'; i++);
  493.  
  494.   if (string[i] == '\n')
  495.     i++;
  496.  
  497.   return (i);
  498. }
  499.  
  500. /* Return the absolute position of the beginning of a tags table in this
  501.    binding starting the search at binding->start. */
  502. long
  503. find_tags_table (binding)
  504.      SEARCH_BINDING *binding;
  505. {
  506.   SEARCH_BINDING search;
  507.   long position;
  508.  
  509.   search.buffer = binding->buffer;
  510.   search.start = binding->start;
  511.   search.end = binding->end;
  512.   search.flags = S_FoldCase;
  513.  
  514.   while ((position = find_node_separator (&search)) != -1 )
  515.     {
  516.       search.start = position;
  517.       search.start += skip_node_separator (search.buffer + search.start);
  518.  
  519.       if (looking_at (TAGS_TABLE_BEG_LABEL, &search))
  520.     return (position);
  521.     }
  522.   return (-1);
  523. }
  524.  
  525. /* Return the absolute position of the node named NODENAME in BINDING.
  526.    This is a brute force search, and we wish to avoid it when possible.
  527.    This function is called when a tag (indirect or otherwise) doesn't
  528.    really point to the right node.  It returns the absolute position of
  529.    the separator preceding the node. */
  530. long
  531. find_node_in_binding (nodename, binding)
  532.      char *nodename;
  533.      SEARCH_BINDING *binding;
  534. {
  535.   register long position;
  536.   register int offset, namelen;
  537.   SEARCH_BINDING search;
  538.  
  539.   namelen = strlen (nodename);
  540.  
  541.   search.buffer = binding->buffer;
  542.   search.start = binding->start;
  543.   search.end = binding->end;
  544.   search.flags = 0;
  545.  
  546.   while ((position = find_node_separator (&search)) != -1)
  547.     {
  548.       search.start = position;
  549.       search.start += skip_node_separator (search.buffer + search.start);
  550.  
  551.       offset = string_in_line (INFO_NODE_LABEL, search.buffer + search.start);
  552.  
  553.       if (offset == -1)
  554.     continue;
  555.  
  556.       search.start += offset;
  557.       search.start += skip_whitespace (search.buffer + search.start);
  558.       offset = skip_node_characters
  559.     (search.buffer + search.start, DONT_SKIP_NEWLINES);
  560.  
  561.       /* Notice that this is an exact match.  You cannot grovel through
  562.      the buffer with this function looking for random nodes. */
  563.        if ((offset == namelen) &&
  564.        (search.buffer[search.start] == nodename[0]) &&
  565.        (strncmp (search.buffer + search.start, nodename, offset) == 0))
  566.      return (position);
  567.     }
  568.   return (-1);
  569. }
  570.