NCBI C Toolkit Cross Reference

   /*   $Id: binary.h,v 1.5 1999/11/23 22:02:30 vakatov Exp $
   * ===========================================================================
   *
   *                            PUBLIC DOMAIN NOTICE
   *            National Center for Biotechnology Information (NCBI)
   *
   *  This software/database is a "United States Government Work" under the
   *  terms of the United States Copyright Act.  It was written as part of
   *  the author's official duties as a United States Government employee and
  *  thus cannot be copyrighted.  This software/database is freely available
  *  to the public for use. The National Library of Medicine and the U.S.
  *  Government do not place any restriction on its use or reproduction.
  *  We would, however, appreciate having the NCBI and the author cited in
  *  any work or product based on this material
  *
  *  Although all reasonable efforts have been taken to ensure the accuracy
  *  and reliability of the software and data, the NLM and the U.S.
  *  Government do not and cannot warrant the performance or results that
  *  may be obtained by using this software or data. The NLM and the U.S.
  *  Government disclaim all warranties, express or implied, including
  *  warranties of performance, merchantability or fitness for any particular
  *  purpose.
  *
  * ===========================================================================
  *
  * File Name:  $Id: binary.h,v 1.5 1999/11/23 22:02:30 vakatov Exp $
  *
  * Author:  Lewis Geer
  *
  * Version Creation Date:   8/24/99
  *
  * $Revision: 1.5 $
  *
  * File Description: Various binary search algorithms
  *
  * Modifications:
  * --------------------------------------------------------------------------
  * $Log: binary.h,v $
  * Revision 1.5  1999/11/23 22:02:30  vakatov
  * Fixed for the MSVC DLL compilation
  *
  * Revision 1.4  1999/11/05 21:39:59  vakatov
  * Get rid of a nested comment in "struct _B_Global"
  *
  * Revision 1.3  1999/10/14 22:00:33  vakatov
  * More changes in the included headers
  *
  * Revision 1.2  1999/10/14 19:08:09  kans
  * header changes for Mac
  *
  * Revision 1.1  1999/09/21 18:09:14  lewisg
  * binary search added to color manager, various bug fixes, etc.
  * ==========================================================================
  */
  
  
  #ifndef BINARY_H
  #define BINARY_H
  
  #include <ncbi.h>
  
  
  #undef NLM_EXTERN
  #ifdef NLM_IMPORT
  #define NLM_EXTERN NLM_IMPORT
  #else
  #define NLM_EXTERN extern
  #endif
  
  #ifdef __cplusplus
  extern "C" {
  #endif
  
  /* 
  typedef for the key comparison function.    
  < 0 if Key1 < Key2, == 0 if Key1 == Key2, > 0 if Key1 > Key2   
  */
  typedef Int4 (*B_CompareFunc)(void *Key1, void *Key2);
  
  /* 
  B_List used in B_Global to hold a List of keys and bags
  */
  typedef struct _B_List {
      void * Key;
      void * Bag;
  } B_List;
  
  /* 
  typedef for the global for binary searching
  */
  typedef struct _B_Global {
      B_CompareFunc CompareFunc;  /* the function used to compare keys */
      Int4 AllocSize;  /* the size of memory block to allocate/deallocate */
      B_List *List;  /* the list of keys and bags */
      Int4 Size; /* the length of the list (NOT in bytes) */
      Int4 TrueSize;  /* The true size of the list (NOT in bytes */
      Int4 Cursor;  /* keeps track of the last search result */
  #if 0
      TNlmRWlock RW;  /* reader/writer lock */
 #endif
 } B_Global;
 
 /*****************************************************************************
 *
 *   B_NewGlobal() returns a new binary search global.  Takes a key comparison
 *   function and the size to realloc the binary search list.  If you pass 0
 *   for AllocSize it will use the default value B_ALLOCSIZE * sizeof(B_List).  
 *   Returns NULL on failure.
 *
 *   B_DeleteGlobal() deletes the global.  Return 1 on success, 0 on failure. 
 *
 *****************************************************************************/
 
 #define B_ALLOCSIZE 64
 
 NLM_EXTERN B_Global * B_NewGlobal(B_CompareFunc CompareFunc, Int4 AllocSize);
 
 NLM_EXTERN Int4 B_DeleteGlobal(B_Global *pGlobal);
 
 
 /*****************************************************************************
 *
 *   Inserts a new entry into the List.  Returns the position.  The position
 *   is not guaranteed between deletions and insertions
 *
 *   Automatically reallocates memory for List as List grows
 *
 *****************************************************************************/
 
 NLM_EXTERN Int4 B_Insert(B_Global *pGlobal, void *Key, void *Bag);
 
 
 /*****************************************************************************
 *
 *   B_Get() Returns the position in the List associated with the key.
 *   Returns INT4_MIN if no match.
 *
 *   B_GetFirst() does the same, but returns the first item in the List that
 *   matches the Key.
 *
 *   B_GetBag() gets bag associated with the key.
 *
 *****************************************************************************/
 
 NLM_EXTERN Int4 B_Get(B_Global *pGlobal, void *Key, Boolean *NotFound);
 
 NLM_EXTERN Int4 B_GetFirst(B_Global *pGlobal, void *Key, Boolean *NotFound);
 
 NLM_EXTERN void * B_GetBag(B_Global *pGlobal, void *Key);
 
 
 /*****************************************************************************
 *
 *   B_Get() is a macro that returns the number of entries in the list
 *   pGlobal is a pointer to the B_Global.
 *
 *****************************************************************************/
 
 #define B_GetSize(pGlobal) ((pGlobal)->Size)
 
 /*****************************************************************************
 *
 *   B_GetList() is a macro that returns entry at a list position
 *   pGlobal is a pointer to the B_Global and 
 *
 *****************************************************************************/
 
 #define B_GetList(pGlobal, Position) ((pGlobal)->List[(Position)])
 
 
 #ifdef __cplusplus
 }
 #endif
 
 #undef NLM_EXTERN
 #ifdef NLM_EXPORT
 #define NLM_EXTERN NLM_EXPORT
 #else
 #define NLM_EXTERN
 #endif
 
 #endif /* BINARY_H */