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: MrmIindex.c /main/13 1996/11/13 13:57:31 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 entering
45 * data entries accessed by index. These routines are read or common
46 * (used by both read and writing (MrmIindexw.c)).
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_ReturnItem - Return the data entry for an index
69 *
70 * Idb__INX_FindIndex - Search the index
71 *
72 * Idb__INX_SearchIndex - Search a record for an index
73 *
74 * Idb__INX_GetBTreeRecord - Read a record in the B-tree
75 *
76 * Idb__INX_FindResources - Search the index for resources
77 * matching the filter
78 *
79 */
80
81
82 /*
83 *
84 * DEFINE and MACRO DEFINITIONS
85 *
86 */
87
88 /*
89 * Macros which validate index records in buffers
90 */
91 #define Idb__INX_ValidLeaf(buffer) \
92 (_IdbBufferRecordType(buffer)==IDBrtIndexLeaf)
93 #define Idb__INX_ValidNode(buffer) \
94 (_IdbBufferRecordType(buffer)==IDBrtIndexNode)
95 #define Idb__INX_ValidRecord(buffer) \
96 (_IdbBufferRecordType(buffer)==IDBrtIndexLeaf || \
97 _IdbBufferRecordType(buffer)==IDBrtIndexNode)
98
99
100
101 /*
102 *++
103 *
104 * PROCEDURE DESCRIPTION:
105 *
106 * Idb__INX_ReturnItem locates a data entry in the file, and returns
107 * the data entry pointer (without reading the data record).
108 *
109 * FORMAL PARAMETERS:
110 *
111 * file_id Open IDB file in which to write entry
112 * index The entry's case-sensitive index
113 * data_entry To return data entry pointer for data
114 *
115 * IMPLICIT INPUTS:
116 *
117 * IMPLICIT OUTPUTS:
118 *
119 * FUNCTION VALUE:
120 *
121 * MrmSUCCESS operation succeeded
122 * MrmFAILURE some other failure
123 *
124 * SIDE EFFECTS:
125 *
126 *--
127 */
128
129 Cardinal
130 Idb__INX_ReturnItem (IDBFile file_id,
131 char *index,
132 IDBDataHandle *data_entry)
133 {
134
135 /*
136 * Local variables
137 */
138 Cardinal result ; /* function results */
139 IDBRecordBufferPtr bufptr ; /* buffer containing entry */
140 MrmCount entndx ; /* entry index */
141 IDBIndexLeafRecordPtr leafrec ; /* index leaf record */
142 IDBIndexNodeRecordPtr noderec ; /* index node record */
143
144 /*
145 * Attempt to find the index
146 */
147 result = Idb__INX_FindIndex (file_id, index, &bufptr, &entndx) ;
148 switch ( result )
149 {
150 case MrmINDEX_GT:
151 case MrmINDEX_LT:
152 return MrmNOT_FOUND ;
153 case MrmSUCCESS:
154 break ;
155 default:
156 return result ;
157 }
158
159 /*
160 * Point into the buffer, and retrieve the data pointer
161 */
162 switch ( _IdbBufferRecordType (bufptr) )
163 {
164 case IDBrtIndexLeaf:
165 leafrec = (IDBIndexLeafRecordPtr) bufptr->IDB_record ;
166 data_entry->rec_no = leafrec->index[entndx].data.internal_id.rec_no ;
167 data_entry->item_offs =
168 leafrec->index[entndx].data.internal_id.item_offs ;
169 return MrmSUCCESS ;
170 case IDBrtIndexNode:
171 noderec = (IDBIndexNodeRecordPtr) bufptr->IDB_record ;
172 data_entry->rec_no = noderec->index[entndx].data.internal_id.rec_no ;
173 data_entry->item_offs =
174 noderec->index[entndx].data.internal_id.item_offs ;
175 return MrmSUCCESS ;
176 default:
177 return Urm__UT_Error ("Idb__INX_ReturnItem", _MrmMMsg_0010,
178 file_id, NULL, MrmBAD_RECORD) ;
179 }
180
181 }
182
183
184
185 /*
186 *++
187 *
188 * PROCEDURE DESCRIPTION:
189 *
190 * Idb__INX_FindIndex finds the index record containing an index entry,
191 * and returns the buffer containing that record. It is used both as the
192 * low-level routine for locating an index for retrieving a data entry,
193 * and for locating the record in which a new index should be inserted.
194 * Thus the interpretation of the return code is:
195 *
196 * MrmSUCCESS found the index, the index record is in the buffer
197 * and the index_return locates the entry
198 * MrmINDEX_GT buffer contains the leaf index record which should
199 * MrmINDEX_LT contain the index, and index_return locates the entry
200 * in the buffer at which search terminated. The result
201 * value indicates how the given index orders against
202 * the entry in index_return.
203 *
204 * FORMAL PARAMETERS:
205 *
206 * file_id Open IDB file in which to find index
207 * index Case-sensitive index string
208 * buffer_return To return pointer to buffer containing index record
209 * index_return To return item's index in the records index vector
210 *
211 * IMPLICIT INPUTS:
212 *
213 * IMPLICIT OUTPUTS:
214 *
215 * FUNCTION VALUE:
216 *
217 * MrmSUCCESS operation succeeded
218 * MrmINDEX_GT index not found, but orders greater-than entry at
219 * index_return
220 * MrmINDEX_LT index not found, but orders less-than entry at
221 * index_return
222 * MrmFAILURE some other failure
223 *
224 * SIDE EFFECTS:
225 *
226 *--
227 */
228
229 Cardinal
Idb__INX_FindIndex(IDBFile file_id,char * index,IDBRecordBufferPtr * buffer_return,MrmCount * index_return)230 Idb__INX_FindIndex (IDBFile file_id,
231 char *index,
232 IDBRecordBufferPtr *buffer_return,
233 MrmCount *index_return)
234 {
235
236 /*
237 * Local variables
238 */
239 Cardinal result ; /* function results */
240
241 /*
242 * Initialize search at the root of the index, then continue searching
243 * until either the index is found or search terminates at some leaf record.
244 */
245 if ( !file_id->index_root ) return MrmFAILURE ;
246 result = Idb__BM_GetRecord (file_id, file_id->index_root, buffer_return) ;
247 if ( result != MrmSUCCESS ) return result ;
248 if ( ! Idb__INX_ValidRecord(*buffer_return) )
249 return Urm__UT_Error ("Idb__INX_FindIndex", _MrmMMsg_0010,
250 file_id, NULL, MrmBAD_RECORD) ;
251
252 do {
253 result =
254 Idb__INX_SearchIndex (file_id, index, *buffer_return, index_return) ;
255 if ( _IdbBufferRecordType(*buffer_return) == IDBrtIndexLeaf) return result ;
256 switch ( result )
257 {
258 case MrmINDEX_GT:
259 case MrmINDEX_LT:
260 result = Idb__INX_GetBtreeRecord
261 (file_id, buffer_return, *index_return, result) ;
262 if (result != MrmSUCCESS )
263 {
264 if (result == MrmNOT_FOUND)
265 result = MrmEOF;
266 return result ;
267 }
268 break ;
269 default:
270 return result ;
271 }
272 } while ( TRUE ) ;
273
274 }
275
276
277
278 /*
279 *++
280 *
281 * PROCEDURE DESCRIPTION:
282 *
283 * Idb__INX_SearchIndex searches a record for an index. The record
284 * may be either a leaf or a node record. If the index is found,
285 * index_return is its entry in the records index vector. If it is not
286 * found, then index_return locates the entry in the record at which
287 * search terminated.
288 *
289 * Thus the interpretation of the return code is:
290 *
291 * MrmSUCCESS found the index, and the index_return locates the entry
292 * MrmINDEX_GT index orders greater-than the entry at index_return
293 * MrmINDEX_LT index orders less-than the entry at index_return
294 *
295 * FORMAL PARAMETERS:
296 *
297 * file_id Open IDB file in which to find index
298 * index Case-sensitive index string
299 * buffer Buffer containing record to be searched
300 * index_return To return item's index in the records index vector
301 *
302 * IMPLICIT INPUTS:
303 *
304 * IMPLICIT OUTPUTS:
305 *
306 * FUNCTION VALUE:
307 *
308 * MrmSUCCESS operation succeeded
309 * MrmINDEX_GT index not found, but orders greater-than entry at
310 * index_return
311 * MrmINDEX_LT index not found, but orders less-than entry at
312 * index_return
313 * MrmFAILURE some other failure
314 *
315 * SIDE EFFECTS:
316 *
317 *--
318 */
319
320 Cardinal
Idb__INX_SearchIndex(IDBFile file_id,char * index,IDBRecordBufferPtr buffer,MrmCount * index_return)321 Idb__INX_SearchIndex (IDBFile file_id,
322 char *index,
323 IDBRecordBufferPtr buffer,
324 MrmCount *index_return)
325 {
326
327 /*
328 * Local variables
329 */
330 MrmType buftyp ; /* buffer type */
331 IDBIndexLeafRecordPtr leafrec =NULL ; /* index leaf record */
332 IDBIndexLeafHdrPtr leafhdr =NULL; /* index leaf header */
333 IDBIndexNodeRecordPtr noderec ; /* index node record */
334 IDBIndexNodeHdrPtr nodehdr ; /* index node header */
335 IDBIndexLeafEntryPtr leaf_ndxvec = NULL; /* index leaf entry vector */
336 IDBIndexNodeEntryPtr node_ndxvec = NULL; /* index node entry vector */
337 MrmCount ndxcnt ; /* number of entries in vector */
338 char *stgbase ; /* base adddress for string offsets */
339 int lowlim ; /* binary search lower limit index */
340 int uprlim ; /* binary search upper limit index */
341 char *ndxstg ; /* pointer to current index string */
342 int cmpres=0; /* strncmp result */
343
344
345 /*
346 * Set up search pointers based on the record type
347 */
348 buftyp = _IdbBufferRecordType (buffer) ;
349 switch ( buftyp )
350 {
351 case IDBrtIndexLeaf:
352 leafrec = (IDBIndexLeafRecordPtr) buffer->IDB_record ;
353 leafhdr = (IDBIndexLeafHdrPtr) &leafrec->leaf_header ;
354 leaf_ndxvec = leafrec->index ;
355 ndxcnt = leafhdr->index_count ;
356 stgbase = (char *) leafrec->index ;
357 break ;
358 case IDBrtIndexNode:
359 noderec = (IDBIndexNodeRecordPtr) buffer->IDB_record ;
360 nodehdr = (IDBIndexNodeHdrPtr) &noderec->node_header ;
361 node_ndxvec = noderec->index ;
362 ndxcnt = nodehdr->index_count ;
363 stgbase = (char *) noderec->index ;
364 break ;
365 default:
366 return Urm__UT_Error ("Idb__INX_SearchIndex", _MrmMMsg_0010,
367 file_id, NULL, MrmBAD_RECORD) ;
368 }
369
370 /*
371 * Search the index vector for the given index (binary search)
372 */
373 Idb__BM_MarkActivity (buffer) ;
374 for ( lowlim=0,uprlim=ndxcnt-1 ; lowlim<=uprlim ; )
375 {
376 *index_return = (lowlim+uprlim) / 2 ;
377 ndxstg = (buftyp==IDBrtIndexLeaf) ?
378 (char *) stgbase + leaf_ndxvec[*index_return].index_stg :
379 (char *) stgbase + node_ndxvec[*index_return].index_stg ;
380 cmpres = strncmp (index, ndxstg, IDBMaxIndexLength) ;
381 if ( cmpres == 0 ) return MrmSUCCESS ;
382 if ( cmpres < 0 ) uprlim = *index_return - 1 ;
383 if ( cmpres > 0 ) lowlim = *index_return + 1 ;
384 }
385
386 /*
387 * Not found, result determined by final ordering.
388 */
389 return (cmpres>0) ? MrmINDEX_GT : MrmINDEX_LT ;
390
391 }
392
393
394
395 /*
396 *++
397 *
398 * PROCEDURE DESCRIPTION:
399 *
400 * This routine reads in the next level index record in the B-tree
401 * associated with some entry in the current record (i.e. the one
402 * currently contained in the buffer). The buffer pointer is reset.
403 * The order variable indicates which record to read:
404 * MrmINDEX_GT - read the record ordering greater-than the entry
405 * MrmINDEX_LT - read the record ordering less-than the entry
406 *
407 * FORMAL PARAMETERS:
408 *
409 * file_id Open IDB file from which to read record
410 * buffer_return points to current buffer; reset to buffer read in
411 * entry_index entry in current buffer to use as reference
412 * order MrmINDEX_GT for GT ordered record, else MrmINDEX_LT
413 * for LT ordered record.
414 *
415 * IMPLICIT INPUTS:
416 *
417 * IMPLICIT OUTPUTS:
418 *
419 * FUNCTION VALUE:
420 *
421 * MrmSUCCESS operation succeeded
422 * MrmBAD_ORDER Order variable has illegal value
423 * MrmBAD_RECORD new record not an index record
424 * MrmFAILURE some other failure
425 *
426 * SIDE EFFECTS:
427 *
428 *--
429 */
430
431 Cardinal
Idb__INX_GetBtreeRecord(IDBFile file_id,IDBRecordBufferPtr * buffer_return,MrmCount entry_index,Cardinal order)432 Idb__INX_GetBtreeRecord ( IDBFile file_id,
433 IDBRecordBufferPtr *buffer_return,
434 MrmCount entry_index,
435 Cardinal order)
436 {
437
438 /*
439 * Local variables
440 */
441 Cardinal result ; /* function results */
442 IDBIndexNodeRecordPtr recptr ; /* node record in buffer */
443 IDBRecordNumber recno ; /* Record number to read in */
444
445 /*
446 * Set buffer pointers
447 */
448 recptr = (IDBIndexNodeRecordPtr) (*buffer_return)->IDB_record ;
449
450 /*
451 * Retrieve the record number
452 */
453 switch ( order )
454 {
455 case MrmINDEX_GT:
456 recno = recptr->index[entry_index].GT_record ;
457 break ;
458 case MrmINDEX_LT:
459 recno = recptr->index[entry_index].LT_record ;
460 break ;
461 default:
462 return Urm__UT_Error ("Idb__INX_GetBTreeRecord", _MrmMMsg_0010,
463 file_id, NULL, MrmBAD_ORDER) ;
464 }
465
466 /*
467 * Retrieve and sanity check the record
468 */
469 result = Idb__BM_GetRecord (file_id, recno, buffer_return) ;
470 if ( result != MrmSUCCESS ) return result ;
471 if ( ! Idb__INX_ValidRecord(*buffer_return) )
472 return Urm__UT_Error ("Idb__INX_GetBTreeRecord", _MrmMMsg_0010,
473 file_id, NULL, MrmBAD_RECORD) ;
474
475 /*
476 * Record successfully retrieved
477 */
478 return MrmSUCCESS ;
479
480 }
481
482
483
484 /*
485 *++
486 *
487 * PROCEDURE DESCRIPTION:
488 *
489 * This is the internal routine which searches the database for
490 * indexed resources matching a filter. It starts at the current node,
491 * then recurses down the BTree inspecting every entry. Each entry
492 * which matches the filter is appended to the index list.
493 *
494 * FORMAL PARAMETERS:
495 *
496 * file_id The IDB file id returned by XmIdbOpenFile
497 * recno The record to be searched. If a node entry,
498 * then each pointed-to record is also searched.
499 * group_filter if not null, entries found must match this group
500 * type_filter if not null, entries found must match this type
501 * index_list A pointer list in which to return index
502 * strings for matches. The required strings
503 * are automatically allocated.
504 *
505 * IMPLICIT INPUTS:
506 *
507 * IMPLICIT OUTPUTS:
508 *
509 * FUNCTION VALUE:
510 *
511 * MrmSUCCESS operation succeeded
512 * MrmFAILURE operation failed, no further reason
513 *
514 * SIDE EFFECTS:
515 *
516 *--
517 */
518
519 Cardinal
Idb__INX_FindResources(IDBFile file_id,IDBRecordNumber recno,MrmGroup group_filter,MrmType type_filter,URMPointerListPtr index_list)520 Idb__INX_FindResources (IDBFile file_id,
521 IDBRecordNumber recno,
522 MrmGroup group_filter,
523 MrmType type_filter,
524 URMPointerListPtr index_list)
525 {
526
527 /*
528 * Local variables
529 */
530 Cardinal result ; /* function results */
531 IDBRecordBufferPtr bufptr ; /* buffer containing entry */
532 int entndx ; /* entry loop index */
533 IDBIndexLeafRecordPtr leafrec ; /* index leaf record */
534 IDBIndexLeafHdrPtr leafhdr ; /* index leaf header */
535 IDBIndexNodeRecordPtr noderec ; /* index node record */
536 IDBIndexNodeHdrPtr nodehdr ; /* index node header */
537 IDBIndexLeafEntryPtr leaf_ndxvec ; /* index leaf entry vector */
538 IDBIndexNodeEntryPtr node_ndxvec ; /* index node entry vector */
539 MrmCount ndxcnt ; /* number of entries in vector */
540 char *stgbase ; /* base adddress for string offsets */
541
542
543
544 /*
545 * Read the record in, then bind pointers and process the record.
546 */
547 result = Idb__BM_GetRecord (file_id, recno, &bufptr) ;
548 if ( result != MrmSUCCESS ) return result ;
549
550 switch ( _IdbBufferRecordType (bufptr) )
551 {
552
553 /*
554 * Simply apply the filter to all entries in the leaf record
555 */
556 case IDBrtIndexLeaf:
557 leafrec = (IDBIndexLeafRecordPtr) bufptr->IDB_record ;
558 leafhdr = (IDBIndexLeafHdrPtr) &leafrec->leaf_header ;
559 leaf_ndxvec = leafrec->index ;
560 ndxcnt = leafhdr->index_count ;
561 stgbase = (char *) leafrec->index ;
562
563 for ( entndx=0 ; entndx<ndxcnt ; entndx++ )
564 {
565 IDBDataHandle entry_data;
566
567 entry_data.rec_no = leaf_ndxvec[entndx].data.internal_id.rec_no;
568 entry_data.item_offs =
569 leaf_ndxvec[entndx].data.internal_id.item_offs;
570
571 if ( Idb__DB_MatchFilter(file_id, entry_data, group_filter,
572 type_filter) )
573 UrmPlistAppendString (index_list,
574 stgbase+leaf_ndxvec[entndx].index_stg) ;
575 Idb__BM_MarkActivity (bufptr) ;
576 }
577 return MrmSUCCESS ;
578
579 /*
580 * Process the first LT record, then process each index followed by
581 * its GT record. This will produce a correctly ordered list. The
582 * record is read again, and all pointers bound, after each FindResources
583 * call in order to guarantee that buffer turning has not purged the
584 * current record from memory
585 */
586 case IDBrtIndexNode:
587 noderec = (IDBIndexNodeRecordPtr) bufptr->IDB_record ;
588 nodehdr = (IDBIndexNodeHdrPtr) &noderec->node_header ;
589 node_ndxvec = noderec->index ;
590 ndxcnt = nodehdr->index_count ;
591 stgbase = (char *) noderec->index ;
592 result = Idb__INX_FindResources
593 (file_id, node_ndxvec[0].LT_record,
594 group_filter, type_filter, index_list) ;
595 if ( result != MrmSUCCESS ) return result ;
596
597 for ( entndx=0 ; entndx<ndxcnt ; entndx++ )
598 {
599 IDBDataHandle entry_data;
600
601 entry_data.rec_no = node_ndxvec[entndx].data.internal_id.rec_no;
602 entry_data.item_offs =
603 node_ndxvec[entndx].data.internal_id.item_offs;
604
605 Idb__BM_GetRecord (file_id, recno, &bufptr) ;
606 noderec = (IDBIndexNodeRecordPtr) bufptr->IDB_record ;
607 nodehdr = (IDBIndexNodeHdrPtr) &noderec->node_header ;
608 node_ndxvec = noderec->index ;
609 stgbase = (char *) noderec->index ;
610 if ( Idb__DB_MatchFilter
611 (file_id, entry_data, group_filter, type_filter) )
612 UrmPlistAppendString (index_list,
613 stgbase+node_ndxvec[entndx].index_stg) ;
614 result = Idb__INX_FindResources
615 (file_id, node_ndxvec[entndx].GT_record,
616 group_filter, type_filter, index_list) ;
617 if ( result != MrmSUCCESS ) return result ;
618 }
619 return MrmSUCCESS ;
620
621 default:
622 return Urm__UT_Error ("Idb__INX_FindResources", _MrmMMsg_0010,
623 file_id, NULL, MrmBAD_RECORD) ;
624 }
625
626 }
627
628