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