/*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*\
\                                                                          /
/   Table management                  Copyright (c)  Dmitry A. Kazakov     \
\   [search for unlimited name]                      St.Petersburg         /
/   TabParse                                         Autumn, 1993          \
\                                                                          /
/                                                                          \
\   (C, ANSI C)                       Last revision :  13:05 10 Nov 2001   /
/                                                                          \
\   This library is free software; you can redistribute it and/or modify   /
/   it  under  the  terms  of  the GNU Library General Public License as   \
\   published  by  the Free Software Foundation; either version 2 of the   /
/   License, or (at your option) any later version.                        \
\                                                                          /
/   As a special exception, if other  files  instantiate  generics  from   \
\   this unit, or you link this unit with  other  files  to  produce  an   /
/   executable, this  unit  does  not  by  itself  cause  the  resulting   \
\   executable  to  be  covered  by the GNU General Public License. This   /
/   exception  does  not  however  invalidate  any other reasons why the   \
\   executable file might be covered by the GNU Public License.            /
/                                                                          \
\   This library is distributed in the hope that it will be useful,  but   /
/   WITHOUT   ANY   WARRANTY;  without  even  the  implied  warranty  of   \
\   MERCHANTABILITY or FITNESS FOR A PARTICULAR  PURPOSE.  See  the  GNU   /
/   Library General Public License for more details.                       \
\                                                                          /
/   You  should  have  received a copy of the GNU Library General Public   \
\   License  along with this library; if not, write to the Free Software   /
/   Foundation,   Inc.,   59  Temple  Place  -  Suite  330,  Boston,  MA   \
\   02111-1307, USA                                                        /
/                                                                          \
\*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/

#include	"tab.h"		/* Table specific		*/

#ifdef NON_ANSI
#define		const
#endif	/*> NON_ANSI <*/
/*>

   TabCompare -- Pointer to the user-defined callback function

	Data	 - The parsing data (modified on success)
        ItemLen	 - The item length
        ItemName - The item

   This function compares the string with an item. The function  returns
   -1 if the string is less than the  item.  Otherwise,  the  number  of
   matched item's characters is returned. When it is equal to  the  item
   length,  the  string  is equal to the item. If not, it is lesser. The
   field of the structure pointed by the parameter Data are modified the
   item matches. 
   
   Returns :

        [-1]  The string is less than the item
        [ *]  The number of matched item characters

<*/
#ifndef NON_ANSI
static int TabCompare
(
   TabParseData	     *	Data,
   const int		ItemLen,
   const char        *	ItemName
)
#else
static int TabCompare (Data, ItemLen, ItemName)
   TabParseData	     *	Data,
   int			ItemLen;
   char		     *	ItemName;
