NCBI C++ ToolKit
bdb_range_map.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BDB__RANGE_MAP_HPP
2 #define BDB__RANGE_MAP_HPP
3 
4 /* $Id: bdb_range_map.hpp 42218 2009-06-15 19:59:58Z ivanovp $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Anatoliy Kuznetsov
30  *
31  * File Description: BDB range map storage
32  *
33  */
34 
35 /// @file bdb_range_map.hpp
36 /// BDB range map storage
37 
38 #include <corelib/ncbistd.hpp>
39 #include <corelib/ncbiexpt.hpp>
40 
41 #include <db/bdb/bdb_blob.hpp>
42 #include <db/bdb/bdb_cursor.hpp>
43 
44 #include <db/error_codes.hpp>
45 
48 
49 
51 
52 /// Range map class, stores unsigned integer range mappings
53 /// like 10 to 15 maps into 100 to 115
54 ///
55 /// This class also maitains free list of mappings
56 /// (inside the mapping regions)
57 /// The free list can be used externally to do id assignments, so ids fall into some
58 /// predefined regions of the mapped list
59 ///
60 /// Range 0-0 is RESERVED for the free list storage.
61 ///
62 /// <pre>
63 /// Example:
64 /// 10-15 --> 100-115
65 /// 20-30 --> 1020-1030
66 /// Free list: { 11,12,23 }
67 /// </pre>
68 ///
69 /// Typical use case: add a range of ids and take them out excluding
70 /// out of free list. When the free list is empty - add a new range.
71 ///
72 template<class TBV>
74 {
75 public:
76  typedef TBV TBitVector;
77 
78 public:
79  CBDB_FieldUint4 FromId; ///< From id
80  CBDB_FieldUint4 ToId; ///< To id
81 public:
82  CBDB_RangeMap();
84 
85  /// Load free list (Storage should be open first)
86  void LoadFreeList();
87 
88  /// Save free list
90 
91  /// Add remapping range. The range should NOT intersect with any existing range
92  /// Optionally new range can be added to the free id list.
93  EBDB_ErrCode AddRange(unsigned from, unsigned to, unsigned dest,
94  bool add_to_free_list);
95 
96  /// Get list of free ids.
97  const TBitVector& GetFreeList() const { return *m_FreeList; }
99 
100  /// Remap one single id
101  ///
102  /// @return Remapped id or 0 if remapping is impossible
103  ///
104  unsigned Remap(unsigned id, bool ignore_free_list=false);
105 
106  /// Remap a bitvector into another bitvector
107  ///
108  /// @param bv_src
109  /// Source bit vector
110  /// @param bv_dst
111  /// Destination set
112  /// @param bv_remapped
113  /// Set of successfully remapped ids
114  ///
115  void Remap(const TBitVector& bv_src,
116  TBitVector* bv_dst,
117  TBitVector* bv_remapped = 0,
118  bool ignore_free_list=false);
119 protected:
121 };
122 
123 
124 
125 /////////////////////////////////////////////////////////////////////////////
126 // IMPLEMENTATION of INLINE functions
127 /////////////////////////////////////////////////////////////////////////////
128 
129 template<class TBV>
131 : m_FreeList(new TBitVector(bm::BM_GAP))
132 {
133  this->BindKey("FromId", &FromId);
134  this->BindKey("ToId", &ToId);
135 }
136 
137 template<class TBV>
139 {
140  try {
141  Save();
142  }
143  catch (CException& ex)
144  {
145  ERR_POST_XX(Db_Bdb_RangeMap, 1, "Exception in ~CBDB_RangeMap()" << ex.GetMsg());
146  }
147  catch (exception& ex)
148  {
149  ERR_POST_XX(Db_Bdb_RangeMap, 2, "Exception in ~CBDB_RangeMap()" << ex.what());
150  }
151 
152  delete m_FreeList;
153 }
154 
155 template<class TBV>
157 {
158  _ASSERT(m_FreeList);
159 
160  TBuffer buf;
161  this->FromId = 0;
162  this->ToId = 0;
164  if (err == eBDB_Ok) {
165  bm::deserialize(*m_FreeList, &(buf[0]));
166  } else {
167  m_FreeList->clear(true);
168  }
169 }
170 
171 template<class TBV>
173 {
174  _ASSERT(m_FreeList);
175 
176  TBuffer buf;
177  BV_Serialize(*m_FreeList, buf, 0, true /*optimize*/);
178 
179  return UpdateInsert(buf);
180 }
181 
182 template<class TBV>
184  unsigned to,
185  unsigned dest,
186  bool add_to_free_list)
187 {
188  if (from == 0 && to == 0) {
189  BDB_THROW(eInvalidValue, "0-0 range is reserved.");
190  }
191  if (from > to) {
192  BDB_THROW(eInvalidValue, "Incorrect range values.");
193  }
194 
195  {{
196  CBDB_FileCursor cur(*this);
197 
198  // check range overlaps
199  //
201  cur.From << from;
202  EBDB_ErrCode ret = cur.FetchFirst();
203  if (ret == eBDB_Ok) {
204  unsigned from_db = this->FromId;
205  unsigned to_db = this->ToId;
206 
207  // from <= from1 <= to ?
208  //
209  if (from >= from_db && from <= to_db) {
210  BDB_THROW(eInvalidValue,
211  "Range overlaps with the previous range.");
212  }
213  }
214 
216  cur.From << to;
217  ret = cur.FetchFirst();
218  if (ret == eBDB_Ok) {
219  unsigned from_db = this->FromId;
220  unsigned to_db = this->ToId;
221 
222  // from <= to1 <= to ?
223  //
224  if (to >= from_db && to <= to_db) {
225  BDB_THROW(eInvalidValue,
226  "Range overlaps with the next range.");
227  }
228  }
229  }}
230 
231  this->FromId = from;
232  this->ToId = to;
233 
234  EBDB_ErrCode ret = Insert(&dest, sizeof(dest));
235 
236  if (ret == eBDB_Ok) {
237  if (add_to_free_list) {
238  m_FreeList->set_range(from, to, true);
239  }
240  }
241  return ret;
242 }
243 
244 template<class TBV>
245 unsigned CBDB_RangeMap<TBV>::Remap(unsigned id, bool ignore_free_list)
246 {
247  if (!ignore_free_list) {
248  if (m_FreeList->test(id)) {
249  return 0;
250  }
251  }
252  CBDB_FileCursor cur(*this);
253 
254  // check range overlaps
255  //
257  cur.From << id;
258  unsigned dst;
259  void* ptr = &dst;
260  EBDB_ErrCode ret = cur.FetchFirst(&ptr, sizeof(dst), eReallocForbidden);
261  if (ret == eBDB_Ok) {
262  unsigned from_id = this->FromId;
263  unsigned to_id = this->ToId;
264  if (from_id <= id && id <= to_id) {
265  return dst + (id - from_id);
266  }
267  }
268  return 0;
269 }
270 
271 template<class TBV>
273  TBitVector* bv_dst,
274  TBitVector* bv_remapped,
275  bool ignore_free_list)
276 {
277  CBDB_FileCursor cur(*this);
278  unsigned from_id, to_id, dst;
279  from_id = to_id = dst = 0;
280 
281  typename TBV::enumerator en(bv_src.first());
282  for ( ;en.valid(); ++en) {
283  unsigned id = *en;
284  if (!ignore_free_list) {
285  if (m_FreeList->test(id)) {
286  continue;
287  }
288  }
289 
290  if (from_id <= id && id <= to_id) {
291  bv_dst->set(dst + (id - from_id));
292  if (bv_remapped) {
293  bv_remapped->set(id);
294  }
295  } else {
297  cur.From << id;
298  void* ptr = &dst;
299  EBDB_ErrCode ret =
300  cur.FetchFirst(&ptr, sizeof(dst), eReallocForbidden);
301  if (ret == eBDB_Ok) {
302  from_id = this->FromId;
303  to_id = this->ToId;
304  if (from_id <= id && id <= to_id) {
305  bv_dst->set(dst + (id - from_id));
306  if (bv_remapped) {
307  bv_remapped->set(id);
308  }
309  }
310  }
311  }
312  } // for
313 }
314 
316 
317 #endif // BDB__RANGE_MAP_HPP
BDB library BLOB support.
Berkeley BDB file cursor.
Berkeley DB BLOB File class.
Definition: bdb_blob.hpp:59
Uint4 field type.
Definition: bdb_types.hpp:1267
Berkeley DB file cursor class.
Definition: bdb_cursor.hpp:95
Range map class, stores unsigned integer range mappings like 10 to 15 maps into 100 to 115.
TBitVector & GetFreeList()
TBitVector * m_FreeList
EBDB_ErrCode AddRange(unsigned from, unsigned to, unsigned dest, bool add_to_free_list)
Add remapping range.
unsigned Remap(unsigned id, bool ignore_free_list=false)
Remap one single id.
CBDB_FieldUint4 FromId
From id.
const TBitVector & GetFreeList() const
Get list of free ids.
void LoadFreeList()
Load free list (Storage should be open first)
CBDB_FieldUint4 ToId
To id.
EBDB_ErrCode Save()
Save free list.
Reallocable memory buffer (no memory copy overhead) Mimics vector<>, without the overhead of explicit...
Include a standard set of the NCBI C++ Toolkit most basic headers.
EBDB_ErrCode ReadRealloc(TBuffer &buffer)
Read BLOB into vector.
Definition: bdb_blob.cpp:92
void SetCondition(ECondition cond_from, ECondition cond_to=eNotSet)
Set search condition(type of interval)
Definition: bdb_cursor.cpp:263
EBDB_ErrCode FetchFirst()
Definition: bdb_cursor.cpp:447
void BindKey(const char *field_name, CBDB_Field *key_field, size_t buf_size=0)
Definition: bdb_file.cpp:1281
EBDB_ErrCode
BDB Return codes.
Definition: bdb_file.hpp:57
CBDB_ConditionHandle From
Definition: bdb_cursor.hpp:252
@ eBDB_Ok
Definition: bdb_file.hpp:58
#define BDB_THROW(errcode, message)
Definition: bdb_expt.hpp:178
#define ERR_POST_XX(error_name, err_subcode, message)
Error posting with error code having given name and with given error subcode.
Definition: ncbidiag.hpp:564
const string & GetMsg(void) const
Get message string.
Definition: ncbiexpt.cpp:461
virtual const char * what(void) const noexcept
Standard report (includes full backlog).
Definition: ncbiexpt.cpp:342
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:148
size_t deserialize(BV &bv, const unsigned char *buf, bm::word_t *temp_block=0, const bm::bv_ref_vector< BV > *ref_vect=0)
Bitvector deserialization from a memory BLOB.
Definition: bmserial.h:3137
Definition of all error codes used in bdb library (bdb.lib and ncbi_xcache_bdb.lib).
char * buf
#include<zmmintrin.h>
Definition: bm.h:78
Compressed bitset (entry point to bm.h)
Bitset relates utilities.
void BV_Serialize(const TBV &bv, TBuffer &buf, bm::word_t *tmp_block=0, bool optimize_bv=false)
Serialize bitset into a vector<char> compatible buffer.
Defines NCBI C++ exception handling.
#define _ASSERT
Modified on Tue May 21 10:58:41 2024 by modify_doxy.py rev. 669887