1 /*
2 * Motif
3 *
4 * Copyright (c) 1987-2012, The Open Group. All rights reserved.
5 *
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
16 * details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
22 */
23 #ifdef HAVE_CONFIG_H
24 #include <config.h>
25 #endif
26
27
28 #ifdef REV_INFO
29 #ifndef lint
30 static char rcsid[] = "$XConsortium: MrmIindexw.c /main/12 1996/11/13 13:57:54 drk $"
31 #endif
32 #endif
33
34
35 /*
36 *++
37 * FACILITY:
38 *
39 * UIL Resource Manager (URM): IDB Facility
40 * Index management routines
41 *
42 * ABSTRACT:
43 *
44 * These routines manage the index of an IDB file, including
45 * retrieving data entries accessed by index, and maintaing the
46 * index structure, particularly index splitting
47 *
48 *--
49 */
50
51
52 /*
53 *
54 * INCLUDE FILES
55 *
56 */
57
58 #include <Mrm/MrmAppl.h>
59 #include <Mrm/Mrm.h>
60 #include <Mrm/IDB.h>
61 #include "MrmMsgI.h"
62
63
64 /*
65 *
66 * TABLE OF CONTENTS
67 *
68 * Idb__INX_EnterItem - Enter a data entry under an index
69 *
70 * Idb__INX_EnterLeafIndex - Add an entry to a leaf record
71 *
72 * Idb__INX_EnterNodeIndex - Add an entry to a node record
73 *
74 * Idb__INX_SplitLeafRecord - Split a leaf index record
75 *
76 * Idb__INX_SplitNodeRecord - Split a node index record
77 *
78 * Idb__INX_InitRootLeafRecord - Init a (root) leaf index record
79 *
80 * Idb__INX_InitRootNodeRecord - Init a (root) node index record
81 *
82 * Idb__INX_CopyLeafRecord - Copy a leaf record
83 *
84 * Idb__INX_CopyNodeRecord - Copy a node record
85 *
86 * Idb__INX_CollapseLeafRecord - Collapse a leaf record (truncate)
87 *
88 * Idb__INX_CollapseNodeRecord - Collapse a node record (truncate)
89 *
90 * Idb__INX_ConfirmNodeSpace - Confirm enough space in node
91 * record for new entry
92 *
93 * Idb__INX_SetParent - Set parent pointer in record
94 *
95 * Idb__INX_FixNodeChildren - Reset parent pointers for all
96 * the children of some node
97 *
98 */
99
100
101 /*
102 *
103 * DEFINE and MACRO DEFINITIONS
104 *
105 */
106
107 /*
108 * Macros which validate index records in buffers
109 */
110 #define Idb__INX_ValidLeaf(buffer) \
111 (_IdbBufferRecordType(buffer)==IDBrtIndexLeaf)
112 #define Idb__INX_ValidNode(buffer) \
113 (_IdbBufferRecordType(buffer)==IDBrtIndexNode)
114 #define Idb__INX_ValidRecord(buffer) \
115 (_IdbBufferRecordType(buffer)==IDBrtIndexLeaf || \
116 _IdbBufferRecordType(buffer)==IDBrtIndexNode)
117
118
119
120 /*
121 *++
122 *
123 * PROCEDURE DESCRIPTION:
124 *
125 * Idb__INX_EnterItem makes an entry in the file's index for a data
126 * entry which has been previously entered in the file.
127 *
128 * FORMAL PARAMETERS:
129 *
130 * file_id Open IDB file in which to write entry
131 * index The entry's case-sensitive index
132 * data_entry Data entry pointer for data
133 *
134 * IMPLICIT INPUTS:
135 *
136 * IMPLICIT OUTPUTS:
137 *
138 * FUNCTION VALUE:
139 *
140 * MrmSUCCESS operation succeeded
141 * MrmEXISTS index already exists in file
142 * MrmFAILURE some other failure
143 *
144 * SIDE EFFECTS:
145 *
146 *--
147 */
148
149 Cardinal
150 Idb__INX_EnterItem (IDBFile file_id ,
151 char *index ,
152 IDBDataHandle data_entry )
153 {
154
155 /*
156 * Local variables
157 */
158 Cardinal result ; /* function results */
159 IDBRecordBufferPtr bufptr ; /* buffer into which to stuff entry */
160 MrmCount entndx ; /* locates pivotal entry in buffer */
161
162
163 /*
164 * Initialize the index with this entry if this is the initial one.
165 */
166 if ( !file_id->index_root )
167 {
168 result = Idb__INX_InitRootLeafRecord (file_id, &bufptr) ;
169 if (result != MrmSUCCESS ) return result ;
170 result = Idb__INX_EnterLeafIndex
171 (file_id, bufptr, index, data_entry, 0, MrmINDEX_LT) ;
172 return result ;
173 }
174
175 /*
176 * Find the (leaf) record in which to place this entry, and the
177 * position in the record. Place it in the record (which must be
178 * a leaf record). This process loops as long as record splitting
179 * forces retries.
180 */
181 do {
182 result = Idb__INX_FindIndex (file_id, index, &bufptr, &entndx) ;
183 switch ( result )
184 {
185 case MrmINDEX_GT:
186 case MrmINDEX_LT:
187 break ;
188 case MrmSUCCESS:
189 return MrmEXISTS ;
190 default:
191 return result ;
192 }
193 result = Idb__INX_EnterLeafIndex
194 (file_id, bufptr, index, data_entry, entndx, result) ;
195 } while ( result == MrmINDEX_RETRY ) ;
196
197 /*
198 * Return results of final attempt to stuff in a leaf record
199 */
200 return result ;
201
202 }
203
204
205
206 /*
207 *++
208 *
209 * PROCEDURE DESCRIPTION:
210 *
211 * Idb__INX_EnterLeafIndex creates a new entry for a data entry in a
212 * leaf index record. If there isn't enough room in the record for
213 * the new entry, the record is split and the enter operation must
214 * be retried.
215 *
216 * FORMAL PARAMETERS:
217 *
218 * file_id Open IDB file
219 * buffer Buffer containing leaf index record
220 * index The entry's case-sensitive index
221 * data_entry Data entry pointer for data
222 * entry_index Entry in record at which to force new entry
223 * order Specifies how new entry orders WRT entry at
224 * entry_index; MrmINDEX_GT or MrmINDEX_LT.
225 *
226 * IMPLICIT INPUTS:
227 *
228 * IMPLICIT OUTPUTS:
229 *
230 * FUNCTION VALUE:
231 *
232 * MrmSUCCESS operation succeeded
233 * MrmINDEX_RETRY operation must be tried again.
234 * MrmFAILURE some other failure
235 *
236 * SIDE EFFECTS:
237 *
238 *--
239 */
240
241 Cardinal
Idb__INX_EnterLeafIndex(IDBFile file_id,IDBRecordBufferPtr buffer,char * index,IDBDataHandle data_entry,MrmCount entry_index,Cardinal order)242 Idb__INX_EnterLeafIndex (IDBFile file_id,
243 IDBRecordBufferPtr buffer,
244 char *index,
245 IDBDataHandle data_entry,
246 MrmCount entry_index,
247 Cardinal order)
248 {
249
250 /*
251 * Local variables
252 */
253 Cardinal result ; /* function results */
254 IDBIndexLeafRecordPtr recptr ; /* leaf record in buffer */
255 IDBIndexLeafHdrPtr hdrptr ; /* record header */
256 MrmCount entndx ; /* index for new entry */
257 Cardinal entsiz ; /* # bytes needed for new entry */
258 MrmCount ndxsiz ; /* # bytes needed for new string */
259 char *ndxstg ; /* location for new string */
260 int ndx ; /* loop index */
261 char *stgheap ; /* string heap beginning */
262 MrmCount nfree ; /* # free bytes */
263 IDBIndexLeafEntryPtr itemvec ; /* The vector of index entries */
264 MrmCount itemcnt ; /* # entries in vector */
265
266
267 /*
268 * Initialize pointers into the record
269 */
270 recptr = (IDBIndexLeafRecordPtr) buffer->IDB_record ;
271 hdrptr = (IDBIndexLeafHdrPtr) &recptr->leaf_header ;
272
273 /*
274 * Compute sizes for new entry. Split record and retry if required
275 * to get enough space.
276 */
277 ndxsiz = MIN(strlen(index),IDBMaxIndexLength) + 1 ;
278 ndxsiz = _FULLWORD(ndxsiz);
279 entsiz = IDBIndexLeafEntrySize + ndxsiz ;
280 nfree = hdrptr->free_bytes ;
281 if ( entsiz > nfree )
282 {
283 result = Idb__INX_SplitLeafRecord (file_id, buffer) ;
284 if ( result != MrmSUCCESS ) return result ;
285 return MrmINDEX_RETRY ;
286 }
287
288 /*
289 * Pick up values and pointers into the record.
290 * Adjust entry index based on ordering, then make room for the
291 * new entry.
292 */
293 stgheap = (char *) &recptr->index[0] + hdrptr->heap_start ;
294 itemvec = recptr->index ;
295 itemcnt = hdrptr->index_count ;
296
297 entndx = (order==MrmINDEX_GT) ? entry_index+1 : entry_index ;
298 ndxstg = (char *) stgheap - ndxsiz ;
299
300 for ( ndx=itemcnt ; ndx>entndx ; ndx--)
301 {
302 itemvec[ndx].index_stg = itemvec[ndx-1].index_stg ;
303 itemvec[ndx].data = itemvec[ndx-1].data ;
304 }
305
306 /*
307 * Move the string and set the values in the vector entry
308 */
309 strcpy (ndxstg, "") ;
310 strncat (ndxstg, index, IDBMaxIndexLength) ;
311 itemvec[entndx].index_stg = (MrmOffset) (ndxstg-(char *)itemvec) ;
312 itemvec[entndx].data.internal_id.rec_no = data_entry.rec_no ;
313 itemvec[entndx].data.internal_id.item_offs = data_entry.item_offs ;
314
315 /*
316 * update the header
317 */
318 hdrptr->index_count++ ;
319 hdrptr->heap_start -= ndxsiz ;
320 hdrptr->free_bytes -= entsiz ;
321
322 /*
323 * entry successfully added
324 */
325 Idb__BM_MarkModified (buffer) ;
326 return MrmSUCCESS ;
327
328 }
329
330
331
332 /*
333 *++
334 *
335 * PROCEDURE DESCRIPTION:
336 *
337 * Idb__INX_EnterNodeIndex creates a new entry for a data entry in a
338 * node index record. It differs from entering an item in a leaf record
339 * in that the position for the new entry is not known.
340 * If there isn't room for the new entry, the record is split, and
341 * the operation must be tried again.
342 *
343 * FORMAL PARAMETERS:
344 *
345 * file_id Open IDB file
346 * buffer Buffer containing node index record
347 * index The entry's case-sensitive index
348 * data_entry Data entry pointer for data
349 * lt_record Record number of the less-than record associated with
350 * this entry
351 * gt_record Record number of the greater-than record associated with
352 * this entry
353 *
354 * IMPLICIT INPUTS:
355 *
356 * IMPLICIT OUTPUTS:
357 *
358 * FUNCTION VALUE:
359 *
360 * MrmSUCCESS operation succeeded
361 * MrmINDEX_RETRY operation must be tried again.
362 * MrmFAILURE some other failure
363 *
364 * SIDE EFFECTS:
365 *
366 *--
367 */
368
369 Cardinal
Idb__INX_EnterNodeIndex(IDBFile file_id,IDBRecordBufferPtr buffer,char * index,IDBDataHandle data_entry,IDBRecordNumber lt_record,IDBRecordNumber gt_record)370 Idb__INX_EnterNodeIndex (IDBFile file_id,
371 IDBRecordBufferPtr buffer,
372 char *index,
373 IDBDataHandle data_entry,
374 IDBRecordNumber lt_record,
375 IDBRecordNumber gt_record)
376 {
377
378 /*
379 * Local variables
380 */
381 Cardinal result ; /* function results */
382 IDBIndexNodeRecordPtr recptr ; /* node record in buffer */
383 IDBIndexNodeHdrPtr hdrptr ; /* record header */
384 MrmCount entry_index ; /* searched location for new entry */
385 Cardinal order ; /* order of index WRT location */
386 MrmCount entndx ; /* index for new entry */
387 Cardinal entsiz ; /* # bytes needed for new entry */
388 MrmCount ndxsiz ; /* # bytes needed for new string */
389 char *ndxstg ; /* location for new string */
390 int ndx ; /* loop index */
391 char *stgheap ; /* string heap beginning */
392 MrmCount nfree ; /* # free bytes */
393 IDBIndexNodeEntryPtr itemvec ; /* The vector of index entries */
394 MrmCount itemcnt ; /* # entries in vector */
395 MrmCount prvndx ; /* preceding entry index */
396 MrmCount nxtndx ; /* succeeding entry index */
397 IDBRecordNumber p_recno ; /* this node record number */
398
399
400 /*
401 * Initialize pointers into the record
402 */
403 recptr = (IDBIndexNodeRecordPtr) buffer->IDB_record ;
404 hdrptr = (IDBIndexNodeHdrPtr) &recptr->node_header ;
405
406 /*
407 * Compute sizes for new entry. Split record and retry if required
408 * to get enough space.
409 */
410 ndxsiz = MIN(strlen(index),IDBMaxIndexLength) + 1 ;
411 ndxsiz = _FULLWORD(ndxsiz);
412 entsiz = IDBIndexNodeEntrySize + ndxsiz ;
413 nfree = hdrptr->free_bytes ;
414 if ( entsiz > nfree )
415 {
416 result = Idb__INX_SplitNodeRecord (file_id, buffer) ;
417 if ( result != MrmSUCCESS ) return result ;
418 return MrmINDEX_RETRY ;
419 }
420
421 /*
422 * Pick up value and pointers into the record. Figure out the
423 * location at which to insert the record (0 for a new entry),
424 * and make room for the new entry.
425 */
426 stgheap = (char *) &recptr->index[0] + hdrptr->heap_start ;
427 itemvec = recptr->index ;
428 itemcnt = hdrptr->index_count ;
429 if ( itemcnt == 0 )
430 entndx = 0 ;
431 else
432 {
433 order = Idb__INX_SearchIndex (file_id, index, buffer, &entry_index) ;
434 entndx = (order==MrmINDEX_GT) ? entry_index+1 : entry_index ;
435 for ( ndx=itemcnt ; ndx>entndx ; ndx--)
436 {
437 itemvec[ndx].index_stg = itemvec[ndx-1].index_stg ;
438 itemvec[ndx].data = itemvec[ndx-1].data ;
439 itemvec[ndx].LT_record = itemvec[ndx-1].LT_record ;
440 itemvec[ndx].GT_record = itemvec[ndx-1].GT_record ;
441 }
442 }
443
444 /*
445 * Move the string and set the values in the vector entry and record vector
446 */
447 ndxstg = (char *) stgheap - ndxsiz ;
448 strcpy (ndxstg, "") ;
449 strncat (ndxstg, index, IDBMaxIndexLength) ;
450 itemvec[entndx].index_stg = (MrmOffset) (ndxstg-(char *)itemvec) ;
451 itemvec[entndx].data.internal_id.rec_no = data_entry.rec_no ;
452 itemvec[entndx].data.internal_id.item_offs = data_entry.item_offs ;
453 itemvec[entndx].LT_record = lt_record ;
454 itemvec[entndx].GT_record = gt_record ;
455
456 /*
457 * update the header
458 */
459 hdrptr->index_count = ++itemcnt ;
460 hdrptr->heap_start -= ndxsiz ;
461 hdrptr->free_bytes -= entsiz ;
462
463 /*
464 * Now the entries to either side of the new index must have their LT
465 * and LT pointers verified and changed. By practice, the GT record of the
466 * new entry is a previous record which should occur as the GT record of
467 * the preceding entry and the LT record of the succeeding entry.
468 * These entries must be modified to have LT and GT pointers matching the
469 * records given here as arguments.
470 */
471 if ( entndx > 0 )
472 {
473 prvndx = entndx - 1 ;
474 if ( itemvec[prvndx].GT_record != gt_record )
475 return Urm__UT_Error ("Idb__INX_EnterNodeIndex", _MrmMMsg_0016,
476 file_id, NULL, MrmBAD_BTREE) ;
477 itemvec[prvndx].GT_record = lt_record ;
478 }
479 if ( entndx < (itemcnt-1) )
480 {
481 nxtndx = entndx + 1 ;
482 if ( itemvec[nxtndx].LT_record != gt_record )
483 return Urm__UT_Error ("Idb__INX_EnterNodeIndex", _MrmMMsg_0017,
484 file_id, NULL, MrmBAD_BTREE) ;
485 itemvec[nxtndx].LT_record = gt_record ;
486 }
487
488 /*
489 * entry successfully added
490 */
491 Idb__BM_MarkModified (buffer) ;
492
493 /*
494 * Set the parent pointer in the LT and GT records
495 */
496 p_recno = _IdbBufferRecordNumber (buffer) ;
497 result = Idb__INX_SetParent (file_id, p_recno, lt_record) ;
498 result = Idb__INX_SetParent (file_id, p_recno, gt_record) ;
499 if ( result != MrmSUCCESS ) return result ;
500
501 return MrmSUCCESS ;
502
503 }
504
505
506
507 /*
508 *++
509 *
510 * PROCEDURE DESCRIPTION:
511 *
512 * Idb__INX_SplitRecord splits an index record in order to make room
513 * for new entries. This is the crucial routine in causing the B-tree
514 * to grow. It splits leaf records only.
515 *
516 * The split process takes place as follows:
517 * - extract the middle entry from the record and save it.
518 * - create a new leaf record and move all the less-than
519 * ordered entries into it.
520 * - reorganize the current record to contain only the greater-than
521 * ordered entries (garbage collecting the string heap).
522 * - Enter the extracted entry in the parent (creating a new
523 * parent if required). This entry takes the less-than
524 * record with it to the parent, thus entering the new leaf
525 * record in the B-tree. The old record is retained as a
526 * greater-than record for the extracted index.
527 *
528 * The trickiest aspect of splitting nodes is maintaining parent
529 * pointers when splitting may cause parents to change. IDB deals
530 * this by splitting from the top of the tree down, so that a node's
531 * parent pointer is guaranteed correct when the node is split.
532 * This is done by:
533 * - Before splitting, check that parent has enough room
534 * for a new entry. If not, the parent will split and
535 * inform the caller to retry.
536 * - Splitting the root node is always safe
537 *
538 * FORMAL PARAMETERS:
539 *
540 * file_id Open IDB file
541 * gt_buffer Buffer containing leaf index record to be split
542 * This will become the new GT buffer
543 *
544 * IMPLICIT INPUTS:
545 *
546 * IMPLICIT OUTPUTS:
547 *
548 * FUNCTION VALUE:
549 *
550 * MrmSUCCESS operation succeeded
551 * MrmBAD_RECORD not a leaf index record
552 * MrmFAILURE some other failure
553 *
554 * SIDE EFFECTS:
555 *
556 *--
557 */
558
559 Cardinal
Idb__INX_SplitLeafRecord(IDBFile file_id,IDBRecordBufferPtr gt_buffer)560 Idb__INX_SplitLeafRecord (IDBFile file_id,
561 IDBRecordBufferPtr gt_buffer)
562 {
563
564 /*
565 * Local variables
566 */
567 Cardinal result ; /* function results */
568 IDBRecordNumber p_recno ; /* parent record number */
569 IDBRecordBufferPtr p_buffer ; /* parent buffer */
570 IDBRecordBufferPtr lt_buffer ; /* buffer for LT leaf record */
571 IDBIndexLeafRecordPtr lt_recptr ; /* LT leaf record in buffer */
572 IDBIndexLeafRecordPtr gt_recptr ; /* GT leaf record in buffer */
573 IDBIndexLeafHdrPtr gt_hdrptr ; /* GT record header */
574 MrmCount p_index ; /* index of hoisted entry */
575 char p_index_stg[IDBMaxIndexLength1] ; /* save hoisted idx */
576 char *p_index_stgadr ; /* Address of hoisted index string */
577 IDBDataHandle p_data ; /* saves hoisted entry data */
578 MrmCount lt_cnt ; /* number of LT items */
579 MrmCount gt_cnt ; /* number of GT items */
580 MrmCount old_cnt ; /* original number of items */
581 IDBIndexLeafEntryPtr old_itmvec ; /* Original vector */
582
583
584 /*
585 * Initialize pointers into the record and sanity check. This record
586 * will become the GT leaf record
587 */
588 if ( ! Idb__INX_ValidLeaf(gt_buffer) )
589 return Urm__UT_Error ("Idb__INX_SplitLeafRecord", _MrmMMsg_0010,
590 file_id, NULL, MrmBAD_RECORD) ;
591
592 gt_recptr = (IDBIndexLeafRecordPtr) gt_buffer->IDB_record ;
593 gt_hdrptr = (IDBIndexLeafHdrPtr) >_recptr->leaf_header ;
594
595 /*
596 * If this node has a parent, make sure it can hold a new entry.
597 * If not, it will split, and we must retry. Note a parent must be
598 * a node record.
599 */
600 p_recno = gt_hdrptr->parent ;
601 if ( gt_hdrptr->parent )
602 {
603 result = Idb__BM_GetRecord (file_id, gt_hdrptr->parent, &p_buffer) ;
604 if ( result != MrmSUCCESS ) return result ;
605 if ( ! Idb__INX_ValidNode(p_buffer) )
606 return Urm__UT_Error ("Idb__INX_SplitLeafRecord", _MrmMMsg_0018,
607 file_id, NULL, MrmBAD_RECORD) ;
608 result = Idb__INX_ConfirmNodeSpace (file_id, p_buffer) ;
609 if ( result != MrmSUCCESS ) return result ;
610 }
611
612 /*
613 * Pick up current parameters
614 */
615 old_cnt = gt_hdrptr->index_count ;
616 old_itmvec = gt_recptr->index ;
617
618 /*
619 * Compute the indexes and counts for the split, and save the hoisted entry.
620 */
621 lt_cnt = old_cnt / 2 ;
622 p_index = lt_cnt ;
623 gt_cnt = old_cnt - lt_cnt - 1;
624 p_index_stgadr = (char *) old_itmvec+old_itmvec[p_index].index_stg ;
625 strcpy (p_index_stg, p_index_stgadr) ;
626 p_data.rec_no = old_itmvec[p_index].data.internal_id.rec_no ;
627 p_data.item_offs = old_itmvec[p_index].data.internal_id.item_offs ;
628
629 /*
630 * Acquire a new record to become the LT part. Copy the entire current
631 * record into it, then collapse both records into their final form.
632 */
633 result = Idb__BM_InitRecord (file_id, 0, IDBrtIndexLeaf, <_buffer) ;
634 lt_recptr = (IDBIndexLeafRecordPtr) lt_buffer->IDB_record ;
635 Idb__INX_CopyLeafRecord (lt_recptr, gt_recptr) ;
636 Idb__INX_CollapseLeafRecord (lt_recptr, 0, lt_cnt-1) ;
637 Idb__INX_CollapseLeafRecord (gt_recptr, p_index+1, p_index+gt_cnt) ;
638
639 /*
640 * Both records now have their parent set correctly via the copy operation,
641 * since our check on space in the parent guarantees that the parent
642 * pointer present in the original buffer will remain the parent after
643 * we host the pivot index (unless we create a new root node, which
644 * is guaranteed safe anyway. So we we can mark the buffers and
645 * hoist the pivot index.
646 */
647 Idb__BM_MarkModified (lt_buffer) ;
648 Idb__BM_MarkModified (gt_buffer) ;
649
650 /*
651 * Either enter the hoisted entry into the parent, or create
652 * a parent (which will be the root record).
653 */
654 if ( !p_recno )
655 {
656 result = Idb__INX_InitRootNodeRecord
657 (file_id, &p_buffer, p_index_stg, p_data,
658 _IdbBufferRecordNumber(lt_buffer), _IdbBufferRecordNumber(gt_buffer)) ;
659 return result ;
660 }
661
662 /*
663 * Hoist the entry into the parent (we know there should be room).
664 * The parent is already loaded in its buffer as part of the space check.
665 */
666 result = Idb__INX_EnterNodeIndex
667 (file_id, p_buffer, p_index_stg, p_data,
668 _IdbBufferRecordNumber(lt_buffer), _IdbBufferRecordNumber(gt_buffer)) ;
669 if ( result != MrmSUCCESS ) return result ;
670
671 /*
672 * Successfully added.
673 */
674 return MrmSUCCESS ;
675
676 }
677
678
679
680 /*
681 *++
682 *
683 * PROCEDURE DESCRIPTION:
684 *
685 * Idb__INX_SplitRecord splits an index record in order to make room
686 * for new entries. This is the crucial routine in causing the B-tree
687 * to grow. It splits node records only.
688 *
689 * The split process takes place as follows:
690 * - extract the middle entry from the record and save it.
691 * - create a new node record and move all the less-than
692 * ordered entries into it.
693 * - reorganize the current record to contain only the greater-than
694 * ordered entries (garbage collecting the string heap).
695 * - Enter the extracted entry in the parent (creating a new
696 * parent if required). This entry takes the less-than
697 * record with it to the parent, thus entering the new node
698 * record in the B-tree. The old record is retained as a
699 * greater-than record for the extracted index.
700 *
701 * For node records, the record vectors are handled entirely by
702 * the collapse routines. No record number is saved for the hoisted
703 * index, since the associated record number is either new LT record
704 * or both records if a root node is created.
705 *
706 * FORMAL PARAMETERS:
707 *
708 * file_id Open IDB file
709 * gt_buffer Buffer containing node index record to be split. This
710 * will become the new GT buffer.
711 *
712 * IMPLICIT INPUTS:
713 *
714 * IMPLICIT OUTPUTS:
715 *
716 * FUNCTION VALUE:
717 *
718 * MrmSUCCESS operation succeeded
719 * MrmBAD_RECORD not a node index record
720 * MrmFAILURE some other failure
721 *
722 * SIDE EFFECTS:
723 *
724 *--
725 */
726
727 Cardinal
Idb__INX_SplitNodeRecord(IDBFile file_id,IDBRecordBufferPtr gt_buffer)728 Idb__INX_SplitNodeRecord (IDBFile file_id,
729 IDBRecordBufferPtr gt_buffer)
730 {
731
732 /*
733 * Local variables
734 */
735 Cardinal result ; /* function results */
736 IDBRecordNumber p_recno ; /* parent record number */
737 IDBRecordBufferPtr p_buffer ; /* parent buffer */
738 IDBRecordBufferPtr lt_buffer ; /* buffer for LT node record */
739 IDBIndexNodeRecordPtr lt_recptr ; /* LT node record in buffer */
740 IDBIndexNodeRecordPtr gt_recptr ; /* GT node record in buffer */
741 IDBIndexNodeHdrPtr gt_hdrptr ; /* GT record header */
742 IDBRecordNumber lt_recno ; /* LT node record number */
743 IDBRecordNumber gt_recno ; /* GT node record number */
744 MrmCount p_index ; /* index of hoisted entry */
745 char p_index_stg[IDBMaxIndexLength1]; /* save hoisted indx */
746 char *p_index_stgadr ; /* Address of hoisted index string */
747 IDBDataHandle p_data ; /* saves hoisted entry data */
748 MrmCount lt_cnt ; /* number of LT items */
749 MrmCount gt_cnt ; /* number of GT items */
750 MrmCount old_cnt ; /* original number of items */
751 IDBIndexNodeEntryPtr old_itmvec ; /* Original vector */
752
753
754 /*
755 * Initialize pointers into the record and sanity check. This record
756 * will become the GT node record
757 */
758 if ( ! Idb__INX_ValidNode(gt_buffer) )
759 return Urm__UT_Error ("Idb__INX_SplitNodeRecord", _MrmMMsg_0010,
760 file_id, NULL, MrmBAD_RECORD) ;
761
762 gt_recptr = (IDBIndexNodeRecordPtr) gt_buffer->IDB_record ;
763 gt_hdrptr = (IDBIndexNodeHdrPtr) >_recptr->node_header ;
764
765 /*
766 * If this node has a parent, make sure it can hold a new entry.
767 * If not, it will split, and we must retry. Note a parent must be
768 * a node record.
769 */
770 p_recno = gt_hdrptr->parent ;
771 if ( p_recno )
772 {
773 result = Idb__BM_GetRecord (file_id, p_recno, &p_buffer) ;
774 if ( result != MrmSUCCESS ) return result ;
775 if ( ! Idb__INX_ValidNode(p_buffer) )
776 return Urm__UT_Error ("Idb__INX_SplitNodeRecord", _MrmMMsg_0018,
777 file_id, NULL, MrmBAD_RECORD) ;
778 result = Idb__INX_ConfirmNodeSpace (file_id, p_buffer) ;
779 if ( result != MrmSUCCESS ) return result ;
780 }
781
782 /*
783 * Pick up current parameters
784 */
785 old_cnt = gt_hdrptr->index_count ;
786 old_itmvec = gt_recptr->index ;
787
788 /*
789 * Compute the indexes and counts for the split, and save the hoisted entry.
790 */
791 lt_cnt = old_cnt / 2 ;
792 p_index = lt_cnt ;
793 gt_cnt = old_cnt - lt_cnt - 1;
794 p_index_stgadr = (char *) old_itmvec+old_itmvec[p_index].index_stg ;
795 strcpy (p_index_stg, p_index_stgadr) ;
796 p_data.rec_no = old_itmvec[p_index].data.internal_id.rec_no ;
797 p_data.item_offs = old_itmvec[p_index].data.internal_id.item_offs ;
798
799 /*
800 * Acquire a new record to become the LT part. Copy the entire current
801 * record into it, then collapse both records into their final form.
802 */
803 result = Idb__BM_InitRecord (file_id, 0, IDBrtIndexNode, <_buffer) ;
804 lt_recptr = (IDBIndexNodeRecordPtr) lt_buffer->IDB_record ;
805 Idb__INX_CopyNodeRecord (lt_recptr, gt_recptr) ;
806 Idb__INX_CollapseNodeRecord (lt_recptr, 0, lt_cnt-1) ;
807 Idb__INX_CollapseNodeRecord (gt_recptr, p_index+1, p_index+gt_cnt) ;
808
809 /*
810 * Both records now have their parent set correctly via the copy operation,
811 * since our check on space in the parent guarantees that the parent
812 * pointer present in the original buffer will remain the parent after
813 * we host the pivot index (unless we create a new root node, which
814 * is guaranteed safe anyway. Thus we are done with all changes to these
815 * buffers, and can mark them. Then save their record numbers and child
816 * list for future operations.
817 */
818 Idb__BM_MarkModified (lt_buffer) ;
819 Idb__BM_MarkModified (gt_buffer) ;
820
821 lt_recno = _IdbBufferRecordNumber (lt_buffer) ;
822 gt_recno = _IdbBufferRecordNumber (gt_buffer) ;
823
824 /*
825 * Either enter the hoisted entry into the parent, or create
826 * a parent (which will be the root record).
827 *
828 * Otherwise, hoist the entry into the parent (we know there should be room).
829 * The parent should be already loaded in its buffer as part of the space
830 * check, but a reload is done to make sure buffer turning hasn't interfered.
831 */
832 if ( !p_recno )
833 {
834 result = Idb__INX_InitRootNodeRecord
835 (file_id, &p_buffer, p_index_stg, p_data, lt_recno, gt_recno) ;
836 if ( result != MrmSUCCESS ) return result ;
837 }
838 else
839 {
840 result = Idb__BM_GetRecord (file_id, p_recno, &p_buffer) ;
841 if ( result != MrmSUCCESS ) return result ;
842 result = Idb__INX_EnterNodeIndex
843 (file_id, p_buffer, p_index_stg, p_data, lt_recno, gt_recno) ;
844 if ( result != MrmSUCCESS ) return result ;
845 }
846
847 /*
848 * Now all child nodes of the split record must have their parent
849 * pointers updated. The gt_buffer children should still have the same
850 * parent, but the update will be done to that buffer as well for
851 * completeness.
852 */
853 result = Idb__INX_FixNodeChildren (file_id, lt_recno) ;
854 if ( result != MrmSUCCESS ) return result ;
855 result = Idb__INX_FixNodeChildren (file_id, gt_recno) ;
856 if ( result != MrmSUCCESS ) return result ;
857
858 /*
859 * Successfully added.
860 */
861 return MrmSUCCESS ;
862
863 }
864
865
866
867 /*
868 *++
869 *
870 * PROCEDURE DESCRIPTION:
871 *
872 * Idb__INX_InitLeafRecord initializes a new leaf index record,
873 * resulting in an empty record with the maximum free space available.
874 * It may be immediately used to enter an index item. This routine
875 * is used just once, to create the initial root record. Thereafter,
876 * all leaf records are created by splitting and collapsing existing
877 * records.
878 *
879 * FORMAL PARAMETERS:
880 *
881 * file_id Open IDB file
882 * buffer_return To return pointer to buffer containing new record
883 *
884 * IMPLICIT INPUTS:
885 *
886 * IMPLICIT OUTPUTS:
887 *
888 * FUNCTION VALUE:
889 *
890 * MrmSUCCESS operation succeeded
891 * MrmFAILURE some other failure
892 *
893 * SIDE EFFECTS:
894 *
895 *--
896 */
897
898 Cardinal
Idb__INX_InitRootLeafRecord(IDBFile file_id,IDBRecordBufferPtr * buffer_return)899 Idb__INX_InitRootLeafRecord (IDBFile file_id,
900 IDBRecordBufferPtr *buffer_return)
901 {
902
903 /*
904 * Local variables
905 */
906 Cardinal result ; /* function results */
907 IDBRecordBufferPtr bufptr ; /* leaf record buffer */
908 IDBIndexLeafRecordPtr recptr ; /* leaf record in buffer */
909 IDBIndexLeafHdrPtr hdrptr ; /* record header */
910
911
912 /*
913 * Acquire a record
914 */
915 result = Idb__BM_InitRecord (file_id, 0, IDBrtIndexLeaf, &bufptr) ;
916 if ( result != MrmSUCCESS ) return result ;
917 recptr = (IDBIndexLeafRecordPtr) bufptr->IDB_record ;
918 hdrptr = (IDBIndexLeafHdrPtr) &recptr->leaf_header ;
919
920 /*
921 * Initialize the record header
922 */
923 hdrptr->parent = 0 ;
924 hdrptr->index_count = 0 ;
925 hdrptr->heap_start = IDBIndexLeafFreeMax ;
926 hdrptr->free_bytes = IDBIndexLeafFreeMax ;
927
928 /*
929 * Successfully initialized
930 */
931 Idb__BM_MarkModified (bufptr) ;
932 *buffer_return = bufptr ;
933
934 file_id->index_root = hdrptr->header.record_num ;
935
936 return MrmSUCCESS ;
937
938 }
939
940 /*
941 *++
942 *
943 * PROCEDURE DESCRIPTION:
944 *
945 * Idb__INX_InitNodeRecord initializes a new node index record. It
946 * creates the initial entry in the record, with its index, data pointer,
947 * and pointers to two children records in the B-tree. This entry always
948 * becomes the root of the B-tree, since the only occasion on which
949 * a node record is created in this way is when a new root is needed.
950 *
951 * FORMAL PARAMETERS:
952 *
953 * file_id Open IDB file
954 * buffer_return To return pointer to buffer containing new record
955 * index Index for single entry in record
956 * data_entry Data entry pointer for data
957 * lt_record Record number of B-tree record ordering < the index
958 * gt_record Record number of B-tree record ordering > the index
959 *
960 * IMPLICIT INPUTS:
961 *
962 * IMPLICIT OUTPUTS:
963 *
964 * FUNCTION VALUE:
965 *
966 * MrmSUCCESS operation succeeded
967 * MrmFAILURE some other failure
968 *
969 * SIDE EFFECTS:
970 *
971 *--
972 */
973
974 Cardinal
Idb__INX_InitRootNodeRecord(IDBFile file_id,IDBRecordBufferPtr * buffer_return,char * index,IDBDataHandle data_entry,IDBRecordNumber lt_record,IDBRecordNumber gt_record)975 Idb__INX_InitRootNodeRecord (IDBFile file_id,
976 IDBRecordBufferPtr *buffer_return,
977 char *index,
978 IDBDataHandle data_entry,
979 IDBRecordNumber lt_record,
980 IDBRecordNumber gt_record)
981 {
982
983 /*
984 * Local variables
985 */
986 Cardinal result ; /* function results */
987 IDBRecordBufferPtr bufptr ; /* node record buffer */
988 IDBIndexNodeRecordPtr recptr ; /* node record in buffer */
989 IDBIndexNodeHdrPtr hdrptr ; /* record header */
990 IDBRecordNumber recno ; /* this buffer's record number */
991
992
993 /*
994 * Acquire a record
995 */
996 result = Idb__BM_InitRecord (file_id, 0, IDBrtIndexNode, &bufptr) ;
997 if ( result != MrmSUCCESS ) return result ;
998 recptr = (IDBIndexNodeRecordPtr) bufptr->IDB_record ;
999 hdrptr = (IDBIndexNodeHdrPtr) &recptr->node_header ;
1000
1001 /*
1002 * Initialize the record header
1003 */
1004 hdrptr->parent = 0 ;
1005 hdrptr->index_count = 0 ;
1006 hdrptr->heap_start = IDBIndexNodeFreeMax ;
1007 hdrptr->free_bytes = IDBIndexNodeFreeMax ;
1008
1009 /*
1010 * Enter the initial entry
1011 */
1012 result = Idb__INX_EnterNodeIndex
1013 (file_id, bufptr, index, data_entry, lt_record, gt_record) ;
1014 if ( result != MrmSUCCESS ) return result ;
1015
1016 /*
1017 * Successfully initialized
1018 */
1019 Idb__BM_MarkModified (bufptr) ;
1020 *buffer_return = bufptr ;
1021
1022 /*
1023 * Set the parent pointers in the two child entries.
1024 */
1025 recno = _IdbBufferRecordNumber (bufptr) ;
1026 result = Idb__INX_SetParent (file_id, recno, lt_record) ;
1027 if ( result != MrmSUCCESS ) return result ;
1028 result = Idb__INX_SetParent (file_id, recno, gt_record) ;
1029 if ( result != MrmSUCCESS ) return result ;
1030
1031 /*
1032 * Root node successfully created. Update file header.
1033 */
1034 file_id->index_root = hdrptr->header.record_num ;
1035 return MrmSUCCESS ;
1036
1037 }
1038
1039
1040
1041 /*
1042 *++
1043 *
1044 * PROCEDURE DESCRIPTION:
1045 *
1046 * This routines copies one leaf record into another.
1047 *
1048 * FORMAL PARAMETERS:
1049 *
1050 * dst_recptr pointer to record into which to copy
1051 * src_recptr source record pointer
1052 *
1053 * IMPLICIT INPUTS:
1054 *
1055 * IMPLICIT OUTPUTS:
1056 *
1057 * FUNCTION VALUE:
1058 *
1059 * SIDE EFFECTS:
1060 *
1061 *--
1062 */
1063
1064 void
Idb__INX_CopyLeafRecord(IDBIndexLeafRecordPtr dst_recptr,IDBIndexLeafRecordPtr src_recptr)1065 Idb__INX_CopyLeafRecord (IDBIndexLeafRecordPtr dst_recptr,
1066 IDBIndexLeafRecordPtr src_recptr)
1067 {
1068
1069 /*
1070 * Local variables
1071 */
1072 IDBIndexLeafHdrPtr dst_hdrptr ; /* destination record header */
1073 IDBIndexLeafHdrPtr src_hdrptr ; /* source record header */
1074 char *dst_data ; /* data part of dest record */
1075 char *src_data ; /* data part of source record */
1076
1077 /*
1078 * copy the header, field by field
1079 */
1080 dst_hdrptr = (IDBIndexLeafHdrPtr) &dst_recptr->leaf_header ;
1081 src_hdrptr = (IDBIndexLeafHdrPtr) &src_recptr->leaf_header ;
1082 dst_hdrptr->parent = src_hdrptr->parent ;
1083 dst_hdrptr->index_count = src_hdrptr->index_count ;
1084 dst_hdrptr->heap_start = src_hdrptr->heap_start ;
1085 dst_hdrptr->free_bytes = src_hdrptr->free_bytes ;
1086
1087 /*
1088 * copy the data area in the record
1089 */
1090 dst_data = (char *) dst_recptr->index ;
1091 src_data = (char *) src_recptr->index ;
1092
1093 UrmBCopy (src_data, dst_data, IDBIndexLeafFreeMax) ;
1094
1095 }
1096
1097 /*
1098 *++
1099 *
1100 * PROCEDURE DESCRIPTION:
1101 *
1102 * This routines copies one node record into another.
1103 *
1104 * FORMAL PARAMETERS:
1105 *
1106 * dst_recptr pointer to record into which to copy
1107 * src_recptr source record pointer
1108 *
1109 * IMPLICIT INPUTS:
1110 *
1111 * IMPLICIT OUTPUTS:
1112 *
1113 * FUNCTION VALUE:
1114 *
1115 * SIDE EFFECTS:
1116 *
1117 *--
1118 */
1119
1120 void
Idb__INX_CopyNodeRecord(IDBIndexNodeRecordPtr dst_recptr,IDBIndexNodeRecordPtr src_recptr)1121 Idb__INX_CopyNodeRecord (IDBIndexNodeRecordPtr dst_recptr,
1122 IDBIndexNodeRecordPtr src_recptr)
1123 {
1124
1125 /*
1126 * Local variables
1127 */
1128 IDBIndexNodeHdrPtr dst_hdrptr ; /* destination record header */
1129 IDBIndexNodeHdrPtr src_hdrptr ; /* source record header */
1130 char *dst_data ; /* data part of dest record */
1131 char *src_data ; /* data part of source record */
1132
1133 /*
1134 * copy the header, field by field
1135 */
1136 dst_hdrptr = (IDBIndexNodeHdrPtr) &dst_recptr->node_header ;
1137 src_hdrptr = (IDBIndexNodeHdrPtr) &src_recptr->node_header ;
1138 dst_hdrptr->parent = src_hdrptr->parent ;
1139 dst_hdrptr->index_count = src_hdrptr->index_count ;
1140 dst_hdrptr->heap_start = src_hdrptr->heap_start ;
1141 dst_hdrptr->free_bytes = src_hdrptr->free_bytes ;
1142
1143 /*
1144 * copy the data area in the record
1145 */
1146 dst_data = (char *) dst_recptr->index ;
1147 src_data = (char *) src_recptr->index ;
1148 UrmBCopy (src_data, dst_data, IDBIndexNodeFreeMax) ;
1149
1150 }
1151
1152 /*
1153 *++
1154 *
1155 * PROCEDURE DESCRIPTION:
1156 *
1157 * This routine collapses a leaf index record as part of splitting
1158 * a record. Collapsing the record truncates the record contents
1159 * by removing part of the index vector, re-organizing the string
1160 * heap to consume minimal space, resetting the heap parameters,
1161 * and resetting the index count.
1162 *
1163 * FORMAL PARAMETERS:
1164 *
1165 * recptr The leaf index record to collapse
1166 * start First entry in the index vector to be preserved
1167 * end Last entry in the index vector to be preserved
1168 *
1169 * IMPLICIT INPUTS:
1170 *
1171 * IMPLICIT OUTPUTS:
1172 *
1173 * FUNCTION VALUE:
1174 *
1175 * SIDE EFFECTS:
1176 *
1177 *--
1178 */
1179
1180 void
Idb__INX_CollapseLeafRecord(IDBIndexLeafRecordPtr recptr,MrmCount start,MrmCount end)1181 Idb__INX_CollapseLeafRecord (IDBIndexLeafRecordPtr recptr,
1182 MrmCount start,
1183 MrmCount end)
1184 {
1185
1186 /*
1187 * Local variables
1188 */
1189 IDBIndexLeafHdrPtr hdrptr ; /* record header */
1190 int ndx ; /* loop index */
1191 char *temp_heap ; /* temporary heap */
1192 char *cur_heap ; /* current heap pointer */
1193 MrmCount heap_size ; /* # bytes used in temp heap */
1194 IDBIndexLeafEntryPtr srcvec ; /* source index vector */
1195 IDBIndexLeafEntryPtr dstvec ; /* destination index vector */
1196 char *stgbase ; /* base address for string offsets */
1197 char *ndxstg ; /* current index string */
1198 MrmCount stgsiz ; /* # bytes for current string */
1199 MrmCount ndxcnt ; /* # entries in collapsed record */
1200 MrmCount nfree ; /* # free bytes in collapsed record */
1201 MrmOffset heap_start ; /* new heap start offset */
1202
1203
1204 /*
1205 * Allocate a temporary heap (big enough to hold data area). Copy each
1206 * string which must be preserved into the temporary heap. The heap
1207 * is allocated top-to-bottom, and the temporary offsets will be
1208 * made permanent when the temporary heap is copied into the record.
1209 *
1210 * Copy the surviving part of the index vector while saving the strings.
1211 * The new offset is set as part of this operation.
1212 */
1213 temp_heap = (char *) XtMalloc (IDBIndexLeafFreeMax) ;
1214 cur_heap = temp_heap ;
1215 heap_size = 0 ;
1216
1217 hdrptr = (IDBIndexLeafHdrPtr) &recptr->leaf_header ;
1218 srcvec = &recptr->index[start] ;
1219 dstvec = &recptr->index[0] ;
1220 stgbase = (char *) recptr->index ;
1221 ndxcnt = end - start + 1 ;
1222
1223 for ( ndx=0 ; ndx<ndxcnt ; ndx++ )
1224 {
1225 dstvec[ndx].data = srcvec[ndx].data ;
1226 ndxstg = (char *) stgbase + srcvec[ndx].index_stg ;
1227 strcpy (cur_heap, ndxstg) ;
1228 dstvec[ndx].index_stg = (MrmOffset) (cur_heap - temp_heap) ;
1229 stgsiz = strlen(cur_heap) + 1 ;
1230 stgsiz = _FULLWORD(stgsiz);
1231 cur_heap += stgsiz ;
1232 heap_size += stgsiz ;
1233 }
1234
1235 /*
1236 * Compute offsets and sizes, and copy heap into record. Then adjust the
1237 * offset to allow for the free space.
1238 */
1239 hdrptr->index_count = ndxcnt ;
1240 heap_start = IDBIndexLeafFreeMax - heap_size ;
1241 hdrptr->heap_start = heap_start ;
1242 nfree = IDBIndexLeafFreeMax - heap_size - ndxcnt*IDBIndexLeafEntrySize ;
1243 hdrptr->free_bytes = nfree ;
1244
1245 UrmBCopy (temp_heap, &stgbase[heap_start], heap_size) ;
1246 for ( ndx=0 ; ndx<ndxcnt ; ndx++ )
1247 dstvec[ndx].index_stg += heap_start ;
1248
1249 XtFree (temp_heap) ;
1250
1251 }
1252
1253
1254 /*
1255 *++
1256 *
1257 * PROCEDURE DESCRIPTION:
1258 *
1259 * This routine collapses a node index record as part of splitting
1260 * a record. Collapsing the record truncates the record contents
1261 * by removing part of the index vector, re-organizing the string
1262 * heap to consume minimal space, resetting the heap parameters,
1263 * and resetting the index count.
1264 *
1265 * The record vector is preserved by moving entires start to end+1.
1266 * For both records being collapsed, these entries are the correct
1267 * ones to associate with the collapsed record.
1268 *
1269 * FORMAL PARAMETERS:
1270 *
1271 * recptr The node index record to collapse
1272 * start First entry in the index vector to be preserved
1273 * end Last entry in the index vector to be preserved
1274 *
1275 * IMPLICIT INPUTS:
1276 *
1277 * IMPLICIT OUTPUTS:
1278 *
1279 * FUNCTION VALUE:
1280 *
1281 * SIDE EFFECTS:
1282 *
1283 *--
1284 */
1285
1286 void
Idb__INX_CollapseNodeRecord(IDBIndexNodeRecordPtr recptr,MrmCount start,MrmCount end)1287 Idb__INX_CollapseNodeRecord (IDBIndexNodeRecordPtr recptr,
1288 MrmCount start,
1289 MrmCount end)
1290 {
1291
1292 /*
1293 * Local variables
1294 */
1295 IDBIndexNodeHdrPtr hdrptr ; /* record header */
1296 int ndx ; /* loop index */
1297 char *temp_heap ; /* temporary heap */
1298 char *cur_heap ; /* current heap pointer */
1299 MrmCount heap_size ; /* # bytes used in temp heap */
1300 IDBIndexNodeEntryPtr srcvec ; /* source index vector */
1301 IDBIndexNodeEntryPtr dstvec ; /* destination index vector */
1302 char *stgbase ; /* base address for string offsets */
1303 char *ndxstg ; /* current index string */
1304 MrmCount stgsiz ; /* # bytes for current string */
1305 MrmCount ndxcnt ; /* # entries in collapsed record */
1306 MrmCount nfree ; /* # free bytes in collapsed record */
1307 MrmOffset heap_start ; /* new heap start offset */
1308
1309
1310 /*
1311 * Allocate a temporary heap (big enough to hold data area). Copy each
1312 * string which must be preserved into the temporary heap. The heap
1313 * is allocated top-to-bottom, and the temporary offsets will be
1314 * made permanent when the temporary heap is copied into the record.
1315 *
1316 * Copy the surviving part of the index vector while saving the strings.
1317 * The new offset is set as part of this operation.
1318 */
1319 temp_heap = (char *) XtMalloc (IDBIndexNodeFreeMax) ;
1320 cur_heap = temp_heap ;
1321 heap_size = 0 ;
1322
1323 hdrptr = (IDBIndexNodeHdrPtr) &recptr->node_header ;
1324 srcvec = &recptr->index[start] ;
1325 dstvec = &recptr->index[0] ;
1326 stgbase = (char *) recptr->index ;
1327 ndxcnt = end - start + 1 ;
1328
1329 for ( ndx=0 ; ndx<ndxcnt ; ndx++ )
1330 {
1331 dstvec[ndx].data = srcvec[ndx].data ;
1332 dstvec[ndx].LT_record = srcvec[ndx].LT_record ;
1333 dstvec[ndx].GT_record = srcvec[ndx].GT_record ;
1334 ndxstg = (char *) stgbase + srcvec[ndx].index_stg ;
1335 strcpy (cur_heap, ndxstg) ;
1336 dstvec[ndx].index_stg = (MrmOffset) (cur_heap - temp_heap) ;
1337 stgsiz = strlen(cur_heap) + 1 ;
1338 stgsiz = _FULLWORD(stgsiz);
1339 cur_heap += stgsiz ;
1340 heap_size += stgsiz ;
1341 }
1342
1343 /*
1344 * Compute offsets and sizes, and copy heap into record. Then adjust the
1345 * offset to allow for the free space.
1346 */
1347 hdrptr->index_count = ndxcnt ;
1348 heap_start = IDBIndexNodeFreeMax - heap_size ;
1349 hdrptr->heap_start = heap_start ;
1350 nfree = IDBIndexNodeFreeMax - heap_size - ndxcnt*IDBIndexNodeEntrySize ;
1351 hdrptr->free_bytes = nfree ;
1352
1353 UrmBCopy (temp_heap, &stgbase[heap_start], heap_size) ;
1354 for ( ndx=0 ; ndx<ndxcnt ; ndx++ )
1355 dstvec[ndx].index_stg += heap_start ;
1356
1357 XtFree (temp_heap) ;
1358
1359 }
1360
1361
1362 /*
1363 *++
1364 *
1365 * PROCEDURE DESCRIPTION:
1366 *
1367 * This routine confirms that there is enough space in an index
1368 * node for a new entry. If there is not, it splits the entry
1369 * and tells the caller to retry.
1370 *
1371 * FORMAL PARAMETERS:
1372 *
1373 * file_id Open IDB file
1374 * buffer Buffer containing the node record to be checked.
1375 *
1376 * IMPLICIT INPUTS:
1377 *
1378 * IMPLICIT OUTPUTS:
1379 *
1380 * FUNCTION VALUE:
1381 *
1382 * MrmSUCCESS There is enough space
1383 * MrmINDEX_RETRY Node was split, caller must retry
1384 * MrmFAILURE Some other failure
1385 *
1386 * SIDE EFFECTS:
1387 *
1388 *--
1389 */
1390
1391 Cardinal
Idb__INX_ConfirmNodeSpace(IDBFile file_id,IDBRecordBufferPtr buffer)1392 Idb__INX_ConfirmNodeSpace (IDBFile file_id,
1393 IDBRecordBufferPtr buffer)
1394 {
1395
1396 /*
1397 * Local variables
1398 */
1399 Cardinal result ; /* function results */
1400 IDBIndexNodeRecordPtr recptr ; /* node record in buffer */
1401 IDBIndexNodeHdrPtr hdrptr ; /* record header */
1402
1403
1404 /*
1405 * Initialize pointers into the record
1406 */
1407 recptr = (IDBIndexNodeRecordPtr) buffer->IDB_record ;
1408 hdrptr = (IDBIndexNodeHdrPtr) &recptr->node_header ;
1409
1410 /*
1411 * Check the size. If there is enough, OK. Else split this record and
1412 * return a retry.
1413 */
1414 if ( hdrptr->free_bytes >= IDBIndexNodeEntryMax ) return MrmSUCCESS ;
1415
1416 result = Idb__INX_SplitNodeRecord (file_id, buffer) ;
1417 if ( result == MrmSUCCESS ) result = MrmINDEX_RETRY ;
1418
1419 return result ;
1420
1421 }
1422
1423
1424 /*
1425 *++
1426 *
1427 * PROCEDURE DESCRIPTION:
1428 *
1429 * This routine sets the parent pointer in a child record
1430 *
1431 * FORMAL PARAMETERS:
1432 *
1433 * file_id Open IDB file
1434 * parent_record Parent record number
1435 * child_record Child record number
1436 *
1437 * IMPLICIT INPUTS:
1438 *
1439 * IMPLICIT OUTPUTS:
1440 *
1441 * FUNCTION VALUE:
1442 *
1443 * MrmSUCCESS operation succeeded
1444 * MrmFAILURE some failure occurred
1445 *
1446 * SIDE EFFECTS:
1447 *
1448 *--
1449 */
1450
1451 Cardinal
Idb__INX_SetParent(IDBFile file_id,IDBRecordNumber parent_record,IDBRecordNumber child_record)1452 Idb__INX_SetParent (IDBFile file_id,
1453 IDBRecordNumber parent_record,
1454 IDBRecordNumber child_record)
1455 {
1456
1457 /*
1458 * Local variables
1459 */
1460 Cardinal result ; /* function results */
1461 IDBRecordBufferPtr buffer ; /* buffer for child record */
1462 IDBIndexLeafRecordPtr leafrec ; /* index leaf record */
1463 IDBIndexLeafHdrPtr leafhdr ; /* index leaf header */
1464 IDBIndexNodeRecordPtr noderec ; /* index node record */
1465 IDBIndexNodeHdrPtr nodehdr ; /* index node header */
1466
1467
1468 /*
1469 * Get the child record
1470 */
1471 result = Idb__BM_GetRecord (file_id, child_record, &buffer) ;
1472 if ( result != MrmSUCCESS ) return result ;
1473 if ( ! Idb__INX_ValidRecord(buffer) )
1474 return Urm__UT_Error ("Idb__INX_SetParent", _MrmMMsg_0010,
1475 file_id, NULL, MrmBAD_RECORD) ;
1476
1477 /*
1478 * Set up pointers and set parent based on record type
1479 */
1480 switch ( _IdbBufferRecordType (buffer) )
1481 {
1482 case IDBrtIndexLeaf:
1483 leafrec = (IDBIndexLeafRecordPtr) buffer->IDB_record ;
1484 leafhdr = (IDBIndexLeafHdrPtr) &leafrec->leaf_header ;
1485 if ( leafhdr->parent != parent_record )
1486 {
1487 leafhdr->parent = parent_record ;
1488 Idb__BM_MarkModified (buffer) ;
1489 }
1490 return MrmSUCCESS ;
1491 case IDBrtIndexNode:
1492 noderec = (IDBIndexNodeRecordPtr) buffer->IDB_record ;
1493 nodehdr = (IDBIndexNodeHdrPtr) &noderec->node_header ;
1494 if ( nodehdr->parent != parent_record )
1495 {
1496 nodehdr->parent = parent_record ;
1497 Idb__BM_MarkModified (buffer) ;
1498 }
1499 return MrmSUCCESS ;
1500 default:
1501 return MrmBAD_RECORD ;
1502 }
1503
1504 }
1505
1506
1507
1508 /*
1509 *++
1510 *
1511 * PROCEDURE DESCRIPTION:
1512 *
1513 * This routine guarantees that the children of a node record have
1514 * a correct parent pointer.
1515 *
1516 * FORMAL PARAMETERS:
1517 *
1518 * file_id Open IDB file
1519 * p_record Record number of parent record
1520 *
1521 * IMPLICIT INPUTS:
1522 *
1523 * IMPLICIT OUTPUTS:
1524 *
1525 * FUNCTION VALUE:
1526 *
1527 * SIDE EFFECTS:
1528 *
1529 * This routine uses MarkActivity to guarantee that the parent
1530 * record remains in memory.
1531 *
1532 *--
1533 */
1534
1535 Cardinal
Idb__INX_FixNodeChildren(IDBFile file_id,IDBRecordNumber p_record)1536 Idb__INX_FixNodeChildren (IDBFile file_id,
1537 IDBRecordNumber p_record)
1538 {
1539
1540 /*
1541 * Local variables
1542 */
1543 Cardinal result ; /* function results */
1544 IDBRecordBufferPtr buffer ; /* parent node buffer */
1545 IDBIndexNodeRecordPtr recptr ; /* parent node record in buffer */
1546 IDBIndexNodeHdrPtr hdrptr ; /* parent record header */
1547 int ndx ; /* loop index */
1548
1549
1550 /*
1551 * Get the parent record
1552 */
1553 result = Idb__BM_GetRecord (file_id, p_record, &buffer) ;
1554 if ( result != MrmSUCCESS ) return result ;
1555 if ( ! Idb__INX_ValidNode(buffer) )
1556 return Urm__UT_Error ("Idb__INX_FixNodeChildren", _MrmMMsg_0010,
1557 file_id, NULL, MrmBAD_RECORD) ;
1558
1559 /*
1560 * Bind pointers into the record, and set each child's parent pointer
1561 */
1562 recptr = (IDBIndexNodeRecordPtr) buffer->IDB_record ;
1563 hdrptr = (IDBIndexNodeHdrPtr) &recptr->node_header ;
1564
1565 for ( ndx=0 ; ndx<hdrptr->index_count ; ndx++ )
1566 {
1567 result = Idb__INX_SetParent (file_id, p_record,
1568 recptr->index[ndx].LT_record) ;
1569 if ( result != MrmSUCCESS ) return result ;
1570 result = Idb__INX_SetParent (file_id, p_record,
1571 recptr->index[ndx].GT_record) ;
1572 if ( result != MrmSUCCESS ) return result ;
1573 Idb__BM_MarkActivity (buffer) ;
1574 }
1575
1576 /*
1577 * Successfully modified
1578 */
1579 return MrmSUCCESS ;
1580
1581 }
1582
1583
1584