#endif	/*> NON_ANSI <*/
{
   const char *	Line    = Data->Line;	/* The line		*/
   int		Length  = Data->Length;	/* The line length	*/
   int		Pointer = Data->Pointer;/* The line position	*/
   int		Index;			/* The item position	*/
   char		Pattern;		/* An item character	*/

   for (Index = 0; Index < ItemLen; Index++)
   {  /* Compare one character					*/
      Pattern = ItemName [Index];
      if (Data->CallBack && Pattern == Data->WildCard)
      {  /* Match the user-defined symbol			*/
         switch ((*Data->CallBack) (&Length, &Line, &Pointer, Data))
	 {  /* It is matched					*/
	    case 0 :	/* It matches				*/
	       continue;
            case 1 :	/* String is lesser			*/
	       return Index;
	    case 2 :	/* String is greater than the symbol	*/
	       return -1;
         }
      }
      if (Pointer >= Length) return Index;
      if (Line [Pointer] != Pattern)
      {  /* They do not match					*/
         if (Line [Pointer] < Pattern) return -1;
         return Index;
      }
      Pointer++;
   }
   Data->Length  = Length;
   Data->Line    = Line;
   Data->Pointer = Pointer;
   return Index;

}	/*>  TabCompare  <*/
/*>

   TabParseEx -- Context free table search (with wild-cards)

	Data	- Points to the structure TabParseData
	Table	- Points to the table

   This function searches for a specified name in the table. A partially
   binary  search  is  used  (see  TabParse).  The parameter Data is the
   pointer  to  the structure TabParseData containing the description of
   the line to be matched, the wild-card character and the  user-defined
   call-back  function  to  match  the  wild-card. The structure has the
   following fields: 

   	Length		- The length of the current line
        Line		- The current line pointer
        Pointer		- The current position within the line (0..)
        WildCard	- The wild-card character
	CallBack	- Pointer to the user-defined call-back function

   When TabParseEx has to match an item character which is equal to  the
   value of the field WildCard against the current  line, it  calls  the
   user-defined call-back function pointed by the  field  CallBack.  The
   value of WildCard is ignored if CallBack is  zero.  The  user-defined
   call-back function has the following parameters: 

	Length	- Pointer to the length of the processed line
	String	- Pointer to the line
	Pointer	- Pointer to the current line position (0..)

   The  call-back  function may change any of its parameters, if parsing
   should continue to a new line, for instance. It should return: 

        [0]  The  wild-card  character  matches  the  line.  The  values
             pointed by the parameters Length, String and Pointer should
             be correctly set by the function. 
        [1]  The unmatched part of  the  line  is  less  than  the  wild
             character. Any  modifications  of  the  parameters  Length,
             String and Pointer are ignored. 
        [2]  The  unmatched  part  of  the line is greater than the wild
             character. Any  modifications  of  the  parameters  Length,
             String and Pointer are ignored. 
   
   After completion of TabParseEx, the fields of the  structure  pointed
   by the parameter Data indicate the current line and the  position  in
   it.  They  are  not  modified  if  parsing  fails.  In  any case Line
   [Pointer] is the first unmatched line position. 

   Returns :

        [+]  TabParse returns  a  positive  number  if  the  search  was
             successful.  The  returned  value is a byte offset from the
             table beginning to the found item.
        [0]  Zero  value  is  returned  if  table  does  not contain the
             specified name. 

<*/
#ifndef NON_ANSI
element TabParseEx
(
   TabParseData	     *	Data,
   const table		Table
)
#else
element	TabParse (Data, Table)
   TabParseData	     *	Data;
   table		Table;
