1 : /**********************************************************************
2 : * $Id: mitab_indfile.cpp,v 1.14 2010-07-07 19:00:15 aboudreault Exp $
3 : *
4 : * Name: mitab_indfile.cpp
5 : * Project: MapInfo TAB Read/Write library
6 : * Language: C++
7 : * Purpose: Implementation of the TABINDFile class used to handle
8 : * access to .IND file (table field indexes) attached to a .DAT file
9 : * Author: Daniel Morissette, dmorissette@dmsolutions.ca
10 : *
11 : **********************************************************************
12 : * Copyright (c) 1999-2001, Daniel Morissette
13 : *
14 : * Permission is hereby granted, free of charge, to any person obtaining a
15 : * copy of this software and associated documentation files (the "Software"),
16 : * to deal in the Software without restriction, including without limitation
17 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 : * and/or sell copies of the Software, and to permit persons to whom the
19 : * Software is furnished to do so, subject to the following conditions:
20 : *
21 : * The above copyright notice and this permission notice shall be included
22 : * in all copies or substantial portions of the Software.
23 : *
24 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 : * DEALINGS IN THE SOFTWARE.
31 : **********************************************************************
32 : *
33 : * $Log: mitab_indfile.cpp,v $
34 : * Revision 1.14 2010-07-07 19:00:15 aboudreault
35 : * Cleanup Win32 Compile Warnings (GDAL bug #2930)
36 : *
37 : * Revision 1.13 2008-01-29 20:46:32 dmorissette
38 : * Added support for v9 Time and DateTime fields (byg 1754)
39 : *
40 : * Revision 1.12 2007/12/11 03:43:03 dmorissette
41 : * Added reporting access mode to error message in TABINDFile::Open()
42 : * (GDAL changeset r12460, ticket 1620)
43 : *
44 : * Revision 1.11 2005/04/29 19:08:56 dmorissette
45 : * Produce an error if m_nSubtreeDepth > 255 when creating a .IND (OGR bug 839)
46 : *
47 : * Revision 1.10 2004/06/30 20:29:04 dmorissette
48 : * Fixed refs to old address danmo@videotron.ca
49 : *
50 : * Revision 1.9 2003/07/24 02:45:57 daniel
51 : * Fixed problem scanning node in TABINDNode::FindNext() - bug 2176, FW
52 : *
53 : * Revision 1.8 2001/05/01 03:38:23 daniel
54 : * Added update support (allows creating new index in existing IND files).
55 : *
56 : * Revision 1.7 2000/11/13 22:17:57 daniel
57 : * When a (child) node's first entry is replaced by InsertEntry() then make
58 : * sure that node's key is updated in its parent node.
59 : *
60 : * Revision 1.6 2000/03/01 00:32:00 daniel
61 : * Added support for float keys, and completed support for generating indexes
62 : *
63 : * Revision 1.5 2000/02/28 16:57:42 daniel
64 : * Added support for writing indexes
65 : *
66 : * Revision 1.4 2000/01/15 22:30:44 daniel
67 : * Switch to MIT/X-Consortium OpenSource license
68 : *
69 : * Revision 1.3 1999/12/14 05:52:05 daniel
70 : * Fixed compile error on Windows
71 : *
72 : * Revision 1.2 1999/12/14 02:19:42 daniel
73 : * Completed .IND support for simple TABViews
74 : *
75 : * Revision 1.1 1999/11/20 15:49:07 daniel
76 : * Initial version
77 : *
78 : **********************************************************************/
79 :
80 : #include "mitab.h"
81 : #include "mitab_utils.h"
82 :
83 : #include <ctype.h> /* toupper() */
84 :
85 : /*=====================================================================
86 : * class TABINDFile
87 : *====================================================================*/
88 :
89 : #define IND_MAGIC_COOKIE 24242424
90 :
91 : /**********************************************************************
92 : * TABINDFile::TABINDFile()
93 : *
94 : * Constructor.
95 : **********************************************************************/
96 14 : TABINDFile::TABINDFile()
97 : {
98 14 : m_fp = NULL;
99 14 : m_pszFname = NULL;
100 14 : m_eAccessMode = TABRead;
101 14 : m_numIndexes = 0;
102 14 : m_papoIndexRootNodes = NULL;
103 14 : m_papbyKeyBuffers = NULL;
104 14 : }
105 :
106 : /**********************************************************************
107 : * TABINDFile::~TABINDFile()
108 : *
109 : * Destructor.
110 : **********************************************************************/
111 14 : TABINDFile::~TABINDFile()
112 : {
113 14 : Close();
114 14 : }
115 :
116 : /**********************************************************************
117 : * TABINDFile::Open()
118 : *
119 : * Open a .IND file, read the header and the root nodes for all the
120 : * field indexes, and be ready to search the indexes.
121 : *
122 : * If the filename that is passed in contains a .DAT extension then
123 : * the extension will be changed to .IND before trying to open the file.
124 : *
125 : * Note that we pass a pszAccess flag, but only read access is supported
126 : * for now (and there are no plans to support write.)
127 : *
128 : * Set bTestOpenNoError=TRUE to silently return -1 with no error message
129 : * if the file cannot be opened because it does not exist.
130 : *
131 : * Returns 0 on success, -1 on error.
132 : **********************************************************************/
133 22 : int TABINDFile::Open(const char *pszFname, const char *pszAccess,
134 : GBool bTestOpenNoError /*=FALSE*/)
135 : {
136 : int nLen;
137 :
138 22 : if (m_fp)
139 : {
140 : CPLError(CE_Failure, CPLE_FileIO,
141 0 : "Open() failed: object already contains an open file");
142 0 : return -1;
143 : }
144 :
145 : /*-----------------------------------------------------------------
146 : * Validate access mode and make sure we use binary access.
147 : * Note that for write access, we actually need read/write access to
148 : * the file.
149 : *----------------------------------------------------------------*/
150 30 : if (EQUALN(pszAccess, "r", 1) && strchr(pszAccess, '+') != NULL)
151 : {
152 8 : m_eAccessMode = TABReadWrite;
153 8 : pszAccess = "rb+";
154 : }
155 14 : else if (EQUALN(pszAccess, "r", 1))
156 : {
157 6 : m_eAccessMode = TABRead;
158 6 : pszAccess = "rb";
159 : }
160 8 : else if (EQUALN(pszAccess, "w", 1))
161 : {
162 8 : m_eAccessMode = TABWrite;
163 8 : pszAccess = "wb+";
164 : }
165 : else
166 : {
167 : CPLError(CE_Failure, CPLE_FileIO,
168 0 : "Open() failed: access mode \"%s\" not supported", pszAccess);
169 0 : return -1;
170 : }
171 :
172 : /*-----------------------------------------------------------------
173 : * Change .DAT (or .TAB) extension to .IND if necessary
174 : *----------------------------------------------------------------*/
175 22 : m_pszFname = CPLStrdup(pszFname);
176 :
177 22 : nLen = strlen(m_pszFname);
178 22 : if (nLen > 4 && !EQUAL(m_pszFname+nLen-4, ".IND") )
179 0 : strcpy(m_pszFname+nLen-4, ".ind");
180 :
181 : #ifndef _WIN32
182 22 : TABAdjustFilenameExtension(m_pszFname);
183 : #endif
184 :
185 : /*-----------------------------------------------------------------
186 : * Open file
187 : *----------------------------------------------------------------*/
188 22 : m_fp = VSIFOpen(m_pszFname, pszAccess);
189 :
190 22 : if (m_fp == NULL)
191 : {
192 0 : if (!bTestOpenNoError)
193 : CPLError(CE_Failure, CPLE_FileIO,
194 0 : "Open() failed for %s (%s)", m_pszFname, pszAccess);
195 :
196 0 : CPLFree(m_pszFname);
197 0 : m_pszFname = NULL;
198 0 : return -1;
199 : }
200 :
201 : /*-----------------------------------------------------------------
202 : * Reset block manager to allocate first block at byte 512, after header.
203 : *----------------------------------------------------------------*/
204 22 : m_oBlockManager.Reset();
205 22 : m_oBlockManager.AllocNewBlock();
206 :
207 : /*-----------------------------------------------------------------
208 : * Read access: Read the header block
209 : * This will also alloc and init the array of index root nodes.
210 : *----------------------------------------------------------------*/
211 22 : if ((m_eAccessMode == TABRead || m_eAccessMode == TABReadWrite) &&
212 : ReadHeader() != 0)
213 : {
214 : // Failed reading header... CPLError() has already been called
215 0 : Close();
216 0 : return -1;
217 : }
218 :
219 : /*-----------------------------------------------------------------
220 : * Write access: Init class members and write a dummy header block
221 : *----------------------------------------------------------------*/
222 22 : if (m_eAccessMode == TABWrite)
223 : {
224 8 : m_numIndexes = 0;
225 :
226 8 : if (WriteHeader() != 0)
227 : {
228 : // Failed writing header... CPLError() has already been called
229 0 : Close();
230 0 : return -1;
231 : }
232 : }
233 :
234 22 : return 0;
235 : }
236 :
237 : /**********************************************************************
238 : * TABINDFile::Close()
239 : *
240 : * Close current file, and release all memory used.
241 : *
242 : * Returns 0 on success, -1 on error.
243 : **********************************************************************/
244 36 : int TABINDFile::Close()
245 : {
246 36 : if (m_fp == NULL)
247 14 : return 0;
248 :
249 : /*-----------------------------------------------------------------
250 : * In Write Mode, commit all indexes to the file
251 : *----------------------------------------------------------------*/
252 22 : if (m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite)
253 : {
254 16 : WriteHeader();
255 :
256 40 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
257 : {
258 48 : if (m_papoIndexRootNodes &&
259 24 : m_papoIndexRootNodes[iIndex])
260 : {
261 24 : m_papoIndexRootNodes[iIndex]->CommitToFile();
262 : }
263 : }
264 : }
265 :
266 : /*-----------------------------------------------------------------
267 : * Free index nodes in memory
268 : *----------------------------------------------------------------*/
269 54 : for (int iIndex=0; iIndex<m_numIndexes; iIndex++)
270 : {
271 32 : if (m_papoIndexRootNodes && m_papoIndexRootNodes[iIndex])
272 32 : delete m_papoIndexRootNodes[iIndex];
273 32 : if (m_papbyKeyBuffers && m_papbyKeyBuffers[iIndex])
274 32 : CPLFree(m_papbyKeyBuffers[iIndex]);
275 : }
276 22 : CPLFree(m_papoIndexRootNodes);
277 22 : m_papoIndexRootNodes = NULL;
278 22 : CPLFree(m_papbyKeyBuffers);
279 22 : m_papbyKeyBuffers = NULL;
280 22 : m_numIndexes = 0;
281 :
282 : /*-----------------------------------------------------------------
283 : * Close file
284 : *----------------------------------------------------------------*/
285 22 : VSIFClose(m_fp);
286 22 : m_fp = NULL;
287 :
288 22 : CPLFree(m_pszFname);
289 22 : m_pszFname = NULL;
290 :
291 22 : return 0;
292 : }
293 :
294 :
295 : /**********************************************************************
296 : * TABINDFile::ReadHeader()
297 : *
298 : * (private method)
299 : * Read the header block and init all class members for read access.
300 : *
301 : * Returns 0 on success, -1 on error.
302 : **********************************************************************/
303 14 : int TABINDFile::ReadHeader()
304 : {
305 :
306 14 : CPLAssert(m_fp);
307 14 : CPLAssert(m_eAccessMode == TABRead || m_eAccessMode == TABReadWrite);
308 :
309 : /*-----------------------------------------------------------------
310 : * In ReadWrite mode, we need to init BlockManager with file size
311 : *----------------------------------------------------------------*/
312 : VSIStatBuf sStatBuf;
313 14 : if (m_eAccessMode == TABReadWrite && VSIStat(m_pszFname, &sStatBuf) != -1)
314 : {
315 8 : m_oBlockManager.SetLastPtr(((sStatBuf.st_size-1)/512)*512);
316 : }
317 :
318 : /*-----------------------------------------------------------------
319 : * Read the header block
320 : *----------------------------------------------------------------*/
321 : TABRawBinBlock *poHeaderBlock;
322 14 : poHeaderBlock = new TABRawBinBlock(m_eAccessMode, TRUE);
323 14 : if (poHeaderBlock->ReadFromFile(m_fp, 0, 512) != 0)
324 : {
325 : // CPLError() has already been called.
326 0 : delete poHeaderBlock;
327 0 : return -1;
328 : }
329 :
330 14 : poHeaderBlock->GotoByteInBlock(0);
331 14 : GUInt32 nMagicCookie = poHeaderBlock->ReadInt32();
332 14 : if (nMagicCookie != IND_MAGIC_COOKIE)
333 : {
334 : CPLError(CE_Failure, CPLE_FileIO,
335 : "%s: Invalid Magic Cookie: got %d, expected %d",
336 0 : m_pszFname, nMagicCookie, IND_MAGIC_COOKIE);
337 0 : delete poHeaderBlock;
338 0 : return -1;
339 : }
340 :
341 14 : poHeaderBlock->GotoByteInBlock(12);
342 14 : m_numIndexes = poHeaderBlock->ReadInt16();
343 14 : if (m_numIndexes < 1 || m_numIndexes > 29)
344 : {
345 : CPLError(CE_Failure, CPLE_FileIO,
346 : "Invalid number of indexes (%d) in file %s",
347 0 : m_numIndexes, m_pszFname);
348 0 : delete poHeaderBlock;
349 0 : return -1;
350 : }
351 :
352 : /*-----------------------------------------------------------------
353 : * Alloc and init the array of index root nodes.
354 : *----------------------------------------------------------------*/
355 : m_papoIndexRootNodes = (TABINDNode**)CPLCalloc(m_numIndexes,
356 14 : sizeof(TABINDNode*));
357 :
358 14 : m_papbyKeyBuffers = (GByte **)CPLCalloc(m_numIndexes, sizeof(GByte*));
359 :
360 : /* First index def. starts at byte 48 */
361 14 : poHeaderBlock->GotoByteInBlock(48);
362 :
363 30 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
364 : {
365 : /*-------------------------------------------------------------
366 : * Read next index definition
367 : *------------------------------------------------------------*/
368 16 : GInt32 nRootNodePtr = poHeaderBlock->ReadInt32();
369 16 : poHeaderBlock->ReadInt16(); // skip... max. num of entries per node
370 16 : int nTreeDepth = poHeaderBlock->ReadByte();
371 16 : int nKeyLength = poHeaderBlock->ReadByte();
372 16 : poHeaderBlock->GotoByteRel(8); // skip next 8 bytes;
373 :
374 : /*-------------------------------------------------------------
375 : * And init root node for this index.
376 : * Note that if nRootNodePtr==0 then this means that the
377 : * corresponding index does not exist (i.e. has been deleted?)
378 : * so we simply do not allocate the root node in this case.
379 : * An error will be produced if the user tries to access this index
380 : * later during execution.
381 : *------------------------------------------------------------*/
382 16 : if (nRootNodePtr > 0)
383 : {
384 16 : m_papoIndexRootNodes[iIndex] = new TABINDNode(m_eAccessMode);
385 16 : if (m_papoIndexRootNodes[iIndex]->InitNode(m_fp, nRootNodePtr,
386 : nKeyLength, nTreeDepth,
387 : FALSE,
388 : &m_oBlockManager)!= 0)
389 : {
390 : // CPLError has already been called
391 0 : delete poHeaderBlock;
392 0 : return -1;
393 : }
394 :
395 : // Alloc a temporary key buffer for this index.
396 : // This buffer will be used by the BuildKey() method
397 16 : m_papbyKeyBuffers[iIndex] = (GByte *)CPLCalloc(nKeyLength+1,
398 16 : sizeof(GByte));
399 : }
400 : else
401 : {
402 0 : m_papoIndexRootNodes[iIndex] = NULL;
403 0 : m_papbyKeyBuffers[iIndex] = NULL;
404 : }
405 : }
406 :
407 : /*-----------------------------------------------------------------
408 : * OK, we won't need the header block any more... free it.
409 : *----------------------------------------------------------------*/
410 14 : delete poHeaderBlock;
411 :
412 14 : return 0;
413 : }
414 :
415 :
416 : /**********************************************************************
417 : * TABINDFile::WriteHeader()
418 : *
419 : * (private method)
420 : * Write the header block based on current index information.
421 : *
422 : * Returns 0 on success, -1 on error.
423 : **********************************************************************/
424 24 : int TABINDFile::WriteHeader()
425 : {
426 24 : CPLAssert(m_fp);
427 24 : CPLAssert(m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite);
428 :
429 : /*-----------------------------------------------------------------
430 : * Write the 48 bytes of file header
431 : *----------------------------------------------------------------*/
432 : TABRawBinBlock *poHeaderBlock;
433 24 : poHeaderBlock = new TABRawBinBlock(m_eAccessMode, TRUE);
434 24 : poHeaderBlock->InitNewBlock(m_fp, 512, 0);
435 :
436 24 : poHeaderBlock->WriteInt32( IND_MAGIC_COOKIE );
437 :
438 24 : poHeaderBlock->WriteInt16( 100 ); // ???
439 24 : poHeaderBlock->WriteInt16( 512 ); // ???
440 24 : poHeaderBlock->WriteInt32( 0 ); // ???
441 :
442 24 : poHeaderBlock->WriteInt16( (GInt16)m_numIndexes );
443 :
444 24 : poHeaderBlock->WriteInt16( 0x15e7); // ???
445 :
446 24 : poHeaderBlock->WriteInt16( 10 ); // ???
447 24 : poHeaderBlock->WriteInt16( 0x611d); // ???
448 :
449 24 : poHeaderBlock->WriteZeros( 28 );
450 :
451 : /*-----------------------------------------------------------------
452 : * The first index definition starts at byte 48
453 : *----------------------------------------------------------------*/
454 48 : for(int iIndex=0; iIndex<m_numIndexes; iIndex++)
455 : {
456 24 : TABINDNode *poRootNode = m_papoIndexRootNodes[iIndex];
457 :
458 24 : if (poRootNode)
459 : {
460 : /*---------------------------------------------------------
461 : * Write next index definition
462 : *--------------------------------------------------------*/
463 24 : poHeaderBlock->WriteInt32(poRootNode->GetNodeBlockPtr());
464 24 : poHeaderBlock->WriteInt16((GInt16)poRootNode->GetMaxNumEntries());
465 24 : poHeaderBlock->WriteByte( (GByte)poRootNode->GetSubTreeDepth());
466 24 : poHeaderBlock->WriteByte( (GByte)poRootNode->GetKeyLength());
467 :
468 24 : poHeaderBlock->WriteZeros( 8 );
469 :
470 : /*---------------------------------------------------------
471 : * Look for overflow of the SubTreeDepth field (byte)
472 : *--------------------------------------------------------*/
473 24 : if (poRootNode->GetSubTreeDepth() > 255)
474 : {
475 : CPLError(CE_Failure, CPLE_AssertionFailed,
476 : "Index no %d is too large and will not be useable. "
477 : "(SubTreeDepth = %d, cannot exceed 255).",
478 0 : iIndex+1, poRootNode->GetSubTreeDepth());
479 0 : return -1;
480 : }
481 : }
482 : else
483 : {
484 : /*---------------------------------------------------------
485 : * NULL Root Node: This index has likely been deleted
486 : *--------------------------------------------------------*/
487 0 : poHeaderBlock->WriteZeros( 16 );
488 : }
489 : }
490 :
491 : /*-----------------------------------------------------------------
492 : * OK, we won't need the header block any more... write and free it.
493 : *----------------------------------------------------------------*/
494 24 : if (poHeaderBlock->CommitToFile() != 0)
495 0 : return -1;
496 :
497 24 : delete poHeaderBlock;
498 :
499 24 : return 0;
500 : }
501 :
502 : /**********************************************************************
503 : * TABINDFile::ValidateIndexNo()
504 : *
505 : * Private method to validate the index no parameter of some methods...
506 : * returns 0 if index no. is OK, or produces an error ands returns -1
507 : * if index no is not valid.
508 : **********************************************************************/
509 558 : int TABINDFile::ValidateIndexNo(int nIndexNumber)
510 : {
511 558 : if (m_fp == NULL)
512 : {
513 : CPLError(CE_Failure, CPLE_AssertionFailed,
514 0 : "TABINDFile: File has not been opened yet!");
515 0 : return -1;
516 : }
517 :
518 1116 : if (nIndexNumber < 1 || nIndexNumber > m_numIndexes ||
519 : m_papoIndexRootNodes == NULL ||
520 558 : m_papoIndexRootNodes[nIndexNumber-1] == NULL)
521 : {
522 : CPLError(CE_Failure, CPLE_AssertionFailed,
523 : "No field index number %d in %s: Valid range is [1..%d].",
524 0 : nIndexNumber, m_pszFname, m_numIndexes);
525 0 : return -1;
526 : }
527 :
528 558 : return 0; // Index seems valid
529 : }
530 :
531 : /**********************************************************************
532 : * TABINDFile::SetIndexFieldType()
533 : *
534 : * Sets the field type for the specified index.
535 : * This information will then be used in building the key values, etc.
536 : *
537 : * Returns 0 on success, -1 on error.
538 : **********************************************************************/
539 0 : int TABINDFile::SetIndexFieldType(int nIndexNumber, TABFieldType eType)
540 : {
541 0 : if (ValidateIndexNo(nIndexNumber) != 0)
542 0 : return -1;
543 :
544 0 : return m_papoIndexRootNodes[nIndexNumber-1]->SetFieldType(eType);
545 : }
546 :
547 : /**********************************************************************
548 : * TABINDFile::SetIndexUnique()
549 : *
550 : * Indicate that an index's keys are unique. This allows for some
551 : * optimization with read access. By default, an index is treated as if
552 : * its keys could have duplicates.
553 : *
554 : * Returns 0 on success, -1 on error.
555 : **********************************************************************/
556 0 : int TABINDFile::SetIndexUnique(int nIndexNumber, GBool bUnique/*=TRUE*/)
557 : {
558 0 : if (ValidateIndexNo(nIndexNumber) != 0)
559 0 : return -1;
560 :
561 0 : m_papoIndexRootNodes[nIndexNumber-1]->SetUnique(bUnique);
562 :
563 0 : return 0;
564 : }
565 :
566 : /**********************************************************************
567 : * TABINDFile::BuildKey()
568 : *
569 : * Encode a field value in the form required to be compared with index
570 : * keys in the specified index.
571 : *
572 : * Note that index numbers are positive values starting at 1.
573 : *
574 : * Returns a reference to an internal buffer that is valid only until the
575 : * next call to BuildKey(). (should not be freed by the caller).
576 : * Returns NULL if field index is invalid.
577 : *
578 : * The first flavour of the function handles integer type of values, this
579 : * corresponds to MapInfo types: integer, smallint, logical and date
580 : **********************************************************************/
581 130 : GByte *TABINDFile::BuildKey(int nIndexNumber, GInt32 nValue)
582 : {
583 130 : if (ValidateIndexNo(nIndexNumber) != 0)
584 0 : return NULL;
585 :
586 130 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
587 :
588 : /*-----------------------------------------------------------------
589 : * Convert all int values to MSB using the right number of bytes
590 : * Note:
591 : * The most significant bit has to be unset for negative values,
592 : * and to be set for positive ones... that's the reverse of what it
593 : * should usually be. Adding 0x80 to the MSB byte will do the job.
594 : *----------------------------------------------------------------*/
595 130 : switch(nKeyLength)
596 : {
597 : case 1:
598 0 : m_papbyKeyBuffers[nIndexNumber-1][0] = (GByte)(nValue & 0xff)+0x80;
599 0 : break;
600 : case 2:
601 0 : m_papbyKeyBuffers[nIndexNumber-1][0] =
602 0 : (GByte)(nValue/0x100 & 0xff)+0x80;
603 0 : m_papbyKeyBuffers[nIndexNumber-1][1] = (GByte)(nValue & 0xff);
604 0 : break;
605 : case 4:
606 130 : m_papbyKeyBuffers[nIndexNumber-1][0] =
607 130 : (GByte)(nValue/0x1000000 &0xff)+0x80;
608 130 : m_papbyKeyBuffers[nIndexNumber-1][1] = (GByte)(nValue/0x10000 & 0xff);
609 130 : m_papbyKeyBuffers[nIndexNumber-1][2] = (GByte)(nValue/0x100 &0xff);
610 130 : m_papbyKeyBuffers[nIndexNumber-1][3] = (GByte)(nValue & 0xff);
611 130 : break;
612 : default:
613 : CPLError(CE_Failure, CPLE_AssertionFailed,
614 : "BuildKey(): %d bytes integer key length not supported",
615 0 : nKeyLength);
616 : break;
617 : }
618 :
619 130 : return m_papbyKeyBuffers[nIndexNumber-1];
620 : }
621 :
622 : /**********************************************************************
623 : * TABINDFile::BuildKey()
624 : *
625 : * BuildKey() for string fields
626 : **********************************************************************/
627 98 : GByte *TABINDFile::BuildKey(int nIndexNumber, const char *pszStr)
628 : {
629 98 : if (ValidateIndexNo(nIndexNumber) != 0 || pszStr == NULL)
630 0 : return NULL;
631 :
632 98 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
633 :
634 : /*-----------------------------------------------------------------
635 : * Strings keys are all in uppercase, and padded with '\0'
636 : *----------------------------------------------------------------*/
637 98 : int i=0;
638 760 : for (i=0; i<nKeyLength && pszStr[i] != '\0'; i++)
639 : {
640 662 : m_papbyKeyBuffers[nIndexNumber-1][i] = (GByte)toupper(pszStr[i]);
641 : }
642 :
643 : /* Pad the end of the buffer with '\0' */
644 2028 : for( ; i<nKeyLength; i++)
645 : {
646 1930 : m_papbyKeyBuffers[nIndexNumber-1][i] = '\0';
647 : }
648 :
649 98 : return m_papbyKeyBuffers[nIndexNumber-1];
650 : }
651 :
652 : /**********************************************************************
653 : * TABINDFile::BuildKey()
654 : *
655 : * BuildKey() for float and decimal fields
656 : **********************************************************************/
657 16 : GByte *TABINDFile::BuildKey(int nIndexNumber, double dValue)
658 : {
659 16 : if (ValidateIndexNo(nIndexNumber) != 0)
660 0 : return NULL;
661 :
662 16 : int nKeyLength = m_papoIndexRootNodes[nIndexNumber-1]->GetKeyLength();
663 16 : CPLAssert(nKeyLength == 8 && sizeof(double) == 8);
664 :
665 : /*-----------------------------------------------------------------
666 : * Convert double and decimal values...
667 : * Reverse the sign of the value, and convert to MSB
668 : *----------------------------------------------------------------*/
669 16 : dValue = -dValue;
670 :
671 : #ifndef CPL_MSB
672 16 : CPL_SWAPDOUBLE(&dValue);
673 : #endif
674 :
675 16 : memcpy(m_papbyKeyBuffers[nIndexNumber-1], (GByte*)(&dValue), nKeyLength);
676 :
677 16 : return m_papbyKeyBuffers[nIndexNumber-1];
678 : }
679 :
680 :
681 : /**********************************************************************
682 : * TABINDFile::FindFirst()
683 : *
684 : * Search one of the indexes for a key value.
685 : *
686 : * Note that index numbers are positive values starting at 1.
687 : *
688 : * Return value:
689 : * - the key's corresponding record number in the .DAT file (greater than 0)
690 : * - 0 if the key was not found
691 : * - or -1 if an error happened
692 : **********************************************************************/
693 60 : GInt32 TABINDFile::FindFirst(int nIndexNumber, GByte *pKeyValue)
694 : {
695 60 : if (ValidateIndexNo(nIndexNumber) != 0)
696 0 : return -1;
697 :
698 60 : return m_papoIndexRootNodes[nIndexNumber-1]->FindFirst(pKeyValue);
699 : }
700 :
701 : /**********************************************************************
702 : * TABINDFile::FindNext()
703 : *
704 : * Continue the Search for pKeyValue previously initiated by FindFirst().
705 : * NOTE: FindFirst() MUST have been previously called for this call to
706 : * work...
707 : *
708 : * Note that index numbers are positive values starting at 1.
709 : *
710 : * Return value:
711 : * - the key's corresponding record number in the .DAT file (greater than 0)
712 : * - 0 if the key was not found
713 : * - or -1 if an error happened
714 : **********************************************************************/
715 70 : GInt32 TABINDFile::FindNext(int nIndexNumber, GByte *pKeyValue)
716 : {
717 70 : if (ValidateIndexNo(nIndexNumber) != 0)
718 0 : return -1;
719 :
720 70 : return m_papoIndexRootNodes[nIndexNumber-1]->FindNext(pKeyValue);
721 : }
722 :
723 :
724 : /**********************************************************************
725 : * TABINDFile::CreateIndex()
726 : *
727 : * Create a new index with the specified field type and size.
728 : * Field size applies only to char field type... the other types have a
729 : * predefined key length.
730 : *
731 : * Key length is limited to 128 chars. char fields longer than 128 chars
732 : * will have their key truncated to 128 bytes.
733 : *
734 : * Note that a .IND file can contain only a maximum of 29 indexes.
735 : *
736 : * Returns the new field index on success (greater than 0), or -1 on error.
737 : **********************************************************************/
738 16 : int TABINDFile::CreateIndex(TABFieldType eType, int nFieldSize)
739 : {
740 16 : int i, nNewIndexNo = -1;
741 :
742 16 : if (m_fp == NULL ||
743 : (m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite))
744 0 : return -1;
745 :
746 : // __TODO__
747 : // We'll need more work in TABDATFile::WriteDateTimeField() before
748 : // we can support indexes on fields of type DateTime (see bug #1844)
749 16 : if (eType == TABFDateTime)
750 : {
751 : CPLError(CE_Failure, CPLE_AssertionFailed,
752 0 : "Index on fields of type DateTime not supported yet.");
753 0 : return -1;
754 : }
755 :
756 : /*-----------------------------------------------------------------
757 : * Look for an empty slot in the current array, if there is none
758 : * then extend the array.
759 : *----------------------------------------------------------------*/
760 24 : for(i=0; m_papoIndexRootNodes && i<m_numIndexes; i++)
761 : {
762 8 : if (m_papoIndexRootNodes[i] == NULL)
763 : {
764 0 : nNewIndexNo = i;
765 0 : break;
766 : }
767 : }
768 :
769 16 : if (nNewIndexNo == -1 && m_numIndexes >= 29)
770 : {
771 : CPLError(CE_Failure, CPLE_AppDefined,
772 : "Cannot add new index to %s. A dataset can contain only a "
773 0 : "maximum of 29 indexes.", m_pszFname);
774 0 : return -1;
775 : }
776 :
777 16 : if (nNewIndexNo == -1)
778 : {
779 : /*-------------------------------------------------------------
780 : * Add a slot for new index at the end of the nodes array.
781 : *------------------------------------------------------------*/
782 16 : m_numIndexes++;
783 : m_papoIndexRootNodes = (TABINDNode**)CPLRealloc( m_papoIndexRootNodes,
784 : m_numIndexes*
785 16 : sizeof(TABINDNode*));
786 :
787 : m_papbyKeyBuffers = (GByte **)CPLRealloc(m_papbyKeyBuffers,
788 16 : m_numIndexes*sizeof(GByte*));
789 :
790 16 : nNewIndexNo = m_numIndexes-1;
791 : }
792 :
793 : /*-----------------------------------------------------------------
794 : * Alloc and init new node
795 : * The call to InitNode() automatically allocates storage space for
796 : * the node in the file.
797 : * New nodes are created with a subtree_depth=1 since they start as
798 : * leaf nodes, i.e. their entries point directly to .DAT records
799 : *----------------------------------------------------------------*/
800 : int nKeyLength = ((eType == TABFInteger) ? 4:
801 : (eType == TABFSmallInt) ? 2:
802 : (eType == TABFFloat) ? 8:
803 : (eType == TABFDecimal) ? 8:
804 : (eType == TABFDate) ? 4:
805 : (eType == TABFTime) ? 4:
806 : (eType == TABFDateTime) ? 8:
807 16 : (eType == TABFLogical) ? 4: MIN(128,nFieldSize));
808 :
809 16 : m_papoIndexRootNodes[nNewIndexNo] = new TABINDNode(m_eAccessMode);
810 16 : if (m_papoIndexRootNodes[nNewIndexNo]->InitNode(m_fp, 0, nKeyLength,
811 : 1, // subtree depth=1
812 : FALSE, // not unique
813 : &m_oBlockManager,
814 : NULL, 0, 0)!= 0)
815 : {
816 : // CPLError has already been called
817 0 : return -1;
818 : }
819 :
820 : // Alloc a temporary key buffer for this index.
821 : // This buffer will be used by the BuildKey() method
822 16 : m_papbyKeyBuffers[nNewIndexNo] = (GByte *)CPLCalloc(nKeyLength+1,
823 16 : sizeof(GByte));
824 :
825 : // Return 1-based index number
826 16 : return nNewIndexNo+1;
827 : }
828 :
829 :
830 : /**********************************************************************
831 : * TABINDFile::AddEntry()
832 : *
833 : * Add an .DAT record entry for pKeyValue in the specified index.
834 : *
835 : * Note that index numbers are positive values starting at 1.
836 : * nRecordNo is the .DAT record number, record numbers start at 1.
837 : *
838 : * Returns 0 on success, -1 on error
839 : **********************************************************************/
840 184 : int TABINDFile::AddEntry(int nIndexNumber, GByte *pKeyValue, GInt32 nRecordNo)
841 : {
842 184 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
843 : ValidateIndexNo(nIndexNumber) != 0)
844 0 : return -1;
845 :
846 184 : return m_papoIndexRootNodes[nIndexNumber-1]->AddEntry(pKeyValue,nRecordNo);
847 : }
848 :
849 :
850 : /**********************************************************************
851 : * TABINDFile::Dump()
852 : *
853 : * Dump block contents... available only in DEBUG mode.
854 : **********************************************************************/
855 : #ifdef DEBUG
856 :
857 0 : void TABINDFile::Dump(FILE *fpOut /*=NULL*/)
858 : {
859 0 : if (fpOut == NULL)
860 0 : fpOut = stdout;
861 :
862 0 : fprintf(fpOut, "----- TABINDFile::Dump() -----\n");
863 :
864 0 : if (m_fp == NULL)
865 : {
866 0 : fprintf(fpOut, "File is not opened.\n");
867 : }
868 : else
869 : {
870 0 : fprintf(fpOut, "File is opened: %s\n", m_pszFname);
871 0 : fprintf(fpOut, " m_numIndexes = %d\n", m_numIndexes);
872 0 : for(int i=0; i<m_numIndexes && m_papoIndexRootNodes; i++)
873 : {
874 0 : if (m_papoIndexRootNodes[i])
875 : {
876 0 : fprintf(fpOut, " ----- Index # %d -----\n", i+1);
877 0 : m_papoIndexRootNodes[i]->Dump(fpOut);
878 : }
879 : }
880 :
881 : }
882 :
883 0 : fflush(fpOut);
884 0 : }
885 :
886 : #endif // DEBUG
887 :
888 :
889 :
890 :
891 :
892 : /*=====================================================================
893 : * class TABINDNode
894 : *====================================================================*/
895 :
896 : /**********************************************************************
897 : * TABINDNode::TABINDNode()
898 : *
899 : * Constructor.
900 : **********************************************************************/
901 32 : TABINDNode::TABINDNode(TABAccess eAccessMode /*=TABRead*/)
902 : {
903 32 : m_fp = NULL;
904 32 : m_poCurChildNode = NULL;
905 32 : m_nSubTreeDepth = 0;
906 32 : m_nKeyLength = 0;
907 32 : m_eFieldType = TABFUnknown;
908 32 : m_poDataBlock = NULL;
909 32 : m_numEntriesInNode = 0;
910 32 : m_nCurIndexEntry = 0;
911 32 : m_nPrevNodePtr = 0;
912 32 : m_nNextNodePtr = 0;
913 32 : m_poBlockManagerRef = NULL;
914 32 : m_poParentNodeRef = NULL;
915 32 : m_bUnique = FALSE;
916 :
917 32 : m_eAccessMode = eAccessMode;
918 32 : }
919 :
920 : /**********************************************************************
921 : * TABINDNode::~TABINDNode()
922 : *
923 : * Destructor.
924 : **********************************************************************/
925 32 : TABINDNode::~TABINDNode()
926 : {
927 32 : if (m_poCurChildNode)
928 0 : delete m_poCurChildNode;
929 :
930 32 : if (m_poDataBlock)
931 32 : delete m_poDataBlock;
932 32 : }
933 :
934 : /**********************************************************************
935 : * TABINDNode::InitNode()
936 : *
937 : * Init a node... this function can be used either to initialize a new
938 : * node, or to make it point to a new data block in the file.
939 : *
940 : * By default, this call will read the data from the file at the
941 : * specified location if necessary, and leave the object ready to be searched.
942 : *
943 : * In write access, if the block does not exist (i.e. nBlockPtr=0) then a
944 : * new one is created and initialized.
945 : *
946 : * poParentNode is used in write access in order to update the parent node
947 : * when this node becomes full and has to be split.
948 : *
949 : * Returns 0 on success, -1 on error.
950 : **********************************************************************/
951 32 : int TABINDNode::InitNode(FILE *fp, int nBlockPtr,
952 : int nKeyLength, int nSubTreeDepth,
953 : GBool bUnique,
954 : TABBinBlockManager *poBlockMgr /*=NULL*/,
955 : TABINDNode *poParentNode /*=NULL*/,
956 : int nPrevNodePtr /*=0*/, int nNextNodePtr /*=0*/)
957 : {
958 : /*-----------------------------------------------------------------
959 : * If the block already points to the right block, then don't do
960 : * anything here.
961 : *----------------------------------------------------------------*/
962 32 : if (m_fp == fp && nBlockPtr> 0 && m_nCurDataBlockPtr == nBlockPtr)
963 0 : return 0;
964 :
965 : // Keep track of some info
966 32 : m_fp = fp;
967 32 : m_nKeyLength = nKeyLength;
968 32 : m_nSubTreeDepth = nSubTreeDepth;
969 32 : m_nCurDataBlockPtr = nBlockPtr;
970 32 : m_bUnique = bUnique;
971 :
972 : // Do not overwrite the following values if we receive NULL (the defaults)
973 32 : if (poBlockMgr)
974 32 : m_poBlockManagerRef = poBlockMgr;
975 32 : if (poParentNode)
976 0 : m_poParentNodeRef = poParentNode;
977 :
978 : // Set some defaults
979 32 : m_numEntriesInNode = 0;
980 32 : m_nPrevNodePtr = nPrevNodePtr;
981 32 : m_nNextNodePtr = nNextNodePtr;
982 :
983 32 : m_nCurIndexEntry = 0;
984 :
985 : /*-----------------------------------------------------------------
986 : * Init RawBinBlock
987 : * The node's buffer has to be created with read/write access since
988 : * the index is a very dynamic structure!
989 : *----------------------------------------------------------------*/
990 32 : if (m_poDataBlock == NULL)
991 32 : m_poDataBlock = new TABRawBinBlock(TABReadWrite, TRUE);
992 :
993 48 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
994 : nBlockPtr == 0 && m_poBlockManagerRef)
995 : {
996 : /*-------------------------------------------------------------
997 : * Write access: Create and init a new block
998 : *------------------------------------------------------------*/
999 16 : m_nCurDataBlockPtr = m_poBlockManagerRef->AllocNewBlock();
1000 16 : m_poDataBlock->InitNewBlock(m_fp, 512, m_nCurDataBlockPtr);
1001 :
1002 16 : m_poDataBlock->WriteInt32( m_numEntriesInNode );
1003 16 : m_poDataBlock->WriteInt32( m_nPrevNodePtr );
1004 16 : m_poDataBlock->WriteInt32( m_nNextNodePtr );
1005 : }
1006 : else
1007 : {
1008 16 : CPLAssert(m_nCurDataBlockPtr > 0);
1009 : /*-------------------------------------------------------------
1010 : * Read the data block from the file, applies to read access, or
1011 : * to write access (to modify an existing block)
1012 : *------------------------------------------------------------*/
1013 16 : if (m_poDataBlock->ReadFromFile(m_fp, m_nCurDataBlockPtr, 512) != 0)
1014 : {
1015 : // CPLError() has already been called.
1016 0 : return -1;
1017 : }
1018 :
1019 16 : m_poDataBlock->GotoByteInBlock(0);
1020 16 : m_numEntriesInNode = m_poDataBlock->ReadInt32();
1021 16 : m_nPrevNodePtr = m_poDataBlock->ReadInt32();
1022 16 : m_nNextNodePtr = m_poDataBlock->ReadInt32();
1023 : }
1024 :
1025 : // m_poDataBlock is now positioned at the beginning of the key entries
1026 :
1027 32 : return 0;
1028 : }
1029 :
1030 :
1031 : /**********************************************************************
1032 : * TABINDNode::GotoNodePtr()
1033 : *
1034 : * Move to the specified node ptr, and read the new node data from the file.
1035 : *
1036 : * This is just a cover funtion on top of InitNode()
1037 : **********************************************************************/
1038 0 : int TABINDNode::GotoNodePtr(GInt32 nNewNodePtr)
1039 : {
1040 : // First flush current changes if any.
1041 0 : if ((m_eAccessMode == TABWrite || m_eAccessMode == TABReadWrite) &&
1042 0 : m_poDataBlock && m_poDataBlock->CommitToFile() != 0)
1043 0 : return -1;
1044 :
1045 0 : CPLAssert(nNewNodePtr % 512 == 0);
1046 :
1047 : // Then move to the requested location.
1048 : return InitNode(m_fp, nNewNodePtr, m_nKeyLength, m_nSubTreeDepth,
1049 0 : m_bUnique);
1050 : }
1051 :
1052 : /**********************************************************************
1053 : * TABINDNode::ReadIndexEntry()
1054 : *
1055 : * Read the key value and record/node ptr for the specified index entry
1056 : * inside the current node data.
1057 : *
1058 : * nEntryNo is the 0-based index of the index entry that we are interested
1059 : * in inside the current node.
1060 : *
1061 : * Returns the record/node ptr, and copies the key value inside the
1062 : * buffer pointed to by *pKeyValue... this assumes that *pKeyValue points
1063 : * to a buffer big enough to hold the key value (m_nKeyLength bytes).
1064 : * If pKeyValue == NULL, then this parameter is ignored and the key value
1065 : * is not copied.
1066 : **********************************************************************/
1067 80 : GInt32 TABINDNode::ReadIndexEntry(int nEntryNo, GByte *pKeyValue)
1068 : {
1069 80 : GInt32 nRecordPtr = 0;
1070 80 : if (nEntryNo >= 0 && nEntryNo < m_numEntriesInNode)
1071 : {
1072 80 : if (pKeyValue)
1073 : {
1074 0 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4));
1075 0 : m_poDataBlock->ReadBytes(m_nKeyLength, pKeyValue);
1076 : }
1077 : else
1078 : {
1079 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4)+
1080 80 : m_nKeyLength);
1081 : }
1082 :
1083 80 : nRecordPtr = m_poDataBlock->ReadInt32();
1084 : }
1085 :
1086 80 : return nRecordPtr;
1087 : }
1088 :
1089 : /**********************************************************************
1090 : * TABINDNode::IndexKeyCmp()
1091 : *
1092 : * Compare the specified index entry with the key value, and
1093 : * return 0 if equal, an integer less than 0 if key is smaller than
1094 : * index entry, and an integer greater than 0 if key is bigger than
1095 : * index entry.
1096 : *
1097 : * nEntryNo is the 0-based index of the index entry that we are interested
1098 : * in inside the current node.
1099 : **********************************************************************/
1100 2774 : int TABINDNode::IndexKeyCmp(GByte *pKeyValue, int nEntryNo)
1101 : {
1102 2774 : CPLAssert(pKeyValue);
1103 2774 : CPLAssert(nEntryNo >= 0 && nEntryNo < m_numEntriesInNode);
1104 :
1105 2774 : m_poDataBlock->GotoByteInBlock(12 + nEntryNo*(m_nKeyLength+4));
1106 :
1107 2774 : return memcmp(pKeyValue, m_poDataBlock->GetCurDataPtr(), m_nKeyLength);
1108 : }
1109 :
1110 : /**********************************************************************
1111 : * TABINDNode::SetFieldType()
1112 : *
1113 : * Sets the field type for the current index and recursively set all
1114 : * children as well.
1115 : * This information will then be used in building the key values, etc.
1116 : *
1117 : * Returns 0 on success, -1 on error.
1118 : **********************************************************************/
1119 0 : int TABINDNode::SetFieldType(TABFieldType eType)
1120 : {
1121 0 : if (m_fp == NULL)
1122 : {
1123 : CPLError(CE_Failure, CPLE_AssertionFailed,
1124 0 : "TABINDNode::SetFieldType(): File has not been opened yet!");
1125 0 : return -1;
1126 : }
1127 :
1128 : /*-----------------------------------------------------------------
1129 : * Validate field type with key length
1130 : *----------------------------------------------------------------*/
1131 0 : if ((eType == TABFInteger && m_nKeyLength != 4) ||
1132 : (eType == TABFSmallInt && m_nKeyLength != 2) ||
1133 : (eType == TABFFloat && m_nKeyLength != 8) ||
1134 : (eType == TABFDecimal && m_nKeyLength != 8) ||
1135 : (eType == TABFDate && m_nKeyLength != 4) ||
1136 : (eType == TABFTime && m_nKeyLength != 4) ||
1137 : (eType == TABFDateTime && m_nKeyLength != 8) ||
1138 : (eType == TABFLogical && m_nKeyLength != 4) )
1139 : {
1140 : CPLError(CE_Failure, CPLE_IllegalArg,
1141 : "Index key length (%d) does not match field type (%s).",
1142 0 : m_nKeyLength, TABFIELDTYPE_2_STRING(eType) );
1143 0 : return -1;
1144 : }
1145 :
1146 0 : m_eFieldType = eType;
1147 :
1148 : /*-----------------------------------------------------------------
1149 : * Pass the field type info to child nodes
1150 : *----------------------------------------------------------------*/
1151 0 : if (m_poCurChildNode)
1152 0 : return m_poCurChildNode->SetFieldType(eType);
1153 :
1154 0 : return 0;
1155 : }
1156 :
1157 : /**********************************************************************
1158 : * TABINDNode::FindFirst()
1159 : *
1160 : * Start a new search in this node and its children for a key value.
1161 : * If the index is not unique, then FindNext() can be used to return
1162 : * the other values that correspond to the key.
1163 : *
1164 : * Return value:
1165 : * - the key's corresponding record number in the .DAT file (greater than 0)
1166 : * - 0 if the key was not found
1167 : * - or -1 if an error happened
1168 : **********************************************************************/
1169 244 : GInt32 TABINDNode::FindFirst(GByte *pKeyValue)
1170 : {
1171 244 : if (m_poDataBlock == NULL)
1172 : {
1173 : CPLError(CE_Failure, CPLE_AssertionFailed,
1174 0 : "TABINDNode::Search(): Node has not been initialized yet!");
1175 0 : return -1;
1176 : }
1177 :
1178 : /*-----------------------------------------------------------------
1179 : * Unless something has been broken, this method will be called by our
1180 : * parent node after it has established that we are the best candidate
1181 : * to contain the first instance of the key value. So there is no
1182 : * need to look in the previous or next nodes in the chain... if the
1183 : * value is not found in the current node block then it is not present
1184 : * in the index at all.
1185 : *
1186 : * m_nCurIndexEntry will be used to keep track of the search pointer
1187 : * when FindNext() will be used.
1188 : *----------------------------------------------------------------*/
1189 244 : m_nCurIndexEntry = 0;
1190 :
1191 244 : if (m_nSubTreeDepth == 1)
1192 : {
1193 : /*-------------------------------------------------------------
1194 : * Leaf node level... we look for an exact match
1195 : *------------------------------------------------------------*/
1196 1840 : while(m_nCurIndexEntry < m_numEntriesInNode)
1197 : {
1198 1458 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1199 1458 : if (nCmpStatus > 0)
1200 : {
1201 : /* Not there yet... (pKey > IndexEntry) */
1202 1352 : m_nCurIndexEntry++;
1203 : }
1204 106 : else if (nCmpStatus == 0)
1205 : {
1206 : /* Found it! Return the record number */
1207 64 : return ReadIndexEntry(m_nCurIndexEntry, NULL);
1208 : }
1209 : else
1210 : {
1211 : /* Item does not exist... return 0 */
1212 42 : return 0;
1213 : }
1214 : }
1215 : }
1216 : else
1217 : {
1218 : /*-------------------------------------------------------------
1219 : * Index Node: Find the child node that is the best candidate to
1220 : * contain the value
1221 : *
1222 : * In the index tree at the node level, for each node entry inside
1223 : * the parent node, the key value (in the parent) corresponds to
1224 : * the value of the first key that you will find when you access
1225 : * the corresponding child node.
1226 : *
1227 : * This means that to find the child that contains the searched
1228 : * key, we look for the first index key >= pKeyValue and the child
1229 : * node that we are looking for is the one that precedes it.
1230 : *
1231 : * If the first key in the list is >= pKeyValue then this means
1232 : * that the pKeyValue does not exist in our children and we just
1233 : * return 0. We do not bother searching the previous node at the
1234 : * same level since this is the responsibility of our parent.
1235 : *
1236 : * The same way if the last indexkey in this node is < pKeyValue
1237 : * we won't bother searching the next node since this should also
1238 : * be taken care of by our parent.
1239 : *------------------------------------------------------------*/
1240 0 : while(m_nCurIndexEntry < m_numEntriesInNode)
1241 : {
1242 0 : int nCmpStatus = IndexKeyCmp(pKeyValue, m_nCurIndexEntry);
1243 :
1244 0 : if (nCmpStatus > 0 && m_nCurIndexEntry+1 < m_numEntriesInNode)
1245 : {
1246 : /* Not there yet... (pKey > IndexEntry) */
1247 0 : m_nCurIndexEntry++;
1248 : }
1249 : else
1250 : {
1251 : /*-----------------------------------------------------
1252 : * We either found an indexkey >= pKeyValue or reached
1253 : * the last entry in this node... still have to decide
1254 : * what we're going to do...
1255 : *----------------------------------------------------*/
1256 0 : if (nCmpStatus < 0 && m_nCurIndexEntry == 0)
1257 : {
1258 : /*-------------------------------------------------
1259 : * First indexkey in block is > pKeyValue...
1260 : * the key definitely does not exist in our children.
1261 : * However, we still want to drill down the rest of the
1262 : * tree because this function is also used when looking
1263 : * for a node to insert a new value.
1264 : *-------------------------------------------------*/
1265 : // Nothing special to do... just continue processing.
1266 : }
1267 :
1268 : /*-----------------------------------------------------
1269 : * If we found an node for which pKeyValue < indexkey
1270 : * (or pKeyValue <= indexkey for non-unique indexes) then
1271 : * we access the preceding child node.
1272 : *
1273 : * Note that for indexkey == pKeyValue in non-unique indexes
1274 : * we also check in the preceding node because when keys
1275 : * are not unique then there are chances that the requested
1276 : * key could also be found at the end of the preceding node.
1277 : * In this case, if we don't find the key in the preceding
1278 : * node then we'll do a second search in the current node.
1279 : *----------------------------------------------------*/
1280 0 : int numChildrenToVisit=1;
1281 0 : if (m_nCurIndexEntry > 0 &&
1282 : (nCmpStatus < 0 || (nCmpStatus==0 && !m_bUnique)) )
1283 : {
1284 0 : m_nCurIndexEntry--;
1285 0 : if (nCmpStatus == 0)
1286 0 : numChildrenToVisit = 2;
1287 : }
1288 :
1289 : /*-----------------------------------------------------
1290 : * OK, now it's time to load/access the candidate child nodes.
1291 : *----------------------------------------------------*/
1292 0 : int nRetValue = 0;
1293 0 : for(int iChild=0; nRetValue==0 &&
1294 : iChild<numChildrenToVisit; iChild++)
1295 : {
1296 : // If we're doing a second pass then jump to next entry
1297 0 : if (iChild > 0)
1298 0 : m_nCurIndexEntry++;
1299 :
1300 0 : int nChildNodePtr = ReadIndexEntry(m_nCurIndexEntry, NULL);
1301 0 : if (nChildNodePtr == 0)
1302 : {
1303 : /* Invalid child node??? */
1304 0 : nRetValue = 0;
1305 0 : continue;
1306 : }
1307 0 : else if (m_poCurChildNode == NULL)
1308 : {
1309 : /* Child node has never been initialized...do it now!*/
1310 :
1311 0 : m_poCurChildNode = new TABINDNode(m_eAccessMode);
1312 0 : if ( m_poCurChildNode->InitNode(m_fp, nChildNodePtr,
1313 : m_nKeyLength,
1314 : m_nSubTreeDepth-1,
1315 : m_bUnique,
1316 : m_poBlockManagerRef,
1317 : this) != 0 ||
1318 : m_poCurChildNode->SetFieldType(m_eFieldType)!=0)
1319 : {
1320 : // An error happened... and was already reported
1321 0 : return -1;
1322 : }
1323 : }
1324 :
1325 0 : if (m_poCurChildNode->GotoNodePtr(nChildNodePtr) != 0)
1326 : {
1327 : // An error happened and has already been reported
1328 0 : return -1;
1329 : }
1330 :
1331 0 : nRetValue = m_poCurChildNode->FindFirst(pKeyValue);
1332 : }/*for iChild*/
1333 :
1334 0 : return nRetValue;
1335 :
1336 : }/*else*/
1337 :
1338 : }/*while numEntries*/
1339 :
1340 : // No node was found that contains the key value.
1341 : // We should never get here... only leaf nodes should return 0
1342 0 : CPLAssert(FALSE);
1343 0 : return 0;
1344 : }
1345 :
1346 138 : return 0; // Not found
1347 : }
1348 :
1349 : /**********************************************************************
1350 : * TABINDNode::FindNext()
1351 : *
1352 : * Continue the search previously started by FindFirst() in this node
1353 : * and its children for a key value.
1354 : *
1355 : * Return value:
1356 : * - the key's corresponding record number in the .DAT file (greater than 0)
1357 : * - 0 if the key was not found
1358 : * - or -1 if an error happened
1359 : **********************************************************************/
1360 70 : GInt32 TABINDNode::FindNext(GByte *pKeyValue)
1361 : {
1362 70 : if (m_poDataBlock == NULL)
1363 : {
1364 : CPLError(CE_Failure, CPLE_AssertionFailed,
1365 0 : "TABINDNode::Search(): Node has not been initialized yet!");
1366 0 : return -1;
1367 : }
1368 :
1369 : /*-----------------------------------------------------------------
1370 : * m_nCurIndexEntry is the index of the last item that has been
1371 : * returned by FindFirst()/FindNext().
1372 : *----------------------------------------------------------------*/
1373 :
1374 70 : if (m_nSubTreeDepth == 1)
1375 : {
1376 : /*-------------------------------------------------------------
1377 : * Leaf node level... check if the next entry is an exact match
1378 : *------------------------------------------------------------*/
1379 70 : m_nCurIndexEntry++;
1380 70 : if (m_nCurIndexEntry >= m_numEntriesInNode && m_nNextNodePtr > 0)
1381 : {
1382 : // We're at the end of a node ... continue with next node
1383 0 : GotoNodePtr(m_nNextNodePtr);
1384 0 : m_nCurIndexEntry = 0;
1385 : }
1386 :
1387 70 : if (m_nCurIndexEntry < m_numEntriesInNode &&
1388 : IndexKeyCmp(pKeyValue, m_nCurIndexEntry) == 0)
1389 : {
1390 : /* Found it! Return the record number */
1391 16 : return ReadIndexEntry(m_nCurIndexEntry, NULL);
1392 : }
1393 : else
1394 : {
1395 : /* No more items with that key... return 0 */
1396 54 : return 0;
1397 : }
1398 : }
1399 : else
1400 : {
1401 : /*-------------------------------------------------------------
1402 : * Index Node: just pass the search to this child node.
1403 : *------------------------------------------------------------*/
1404 0 : while(m_nCurIndexEntry < m_numEntriesInNode)
1405 : {
1406 0 : if (m_poCurChildNode != NULL)
1407 0 : return m_poCurChildNode->FindNext(pKeyValue);
1408 : }
1409 : }
1410 :
1411 : // No more nodes were found that contain the key value.
1412 0 : return 0;
1413 : }
1414 :
1415 :
1416 : /**********************************************************************
1417 : * TABINDNode::CommitToFile()
1418 : *
1419 : * For write access, write current block and its children to file.
1420 : *
1421 : * note: TABRawBinBlock::CommitToFile() does nothing unless the block has
1422 : * been modified. (it has an internal bModified flag)
1423 : *
1424 : * Returns 0 on success, -1 on error.
1425 : **********************************************************************/
1426 24 : int TABINDNode::CommitToFile()
1427 : {
1428 24 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1429 : m_poDataBlock == NULL)
1430 0 : return -1;
1431 :
1432 24 : if (m_poCurChildNode)
1433 : {
1434 0 : if (m_poCurChildNode->CommitToFile() != 0)
1435 0 : return -1;
1436 :
1437 0 : m_nSubTreeDepth = m_poCurChildNode->GetSubTreeDepth() + 1;
1438 : }
1439 :
1440 24 : return m_poDataBlock->CommitToFile();
1441 : }
1442 :
1443 : /**********************************************************************
1444 : * TABINDNode::AddEntry()
1445 : *
1446 : * Add an .DAT record entry for pKeyValue in this index
1447 : *
1448 : * nRecordNo is the .DAT record number, record numbers start at 1.
1449 : *
1450 : * In order to insert a new value, the root node first does a FindFirst()
1451 : * that will load the whole tree branch up to the insertion point.
1452 : * Then AddEntry() is recursively called up to the leaf node level for
1453 : * the insertion of the actual value.
1454 : * If the leaf node is full then it will be split and if necessary the
1455 : * split will propagate up in the tree through the pointer that each node
1456 : * has on its parent.
1457 : *
1458 : * If bAddInThisNodeOnly=TRUE, then the entry is added only locally and
1459 : * we do not try to update the child node. This is used when the parent
1460 : * of a node that is being splitted has to be updated.
1461 : *
1462 : * bInsertAfterCurChild forces the insertion to happen immediately after
1463 : * the m_nCurIndexEntry. This works only when bAddInThisNodeOnly=TRUE.
1464 : * The default is to search the node for a an insertion point.
1465 : *
1466 : * Returns 0 on success, -1 on error
1467 : **********************************************************************/
1468 184 : int TABINDNode::AddEntry(GByte *pKeyValue, GInt32 nRecordNo,
1469 : GBool bAddInThisNodeOnly /*=FALSE*/,
1470 : GBool bInsertAfterCurChild /*=FALSE*/,
1471 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1472 : {
1473 184 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
1474 : m_poDataBlock == NULL)
1475 0 : return -1;
1476 :
1477 : /*-----------------------------------------------------------------
1478 : * If I'm the root node, then do a FindFirst() to init all the nodes
1479 : * and to make all of them point ot the insertion point.
1480 : *----------------------------------------------------------------*/
1481 184 : if (m_poParentNodeRef == NULL && !bAddInThisNodeOnly)
1482 : {
1483 184 : if (FindFirst(pKeyValue) < 0)
1484 0 : return -1; // Error happened and has already been reported.
1485 : }
1486 :
1487 184 : if (m_poCurChildNode && !bAddInThisNodeOnly)
1488 : {
1489 0 : CPLAssert(m_nSubTreeDepth > 1);
1490 : /*-------------------------------------------------------------
1491 : * Propagate the call down to our children
1492 : * Note: this recursive call could result in new levels of nodes
1493 : * being added under our feet by SplitRootnode() so it is very
1494 : * important to return right after this call or we might not be
1495 : * able to recognize this node at the end of the call!
1496 : *------------------------------------------------------------*/
1497 0 : return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo);
1498 : }
1499 : else
1500 : {
1501 : /*-------------------------------------------------------------
1502 : * OK, we're a leaf node... this is where the real work happens!!!
1503 : *------------------------------------------------------------*/
1504 184 : CPLAssert(m_nSubTreeDepth == 1 || bAddInThisNodeOnly);
1505 :
1506 : /*-------------------------------------------------------------
1507 : * First thing to do is make sure that there is room for a new
1508 : * entry in this node, and to split it if necessary.
1509 : *------------------------------------------------------------*/
1510 184 : if (GetNumEntries() == GetMaxNumEntries())
1511 : {
1512 0 : if (m_poParentNodeRef == NULL)
1513 : {
1514 : /*-----------------------------------------------------
1515 : * Splitting the root node adds one level to the tree, so
1516 : * after splitting we just redirect the call to our child.
1517 : *----------------------------------------------------*/
1518 0 : if (SplitRootNode() != 0)
1519 0 : return -1; // Error happened and has already been reported
1520 :
1521 0 : CPLAssert(m_poCurChildNode);
1522 0 : CPLAssert(m_nSubTreeDepth > 1);
1523 : return m_poCurChildNode->AddEntry(pKeyValue, nRecordNo,
1524 : bAddInThisNodeOnly,
1525 : bInsertAfterCurChild,
1526 0 : bMakeNewEntryCurChild);
1527 : }
1528 : else
1529 : {
1530 : /*-----------------------------------------------------
1531 : * Splitting a regular node will leave it 50% full.
1532 : *----------------------------------------------------*/
1533 0 : if (SplitNode() != 0)
1534 0 : return -1;
1535 : }
1536 : }
1537 :
1538 : /*-------------------------------------------------------------
1539 : * Insert new key/value at the right position in node.
1540 : *------------------------------------------------------------*/
1541 184 : if (InsertEntry(pKeyValue, nRecordNo,
1542 : bInsertAfterCurChild, bMakeNewEntryCurChild) != 0)
1543 0 : return -1;
1544 : }
1545 :
1546 184 : return 0;
1547 : }
1548 :
1549 : /**********************************************************************
1550 : * TABINDNode::InsertEntry()
1551 : *
1552 : * (private method)
1553 : *
1554 : * Insert a key/value pair in the current node buffer.
1555 : *
1556 : * Returns 0 on success, -1 on error
1557 : **********************************************************************/
1558 184 : int TABINDNode::InsertEntry(GByte *pKeyValue, GInt32 nRecordNo,
1559 : GBool bInsertAfterCurChild /*=FALSE*/,
1560 : GBool bMakeNewEntryCurChild /*=FALSE*/)
1561 : {
1562 184 : int iInsertAt=0;
1563 :
1564 184 : if (GetNumEntries() >= GetMaxNumEntries())
1565 : {
1566 : CPLError(CE_Failure, CPLE_AssertionFailed,
1567 0 : "Node is full! Cannot insert key!");
1568 0 : return -1;
1569 : }
1570 :
1571 : /*-----------------------------------------------------------------
1572 : * Find the spot where the key belongs
1573 : *----------------------------------------------------------------*/
1574 184 : if (bInsertAfterCurChild)
1575 : {
1576 0 : iInsertAt = m_nCurIndexEntry+1;
1577 : }
1578 : else
1579 : {
1580 1586 : while(iInsertAt < m_numEntriesInNode)
1581 : {
1582 1270 : int nCmpStatus = IndexKeyCmp(pKeyValue, iInsertAt);
1583 1270 : if (nCmpStatus <= 0)
1584 : {
1585 52 : break;
1586 : }
1587 1218 : iInsertAt++;
1588 : }
1589 : }
1590 :
1591 184 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));
1592 :
1593 : /*-----------------------------------------------------------------
1594 : * Shift all entries that follow in the array
1595 : *----------------------------------------------------------------*/
1596 184 : if (iInsertAt < m_numEntriesInNode)
1597 : {
1598 : // Since we use memmove() directly, we need to inform
1599 : // m_poDataBlock that the upper limit of the buffer will move
1600 : m_poDataBlock->GotoByteInBlock(12 + (m_numEntriesInNode+1)*
1601 52 : (m_nKeyLength+4));
1602 52 : m_poDataBlock->GotoByteInBlock(12 + iInsertAt*(m_nKeyLength+4));
1603 :
1604 : memmove(m_poDataBlock->GetCurDataPtr()+(m_nKeyLength+4),
1605 : m_poDataBlock->GetCurDataPtr(),
1606 52 : (m_numEntriesInNode-iInsertAt)*(m_nKeyLength+4));
1607 :
1608 : }
1609 :
1610 : /*-----------------------------------------------------------------
1611 : * Write new entry
1612 : *----------------------------------------------------------------*/
1613 184 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1614 184 : m_poDataBlock->WriteInt32(nRecordNo);
1615 :
1616 184 : m_numEntriesInNode++;
1617 184 : m_poDataBlock->GotoByteInBlock(0);
1618 184 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1619 :
1620 184 : if (bMakeNewEntryCurChild)
1621 0 : m_nCurIndexEntry = iInsertAt;
1622 184 : else if (m_nCurIndexEntry >= iInsertAt)
1623 184 : m_nCurIndexEntry++;
1624 :
1625 : /*-----------------------------------------------------------------
1626 : * If we replaced the first entry in the node, then this node's key
1627 : * changes and we have to update the reference in the parent node.
1628 : *----------------------------------------------------------------*/
1629 184 : if (iInsertAt == 0 && m_poParentNodeRef)
1630 : {
1631 0 : if (m_poParentNodeRef->UpdateCurChildEntry(GetNodeKey(),
1632 : GetNodeBlockPtr()) != 0)
1633 0 : return -1;
1634 : }
1635 :
1636 184 : return 0;
1637 : }
1638 :
1639 :
1640 : /**********************************************************************
1641 : * TABINDNode::UpdateCurChildEntry()
1642 : *
1643 : * Update the key for the current child node. This method is called by
1644 : * the child when its first entry (defining its node key) is changed.
1645 : *
1646 : * Returns 0 on success, -1 on error
1647 : **********************************************************************/
1648 0 : int TABINDNode::UpdateCurChildEntry(GByte *pKeyValue, GInt32 nRecordNo)
1649 : {
1650 :
1651 : /*-----------------------------------------------------------------
1652 : * Update current child entry with the info for the first node.
1653 : *
1654 : * For some reason, the key for first entry of the first node of each
1655 : * level has to be set to 0 except for the leaf level.
1656 : *----------------------------------------------------------------*/
1657 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));
1658 :
1659 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1660 : {
1661 0 : m_poDataBlock->WriteZeros(m_nKeyLength);
1662 : }
1663 : else
1664 : {
1665 0 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue);
1666 : }
1667 0 : m_poDataBlock->WriteInt32(nRecordNo);
1668 :
1669 0 : return 0;
1670 : }
1671 :
1672 :
1673 :
1674 : /**********************************************************************
1675 : * TABINDNode::UpdateSplitChild()
1676 : *
1677 : * Update the key and/or record ptr information corresponding to the
1678 : * current child node.
1679 : *
1680 : * Returns 0 on success, -1 on error
1681 : **********************************************************************/
1682 0 : int TABINDNode::UpdateSplitChild(GByte *pKeyValue1, GInt32 nRecordNo1,
1683 : GByte *pKeyValue2, GInt32 nRecordNo2,
1684 : int nNewCurChildNo /* 1 or 2 */)
1685 : {
1686 :
1687 : /*-----------------------------------------------------------------
1688 : * Update current child entry with the info for the first node.
1689 : *
1690 : * For some reason, the key for first entry of the first node of each
1691 : * level has to be set to 0 except for the leaf level.
1692 : *----------------------------------------------------------------*/
1693 0 : m_poDataBlock->GotoByteInBlock(12 + m_nCurIndexEntry*(m_nKeyLength+4));
1694 :
1695 0 : if (m_nCurIndexEntry == 0 && m_nSubTreeDepth > 1 && m_nPrevNodePtr == 0)
1696 : {
1697 0 : m_poDataBlock->WriteZeros(m_nKeyLength);
1698 : }
1699 : else
1700 : {
1701 0 : m_poDataBlock->WriteBytes(m_nKeyLength, pKeyValue1);
1702 : }
1703 0 : m_poDataBlock->WriteInt32(nRecordNo1);
1704 :
1705 : /*-----------------------------------------------------------------
1706 : * Add an entry for the second node after the current one and ask
1707 : * AddEntry() to update m_nCurIndexEntry if the new node should
1708 : * become the new current child.
1709 : *----------------------------------------------------------------*/
1710 0 : if (AddEntry(pKeyValue2, nRecordNo2,
1711 : TRUE, /* bInThisNodeOnly */
1712 : TRUE, /* bInsertAfterCurChild */
1713 : (nNewCurChildNo==2)) != 0)
1714 : {
1715 0 : return -1;
1716 : }
1717 :
1718 0 : return 0;
1719 : }
1720 :
1721 :
1722 : /**********************************************************************
1723 : * TABINDNode::SplitNode()
1724 : *
1725 : * (private method)
1726 : *
1727 : * Split a node, update the references in the parent node, etc.
1728 : * Note that Root Nodes cannot be split using this method... SplitRootNode()
1729 : * should be used instead.
1730 : *
1731 : * The node is split in a way that the current child stays inside this
1732 : * node object, and a new node is created for the other half of the
1733 : * entries. This way, the object references in this node's parent and in its
1734 : * current child all remain valid. The new node is not kept in memory,
1735 : * it is written to disk right away.
1736 : *
1737 : * Returns 0 on success, -1 on error
1738 : **********************************************************************/
1739 0 : int TABINDNode::SplitNode()
1740 : {
1741 0 : TABINDNode *poNewNode=NULL;
1742 : int numInNode1, numInNode2;
1743 :
1744 0 : CPLAssert(m_numEntriesInNode >= 2);
1745 0 : CPLAssert(m_poParentNodeRef); // This func. does not work for root nodes
1746 :
1747 : /*-----------------------------------------------------------------
1748 : * Prepare new node
1749 : *----------------------------------------------------------------*/
1750 0 : numInNode1 = (m_numEntriesInNode+1)/2;
1751 0 : numInNode2 = m_numEntriesInNode - numInNode1;
1752 :
1753 0 : poNewNode = new TABINDNode(m_eAccessMode);
1754 :
1755 0 : if (m_nCurIndexEntry < numInNode1)
1756 : {
1757 : /*-------------------------------------------------------------
1758 : * We will move the second half of the array to a new node.
1759 : *------------------------------------------------------------*/
1760 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1761 : m_nSubTreeDepth, m_bUnique,
1762 : m_poBlockManagerRef, m_poParentNodeRef,
1763 : GetNodeBlockPtr(), m_nNextNodePtr)!= 0 ||
1764 : poNewNode->SetFieldType(m_eFieldType) != 0 )
1765 : {
1766 0 : return -1;
1767 : }
1768 :
1769 : // We have to update m_nPrevNodePtr in the node that used to follow
1770 : // the current node and will now follow the new node.
1771 0 : if (m_nNextNodePtr)
1772 : {
1773 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1774 0 : if (poTmpNode->InitNode(m_fp, m_nNextNodePtr,
1775 : m_nKeyLength, m_nSubTreeDepth,
1776 : m_bUnique, m_poBlockManagerRef,
1777 : m_poParentNodeRef) != 0 ||
1778 : poTmpNode->SetPrevNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1779 : poTmpNode->CommitToFile() != 0)
1780 : {
1781 0 : return -1;
1782 : }
1783 0 : delete poTmpNode;
1784 : }
1785 :
1786 0 : m_nNextNodePtr = poNewNode->GetNodeBlockPtr();
1787 :
1788 : // Move half the entries to the new block
1789 0 : m_poDataBlock->GotoByteInBlock(12 + numInNode1*(m_nKeyLength+4));
1790 :
1791 0 : if (poNewNode->SetNodeBufferDirectly(numInNode2,
1792 : m_poDataBlock->GetCurDataPtr()) != 0)
1793 0 : return -1;
1794 :
1795 : #ifdef DEBUG
1796 : // Just in case, reset space previously used by moved entries
1797 0 : memset(m_poDataBlock->GetCurDataPtr(), 0, numInNode2*(m_nKeyLength+4));
1798 : #endif
1799 : // And update current node members
1800 0 : m_numEntriesInNode = numInNode1;
1801 :
1802 : // Update parent node with new children info
1803 0 : if (m_poParentNodeRef)
1804 : {
1805 0 : if (m_poParentNodeRef->UpdateSplitChild(GetNodeKey(),
1806 : GetNodeBlockPtr(),
1807 : poNewNode->GetNodeKey(),
1808 : poNewNode->GetNodeBlockPtr(), 1) != 0)
1809 0 : return -1;
1810 : }
1811 :
1812 : }
1813 : else
1814 : {
1815 : /*-------------------------------------------------------------
1816 : * We will move the first half of the array to a new node.
1817 : *------------------------------------------------------------*/
1818 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1819 : m_nSubTreeDepth, m_bUnique,
1820 : m_poBlockManagerRef, m_poParentNodeRef,
1821 : m_nPrevNodePtr, GetNodeBlockPtr())!= 0 ||
1822 : poNewNode->SetFieldType(m_eFieldType) != 0 )
1823 : {
1824 0 : return -1;
1825 : }
1826 :
1827 : // We have to update m_nNextNodePtr in the node that used to precede
1828 : // the current node and will now precede the new node.
1829 0 : if (m_nPrevNodePtr)
1830 : {
1831 0 : TABINDNode *poTmpNode = new TABINDNode(m_eAccessMode);
1832 0 : if (poTmpNode->InitNode(m_fp, m_nPrevNodePtr,
1833 : m_nKeyLength, m_nSubTreeDepth,
1834 : m_bUnique, m_poBlockManagerRef,
1835 : m_poParentNodeRef) != 0 ||
1836 : poTmpNode->SetNextNodePtr(poNewNode->GetNodeBlockPtr()) != 0 ||
1837 : poTmpNode->CommitToFile() != 0)
1838 : {
1839 0 : return -1;
1840 : }
1841 0 : delete poTmpNode;
1842 : }
1843 :
1844 0 : m_nPrevNodePtr = poNewNode->GetNodeBlockPtr();
1845 :
1846 : // Move half the entries to the new block
1847 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1848 :
1849 0 : if (poNewNode->SetNodeBufferDirectly(numInNode1,
1850 : m_poDataBlock->GetCurDataPtr()) != 0)
1851 0 : return -1;
1852 :
1853 : // Shift the second half of the entries to beginning of buffer
1854 : memmove (m_poDataBlock->GetCurDataPtr(),
1855 : m_poDataBlock->GetCurDataPtr()+numInNode1*(m_nKeyLength+4),
1856 0 : numInNode2*(m_nKeyLength+4));
1857 :
1858 : #ifdef DEBUG
1859 : // Just in case, reset space previously used by moved entries
1860 : memset(m_poDataBlock->GetCurDataPtr()+numInNode2*(m_nKeyLength+4),
1861 0 : 0, numInNode1*(m_nKeyLength+4));
1862 : #endif
1863 :
1864 : // And update current node members
1865 0 : m_numEntriesInNode = numInNode2;
1866 0 : m_nCurIndexEntry -= numInNode1;
1867 :
1868 : // Update parent node with new children info
1869 0 : if (m_poParentNodeRef)
1870 : {
1871 0 : if (m_poParentNodeRef->UpdateSplitChild(poNewNode->GetNodeKey(),
1872 : poNewNode->GetNodeBlockPtr(),
1873 : GetNodeKey(),
1874 : GetNodeBlockPtr(), 2) != 0)
1875 0 : return -1;
1876 : }
1877 :
1878 : }
1879 :
1880 : /*-----------------------------------------------------------------
1881 : * Update current node header
1882 : *----------------------------------------------------------------*/
1883 0 : m_poDataBlock->GotoByteInBlock(0);
1884 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1885 0 : m_poDataBlock->WriteInt32(m_nPrevNodePtr);
1886 0 : m_poDataBlock->WriteInt32(m_nNextNodePtr);
1887 :
1888 : /*-----------------------------------------------------------------
1889 : * Flush and destroy temporary node
1890 : *----------------------------------------------------------------*/
1891 0 : if (poNewNode->CommitToFile() != 0)
1892 0 : return -1;
1893 :
1894 0 : delete poNewNode;
1895 :
1896 0 : return 0;
1897 : }
1898 :
1899 : /**********************************************************************
1900 : * TABINDNode::SplitRootNode()
1901 : *
1902 : * (private method)
1903 : *
1904 : * Split a Root Node.
1905 : * First, a level of nodes must be added to the tree, then the contents
1906 : * of what used to be the root node is moved 1 level down and then that
1907 : * node is split like a regular node.
1908 : *
1909 : * Returns 0 on success, -1 on error
1910 : **********************************************************************/
1911 0 : int TABINDNode::SplitRootNode()
1912 : {
1913 : /*-----------------------------------------------------------------
1914 : * Since a root note cannot be split, we add a level of nodes
1915 : * under it and we'll do the split at that level.
1916 : *----------------------------------------------------------------*/
1917 0 : TABINDNode *poNewNode = new TABINDNode(m_eAccessMode);
1918 :
1919 0 : if (poNewNode->InitNode(m_fp, 0, m_nKeyLength,
1920 : m_nSubTreeDepth, m_bUnique, m_poBlockManagerRef,
1921 : this, 0, 0)!= 0 ||
1922 : poNewNode->SetFieldType(m_eFieldType) != 0)
1923 : {
1924 0 : return -1;
1925 : }
1926 :
1927 : // Move all entries to the new child
1928 0 : m_poDataBlock->GotoByteInBlock(12 + 0);
1929 0 : if (poNewNode->SetNodeBufferDirectly(m_numEntriesInNode,
1930 : m_poDataBlock->GetCurDataPtr(),
1931 : m_nCurIndexEntry,
1932 : m_poCurChildNode) != 0)
1933 : {
1934 0 : return -1;
1935 : }
1936 :
1937 : #ifdef DEBUG
1938 : // Just in case, reset space previously used by moved entries
1939 : memset(m_poDataBlock->GetCurDataPtr(), 0,
1940 0 : m_numEntriesInNode*(m_nKeyLength+4));
1941 : #endif
1942 :
1943 : /*-----------------------------------------------------------------
1944 : * Rewrite current node. (the new root node)
1945 : *----------------------------------------------------------------*/
1946 0 : m_numEntriesInNode = 0;
1947 0 : m_nSubTreeDepth++;
1948 :
1949 0 : m_poDataBlock->GotoByteInBlock(0);
1950 0 : m_poDataBlock->WriteInt32(m_numEntriesInNode);
1951 :
1952 0 : InsertEntry(poNewNode->GetNodeKey(), poNewNode->GetNodeBlockPtr());
1953 :
1954 : /*-----------------------------------------------------------------
1955 : * Keep a reference to the new child
1956 : *----------------------------------------------------------------*/
1957 0 : m_poCurChildNode = poNewNode;
1958 0 : m_nCurIndexEntry = 0;
1959 :
1960 : /*-----------------------------------------------------------------
1961 : * And finally force the child to split itself
1962 : *----------------------------------------------------------------*/
1963 0 : return m_poCurChildNode->SplitNode();
1964 : }
1965 :
1966 : /**********************************************************************
1967 : * TABINDNode::SetNodeBufferDirectly()
1968 : *
1969 : * (private method)
1970 : *
1971 : * Set the key/value part of the nodes buffer and the pointers to the
1972 : * current child direclty. This is used when copying info to a new node
1973 : * in SplitNode() and SplitRootNode()
1974 : *
1975 : * Returns 0 on success, -1 on error
1976 : **********************************************************************/
1977 0 : int TABINDNode::SetNodeBufferDirectly(int numEntries, GByte *pBuf,
1978 : int nCurIndexEntry/*=0*/,
1979 : TABINDNode *poCurChild/*=NULL*/)
1980 : {
1981 0 : m_poDataBlock->GotoByteInBlock(0);
1982 0 : m_poDataBlock->WriteInt32(numEntries);
1983 :
1984 0 : m_numEntriesInNode = numEntries;
1985 :
1986 0 : m_poDataBlock->GotoByteInBlock(12);
1987 0 : if ( m_poDataBlock->WriteBytes(numEntries*(m_nKeyLength+4), pBuf) != 0)
1988 : {
1989 0 : return -1; // An error msg should have been reported already
1990 : }
1991 :
1992 0 : m_nCurIndexEntry = nCurIndexEntry;
1993 0 : m_poCurChildNode = poCurChild;
1994 0 : if (m_poCurChildNode)
1995 0 : m_poCurChildNode->m_poParentNodeRef = this;
1996 :
1997 0 : return 0;
1998 : }
1999 :
2000 : /**********************************************************************
2001 : * TABINDNode::GetNodeKey()
2002 : *
2003 : * Returns a reference to the key for the first entry in the node, which
2004 : * is also the key for this node at the level above it in the tree.
2005 : *
2006 : * Returns NULL if node is empty.
2007 : **********************************************************************/
2008 0 : GByte* TABINDNode::GetNodeKey()
2009 : {
2010 0 : if (m_poDataBlock == NULL || m_numEntriesInNode == 0)
2011 0 : return NULL;
2012 :
2013 0 : m_poDataBlock->GotoByteInBlock(12);
2014 :
2015 0 : return m_poDataBlock->GetCurDataPtr();
2016 : }
2017 :
2018 : /**********************************************************************
2019 : * TABINDNode::SetPrevNodePtr()
2020 : *
2021 : * Update the m_nPrevNodePtr member.
2022 : *
2023 : * Returns 0 on success, -1 on error.
2024 : **********************************************************************/
2025 0 : int TABINDNode::SetPrevNodePtr(GInt32 nPrevNodePtr)
2026 : {
2027 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2028 : m_poDataBlock == NULL)
2029 0 : return -1;
2030 :
2031 0 : if (m_nPrevNodePtr == nPrevNodePtr)
2032 0 : return 0; // Nothing to do.
2033 :
2034 0 : m_poDataBlock->GotoByteInBlock(4);
2035 0 : return m_poDataBlock->WriteInt32(nPrevNodePtr);
2036 : }
2037 :
2038 : /**********************************************************************
2039 : * TABINDNode::SetNextNodePtr()
2040 : *
2041 : * Update the m_nNextNodePtr member.
2042 : *
2043 : * Returns 0 on success, -1 on error.
2044 : **********************************************************************/
2045 0 : int TABINDNode::SetNextNodePtr(GInt32 nNextNodePtr)
2046 : {
2047 0 : if ((m_eAccessMode != TABWrite && m_eAccessMode != TABReadWrite) ||
2048 : m_poDataBlock == NULL)
2049 0 : return -1;
2050 :
2051 0 : if (m_nNextNodePtr == nNextNodePtr)
2052 0 : return 0; // Nothing to do.
2053 :
2054 0 : m_poDataBlock->GotoByteInBlock(8);
2055 0 : return m_poDataBlock->WriteInt32(nNextNodePtr);
2056 : }
2057 :
2058 :
2059 :
2060 : /**********************************************************************
2061 : * TABINDNode::Dump()
2062 : *
2063 : * Dump block contents... available only in DEBUG mode.
2064 : **********************************************************************/
2065 : #ifdef DEBUG
2066 :
2067 0 : void TABINDNode::Dump(FILE *fpOut /*=NULL*/)
2068 : {
2069 0 : if (fpOut == NULL)
2070 0 : fpOut = stdout;
2071 :
2072 0 : fprintf(fpOut, "----- TABINDNode::Dump() -----\n");
2073 :
2074 0 : if (m_fp == NULL)
2075 : {
2076 0 : fprintf(fpOut, "Node is not initialized.\n");
2077 : }
2078 : else
2079 : {
2080 0 : fprintf(fpOut, " m_numEntriesInNode = %d\n", m_numEntriesInNode);
2081 0 : fprintf(fpOut, " m_nCurDataBlockPtr = %d\n", m_nCurDataBlockPtr);
2082 0 : fprintf(fpOut, " m_nPrevNodePtr = %d\n", m_nPrevNodePtr);
2083 0 : fprintf(fpOut, " m_nNextNodePtr = %d\n", m_nNextNodePtr);
2084 0 : fprintf(fpOut, " m_nSubTreeDepth = %d\n", m_nSubTreeDepth);
2085 0 : fprintf(fpOut, " m_nKeyLength = %d\n", m_nKeyLength);
2086 : fprintf(fpOut, " m_eFieldtype = %s\n",
2087 0 : TABFIELDTYPE_2_STRING(m_eFieldType) );
2088 0 : if (m_nSubTreeDepth > 0)
2089 : {
2090 : GByte aKeyValBuf[255];
2091 : GInt32 nRecordPtr, nValue;
2092 0 : TABINDNode oChildNode;
2093 :
2094 0 : if (m_nKeyLength > 254)
2095 : {
2096 : CPLError(CE_Failure, CPLE_NotSupported,
2097 0 : "Dump() cannot handle keys longer than 254 chars.");
2098 : return;
2099 : }
2100 :
2101 0 : fprintf(fpOut, "\n");
2102 0 : for (int i=0; i<m_numEntriesInNode; i++)
2103 : {
2104 0 : if (m_nSubTreeDepth > 1)
2105 : {
2106 : fprintf(fpOut, " >>>> Child %d of %d <<<<<\n", i,
2107 0 : m_numEntriesInNode);
2108 : }
2109 : else
2110 : {
2111 : fprintf(fpOut, " >>>> Record (leaf) %d of %d <<<<<\n", i,
2112 0 : m_numEntriesInNode);
2113 : }
2114 :
2115 0 : if (m_eFieldType == TABFChar)
2116 : {
2117 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2118 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2119 0 : fprintf(fpOut, " Char Val= \"%s\"\n", (char*)aKeyValBuf);
2120 : }
2121 0 : else if (m_nKeyLength != 4)
2122 : {
2123 0 : nRecordPtr = ReadIndexEntry(i, aKeyValBuf);
2124 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2125 0 : fprintf(fpOut, " Int Value = %d\n", *(GInt32*)aKeyValBuf);
2126 0 : fprintf(fpOut, " Int16 Val= %d\n",*(GInt16*)(aKeyValBuf+2));
2127 0 : fprintf(fpOut, " Hex Val= 0x%8.8x\n",*(GUInt32*)aKeyValBuf);
2128 : }
2129 : else
2130 : {
2131 0 : nRecordPtr = ReadIndexEntry(i, (GByte*)&nValue);
2132 0 : fprintf(fpOut, " nRecordPtr = %d\n", nRecordPtr);
2133 0 : fprintf(fpOut, " Int Value = %d\n", nValue);
2134 0 : fprintf(fpOut, " Hex Value = 0x%8.8x\n",nValue);
2135 : }
2136 :
2137 0 : if (m_nSubTreeDepth > 1)
2138 : {
2139 : oChildNode.InitNode(m_fp, nRecordPtr, m_nKeyLength,
2140 0 : m_nSubTreeDepth - 1, FALSE);
2141 0 : oChildNode.SetFieldType(m_eFieldType);
2142 0 : oChildNode.Dump(fpOut);
2143 : }
2144 0 : }
2145 : }
2146 : }
2147 :
2148 0 : fflush(fpOut);
2149 : }
2150 :
2151 : #endif // DEBUG
|
