NCBI C Toolkit Cross Reference

C/corelib/binary.h


  1 /*   $Id: binary.h,v 1.5 1999/11/23 22:02:30 vakatov Exp $
  2 * ===========================================================================
  3 *
  4 *                            PUBLIC DOMAIN NOTICE
  5 *            National Center for Biotechnology Information (NCBI)
  6 *
  7 *  This software/database is a "United States Government Work" under the
  8 *  terms of the United States Copyright Act.  It was written as part of
  9 *  the author's official duties as a United States Government employee and
 10 *  thus cannot be copyrighted.  This software/database is freely available
 11 *  to the public for use. The National Library of Medicine and the U.S.
 12 *  Government do not place any restriction on its use or reproduction.
 13 *  We would, however, appreciate having the NCBI and the author cited in
 14 *  any work or product based on this material
 15 *
 16 *  Although all reasonable efforts have been taken to ensure the accuracy
 17 *  and reliability of the software and data, the NLM and the U.S.
 18 *  Government do not and cannot warrant the performance or results that
 19 *  may be obtained by using this software or data. The NLM and the U.S.
 20 *  Government disclaim all warranties, express or implied, including
 21 *  warranties of performance, merchantability or fitness for any particular
 22 *  purpose.
 23 *
 24 * ===========================================================================
 25 *
 26 * File Name:  $Id: binary.h,v 1.5 1999/11/23 22:02:30 vakatov Exp $
 27 *
 28 * Author:  Lewis Geer
 29 *
 30 * Version Creation Date:   8/24/99
 31 *
 32 * $Revision: 1.5 $
 33 *
 34 * File Description: Various binary search algorithms
 35 *
 36 * Modifications:
 37 * --------------------------------------------------------------------------
 38 * $Log: binary.h,v $
 39 * Revision 1.5  1999/11/23 22:02:30  vakatov
 40 * Fixed for the MSVC DLL compilation
 41 *
 42 * Revision 1.4  1999/11/05 21:39:59  vakatov
 43 * Get rid of a nested comment in "struct _B_Global"
 44 *
 45 * Revision 1.3  1999/10/14 22:00:33  vakatov
 46 * More changes in the included headers
 47 *
 48 * Revision 1.2  1999/10/14 19:08:09  kans
 49 * header changes for Mac
 50 *
 51 * Revision 1.1  1999/09/21 18:09:14  lewisg
 52 * binary search added to color manager, various bug fixes, etc.
 53 * ==========================================================================
 54 */
 55 
 56 
 57 #ifndef BINARY_H
 58 #define BINARY_H
 59 
 60 #include <ncbi.h>
 61 
 62 
 63 #undef NLM_EXTERN
 64 #ifdef NLM_IMPORT
 65 #define NLM_EXTERN NLM_IMPORT
 66 #else
 67 #define NLM_EXTERN extern
 68 #endif
 69 
 70 #ifdef __cplusplus
 71 extern "C" {
 72 #endif
 73 
 74 /* 
 75 typedef for the key comparison function.    
 76 < 0 if Key1 < Key2, == 0 if Key1 == Key2, > 0 if Key1 > Key2   
 77 */
 78 typedef Int4 (*B_CompareFunc)(void *Key1, void *Key2);
 79 
 80 /* 
 81 B_List used in B_Global to hold a List of keys and bags
 82 */
 83 typedef struct _B_List {
 84     void * Key;
 85     void * Bag;
 86 } B_List;
 87 
 88 /* 
 89 typedef for the global for binary searching
 90 */
 91 typedef struct _B_Global {
 92     B_CompareFunc CompareFunc;  /* the function used to compare keys */
 93     Int4 AllocSize;  /* the size of memory block to allocate/deallocate */
 94     B_List *List;  /* the list of keys and bags */
 95     Int4 Size; /* the length of the list (NOT in bytes) */
 96     Int4 TrueSize;  /* The true size of the list (NOT in bytes */
 97     Int4 Cursor;  /* keeps track of the last search result */
 98 #if 0
 99     TNlmRWlock RW;  /* reader/writer lock */
100 #endif
101 } B_Global;
102 
103 /*****************************************************************************
104 *
105 *   B_NewGlobal() returns a new binary search global.  Takes a key comparison
106 *   function and the size to realloc the binary search list.  If you pass 0
107 *   for AllocSize it will use the default value B_ALLOCSIZE * sizeof(B_List).  
108 *   Returns NULL on failure.
109 *
110 *   B_DeleteGlobal() deletes the global.  Return 1 on success, 0 on failure. 
111 *
112 *****************************************************************************/
113 
114 #define B_ALLOCSIZE 64
115 
116 NLM_EXTERN B_Global * B_NewGlobal(B_CompareFunc CompareFunc, Int4 AllocSize);
117 
118 NLM_EXTERN Int4 B_DeleteGlobal(B_Global *pGlobal);
119 
120 
121 /*****************************************************************************
122 *
123 *   Inserts a new entry into the List.  Returns the position.  The position
124 *   is not guaranteed between deletions and insertions
125 *
126 *   Automatically reallocates memory for List as List grows
127 *
128 *****************************************************************************/
129 
130 NLM_EXTERN Int4 B_Insert(B_Global *pGlobal, void *Key, void *Bag);
131 
132 
133 /*****************************************************************************
134 *
135 *   B_Get() Returns the position in the List associated with the key.
136 *   Returns INT4_MIN if no match.
137 *
138 *   B_GetFirst() does the same, but returns the first item in the List that
139 *   matches the Key.
140 *
141 *   B_GetBag() gets bag associated with the key.
142 *
143 *****************************************************************************/
144 
145 NLM_EXTERN Int4 B_Get(B_Global *pGlobal, void *Key, Boolean *NotFound);
146 
147 NLM_EXTERN Int4 B_GetFirst(B_Global *pGlobal, void *Key, Boolean *NotFound);
148 
149 NLM_EXTERN void * B_GetBag(B_Global *pGlobal, void *Key);
150 
151 
152 /*****************************************************************************
153 *
154 *   B_Get() is a macro that returns the number of entries in the list
155 *   pGlobal is a pointer to the B_Global.
156 *
157 *****************************************************************************/
158 
159 #define B_GetSize(pGlobal) ((pGlobal)->Size)
160 
161 /*****************************************************************************
162 *
163 *   B_GetList() is a macro that returns entry at a list position
164 *   pGlobal is a pointer to the B_Global and 
165 *
166 *****************************************************************************/
167 
168 #define B_GetList(pGlobal, Position) ((pGlobal)->List[(Position)])
169 
170 
171 #ifdef __cplusplus
172 }
173 #endif
174 
175 #undef NLM_EXTERN
176 #ifdef NLM_EXPORT
177 #define NLM_EXTERN NLM_EXPORT
178 #else
179 #define NLM_EXTERN
180 #endif
181 
182 #endif /* BINARY_H */
183 

source navigation ]   [ diff markup ]   [ identifier search ]   [ freetext search ]   [ file search ]  

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.