#endif	/*> NON_ANSI <*/
{
   TabParseData	SavedData;
   TabParseData	CurrentData;
   int		FoundItem = 0;	/* Offset to found item		*/
   int		FoundLen  = -1;	/* Length of matched item	*/
   item		Item;		/* Pointer to current item	*/
   const char *	TOCBeg;		/* TOC beginning		*/
   int		High;		/* No. of the uppermost item 	*/
   int		Low;		/* No. of the lowermost item	*/
   int		Current;	/* Current item no.		*/
   int		ItemLen;	/* Length of the item		*/
   int		MatchedLen;	/* Matched item characters	*/

   TOCBeg = TAB_TOC_BEG (Table);
   Low = 0;
   High = (TAB_TOC_END (Table) - (char *) TOCBeg) / TAB_ITEM_SIZE;
   if (High == Low) return (-(int) sizeof (TabHeader));
   Current = (High + Low) >> 1;

   SavedData.Length  = Data->Length;
   SavedData.Line    = Data->Line;
   SavedData.Pointer = Data->Pointer;

   CurrentData.Length   = Data->Length;
   CurrentData.Line     = Data->Line;
   CurrentData.Pointer  = Data->Pointer;
   CurrentData.WildCard = Data->WildCard;
   CurrentData.CallBack = Data->CallBack;

   for (;;)
   {
      Item = (item) (TOCBeg + Current * TAB_ITEM_SIZE);
      ItemLen = TAB_NAME_LENGTH (Item);
      MatchedLen =
         TabCompare
         (  &CurrentData,
	    ItemLen,   
            (  (ItemLen > TAB_EMBEDDED_NAME)
            ?  TAB_END (Table) - Item->NameField
            :  (char *) & (Item->NameField)
         )  );
      if (0 > MatchedLen) goto Down;
      if (MatchedLen < ItemLen)
      {  /*>

         The string is greater  than  the  item.  This  means  that  the
         greater items should be  tested.  However,  its  possible  that
         there are lesser items that yet match the string too. We should
         scan  them  to ensure that there is no one which is longer than
         already found ones. Example: 

	    Table:   String:
	    A
	    AC   >   AD    We must check if A fits

         <*/
         int	This ;	/* Low current item number		*/

         for (This = Current - 1; This  >= Low; --This )
         {  /* Try this one					*/
            Item = (item) (TOCBeg + This * TAB_ITEM_SIZE); 
            ItemLen = TAB_NAME_LENGTH (Item);
            if (ItemLen <= FoundLen) goto Up;
            MatchedLen =
               TabCompare
               (  &CurrentData,
	          ItemLen,   
                  (  (ItemLen > TAB_EMBEDDED_NAME)
                  ?  TAB_END (Table) - Item->NameField
                  :  (char *) & (Item->NameField)
               )  );         
            if (MatchedLen <= FoundLen) goto Up;
            if (MatchedLen >= ItemLen) goto Found;
         }
         goto Up;
      }
      if (MatchedLen <= FoundLen) goto Up;
   /*>

      An item was successfully matched. Store the result and restore the
      state. 

   <*/
   Found :

      FoundItem = ((char *) Item - (char *) Table);
      FoundLen  = ItemLen;

      Data->Length  = CurrentData.Length;
      Data->Line    = CurrentData.Line;
      Data->Pointer = CurrentData.Pointer;

      CurrentData.Length  = SavedData.Length;
      CurrentData.Line    = SavedData.Line;
      CurrentData.Pointer = SavedData.Pointer;
   /*>

      The  string is alphabetically greater than the current item. Let's
      try greater items. 

   <*/
   Up :

      Low = Current;
      Current = ((Current + High) >> 1);
      if (Current == Low) break;
      Low++;		/* Do not try it again			*/ 
      continue;
   /*>

      The  string  is  alphabetically  less than the name of the current
      item. Let's try lesser items. 

   <*/
   Down :

      High = Current;
      Current = ((Low + Current) >> 1);
      if (Current == High) break;
   }
   return (FoundItem);

}	/*>  TabParseEx  <*/
/*>

   TabParse -- Context free table search

	Length	- The line length
	String	- Pointer to the line
	Pointer	- The starting line position (0..)
	Table	- Points to the table

   This function searches for a specified name in the table. A partially
   binary search is used. The name to be  searched  is  specified  as  a
   string (the parameter String) indexed by the parameter Pointer. So it
   is assumed that the name starts  with  String  [Pointer],  while  the
   right name boundary is unknown. The  parameter  Length  just  defines
   where the string ends, rather than the actual  length  of  the  name.
   TabParse tries to match a longest item from  the  table.  On  success
   TabParse resets the parameter Pointer to point to the first unmatched
   string  character. So consequtive calls of TabParse will move Pointer
   from  left  to the right. See also TabParseEx which supports multiple
   lines and user-defined wild-card characters. 
   
   Returns :

        [+]  TabParse returns  a  positive  number  if  the  search  was
             successful.  The  returned  value is a byte offset from the
             table beginning to the found item. 
        [0]  Zero  value  is  returned  if  table  does  not contain the
             specified name. 

<*/
#ifndef NON_ANSI
element	TabParse
(
   const int		Length,
   const char        *	String,
   int	             *	Pointer,
   const table		Table
)
#else
element	TabParse (Length, String, Pointer, Table)
   int			Length;
   char              *	String;
   int	             *	Pointer;
   table		Table;
#endif	/*> NON_ANSI <*/
{
   TabParseData	Data;
   element	Result;

   Data.Length   = Length;
   Data.Line     = String;
   Data.Pointer  = Pointer [0];
   Data.CallBack = 0;

   Result = TabParseEx (&Data, Table);
   Pointer [0] = Data.Pointer;
   return (Result);

}	/*>  TabParse  <*/