1 /*
2 pblkf.c - key file library implementation
3
4 Copyright (C) 2002 - 2007 Peter Graf
5
6 This file is part of PBL - The Program Base Library.
7 PBL is free software.
8
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation; either
12 version 2.1 of the License, or (at your option) any later version.
13
14 This library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
18
19 You should have received a copy of the GNU Lesser General Public
20 License along with this library; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22
23 For more information on the Program Base Library or Peter Graf,
24 please see: http://www.mission-base.com/.
25
26 $Log: pblkf.c,v $
27 Revision 1.22 2010/05/30 20:06:45 peter
28 Removed warnings found by 'Microsoft Visual C++ 2010'.
29
30 Revision 1.21 2009/03/08 20:56:50 peter
31 port to gcc (Ubuntu 4.3.2-1ubuntu12) 4.3.2.
32 Exposing the hash set and tree set interfaces.
33
34 Revision 1.20 2009/02/03 16:40:14 peter
35 PBL vesion 1.04, optimizations,
36 MAC OS X port, port to Microsoft Visual C++ 2008 Express Edition,
37 exposing the array list and the linked list interface
38
39 Revision 1.4 2003/02/19 22:26:49 peter
40 made sure #defined values can be set by compiler switches
41
42 Revision 1.3 2002/11/01 13:56:24 peter
43 Truncation of the memory block list is now called
44 at every file close.
45
46 Revision 1.2 2002/11/01 13:27:30 peter
47 The block reference hash table is deleted when the
48 last block is deleted from the table, i.e. when the
49 last file is closed
50
51 Revision 1.1 2002/09/12 20:47:07 peter
52 Initial revision
53
54 */
55
56 /*
57 * make sure "strings <exe> | grep Id | sort -u" shows the source file versions
58 */
59 char * pblkf_c_id = "$Id: pblkf.c,v 1.22 2010/05/30 20:06:45 peter Exp $";
60
61 #ifndef _WIN32
62
63 #include <unistd.h>
64
65 #endif
66
67 #include <stdio.h>
68 #include <stdlib.h>
69 #include <errno.h>
70
71 #include <sys/types.h>
72 #include <sys/stat.h>
73
74 #include <fcntl.h>
75 #include <memory.h>
76 #include <string.h>
77
78
79 #include "pbl.h" /* program base library */
80
81 /******************************************************************************/
82 /* #defines */
83 /******************************************************************************/
84
85 #ifndef PBL_KF_TEST_DEFINES
86
87 #ifndef PBLDATASIZE /* value might be set by compiler switch */
88 #define PBLDATASIZE 4096 /* size of entire block data */
89 #endif
90
91 #ifndef PBLBLOCKSPERFILE /* value might be set by compiler switch */
92 #define PBLBLOCKSPERFILE 2048 /* default number of cache blocks per file */
93 #endif
94
95 #ifndef PBLFILEBLOCKS /* value might be set by compiler switch */
96 #define PBLFILEBLOCKS 0xffff /* number of blocks per big file on disk */
97 #endif
98
99 #ifndef PBL_NFILES /* value might be set by compiler switch */
100 #define PBL_NFILES 256 /* maximum number of open key files */
101 #endif
102
103 #else /* PBL_TEST_DEFINES */
104
105 #define PBLDATASIZE 64 /* size of entire block data */
106 #define PBLBLOCKSPERFILE 10 /* default number of blocks in our cache */
107 #define PBLNEXPANDED 5 /* default number of expanded blocks */
108 #define PBLFILEBLOCKS 3 /* number of blocks per file */
109
110 #undef PBLKEYLENGTH
111 #define PBLKEYLENGTH 8 /* maximum length of a key */
112
113 #undef PBLDATALENGTH
114 #define PBLDATALENGTH 16 /* maximum length of data that is stored */
115 /* with an item on the level 0 block */
116 /* data that is longer is stored on data */
117 /* blocks */
118 #ifndef PBL_NFILES
119 #define PBL_NFILES 256 /* maximum number of open key files */
120 #endif
121
122 #endif /* PBL_TEST_DEFINES */
123
124 #define PBLHEADERSIZE 13 /* offset of first free byte on a new block */
125
126 #define PBLDATABLOCKMAXFREE ( PBLDATASIZE - PBLHEADERSIZE )
127 /* maximum number of free bytes on a data */
128 /* block */
129
130 #define PBLMAGIC "1.00 Peter's B Tree"
131 /* during creation this string is written */
132 /* to the files */
133
134 /******************************************************************************/
135 /* #macros */
136 /******************************************************************************/
137
138 /*
139 * macro to determine free space on an index block
140 */
141 #define PBLINDEXBLOCKNFREE( B ) ((PBLDATASIZE - B->free) - (2 * B->nentries))
142
143 /*
144 * macro to determine free space on a data block
145 */
146 #define PBLDATABLOCKNFREE( B ) ( PBLDATASIZE - B->free )
147
148 /*
149 * macros for getting pointers or buffer offsets from the index
150 */
151 #define PBLINDEXTOPTR( B, I ) ( B->data\
152 + ( PBLDATASIZE - 2 * ( 1 + ( I ) )))
153
154 #define PBLINDEXTOBUFOFF( B, I ) pbl_BufToShort( PBLINDEXTOPTR( B, I ))
155
156 #define PBL_MINIMAL_ITEM_SIZE 5
157
158 #define PBL_CACHED_ITEMS_PER_BLOCK ((( PBLDATASIZE - PBLHEADERSIZE ) / PBL_MINIMAL_ITEM_SIZE) + 1 )
159
160 /******************************************************************************/
161 /* typedefs */
162 /******************************************************************************/
163
164 /*
165 * PBL key file descriptor
166 */
167 typedef struct PBLKFILE_s
168 {
169 char * magic; /* magic string */
170 int bf; /* file handle from bigfile handling */
171 int update; /* flag: file open for update */
172
173 long blockno; /* of block current record is on */
174 int index; /* of current record on this block */
175
176 long saveblockno; /* block number of saved position */
177 int saveindex; /* item index of saved position */
178
179 void * filesettag; /* file set tag attached to file */
180
181 int transactions; /* number of transactions active for file */
182 int rollback; /* next commit should lead to a rollback */
183
184 void * writeableListHead; /* head and tail of writeable blocks */
185 void * writeableListTail;
186
187 /* a user defined key compare function */
188 int (*keycompare)( void * left, size_t llen, void * right, size_t rlen );
189
190 } PBLKFILE_t;
191
192 /*
193 * items are the things we store in the data array of the index blocks,
194 * while a block is in memory the items of the block are cached for
195 * fast data access
196 */
197 typedef struct PBL_CACHED_ITEM_s
198 {
199 unsigned char * key; /* pointer to the key */
200
201 long datalen; /* length of the data */
202
203 long datablock; /* number of block the data is on */
204 long dataoffset; /* offset of data on block */
205 unsigned char keycommon; /* number of initial bytes this item has in */
206 /* common with its predecessor on tbe block */
207
208 unsigned char keylen; /* length of the key */
209
210 } PBL_CACHED_ITEM_t;
211
212 /*
213 * items are the things we store in the data array of the index blocks
214 */
215 typedef struct PBLITEM_s
216 {
217 unsigned int level; /* level where item is inserted */
218
219 int keycommon; /* number of initial bytes this item has in */
220 /* common with its predecessor on tbe block */
221
222 int keylen; /* length of the key */
223 unsigned char * key; /* pointer to the key */
224
225 long datalen; /* length of the data */
226 unsigned char * data; /* the data of the item */
227
228 long datablock; /* number of block the data is on */
229 long dataoffset; /* offset of data on block */
230
231 struct PBLITEM_s * next; /* we save items in a list */
232 struct PBLITEM_s * prev; /* during an insert */
233
234 } PBLITEM_t;
235
236 /*
237 * memory blocks that have expanded keys are stored in an extra list
238 */
239 typedef struct PBLBLOCKLINK_s
240 {
241 struct PBLBLOCKLINK_s * next;
242 struct PBLBLOCKLINK_s * prev;
243
244 } PBLBLOCKLINK_t;
245
246 /*
247 * a file block in memory has this format
248 */
249 typedef struct PBLBLOCK_s
250 {
251 PBLBLOCKLINK_t blocklink; /* for linking blocks in a list */
252
253 unsigned int level; /* of block */
254
255 long blockno; /* block number in file */
256 int bf; /* big file handle block belongs to */
257 void * filesettag; /* file set tag attached */
258
259 unsigned char data[ PBLDATASIZE ]; /* the real data */
260
261 long nblock; /* next block of same level */
262 long pblock; /* previous block of same level */
263 unsigned int nentries; /* number of entries */
264 int free; /* offset of first free byte */
265
266 long parentblock; /* number of parent block */
267 int parentindex; /* index on parentblock */
268
269 int writeable; /* block can be written to */
270 int dirty; /* has the block been written to ? */
271
272 unsigned int maxItemCacheIndex; /* maximum index of cached item */
273 /* pointers to the cached items */
274 PBL_CACHED_ITEM_t * cachedItems[ PBL_CACHED_ITEMS_PER_BLOCK ];
275
276 struct PBLBLOCK_s * next; /* we keep the blocks we have */
277 struct PBLBLOCK_s * prev; /* in memory in a LRU chain */
278
279 } PBLBLOCK_t;
280
281 /*
282 * all file handles of all open filesystem files of
283 * all bigfiles are stored in a list
284 */
285 typedef struct PBLBIGFILEHANDLE_s
286 {
287 int bf; /* bigfile handle of file */
288 int n; /* bigfile index of file */
289
290 int fh; /* filesystem handle */
291 int mode; /* open mode */
292
293 struct PBLBIGFILEHANDLE_s * next;
294 struct PBLBIGFILEHANDLE_s * prev;
295
296 } PBLBIGFILEHANDLE_t;
297
298 /*
299 * a bigfile in memory
300 */
301 typedef struct PBLBIGFILE_s
302 {
303 char * name; /* name of first filesystem file */
304
305 int mode; /* open mode */
306 long blocksperfile; /* blocks per filesystem file */
307 long blocksize; /* size of one block */
308 long nextblockno; /* block number of next free block */
309
310 } PBLBIGFILE_t;
311
312 /*
313 * references to blocks are stored in a hashtable
314 */
315 typedef struct PBLBLOCKREF_s
316 {
317 long blockno; /* block number in file */
318 long bf; /* big file handle block belongs to */
319
320 PBLBLOCK_t * block; /* address of block */
321
322 } PBLBLOCKREF_t;
323
324 typedef struct PBLBLOCKHASHKEY_s
325 {
326 long blockno; /* block number in file */
327 long bf; /* big file handle block belongs to */
328
329 } PBLBLOCKHASHKEY_t;
330
331 /******************************************************************************/
332 /* globals */
333 /******************************************************************************/
334
335 long pblnreads = 0;
336 long pblnwrites = 0;
337
338 static char * magic = PBLMAGIC;
339
340 /*
341 * pool of open bigfiles
342 */
343 static PBLBIGFILE_t pbf_pool[ PBL_NFILES ];
344
345 /*
346 * headers for lists
347 */
348 static PBLBIGFILEHANDLE_t * pbf_ft_head;
349 static PBLBIGFILEHANDLE_t * pbf_ft_tail;
350 static PBLBLOCK_t * blockListHead;
351 static PBLBLOCK_t * blockListTail;
352 static PBLITEM_t * itemListHead;
353 static PBLITEM_t * itemListTail;
354
355 /*
356 * counters
357 */
358 static int pblnblocks;
359 static int pblblocksperfile = PBLBLOCKSPERFILE;
360 static long pblnfiles;
361
362 /*
363 * block reference hash table
364 */
365 static pblHashTable_t * pblblockhash;
366
367 /******************************************************************************/
368 /* declarations */
369 /******************************************************************************/
370
371
372 /******************************************************************************/
373 /* functions */
374 /******************************************************************************/
375 /*
376 * verify consistency of parameters
377 */
pblParamsCheck(unsigned char * key,unsigned int keylen,unsigned char * data,long datalen)378 static int pblParamsCheck(
379 unsigned char * key,
380 unsigned int keylen,
381 unsigned char * data,
382 long datalen
383 )
384 {
385 if(( keylen < 1 ) || ( keylen > 255 ))
386 {
387 pbl_errno = PBL_ERROR_PARAM_KEYLEN;
388 return( -1 );
389 }
390
391 if( datalen < 0 )
392 {
393 pbl_errno = PBL_ERROR_PARAM_DATALEN;
394 return( -1 );
395 }
396
397 if( !key )
398 {
399 pbl_errno = PBL_ERROR_PARAM_KEY;
400 return( -1 );
401 }
402
403 if( datalen && ( !data ))
404 {
405 pbl_errno = PBL_ERROR_PARAM_DATA;
406 return( -1 );
407 }
408
409 return( 0 );
410 }
411
412 /*
413 * functions on the block reference hash table
414 */
415 /*
416 ------------------------------------------------------------------------------
417 FUNCTION: pblBlockHashInsert
418
419 DESCRIPTION: inserts a new block reference into the hash table
420
421 RETURNS: int rc == 0: a new reference was inserted
422 int rc == 1: the reference was already there, it was udpated
423 int rc < 0: some error occured, see pbl_errno
424 PBL_ERROR_OUT_OF_MEMORY: malloc failed, out of memory
425 ------------------------------------------------------------------------------
426 */
pblBlockHashInsert(long blockno,long bf,PBLBLOCK_t * block)427 static int pblBlockHashInsert( long blockno, long bf, PBLBLOCK_t * block )
428 {
429 PBLBLOCKHASHKEY_t key;
430 PBLBLOCKREF_t * ref;
431 int rc;
432
433 memset( &key, 0, sizeof( key ));
434 key.blockno = blockno;
435 key.bf = bf;
436
437 if( !pblblockhash )
438 {
439 pblblockhash = pblHtCreate();
440 if( !pblblockhash )
441 {
442 return( -1 );
443 }
444 }
445
446 /*
447 * see whether we have the reference already
448 */
449 ref = (PBLBLOCKREF_t *)pblHtLookup( pblblockhash, &key, sizeof( key ));
450 if( ref )
451 {
452 /*
453 * the reference is already there, update the block pointer
454 */
455 ref->block = block;
456 return( 1 );
457 }
458
459 if( pbl_errno == PBL_ERROR_NOT_FOUND )
460 {
461 pbl_errno = 0;
462 }
463
464 /*
465 * allocate memory for new reference
466 */
467 ref = pbl_malloc0( "pblBlockHashInsert BLOCKREF", sizeof( PBLBLOCKREF_t ));
468 if( !ref )
469 {
470 return( -1 );
471 }
472
473 /*
474 * insert to the hash table
475 */
476 rc = pblHtInsert( pblblockhash, &key, sizeof( key ), ref );
477 if( !rc )
478 {
479 ref->block = block;
480 ref->blockno = blockno;
481 ref->bf = bf;
482 }
483 else
484 {
485 PBL_FREE( ref );
486 return( -1 );
487 }
488
489 return( 0 );
490 }
491
492 /*
493 ------------------------------------------------------------------------------
494 FUNCTION: pblBlockHashRemove
495
496 DESCRIPTION: Remove a block reference from the hash table
497
498 RETURNS: int rc == 0: call went ok;
499 otherwise: block not found in hash table
500 ------------------------------------------------------------------------------
501 */
pblBlockHashRemove(long blockno,long bf)502 static int pblBlockHashRemove( long blockno, long bf )
503 {
504 PBLBLOCKHASHKEY_t key;
505 PBLBLOCKREF_t * ref;
506 int rc;
507
508 memset( &key, 0, sizeof( key ));
509 key.blockno = blockno;
510 key.bf = bf;
511
512 /*
513 * if there is no hash table yet, the reference is not found
514 */
515 if( !pblblockhash )
516 {
517 return( 1 );
518 }
519
520 /*
521 * see whether we have the reference
522 */
523 ref = pblHtLookup( pblblockhash, &key, sizeof( key ));
524 if( !ref )
525 {
526 if( pbl_errno == PBL_ERROR_NOT_FOUND )
527 {
528 pbl_errno = 0;
529 }
530
531 return( 1 );
532 }
533
534 /*
535 * remove the reference from the hash table
536 */
537 rc = pblHtRemove( pblblockhash, &key, sizeof( key ));
538 if( rc )
539 {
540 return( 1 );
541 }
542
543 PBL_FREE( ref );
544
545 /*
546 * attempt to remove the hashtable
547 */
548 rc = pblHtDelete( pblblockhash );
549 if( !rc )
550 {
551 /*
552 * the hash table was empty and is deleted now
553 */
554 pblblockhash = 0;
555 }
556 else
557 {
558 /*
559 * the hash table was not deleted because it is not
560 * empty, clear the error
561 */
562 pbl_errno = 0;
563 }
564
565 return( 0 );
566 }
567
568 /*
569 ------------------------------------------------------------------------------
570 FUNCTION: pblBlockHashFind
571
572 DESCRIPTION: Find a block reference in the hash table
573
574 RETURNS: PBLBLOCK_t * retptr == 0: block not found
575 otherwise: pointer to block in memory
576 ------------------------------------------------------------------------------
577 */
pblBlockHashFind(long blockno,long bf)578 static PBLBLOCK_t * pblBlockHashFind( long blockno, long bf )
579 {
580 PBLBLOCKHASHKEY_t key;
581 PBLBLOCKREF_t * ref;
582
583 memset( &key, 0, sizeof( key ));
584 key.blockno = blockno;
585 key.bf = bf;
586
587 /*
588 * if there is no hash table yet, the reference is not found
589 */
590 if( !pblblockhash )
591 {
592 return( 0 );
593 }
594
595 /*
596 * see whether we have the reference
597 */
598 ref = pblHtLookup( pblblockhash, &key, sizeof( key ));
599 if( !ref )
600 {
601 if( pbl_errno == PBL_ERROR_NOT_FOUND )
602 {
603 pbl_errno = 0;
604 }
605
606 return( 0 );
607 }
608
609 return( ref->block );
610 }
611
612 /*
613 * BIGFILE functions
614 */
615 /*
616 * find a filehandle of a filesystem file
617 */
pbf_fh_find(int bf,int n)618 static PBLBIGFILEHANDLE_t * pbf_fh_find( int bf, int n )
619 {
620 PBLBIGFILEHANDLE_t * entry;
621
622 /*
623 * file system handles are kept in an LRU list
624 */
625 for( entry = pbf_ft_head; entry; entry = entry->next )
626 {
627 if( bf == entry->bf && n == entry->n )
628 {
629 if( entry != pbf_ft_head )
630 {
631 PBL_LIST_UNLINK( pbf_ft_head, pbf_ft_tail, entry, next, prev );
632 PBL_LIST_PUSH( pbf_ft_head, pbf_ft_tail, entry, next, prev );
633 }
634 return( entry );
635 }
636 }
637
638 return( 0 );
639 }
640
641 /*
642 * close files with the filesystem
643 */
pbf_fh_close(int bf,int n)644 static void pbf_fh_close( int bf, int n )
645 {
646 PBLBIGFILEHANDLE_t * entry;
647 PBLBIGFILEHANDLE_t * tmp;
648
649 if( n < 0 )
650 {
651 /*
652 * close all file handles of this big file
653 */
654 for( entry = pbf_ft_head; entry; )
655 {
656 tmp = entry;
657 entry = entry->next;
658
659 if( bf == tmp->bf )
660 {
661 close( tmp->fh );
662 PBL_LIST_UNLINK( pbf_ft_head, pbf_ft_tail, tmp, next, prev );
663 PBL_FREE( tmp );
664 }
665 }
666
667 return;
668 }
669
670 /*
671 * close a particular file handle
672 */
673 entry = pbf_fh_find( bf, n );
674 if( !entry )
675 {
676 return;
677 }
678
679 close( entry->fh );
680
681 PBL_LIST_UNLINK( pbf_ft_head, pbf_ft_tail, entry, next, prev );
682 PBL_FREE( entry );
683 }
684
685 /*
686 * create the bigfile path of a file
687 * bigfiles are stored in multiple filesystem files
688 * if the first one is called "file.ext",
689 * the others have names like "file_0002.ext" etc.
690 */
pbf_fh_path(char * name,long n)691 static char * pbf_fh_path( char * name, long n )
692 {
693 char * path;
694 char * dotptr;
695
696 if( n < 1 )
697 {
698 /*
699 * the name of the first file does not change
700 */
701 path = pbl_strdup( "pbf_fh_path first path", name );
702 if( !path )
703 {
704 pbl_errno = PBL_ERROR_OUT_OF_MEMORY;
705 return( 0 );
706 }
707 return( path );
708 }
709
710 path = (char *)pbl_malloc( "pbf_fh_path path", 6 + strlen( name ));
711 if( !path )
712 {
713 return( 0 );
714 }
715
716 /*
717 * see if there is a ".ext" after the last slash
718 */
719 dotptr = strrchr( name, '.' );
720 if( dotptr )
721 {
722 if( strchr( dotptr, '/' ) || strchr( dotptr, '\\' ))
723 {
724 dotptr = 0;
725 }
726 }
727
728 /*
729 * build the filename, start counting at one
730 */
731 n++;
732 if( dotptr )
733 {
734 memcpy( path, name, dotptr - name );
735 snprintf( path + ( dotptr - name ), 6, "_%04lx", 0xffff & n );
736 strcat( path, dotptr );
737 }
738 else
739 {
740 strcpy( path, name );
741 snprintf( path + strlen( path ), 6, "_%04lx", 0xffff & n );
742 }
743
744 return( path );
745 }
746
747 /*
748 * open a file with the file system
749 */
pbf_fh_open(char * name,int mode,int bf,int n)750 static int pbf_fh_open( char * name, int mode, int bf, int n )
751 {
752 PBLBIGFILEHANDLE_t * entry;
753 int fh = -1;
754 int i;
755 char * path;
756
757 /*
758 * look in LRU list of open filesystem files
759 */
760 entry = pbf_fh_find( bf, n );
761 if( entry )
762 {
763 if( entry->mode != mode )
764 {
765 /*
766 * the file was found, but the open mode is wrong, close the file
767 */
768 pbf_fh_close( bf, n );
769 entry = 0;
770 }
771 else
772 {
773 /*
774 * the file is open in the right mode, use the file handle
775 */
776 return( entry->fh );
777 }
778 }
779
780 /*
781 * open the file
782 */
783 path = pbf_fh_path( name, n );
784 if( !path )
785 {
786 return( -1 );
787 }
788
789 for( i = 0; i < 3; i++ )
790 {
791 fh = open( path, mode, S_IREAD | S_IWRITE );
792 if( -1 == fh && pbf_ft_tail )
793 {
794 /*
795 * maybe the process or the system ran out of filehandles
796 * close one file and try again
797 */
798 pbf_fh_close( pbf_ft_tail->bf, pbf_ft_tail->n );
799 continue;
800 }
801
802 break;
803 }
804 PBL_FREE( path );
805
806 if( -1 == fh )
807 {
808 pbl_errno = PBL_ERROR_OPEN;
809 return( -1 );
810 }
811
812 /*
813 * create and link the file handle list entry
814 */
815 entry = (PBLBIGFILEHANDLE_t *)pbl_malloc0( "pbf_fh_open *entry", sizeof( *entry ));
816 if( !entry )
817 {
818 close( fh );
819 return( 0 );
820 }
821
822 entry->fh = fh;
823 entry->mode = mode;
824 entry->bf = bf;
825 entry->n = n;
826
827 PBL_LIST_PUSH( pbf_ft_head, pbf_ft_tail, entry, next, prev );
828
829 return( entry->fh );
830 }
831
832 /*
833 * close a bigfile
834 */
pbf_close(int bf)835 static int pbf_close( int bf )
836 {
837 if( bf < 0 || bf >= PBL_NFILES )
838 {
839 return( -1 );
840 }
841
842 /*
843 * close all filesystem files
844 */
845 pbf_fh_close( bf, -1 );
846
847 PBL_FREE( pbf_pool[ bf ].name );
848 pbf_pool[ bf ].name = 0;
849
850 return( 0 );
851 }
852
853 /*
854 * open a bigfile
855 */
pbf_open(char * name,int update,long blocksperfile,long blocksize)856 static int pbf_open(
857 char * name,
858 int update,
859 long blocksperfile,
860 long blocksize
861 )
862 {
863 int fh = -1;
864 int mode;
865 int i;
866 char * path;
867
868 path = pbf_fh_path( name, 0 );
869 if( !path )
870 {
871 return( -1 );
872 }
873
874 if( update )
875 {
876 mode = O_CREAT | O_BINARY | O_RDWR;
877 }
878 else
879 {
880 mode = O_BINARY | O_RDONLY;
881 }
882
883 /*
884 * find a slot in the big file pool that is free
885 */
886 for( i = 0; i < PBL_NFILES; i++ )
887 {
888 if( pbf_pool[ i ].name )
889 {
890 continue;
891 }
892
893 /*
894 * reserve the slot
895 */
896 pbf_pool[ i ].mode = mode;
897 pbf_pool[ i ].nextblockno = -1;
898 pbf_pool[ i ].blocksperfile = blocksperfile;
899 pbf_pool[ i ].blocksize = blocksize;
900
901 /*
902 * open the first filesystem file
903 */
904 fh = pbf_fh_open( path, mode, i, 0 );
905 if( -1 == fh )
906 {
907 PBL_FREE( path );
908 pbl_errno = PBL_ERROR_OPEN;
909 return( -1 );
910 }
911
912 pbf_pool[ i ].name = path;
913 return( i );
914 }
915
916 PBL_FREE( path );
917 pbl_errno = PBL_ERROR_OPEN;
918 return( -1 );
919 }
920
921 /*
922 * file io for a bigfile
923 */
pbf_blockio(int bf,int blockwrite,long blockno,unsigned char * buffer)924 static int pbf_blockio(
925 int bf,
926 int blockwrite,
927 long blockno,
928 unsigned char * buffer
929 )
930 {
931 long rc = -1;
932 long n;
933 int fh;
934 int i;
935 int j;
936 long offset;
937
938 if( bf < 0 || bf >= PBL_NFILES || !pbf_pool[ bf ].name )
939 {
940 pbl_errno = PBL_ERROR_BAD_FILE;
941 return( -1 );
942 }
943
944 /*
945 * make sure the n'th filesystem file is open
946 */
947 n = blockno / pbf_pool[ bf ].blocksperfile;
948
949 fh = pbf_fh_open( pbf_pool[ bf ].name, pbf_pool[ bf ].mode, bf, n );
950 if( -1 == fh )
951 {
952 pbl_errno = PBL_ERROR_READ;
953 return( -1 );
954 }
955
956 blockno %= pbf_pool[ bf ].blocksperfile;
957 offset = blockno * pbf_pool[ bf ].blocksize;
958
959 if( blockwrite )
960 {
961 /*
962 * try the write more than once if needed
963 */
964 for( i = 0; i < 3; i++ )
965 {
966 /*
967 * try the seek more than once if needed
968 */
969 for( j = 0; j < 3; j++ )
970 {
971 rc = lseek( fh, offset, SEEK_SET );
972 if( offset != rc )
973 {
974 continue;
975 }
976 break;
977 }
978 if( offset != rc )
979 {
980 pbl_errno = PBL_ERROR_SEEK;
981 return( -1 );
982 }
983
984 rc = write( fh, buffer, (unsigned int) pbf_pool[ bf ].blocksize );
985 if( rc != pbf_pool[ bf ].blocksize )
986 {
987 if( errno == EINTR )
988 {
989 continue;
990 }
991 pbl_errno = PBL_ERROR_WRITE;
992 return( -1 );
993 }
994 break;
995 }
996 if( i >= 3 )
997 {
998 pbl_errno = PBL_ERROR_WRITE;
999 return( -1 );
1000 }
1001
1002 pblnwrites++;
1003 }
1004 else
1005 {
1006 /*
1007 * try the read more than once if needed
1008 */
1009 for( i = 0; i < 3; i++ )
1010 {
1011 /*
1012 * try the seek more than once if needed
1013 */
1014 for( j = 0; j < 3; j++ )
1015 {
1016 rc = lseek( fh, offset, SEEK_SET );
1017 if( offset != rc )
1018 {
1019 continue;
1020 }
1021 break;
1022 }
1023 if( offset != rc )
1024 {
1025 pbl_errno = PBL_ERROR_SEEK;
1026 return( -1 );
1027 }
1028
1029 rc = read( fh, buffer, (unsigned int) pbf_pool[ bf ].blocksize );
1030 if( rc < 0 )
1031 {
1032 if( errno == EINTR )
1033 {
1034 continue;
1035 }
1036 pbl_errno = PBL_ERROR_READ;
1037 return( -1 );
1038 }
1039 pblnreads++;
1040
1041 if( rc != pbf_pool[ bf ].blocksize )
1042 {
1043 if( errno == EINTR )
1044 {
1045 continue;
1046 }
1047 pbl_errno = PBL_ERROR_BAD_FILE;
1048 return( -1 );
1049 }
1050 break;
1051 }
1052 if( i >= 3 )
1053 {
1054 pbl_errno = PBL_ERROR_READ;
1055 return( -1 );
1056 }
1057 }
1058
1059 return( 0 );
1060 }
1061
1062 /*
1063 * read a block from a bigfile
1064 */
pbf_blockread(int bf,long blockno,unsigned char * buffer)1065 static int pbf_blockread( int bf, long blockno, unsigned char * buffer )
1066 {
1067 int rc;
1068
1069 rc = pbf_blockio( bf, 0, blockno, buffer );
1070
1071 return( rc );
1072 }
1073
1074 /*
1075 * write a block to a bigfile
1076 */
pbf_blockwrite(int bf,long blockno,unsigned char * buffer)1077 static int pbf_blockwrite( int bf, long blockno, unsigned char * buffer )
1078 {
1079 int rc;
1080
1081 rc = pbf_blockio( bf, 1, blockno, buffer );
1082
1083 return( rc );
1084 }
1085
1086 /*
1087 * append a block to a bigfile
1088 */
pbf_blockappend(int bf,unsigned char * buffer)1089 static long pbf_blockappend( int bf, unsigned char * buffer )
1090 {
1091 int fh;
1092 long offset;
1093 int i;
1094 int j;
1095 long rc = -1;
1096 unsigned char c;
1097
1098 if( bf < 0 || bf >= PBL_NFILES || !pbf_pool[ bf ].name )
1099 {
1100 pbl_errno = PBL_ERROR_BAD_FILE;
1101 return( -1 );
1102 }
1103
1104 if( pbf_pool[ bf ].nextblockno == 0x3fff )
1105 {
1106 rc = -1;
1107 }
1108
1109 /*
1110 * if we don't know the next free block of the file yet
1111 */
1112 if( pbf_pool[ bf ].nextblockno < 0 )
1113 {
1114 /*
1115 * find the next free block of a bigfile
1116 */
1117 for( i = 0; 1; i++ )
1118 {
1119 /*
1120 * create and open next filesytem file used for the bigfile
1121 */
1122 fh = pbf_fh_open( pbf_pool[ bf ].name, pbf_pool[ bf ].mode, bf, i );
1123 if( -1 == fh )
1124 {
1125 pbl_errno = PBL_ERROR_WRITE;
1126 return( -1 );
1127 }
1128
1129 /*
1130 * reopen the filesystem file read only
1131 */
1132 fh = pbf_fh_open( pbf_pool[ bf ].name, O_BINARY | O_RDONLY, bf, i );
1133 if( -1 == fh )
1134 {
1135 pbl_errno = PBL_ERROR_WRITE;
1136 return( -1 );
1137 }
1138
1139 /*
1140 * seek to the end of the file
1141 */
1142 offset = pbf_pool[ bf ].blocksperfile * pbf_pool[ bf ].blocksize -1;
1143
1144 for( j = 0; j < 3; j++ )
1145 {
1146 rc = lseek( fh, offset, SEEK_SET );
1147 if( offset != rc )
1148 {
1149 if( errno == EINTR )
1150 {
1151 continue;
1152 }
1153 rc = -1;
1154 break;
1155 }
1156
1157 /*
1158 * check whether the block exist, by reading its last byte
1159 */
1160 rc = read( fh, &c, 1 );
1161 if( rc < 1 )
1162 {
1163 if( errno == EINTR )
1164 {
1165 continue;
1166 }
1167 }
1168 break;
1169 }
1170
1171 if( rc == 1 )
1172 {
1173 /*
1174 * we can read the last byte of the block, it is not free
1175 */
1176 continue;
1177 }
1178
1179 /*
1180 * we found the last filesystem file used for the bigfile
1181 * seek to the end of the file
1182 */
1183 for( j = 0; j < 3; j++ )
1184 {
1185 rc = lseek( fh, 0, SEEK_END );
1186 if( rc < 0 )
1187 {
1188 if( errno == EINTR )
1189 {
1190 continue;
1191 }
1192
1193 pbl_errno = PBL_ERROR_WRITE;
1194 return( -1 );
1195 }
1196 break;
1197 }
1198
1199 if( rc % pbf_pool[ bf ].blocksize )
1200 {
1201 pbl_errno = PBL_ERROR_BAD_FILE;
1202 return( -1 );
1203 }
1204
1205 pbf_pool[ bf ].nextblockno = rc / pbf_pool[ bf ].blocksize;
1206 break;
1207 }
1208 }
1209
1210 /*
1211 * append the block to the bigfile
1212 */
1213 rc = pbf_blockio( bf, 1, pbf_pool[ bf ].nextblockno, buffer );
1214 if( rc )
1215 {
1216 return( rc );
1217 }
1218
1219 return( pbf_pool[ bf ].nextblockno++ );
1220 }
1221
1222 /*
1223 * ITEM functions
1224 *
1225 * Layout of an item in the data of a block with a level greater than 0
1226 *
1227 * LENGTH NAME SEMANTICS
1228 *
1229 * 1 KEYLEN length of the key of the item
1230 * 1 KEYCOMMON number of bytes the key has in common with
1231 * the key of the predecessor of the item on the block
1232 * VARLONG DATABLOCK block number of block this item points to
1233 * KEYLEN KEY the key itself, only the last KEYLEN - KEYCOMMON
1234 * bytes are stored
1235 *
1236 * Layout of an item in the data of a block with a level 0 and
1237 * with the datalen of the item smaller than or equal to PBLDATALENGTH
1238 *
1239 * LENGTH NAME SEMANTICS
1240 *
1241 * 1 KEYLEN length of the key of the item
1242 * 1 KEYCOMMON number of bytes the key has in common with
1243 * the key of the predecessor of the item on the block
1244 * VARLONG DATALEN length of the data stored on the block
1245 * KEYLEN KEY the key itself, only the last KEYLEN - KEYCOMMON
1246 * bytes are stored
1247 * DATALEN DATA the data is stored on the block
1248 *
1249 * Layout of an item in the data of a block with a level 0 and
1250 * with the datalen of the item greater than PBLDATALENGTH
1251 *
1252 * LENGTH NAME SEMANTICS
1253 *
1254 * 1 KEYLEN length of the key of the item
1255 * 1 KEYCOMMON number of bytes the key has in common with
1256 * the key of the predecessor of the item on the block
1257 * VARLONG DATALEN length of the data stored on the datablock
1258 * KEYLEN KEY the key itself, only the last KEYLEN - KEYCOMMON
1259 * bytes are stored
1260 * VARLONG DATABLOCK block number of block data is stored on
1261 * VARLONG DATAOFFSET offset of the data on that block
1262 *
1263 * The long values stored for an item, DATALEN, DATABLOCK and DATAOFFSET
1264 * are stored as variable length buffers, i.e. the number of bytes
1265 * used in the file for the values depends on their numerical value.
1266 * See the VarBuf* functions for details.
1267 *
1268 * The smallest item of an inner block always has KEYLEN 0, which makes
1269 * it's key logically smaller than any other possible key of an item.
1270 *
1271 * The items stored on a block start at address ( block->data + PBLHEADERSIZE ).
1272 * The items are always stored immediately one after the other starting at
1273 * at this address, we leave no space in between.
1274 *
1275 * As the keys of the items and therefore the items themselves can have
1276 * different lengths, we store the relative offsets of the items in the
1277 * data of a block also in the data of the block. Those relative offsets
1278 * are stored as two byte unsigned shorts at the end of the data of the block.
1279 * The relative offsets are called slots in the code below.
1280 *
1281 * The slots in the slot array are kept in order.
1282 *
1283 * For every block the short block->free gives the relative offset of the first
1284 * free byte of the block, immediately after the end of the last item stored.
1285 *
1286 * Before we append an item we check if there is enough space for the item
1287 * and its slot between the end of the last item stored and the beginning
1288 * of the slot array of the items stored. If not, PBL_ERROR_NOFIT is given
1289 * to the pblinsert procedure which then has to split the block.
1290 *
1291 * During deletion we pack the ordered array of the slots
1292 * and the items themselves by shifting them on the block.
1293 *
1294 * The number of bytes the key of an item has in common with the key
1295 * of the predecessor of the item is stored with each item.
1296 * This is done in order to minimize the space needed for keys.
1297 *
1298 * EG: If a key is "New York" and its predecessor is "New Haven",
1299 * only the string "York" is stored for the second key together
1300 * with one byte indicating that the key has the first 4 bytes
1301 * with its predecessor, the key "New Haven".
1302 *
1303 * Whenever the full keys are needed for the items of a block,
1304 * the keys of the items of the block have to be "expanded" first.
1305 */
1306
1307 /*
1308 * The following three static procedures are the only ones that 'know' the
1309 * layout of an item stored on a block
1310 */
pblItemToBuf(PBLBLOCK_t * block,int bufoff,PBLITEM_t * item)1311 static void pblItemToBuf( PBLBLOCK_t * block, int bufoff, PBLITEM_t * item )
1312 {
1313 unsigned char * ptr = &( block->data[ bufoff ] );
1314 int bytesToStore = item->keylen - item->keycommon;
1315
1316 *ptr++ = ( unsigned char ) item->keylen;
1317 *ptr++ = ( unsigned char ) item->keycommon;
1318
1319 if( block->level > 0 )
1320 {
1321 ptr += pbl_LongToVarBuf( ptr, item->datablock );
1322 }
1323 else
1324 {
1325 ptr += pbl_LongToVarBuf( ptr, item->datalen );
1326 }
1327
1328 if( bytesToStore > 0 )
1329 {
1330 unsigned char * from = item->key + item->keycommon;
1331
1332 /*
1333 * make sure we don't copy in place
1334 */
1335 if( ptr != from )
1336 {
1337 pbl_memlcpy( ptr, PBLKEYLENGTH, from, bytesToStore );
1338 }
1339 ptr += bytesToStore;
1340 }
1341
1342 /*
1343 * the block needs to be written to the filesystem
1344 */
1345 block->dirty = 1;
1346
1347 if( block->level > 0 )
1348 {
1349 return;
1350 }
1351
1352 if( item->datalen <= PBLDATALENGTH )
1353 {
1354 if( item->datalen > 0 )
1355 {
1356 if( ptr != item->data )
1357 {
1358 memcpy( ptr, item->data, item->datalen );
1359 }
1360 }
1361 }
1362 else
1363 {
1364 ptr += pbl_LongToVarBuf( ptr, item->datablock );
1365 pbl_LongToVarBuf( ptr, item->dataoffset );
1366 }
1367 }
1368
pblBufToCachedItem(PBLBLOCK_t * block,unsigned int itemIndex)1369 static PBL_CACHED_ITEM_t * pblBufToCachedItem( PBLBLOCK_t * block, unsigned int itemIndex )
1370 {
1371 unsigned char * ptr;
1372 unsigned char * endptr;
1373 int bufoff;
1374 unsigned int index;
1375 int keylen;
1376 int keycommon;
1377 int keybytesmissing;
1378 PBL_CACHED_ITEM_t * item;
1379 unsigned char keybuffer[ PBLKEYLENGTH + 1];
1380
1381 if( itemIndex >= PBL_CACHED_ITEMS_PER_BLOCK )
1382 {
1383 pbl_errno = PBL_ERROR_BAD_FILE;
1384 return( 0 );
1385 }
1386
1387 /*
1388 * If the item is already cached, we are done
1389 */
1390 item = block->cachedItems[ itemIndex ];
1391 if( item )
1392 {
1393 return( item );
1394 }
1395 index = itemIndex;
1396
1397 /*
1398 * make sure the offset is in bounds
1399 */
1400 bufoff = PBLINDEXTOBUFOFF( block, itemIndex );
1401 if( bufoff < 0 || bufoff >= (int)sizeof( block->data ))
1402 {
1403 pbl_errno = PBL_ERROR_BAD_FILE;
1404 return( 0 );
1405 }
1406
1407 /*
1408 * malloc space for the cached item
1409 */
1410 item = (PBL_CACHED_ITEM_t *)pbl_malloc0("pblBufToCachedItem item", sizeof(PBL_CACHED_ITEM_t));
1411 if( !item )
1412 {
1413 return( 0 );
1414 }
1415
1416 endptr = &( block->data[ sizeof( block->data ) ] );
1417 ptr = &( block->data[ bufoff ] );
1418
1419 /*
1420 * parse the item
1421 */
1422 item->keylen = *ptr++;
1423 keylen = item->keylen & 0xff;
1424
1425 item->keycommon = *ptr++;
1426 keycommon = item->keycommon & 0xff;
1427
1428 keylen -= keycommon;
1429
1430 if( block->level > 0 )
1431 {
1432 ptr += pbl_VarBufToLong( ptr, (unsigned long *)&( item->datablock ));
1433 item->datalen = 0;
1434 }
1435 else
1436 {
1437 ptr += pbl_VarBufToLong( ptr, (unsigned long *)&( item->datalen ));
1438 item->datablock = 0;
1439 }
1440
1441 if( ptr >= endptr )
1442 {
1443 PBL_FREE( item );
1444 pbl_errno = PBL_ERROR_BAD_FILE;
1445 return( 0 );
1446 }
1447
1448 if( item->keylen > 0 )
1449 {
1450 item->key = ptr;
1451 ptr += keylen;
1452 if( ptr >= endptr )
1453 {
1454 PBL_FREE( item );
1455 pbl_errno = PBL_ERROR_BAD_FILE;
1456 return( 0 );
1457 }
1458 }
1459 else
1460 {
1461 item->key = 0;
1462 }
1463
1464 if( block->level > 0 )
1465 {
1466 item->dataoffset = 0;
1467
1468 if( item->keylen < 1 || keycommon < 1)
1469 {
1470 /*
1471 * Store the key on the heap
1472 */
1473 if( item->keylen > 0 )
1474 {
1475 item->key = pbl_memdup("pblBufToCachedItem key", item->key, item->keylen);
1476 if( !item->key )
1477 {
1478 PBL_FREE( item );
1479 return( 0 );
1480 }
1481 }
1482 block->cachedItems[ itemIndex ] = item;
1483 return( item );
1484 }
1485
1486 keybytesmissing = keycommon;
1487 keybuffer[ item->keylen ] = 0;
1488
1489 if( keylen > 0 )
1490 {
1491 /*
1492 * copy the key to the key buffer
1493 */
1494 memcpy( keybuffer + keybytesmissing, item->key, keylen );
1495 }
1496 item->key = keybuffer;
1497
1498 while( keycommon > 0 )
1499 {
1500 if( index-- < 1)
1501 {
1502 PBL_FREE( item );
1503 pbl_errno = PBL_ERROR_BAD_FILE;
1504 return( 0 );
1505 }
1506 else
1507 {
1508 PBL_CACHED_ITEM_t * prevItem = block->cachedItems[ index ];
1509 if( prevItem )
1510 {
1511 /*
1512 * Take the bytes from the previous cached item
1513 */
1514 memcpy( keybuffer, prevItem->key, keybytesmissing );
1515 break;
1516 }
1517 }
1518
1519 bufoff = PBLINDEXTOBUFOFF( block, index );
1520
1521 /*
1522 * make sure the offset is in bounds
1523 */
1524 if( bufoff < 0 || bufoff >= (int)sizeof( block->data ))
1525 {
1526 PBL_FREE( item );
1527 pbl_errno = PBL_ERROR_BAD_FILE;
1528 return( 0 );
1529 }
1530 ptr = &( block->data[ bufoff ] );
1531
1532 /*
1533 * parse the item
1534 */
1535 keylen = *ptr++;
1536 if( keylen < 1 )
1537 {
1538 PBL_FREE( item );
1539 pbl_errno = PBL_ERROR_BAD_FILE;
1540 return( 0 );
1541 }
1542
1543 keycommon = *ptr++;
1544 if( keycommon >= keybytesmissing)
1545 {
1546 continue;
1547 }
1548
1549 keylen = keybytesmissing - keycommon;
1550
1551 ptr += pbl_VarBufSize( ptr );
1552
1553 if( keylen > 0 )
1554 {
1555 if( ptr + keylen >= endptr )
1556 {
1557 PBL_FREE( item );
1558 pbl_errno = PBL_ERROR_BAD_FILE;
1559 return( 0 );
1560 }
1561
1562 keybytesmissing -= keylen;
1563 memcpy( keybuffer + keybytesmissing, ptr, keylen );
1564 }
1565 }
1566
1567 /*
1568 * Store the key on the heap
1569 */
1570 if( item->keylen > 0 )
1571 {
1572 item->key = pbl_memdup("pblBufToCachedItem key", item->key, item->keylen);
1573 if( !item->key )
1574 {
1575 PBL_FREE( item );
1576 return( 0 );
1577 }
1578 }
1579 block->cachedItems[ itemIndex ] = item;
1580 return( item );
1581 }
1582
1583 if( item->datalen <= PBLDATALENGTH )
1584 {
1585 if( item->datalen > 0 )
1586 {
1587 item->dataoffset = ptr - block->data;
1588 ptr += item->datalen;
1589 if( ptr >= endptr )
1590 {
1591 PBL_FREE( item );
1592 pbl_errno = PBL_ERROR_BAD_FILE;
1593 return( 0 );
1594 }
1595 }
1596 else
1597 {
1598 item->dataoffset = 0;
1599 }
1600 }
1601 else
1602 {
1603 ptr += pbl_VarBufToLong( ptr, (unsigned long *)&( item->datablock ));
1604 pbl_VarBufToLong( ptr, (unsigned long *)&( item->dataoffset ));
1605 }
1606
1607 if( ptr >= endptr )
1608 {
1609 PBL_FREE( item );
1610 pbl_errno = PBL_ERROR_BAD_FILE;
1611 return( 0 );
1612 }
1613
1614 if( item->keylen < 1 || keycommon < 1)
1615 {
1616 /*
1617 * Store the key on the heap
1618 */
1619 if( item->keylen > 0 )
1620 {
1621 item->key = pbl_memdup("pblBufToCachedItem key", item->key, item->keylen);
1622 if( !item->key )
1623 {
1624 PBL_FREE( item );
1625 return( 0 );
1626 }
1627 }
1628 block->cachedItems[ itemIndex ] = item;
1629 return( item );
1630 }
1631
1632 keybytesmissing = keycommon;
1633 keybuffer[ item->keylen ] = 0;
1634
1635 if( keylen > 0 )
1636 {
1637 /*
1638 * copy the key to the key buffer
1639 */
1640 memcpy( keybuffer + keybytesmissing, item->key, keylen );
1641 }
1642 item->key = keybuffer;
1643
1644 while( keycommon > 0)
1645 {
1646 if( index-- < 1)
1647 {
1648 PBL_FREE( item );
1649 pbl_errno = PBL_ERROR_BAD_FILE;
1650 return( 0 );
1651 }
1652 else
1653 {
1654 PBL_CACHED_ITEM_t * prevItem = block->cachedItems[ index ];
1655 if( prevItem )
1656 {
1657 /*
1658 * Take the bytes from the previous cached item
1659 */
1660 memcpy( keybuffer, prevItem->key, keybytesmissing );
1661 break;
1662 }
1663 }
1664
1665 bufoff = PBLINDEXTOBUFOFF( block, index );
1666
1667 /*
1668 * make sure the offset is in bounds
1669 */
1670 if( bufoff < 0 || bufoff >= (int)sizeof( block->data ))
1671 {
1672 PBL_FREE( item );
1673 pbl_errno = PBL_ERROR_BAD_FILE;
1674 return( 0 );
1675 }
1676 ptr = &( block->data[ bufoff ] );
1677
1678 /*
1679 * parse the item
1680 */
1681 keylen = *ptr++;
1682 if( keylen < 1 )
1683 {
1684 PBL_FREE( item );
1685 pbl_errno = PBL_ERROR_BAD_FILE;
1686 return( 0 );
1687 }
1688
1689 keycommon = *ptr++;
1690 if( keycommon >= keybytesmissing)
1691 {
1692 continue;
1693 }
1694
1695 keylen = keybytesmissing - keycommon;
1696
1697 ptr += pbl_VarBufSize( ptr );
1698
1699 if( keylen > 0 )
1700 {
1701 if( ptr + keylen >= endptr )
1702 {
1703 PBL_FREE( item );
1704 pbl_errno = PBL_ERROR_BAD_FILE;
1705 return( 0 );
1706 }
1707
1708 keybytesmissing -= keylen;
1709 memcpy( keybuffer + keybytesmissing, ptr, keylen );
1710 }
1711 }
1712
1713 /*
1714 * Store the key on the heap
1715 */
1716 if( item->keylen > 0 )
1717 {
1718 item->key = pbl_memdup("pblBufToCachedItem key", item->key, item->keylen);
1719 if( !item->key )
1720 {
1721 PBL_FREE( item );
1722 return( 0 );
1723 }
1724 }
1725 block->cachedItems[ itemIndex ] = item;
1726 return( item );
1727 }
1728
1729 #ifdef PBL_MEMTRACE
1730
checkCachedItems(PBLBLOCK_t * block)1731 static int checkCachedItems( PBLBLOCK_t * block )
1732 {
1733 void * ptr;
1734 int i = 0;
1735
1736 pblHashTable_t * ptrHash = pblHtCreate();
1737
1738 int saveErrno = pbl_errno;
1739
1740 for( i = 0; i < PBL_CACHED_ITEMS_PER_BLOCK; i++ )
1741 {
1742 ptr = block->cachedItems[ i ];
1743 if( !ptr )
1744 {
1745 continue;
1746 }
1747
1748 if( pblHtLookup( ptrHash, &ptr, sizeof( ptr )))
1749 {
1750 pbl_errno = PBL_ERROR_PROGRAM;
1751 return -1;
1752 }
1753
1754 if( pblHtInsert( ptrHash, &ptr, sizeof( ptr ), ptr ))
1755 {
1756 return -1;
1757 }
1758 }
1759
1760
1761 while(( ptr = pblHtFirst( ptrHash )) != 0 )
1762 {
1763 if( pblHtRemove( ptrHash, &ptr, sizeof( ptr )))
1764 {
1765 pbl_errno = PBL_ERROR_PROGRAM;
1766 return -1;
1767 }
1768 }
1769 if( pblHtDelete( ptrHash ))
1770 {
1771 pbl_errno = PBL_ERROR_PROGRAM;
1772 return -1;
1773 }
1774
1775 pbl_errno = saveErrno;
1776 return 0;
1777 }
1778
1779 #endif
1780
pblBufToItem(PBLBLOCK_t * block,unsigned int index,PBLITEM_t * item)1781 static int pblBufToItem( PBLBLOCK_t * block, unsigned int index, PBLITEM_t * item )
1782 {
1783 PBL_CACHED_ITEM_t * cachedItem;
1784
1785 item->level = block->level;
1786
1787 /*
1788 * get the item to the cache
1789 */
1790 cachedItem = pblBufToCachedItem( block, index );
1791 if( !cachedItem )
1792 {
1793 return( -1 );
1794 }
1795
1796 if( index > block->maxItemCacheIndex )
1797 {
1798 block->maxItemCacheIndex = index;
1799 }
1800
1801 #ifdef PBL_MEMTRACE
1802
1803 checkCachedItems( block );
1804
1805 #endif
1806
1807 /*
1808 * get the values from the cached item
1809 */
1810 if( block->level > 0 )
1811 {
1812 item->data = NULL;
1813 item->datablock = cachedItem->datablock;
1814 item->datalen = cachedItem->datalen;
1815 item->dataoffset = cachedItem->dataoffset;
1816 }
1817 else
1818 {
1819 item->datalen = cachedItem->datalen;
1820 if( item->datalen <= PBLDATALENGTH )
1821 {
1822 item->datablock = 0;
1823 item->dataoffset = 0;
1824
1825 if( item->datalen > 0 )
1826 {
1827 item->data = block->data + cachedItem->dataoffset;
1828 }
1829 else
1830 {
1831 item->data = NULL;
1832 }
1833 }
1834 else
1835 {
1836 item->data = NULL;
1837 item->datablock = cachedItem->datablock;
1838 item->dataoffset = cachedItem->dataoffset;
1839 }
1840 }
1841
1842 item->key = cachedItem->key;
1843 item->keycommon = cachedItem->keycommon & 0xff;
1844 item->keylen = cachedItem->keylen & 0xff;
1845
1846 return 0;
1847 }
1848
pblBufToItemKey(PBLBLOCK_t * block,unsigned int index,PBLITEM_t * item)1849 static int pblBufToItemKey( PBLBLOCK_t * block, unsigned int index, PBLITEM_t * item )
1850 {
1851 /*
1852 * get the item to the cache
1853 */
1854 PBL_CACHED_ITEM_t * cachedItem = pblBufToCachedItem( block, index );
1855 if( !cachedItem )
1856 {
1857 return( -1 );
1858 }
1859
1860 if( index > block->maxItemCacheIndex )
1861 {
1862 block->maxItemCacheIndex = index;
1863 }
1864
1865 item->key = cachedItem->key;
1866 item->keylen = cachedItem->keylen & 0xff;
1867
1868 return 0;
1869 }
1870
pblItemSize(PBLBLOCK_t * block,PBLITEM_t * item)1871 static int pblItemSize( PBLBLOCK_t * block, PBLITEM_t * item )
1872 {
1873 int rc = 2;
1874
1875 if( block->level > 0 )
1876 {
1877 rc += pbl_LongSize( item->datablock );
1878 }
1879 else
1880 {
1881 rc += pbl_LongSize( item->datalen );
1882 }
1883
1884 if( item->keylen - item->keycommon > 0 )
1885 {
1886 rc += item->keylen - item->keycommon;
1887 }
1888
1889 if( block->level > 0 )
1890 {
1891 return( rc );
1892 }
1893
1894 if( item->datalen <= PBLDATALENGTH )
1895 {
1896 if( item->datalen > 0 )
1897 {
1898 rc += item->datalen;
1899 }
1900 }
1901 else
1902 {
1903 rc += pbl_LongSize( item->datablock );
1904 rc += pbl_LongSize( item->dataoffset );
1905 }
1906
1907 return( rc );
1908 }
1909
1910 /*
1911 * compare two items
1912 */
pblItemCompare(PBLKFILE_t * kf,PBLITEM_t * left,PBLITEM_t * right)1913 static int pblItemCompare( PBLKFILE_t *kf, PBLITEM_t *left, PBLITEM_t *right )
1914 {
1915 int rc;
1916
1917 if( kf->keycompare )
1918 {
1919 /*
1920 * there is a specific compare function for the key file
1921 */
1922 rc = (*kf->keycompare)( left->key, left->keylen,
1923 right->key, right->keylen );
1924 }
1925 else
1926 {
1927 /*
1928 * use the default key compare function
1929 */
1930 rc = pbl_memcmp( left->key, left->keylen,
1931 right->key, right->keylen );
1932 }
1933
1934 return( rc );
1935 }
1936
pblItemGet(PBLBLOCK_t * block,unsigned int index,PBLITEM_t * item)1937 static int pblItemGet( PBLBLOCK_t * block, unsigned int index, PBLITEM_t *item )
1938 {
1939 /*
1940 * if there is no item with required index
1941 */
1942 if( index >= (unsigned int)block->nentries )
1943 {
1944 pbl_errno = PBL_ERROR_BAD_FILE;
1945 return( -1 );
1946 }
1947
1948 /*
1949 * copy the item with the required index
1950 */
1951 if( pblBufToItem( block, index, item ))
1952 {
1953 return( -1 );
1954 }
1955
1956 return( 0 );
1957 }
1958
pblItemGetKey(PBLBLOCK_t * block,unsigned int index,PBLITEM_t * item)1959 static int pblItemGetKey( PBLBLOCK_t * block, unsigned int index, PBLITEM_t *item )
1960 {
1961 /*
1962 * if there is no item with required index
1963 */
1964 if( index >= (unsigned int)block->nentries )
1965 {
1966 pbl_errno = PBL_ERROR_BAD_FILE;
1967 return( -1 );
1968 }
1969
1970 /*
1971 * copy the item with the required index
1972 */
1973 if( pblBufToItemKey( block, index, item ))
1974 {
1975 return( -1 );
1976 }
1977
1978 return( 0 );
1979 }
1980
1981 /*
1982 * append an item to a block
1983 */
pblItemAppend(PBLBLOCK_t * block,unsigned char * predkey,unsigned int predkeylen,PBLITEM_t * item)1984 static int pblItemAppend(
1985 PBLBLOCK_t * block,
1986 unsigned char * predkey,
1987 unsigned int predkeylen,
1988 PBLITEM_t * item
1989 )
1990 {
1991 unsigned char * ptr;
1992 unsigned int itemsize;
1993
1994 if( !block->writeable )
1995 {
1996 pbl_errno = PBL_ERROR_PROGRAM;
1997 return( -1 );
1998 }
1999
2000 if( !predkey && block->nentries > 0 )
2001 {
2002 pbl_errno = PBL_ERROR_PROGRAM;
2003 return( -1 );
2004 }
2005
2006 /*
2007 * calculate how many bytes the key of the item has in common
2008 * with the key of the predecessor on the block
2009 */
2010 if( predkey && ( predkeylen > 0 ))
2011 {
2012 item->keycommon = pbl_memcmplen( predkey, predkeylen,
2013 item->key, item->keylen );
2014 }
2015 else
2016 {
2017 item->keycommon = 0;
2018 }
2019
2020 /*
2021 * calculate the size the item needs on the block
2022 */
2023 itemsize = pblItemSize( block, item );
2024
2025 /*
2026 * check if the item fits here, the "+ 2" is for the slot!
2027 */
2028 if( PBLINDEXBLOCKNFREE( block ) < itemsize + 2 )
2029 {
2030 pbl_errno = PBL_ERROR_NOFIT;
2031 return( -1 );
2032 }
2033
2034 /*
2035 * put item to data part of block
2036 */
2037 pblItemToBuf( block, block->free, item );
2038
2039 /*
2040 * put the slot to the block
2041 */
2042 ptr = PBLINDEXTOPTR( block, block->nentries );
2043 pbl_ShortToBuf( ptr, block->free );
2044
2045 block->free += itemsize;
2046 block->nentries += 1;
2047
2048 return( 0 );
2049 }
2050
2051 /*
2052 * delete an item from a block
2053 */
pblItemDelete(PBLBLOCK_t * block,int index)2054 static int pblItemDelete( PBLBLOCK_t * block, int index )
2055 {
2056 PBLITEM_t item;
2057 int ntomove;
2058 unsigned int i;
2059 int offset;
2060 int itemoffset;
2061 unsigned char * ptr;
2062 unsigned int itemsize;
2063 PBL_CACHED_ITEM_t * cachedItem;
2064 int itemsMoved = 0;
2065
2066 /*
2067 * read the item to delete
2068 */
2069 if( pblItemGet( block, index, &item ))
2070 {
2071 return( -1 );
2072 }
2073
2074 /*
2075 * calculate the size the item ocupies on the block
2076 */
2077 itemsize = pblItemSize( block, &item );
2078
2079 /*
2080 * calculate the number of items that have to be moved
2081 */
2082 itemoffset = PBLINDEXTOBUFOFF( block, index );
2083 ptr = block->data + itemoffset;
2084 ntomove = block->free - ( itemoffset + itemsize );
2085 if( ntomove < 0 )
2086 {
2087 pbl_errno = PBL_ERROR_BAD_FILE;
2088 return( -1 );
2089 }
2090
2091 if( ntomove > 0 )
2092 {
2093 /*
2094 * move the other items to the left
2095 */
2096 memmove( ptr, ptr + itemsize, ntomove );
2097 itemsMoved = 1;
2098
2099 /*
2100 * the slots who's offsets are to the right of the deleted item
2101 * have to change, because the items where moved
2102 */
2103 for( i = 0; i < block->nentries; i++ )
2104 {
2105 offset = PBLINDEXTOBUFOFF( block, i );
2106 if( offset > itemoffset )
2107 {
2108 offset -= itemsize;
2109 ptr = PBLINDEXTOPTR( block, i );
2110 pbl_ShortToBuf( ptr, offset );
2111 }
2112 }
2113 }
2114
2115 /*
2116 * blank out the bytes deleted
2117 */
2118 memset(( block->data + block->free ) - itemsize, 0, itemsize );
2119
2120 /*
2121 * there is more free space on the block now
2122 */
2123 block->free -= itemsize;
2124
2125 /*
2126 * delete the slot from the slots array
2127 */
2128 ptr = PBLINDEXTOPTR( block, block->nentries - 1 );
2129 if( index < (int)block->nentries - 1 )
2130 {
2131 ntomove = ( block->nentries - 1 ) - index;
2132 memmove( ptr + 2, ptr, ntomove * 2 );
2133 }
2134
2135 /*
2136 * blank out the last slot
2137 */
2138 *ptr++ = 0;
2139 *ptr = 0;
2140
2141 /*
2142 * there is one less slot on the block
2143 */
2144 block->nentries -= 1;
2145
2146 /*
2147 * remove the item from the itemcache
2148 */
2149 cachedItem = block->cachedItems[ index ];
2150 if( cachedItem )
2151 {
2152 if( cachedItem->key )
2153 {
2154 PBL_FREE( cachedItem->key );
2155 }
2156 PBL_FREE( cachedItem );
2157 }
2158
2159 for( i = index + 1; i < PBL_CACHED_ITEMS_PER_BLOCK; i++ )
2160 {
2161 block->cachedItems[ i - 1 ] = block->cachedItems[ i ];
2162
2163 if( i > block->maxItemCacheIndex )
2164 {
2165 break;
2166 }
2167 }
2168 block->cachedItems[ PBL_CACHED_ITEMS_PER_BLOCK - 1 ] = 0;
2169
2170 if( block->level == 0 && itemsMoved != 0 )
2171 {
2172 /*
2173 * The cached items that point to items that where moved above
2174 * need to have their dataoffset adjusted by the size of the deleted item
2175 */
2176 for( i = 0; i < PBL_CACHED_ITEMS_PER_BLOCK; i++ )
2177 {
2178 if( i > block->maxItemCacheIndex )
2179 {
2180 break;
2181 }
2182
2183 cachedItem = block->cachedItems[ i ];
2184 if( !cachedItem )
2185 {
2186 continue;
2187 }
2188
2189 if( cachedItem->datalen < 1 )
2190 {
2191 continue;
2192 }
2193
2194 if( cachedItem->datalen > PBLDATALENGTH )
2195 {
2196 continue;
2197 }
2198
2199 if( cachedItem->dataoffset < itemoffset )
2200 {
2201 continue;
2202 }
2203
2204 cachedItem->dataoffset -= itemsize;
2205 }
2206 }
2207
2208 #ifdef PBL_MEMTRACE
2209
2210 checkCachedItems( block );
2211
2212 #endif
2213
2214 block->dirty = 1;
2215 return( 0 );
2216 }
2217
2218 /*
2219 * insert an item on a block before the item with a given index
2220 */
pblItemInsert(PBLBLOCK_t * block,PBLITEM_t * item,int index)2221 static int pblItemInsert( PBLBLOCK_t * block, PBLITEM_t * item, int index )
2222 {
2223 int ntomove;
2224 unsigned char * ptr;
2225 unsigned int itemsize;
2226
2227 /*
2228 * calculate the size the item needs on the block
2229 */
2230 itemsize = pblItemSize( block, item );
2231
2232 /*
2233 * check if the item fits here, the "+ 2" is for the slot!
2234 */
2235 if( PBLINDEXBLOCKNFREE( block ) < itemsize + 2 )
2236 {
2237 pbl_errno = PBL_ERROR_NOFIT;
2238 return( -1 );
2239 }
2240
2241 /*
2242 * put item to data part of block
2243 */
2244 pblItemToBuf( block, block->free, item );
2245
2246 /*
2247 * move the slots of the items after index
2248 */
2249 ptr = PBLINDEXTOPTR( block, block->nentries );
2250 ntomove = block->nentries - index;
2251 if( ntomove > 0 )
2252 {
2253 memmove( ptr, ptr + 2, 2 * ntomove );
2254 }
2255
2256 /*
2257 * put the slot to the slots array
2258 */
2259 ptr = PBLINDEXTOPTR( block, index );
2260 pbl_ShortToBuf( ptr, block->free );
2261
2262 block->free += itemsize;
2263 block->nentries += 1;
2264
2265 /*
2266 * Move the cached item pointers
2267 */
2268 if( ntomove > 0 )
2269 {
2270 char * ptr = (char*)&(block->cachedItems[ index ]);
2271 memmove( ptr + sizeof( PBL_CACHED_ITEM_t *), ptr, ntomove * sizeof( PBL_CACHED_ITEM_t *));
2272 block->maxItemCacheIndex++;
2273 }
2274
2275 block->cachedItems[ index ] = 0;
2276
2277 #ifdef PBL_MEMTRACE
2278
2279 checkCachedItems( block );
2280
2281 #endif
2282
2283 block->dirty = 1;
2284 return( 0 );
2285 }
2286
2287 /*
2288 * remove an item from a block
2289 */
pblItemRemove(PBLBLOCK_t * block,unsigned int index)2290 static int pblItemRemove( PBLBLOCK_t *block, unsigned int index )
2291 {
2292 PBLITEM_t peeritem;
2293 PBLITEM_t previtem;
2294 unsigned char data[ PBLDATALENGTH ];
2295 unsigned char savekey[ PBLKEYLENGTH ];
2296 int rc;
2297 int keycommon;
2298 int dodelete = 0;
2299
2300 memset( &previtem,0, sizeof( previtem));
2301
2302 if( !block->writeable )
2303 {
2304 pbl_errno = PBL_ERROR_PROGRAM;
2305 return( -1 );
2306 }
2307
2308 /*
2309 * if there is no item with required index
2310 */
2311 if( index >= block->nentries )
2312 {
2313 pbl_errno = PBL_ERROR_BAD_FILE;
2314 return( -1 );
2315 }
2316
2317 if( index == block->nentries - 1 )
2318 {
2319 /*
2320 * delete the last item on the block
2321 */
2322 rc = pblItemDelete( block, index );
2323 return( rc );
2324 }
2325
2326 /*
2327 * read the previous item on the block
2328 */
2329 if( index > 0 )
2330 {
2331 if( pblItemGet( block, index - 1, &previtem ))
2332 {
2333 return( -1 );
2334 }
2335 }
2336
2337 /*
2338 * read the next item on the block
2339 */
2340 if( pblItemGet( block, index + 1, &peeritem ))
2341 {
2342 return( -1 );
2343 }
2344
2345 if(( index > 0 ) && ( previtem.keylen > 0 ))
2346 {
2347 keycommon = pbl_memcmplen( previtem.key, previtem.keylen,
2348 peeritem.key, peeritem.keylen );
2349 }
2350 else
2351 {
2352 keycommon = 0;
2353 }
2354
2355 /*
2356 * if the next item has to change
2357 */
2358 if( keycommon != peeritem.keycommon )
2359 {
2360 /*
2361 * delete and reinsert the next item, because its keycommon changed
2362 */
2363 dodelete = 1;
2364
2365 /*
2366 * set the new keycommon value for the next item
2367 */
2368 peeritem.keycommon = keycommon;
2369
2370 /*
2371 * save the data of the next item
2372 */
2373 if( peeritem.datalen <= PBLDATALENGTH )
2374 {
2375 memcpy( data, peeritem.data, peeritem.datalen );
2376 peeritem.data = data;
2377 }
2378
2379 /*
2380 * save the key of the next item
2381 */
2382 memcpy( savekey, peeritem.key, peeritem.keylen );
2383 peeritem.key = savekey;
2384
2385 /*
2386 * delete the next item
2387 */
2388 rc = pblItemDelete( block, index + 1 );
2389 if( rc )
2390 {
2391 return( rc );
2392 }
2393 }
2394
2395 /*
2396 * delete the index'th item
2397 */
2398 rc = pblItemDelete( block, index );
2399 if( rc )
2400 {
2401 return( rc );
2402 }
2403
2404 if( dodelete )
2405 {
2406 /*
2407 * insert the saved item again
2408 */
2409 rc = pblItemInsert( block, &peeritem, index );
2410 }
2411 return( rc );
2412 }
2413
2414 /*
2415 * find an item that has a key equal to the search key
2416 *
2417 * - uses a binary search to position to an item on a block
2418 */
pblItemFind(PBLKFILE_t * kf,PBLBLOCK_t * block,PBLITEM_t * item,int which)2419 static int pblItemFind(
2420 PBLKFILE_t * kf,
2421 PBLBLOCK_t * block,
2422 PBLITEM_t * item,
2423 int which
2424 )
2425 {
2426 int found = -1;
2427 int index = 0;
2428 int left = 0;
2429 int right = block->nentries - 1;
2430 int rc = 1;
2431 PBLITEM_t curitem;
2432
2433 while( left <= right )
2434 {
2435 index = ( left + right ) / 2;
2436
2437 if( pblItemGetKey( block, index, &curitem ))
2438 {
2439 return( -1 );
2440 }
2441
2442 rc = pblItemCompare( kf, &curitem, item );
2443 if( rc == 0 )
2444 {
2445 switch( which )
2446 {
2447 case PBLLT:
2448 right = index - 1;
2449 break;
2450
2451 case PBLLE:
2452 case PBLFI:
2453 found = index;
2454 right = index - 1;
2455 break;
2456
2457 case PBLEQ:
2458 found = index;
2459 return( found );
2460
2461 case PBLLA:
2462 case PBLGE:
2463 found = index;
2464 left = index + 1;
2465 break;
2466
2467 case PBLGT:
2468 left = index + 1;
2469 break;
2470 }
2471 }
2472 else if ( rc < 0 )
2473 {
2474 switch( which )
2475 {
2476 case PBLLT:
2477 case PBLLE:
2478 found = index;
2479 left = index + 1;
2480 break;
2481
2482 case PBLFI:
2483 case PBLEQ:
2484 case PBLLA:
2485 case PBLGE:
2486 case PBLGT:
2487 left = index + 1;
2488 break;
2489 }
2490 }
2491 else
2492 {
2493 switch( which )
2494 {
2495 case PBLLT:
2496 case PBLLE:
2497 case PBLFI:
2498 case PBLEQ:
2499 case PBLLA:
2500 right = index - 1;
2501 break;
2502
2503 case PBLGE:
2504 case PBLGT:
2505 found = index;
2506 right = index - 1;
2507 break;
2508 }
2509 }
2510 }
2511
2512 if( found < 0 )
2513 {
2514 pbl_errno = PBL_ERROR_NOT_FOUND;
2515 }
2516
2517 return( found );
2518 }
2519
pblItemAdd(PBLKFILE_t * kf,PBLBLOCK_t * block,PBLITEM_t * item)2520 static int pblItemAdd( PBLKFILE_t * kf, PBLBLOCK_t * block, PBLITEM_t * item )
2521 {
2522 PBLITEM_t previtem;
2523 PBLITEM_t peeritem;
2524 int rc;
2525 int index;
2526 unsigned char savekey[ PBLKEYLENGTH ];
2527 unsigned int savekeylen;
2528 unsigned char data[ PBLDATALENGTH ];
2529 unsigned int itemsize;
2530 int keycommon;
2531
2532 if( !block->writeable )
2533 {
2534 pbl_errno = PBL_ERROR_PROGRAM;
2535 return( -1 );
2536 }
2537
2538 if( block->nentries < 1 )
2539 {
2540 if( pblItemAppend( block, 0, 0, item ))
2541 {
2542 return( -1 );
2543 }
2544 return( 0 );
2545 }
2546
2547 /*
2548 * find the first item that is bigger than the one we insert
2549 */
2550 index = pblItemFind( kf, block, item, PBLGT );
2551 if( index < 0 )
2552 {
2553 if( pbl_errno != PBL_ERROR_NOT_FOUND )
2554 {
2555 return( -1 );
2556 }
2557
2558 /*
2559 * append to the block
2560 */
2561 pbl_errno = 0;
2562 index = block->nentries;
2563
2564 if( pblItemGet( block, index - 1, &peeritem ))
2565 {
2566 return( -1 );
2567 }
2568
2569 savekeylen = peeritem.keylen;
2570 if( savekeylen > 0 )
2571 {
2572 pbl_memlcpy( savekey, sizeof( savekey ), peeritem.key, savekeylen );
2573 }
2574
2575 if( pblItemAppend( block, savekey, savekeylen, item ))
2576 {
2577 return( -1 );
2578 }
2579 return( index );
2580 }
2581
2582 /*
2583 * read the previous item on the block
2584 */
2585 if( index > 0 )
2586 {
2587 if( pblItemGet( block, index - 1, &previtem ))
2588 {
2589 return( -1 );
2590 }
2591 }
2592
2593 /*
2594 * calculate the number of bytes the key of the item has in
2595 * common with the key of its predecessor
2596 */
2597 if(( index > 0 ) && ( previtem.keylen > 0 ))
2598 {
2599 item->keycommon = pbl_memcmplen( previtem.key, previtem.keylen,
2600 item->key, item->keylen );
2601 }
2602 else
2603 {
2604 item->keycommon = 0;
2605 }
2606
2607 /*
2608 * calculate the size the item needs on the block
2609 */
2610 itemsize = pblItemSize( block, item );
2611
2612 /*
2613 * check if the item fits here, the "+ 2" is for the slot!
2614 */
2615 if( PBLINDEXBLOCKNFREE( block ) < itemsize + 2 )
2616 {
2617 pbl_errno = PBL_ERROR_NOFIT;
2618 return( -1 );
2619 }
2620
2621 /*
2622 * read the next item on the block
2623 */
2624 if( pblItemGet( block, index, &peeritem ))
2625 {
2626 return( -1 );
2627 }
2628
2629 /*
2630 * calculate the number of bytes the key of the next item has in
2631 * common with the key of the new item
2632 */
2633 if( item->keylen > 0 )
2634 {
2635 keycommon = pbl_memcmplen( item->key, item->keylen,
2636 peeritem.key, peeritem.keylen );
2637 }
2638 else
2639 {
2640 keycommon = 0;
2641 }
2642
2643 /*
2644 * if the next item has to change
2645 */
2646 if( keycommon != peeritem.keycommon )
2647 {
2648 /*
2649 * set the new keycommon value for the next item
2650 */
2651 peeritem.keycommon = keycommon;
2652
2653 /*
2654 * save the data of that item
2655 */
2656 if( peeritem.datalen <= PBLDATALENGTH )
2657 {
2658 memcpy( data, peeritem.data, peeritem.datalen );
2659 peeritem.data = data;
2660 }
2661
2662 /*
2663 * save the key of the item
2664 */
2665 memcpy( savekey, peeritem.key, peeritem.keylen );
2666 peeritem.key = savekey;
2667
2668 /*
2669 * delete the next item
2670 */
2671 rc = pblItemDelete( block, index );
2672 if( rc )
2673 {
2674 return( rc );
2675 }
2676
2677 /*
2678 * insert the saved item again
2679 */
2680 rc = pblItemInsert( block, &peeritem, index );
2681 if( rc )
2682 {
2683 return( rc );
2684 }
2685 }
2686
2687 /*
2688 * insert the new item
2689 */
2690 rc = pblItemInsert( block, item, index );
2691 if( rc )
2692 {
2693 return( rc );
2694 }
2695
2696 return( index );
2697 }
2698
2699 /*
2700 * BLOCK functions
2701 *
2702 * The size of a block in the file is PBLDATASIZE
2703 *
2704 * The layout is as follows:
2705 *
2706 * OFFSET NAME SEMANTICS
2707 *
2708 * 0 LEVEL Level of the block in the tree
2709 * if 0: the block is a leaf node
2710 * if 254: the block is a free block, can be reused
2711 * if 255: the block is a data block, not belonging to
2712 * the tree.
2713 * otherwise: block is an inner node of the tree
2714 *
2715 * 1 - 4 NOFFSET block number of next block of same level, as the root block
2716 * always is the only block of it's level, the block number
2717 * of the last data block is stored here, we use this block
2718 * for appending data if necessary.
2719 *
2720 * 5 - 8 POFFEST file offset of previous block of the same level,
2721 * as the root block always is the only block of it's level,
2722 * the block number of the first free block with level 254
2723 * is stored on the root block
2724 *
2725 * 9 - 10 NENTRIES number of items stored in the data of the block.
2726 * always 0 for data blocks.
2727 *
2728 * 11 - 12 FREE relative offset of first free byte in the data of the block
2729 *
2730 * 13 - ( PBLDATASIZE - 1 ) data area of the block used for storing items on
2731 * tree blocks ( level 0 - 253 ) or used for storing
2732 * the data of the items on data blocks ( level 255 ).
2733 *
2734 * The root block of the tree is always stored at file offset 0. The first data
2735 * block at file offset PBLDATASIZE. There are at least two blocks in a file
2736 * even if there are no items stored at all.
2737 *
2738 * For records with a datalen of less or equal to PBLDATALENGTH characters
2739 * the data is stored on the level 0 index blocks. For records with
2740 * data longer than PBLDATALENGTH characters the data is stored on data blocks.
2741 *
2742 * This is done in order to keep the height of the tree small and to allow
2743 * data lengths of more than PBLDATASIZE bytes.
2744 *
2745 * Only one data record is stored per data block.
2746 *
2747 * Blocks read from disk are cached in an LRU list, references to blocks
2748 * in that list are kept in a hash table in order to speed up access.
2749 *
2750 * Blocks changed during a transaction are kept in the writeable block
2751 * list. If a cached block that is dirty has to be made writeable a copy
2752 * of the block is created in the writeable list, if the block is not
2753 * dirty the block is moved from the cached list to the writeable list
2754 * without creating a copy.
2755 *
2756 * During a transaction blocks from the writeable list take precedence
2757 * over the copy of the same block from the cached list.
2758 *
2759 * During a rollback all blocks from the writeable list are discarded,
2760 * thus reverting the file to the state before the beginning of the
2761 * transaction.
2762 *
2763 * During a commit all blocks are moved from the writeable list to the
2764 * cached list.
2765 */
2766
2767 /*
2768 * The following two procedures are the only ones that 'know' the layout
2769 * of a the data of a block in the file
2770 */
pblDataToBlock(PBLBLOCK_t * block)2771 static void pblDataToBlock( PBLBLOCK_t * block )
2772 {
2773 block->data[ 0 ] = block->level;
2774
2775 pbl_LongToBuf ( &( block->data[ 1 ]), block->nblock );
2776 pbl_LongToBuf ( &( block->data[ 5 ]), block->pblock );
2777 pbl_ShortToBuf( &( block->data[ 9 ]), block->nentries );
2778 pbl_ShortToBuf( &( block->data[ 11 ]), block->free );
2779 }
2780
pblBlockToData(PBLBLOCK_t * block)2781 static void pblBlockToData( PBLBLOCK_t * block )
2782 {
2783 block->level = block->data[ 0 ];
2784
2785 block->nblock = pbl_BufToLong ( &( block->data[ 1 ]));
2786 block->pblock = pbl_BufToLong ( &( block->data[ 5 ]));
2787 block->nentries = pbl_BufToShort( &( block->data[ 9 ]));
2788 block->free = pbl_BufToShort( &( block->data[ 11 ]));
2789 }
2790
2791 /*
2792 * release the cached items of a block
2793 */
pblBlockCachedItemsRelease(PBLBLOCK_t * block)2794 static void pblBlockCachedItemsRelease( PBLBLOCK_t * block )
2795 {
2796 unsigned int i;
2797 PBL_CACHED_ITEM_t * cachedItem;
2798
2799 for( i = 0; i < PBL_CACHED_ITEMS_PER_BLOCK; i++ )
2800 {
2801 cachedItem = block->cachedItems[ i ];
2802 if( cachedItem )
2803 {
2804 if( cachedItem->key )
2805 {
2806 PBL_FREE( cachedItem->key );
2807 }
2808 PBL_FREE( cachedItem );
2809 block->cachedItems[ i ] = 0;
2810 }
2811
2812 if( i > block->maxItemCacheIndex )
2813 {
2814 break;
2815 }
2816 }
2817 block->maxItemCacheIndex = 0;
2818 }
2819
2820 /*
2821 * release all memory blocks of a file
2822 */
pblBlocksRelease(int bf)2823 static void pblBlocksRelease( int bf )
2824 {
2825 PBLBLOCK_t * block;
2826
2827 /*
2828 * all blocks that were belonging to the file are marked unused
2829 */
2830 for( block = blockListHead; block; block = block->next )
2831 {
2832 if( block->bf == bf )
2833 {
2834 pblBlockHashRemove( block->blockno, block->bf );
2835 pblBlockCachedItemsRelease( block );
2836
2837 block->bf = -1;
2838 block->filesettag = NULL;
2839 }
2840 }
2841 return;
2842 }
2843
2844
pblBlockWrite(PBLBLOCK_t * block)2845 static int pblBlockWrite( PBLBLOCK_t * block )
2846 {
2847 long rc;
2848
2849 /*
2850 * prepare the block data for writing
2851 */
2852 pblDataToBlock( block );
2853
2854 /*
2855 * write the block to the big file
2856 */
2857 rc = pbf_blockwrite( block->bf, block->blockno, block->data );
2858 if( rc < 0 )
2859 {
2860 block->bf = -1;
2861 block->filesettag = NULL;
2862 pbl_errno = PBL_ERROR_WRITE;
2863 return( -1 );
2864 }
2865
2866 return( 0 );
2867 }
2868
pblBlockFlush(int bf,int release)2869 static int pblBlockFlush( int bf, int release )
2870 {
2871 PBLBLOCK_t * block;
2872 PBLBLOCK_t * tmp;
2873
2874 for( tmp = blockListHead; tmp; )
2875 {
2876 /*
2877 * move through the list of blocks before handling this one
2878 */
2879 block = tmp;
2880 tmp = tmp->next;
2881
2882 if( block->bf != bf )
2883 {
2884 continue;
2885 }
2886
2887 /*
2888 * if a file set tag is set for the block we flush
2889 * all blocks having the same tag set
2890 */
2891 if( block->dirty && block->filesettag )
2892 {
2893 PBLBLOCK_t * b;
2894
2895 /*
2896 * run through all blocks on all files in the set and write them
2897 */
2898 for( b = blockListHead; b; b = b->next )
2899 {
2900 if( b->dirty && b->bf >= 0
2901 && ( block->filesettag == b->filesettag ))
2902 {
2903 if( pblBlockWrite( b ))
2904 {
2905 pblBlocksRelease( b->bf );
2906 break;
2907 }
2908 else
2909 {
2910 b->dirty = 0;
2911 }
2912 }
2913 }
2914 }
2915
2916 if( block->dirty )
2917 {
2918 if( pblBlockWrite( block ))
2919 {
2920 /*
2921 * this write always is a rewrite of an existing block
2922 * therefore a write error is a strange condition,
2923 * we unlink all blocks from the file
2924 * most likely the file is inconsistent after that !!!!
2925 */
2926 pblBlocksRelease( bf );
2927 return( -1 );
2928 }
2929 else
2930 {
2931 block->dirty = 0;
2932 }
2933 }
2934
2935 if( release )
2936 {
2937 pblBlockHashRemove( block->blockno, block->bf );
2938 pblBlockCachedItemsRelease( block );
2939
2940 block->bf = -1;
2941 block->filesettag = NULL;
2942
2943 /*
2944 * put the block to the end of the LRU list
2945 */
2946 if( block != blockListTail )
2947 {
2948 PBL_LIST_UNLINK( blockListHead, blockListTail,
2949 block, next, prev );
2950 PBL_LIST_APPEND( blockListHead, blockListTail,
2951 block, next, prev );
2952 }
2953 }
2954 }
2955 return( 0 );
2956 }
2957
pblBlockGetVictim(PBLKFILE_t * file)2958 static PBLBLOCK_t * pblBlockGetVictim( PBLKFILE_t * file )
2959 {
2960 int rc;
2961 PBLBLOCK_t * block;
2962
2963 /*
2964 * if we have not exceeded the number of blocks we can have at most
2965 * or of the last block in the LRU chain is dirty and we are updating
2966 */
2967 if(( pblnblocks < 8 + ( pblblocksperfile * pblnfiles ) )
2968 ||( blockListTail && blockListTail->dirty
2969 && blockListTail->bf != -1 && file->writeableListHead ))
2970 {
2971 block = (PBLBLOCK_t *)pbl_malloc0( "pblBlockGetVictim BLOCK", sizeof( PBLBLOCK_t ));
2972 if( !block )
2973 {
2974 return( ( PBLBLOCK_t * ) 0 );
2975 }
2976 pblnblocks++;
2977 PBL_LIST_PUSH( blockListHead, blockListTail, block, next, prev );
2978 }
2979 else
2980 {
2981 /*
2982 * we reuse the last block in the LRU chain
2983 */
2984 if( blockListTail )
2985 {
2986 if( blockListTail->bf != -1 )
2987 {
2988 /*
2989 * flush the block to disk if it is dirty
2990 */
2991 if( blockListTail->dirty )
2992 {
2993 rc = pblBlockFlush( blockListTail->bf, 0 );
2994 if( rc )
2995 {
2996 return( ( PBLBLOCK_t * ) 0 );
2997 }
2998 }
2999
3000 /*
3001 * remove the reference to the block from the hash table
3002 */
3003 pblBlockHashRemove( blockListTail->blockno, blockListTail->bf );
3004 }
3005
3006 if(( block = blockListTail ))
3007 {
3008 PBL_LIST_UNLINK( blockListHead, blockListTail,
3009 block, next, prev );
3010 PBL_LIST_PUSH( blockListHead, blockListTail,
3011 block, next, prev );
3012 }
3013 }
3014 else
3015 {
3016 pbl_errno = PBL_ERROR_PROGRAM;
3017 return( 0 );
3018 }
3019
3020 pblBlockCachedItemsRelease( block );
3021 }
3022
3023 block->parentblock = -1;
3024 block->parentindex = -1;
3025 block->dirty = 0;
3026 block->bf = -1;
3027 block->filesettag = NULL;
3028
3029 return( block );
3030 }
3031
pblBlockFind(PBLKFILE_t * file,long blockno)3032 static PBLBLOCK_t * pblBlockFind( PBLKFILE_t * file, long blockno )
3033 {
3034 PBLBLOCK_t * block;
3035
3036 /*
3037 * check if the block is in the LRU list of writeable blocks
3038 */
3039 for( block = file->writeableListHead; block; block = block->next )
3040 {
3041 if(( block->blockno == blockno )
3042 &&( block->bf == file->bf ))
3043 {
3044 /*
3045 * the block is already there, make it the first of the LRU chain
3046 */
3047 if( block != file->writeableListHead )
3048 {
3049 PBL_LIST_UNLINK( file->writeableListHead,
3050 file->writeableListTail, block, next, prev );
3051 PBL_LIST_PUSH( file->writeableListHead,
3052 file->writeableListTail, block, next, prev );
3053 }
3054
3055 return( block );
3056 }
3057 }
3058
3059 /*
3060 * check if the block is the head of the LRU list of blocks cached
3061 */
3062 if( blockListHead
3063 && blockListHead->blockno == blockno
3064 && blockListHead->bf == file->bf )
3065 {
3066 return( blockListHead );
3067 }
3068
3069 /*
3070 * lookup the block in the LRU list of blocks cached
3071 */
3072 block = pblBlockHashFind( blockno, file->bf );
3073 if( block )
3074 {
3075 /*
3076 * the block is there, make it the first of the LRU chain
3077 */
3078 if( block != blockListHead )
3079 {
3080 PBL_LIST_UNLINK( blockListHead, blockListTail, block, next, prev );
3081 PBL_LIST_PUSH( blockListHead, blockListTail, block, next, prev );
3082 }
3083
3084 return( block );
3085 }
3086
3087 return( 0 );
3088 }
3089
pblBlockGet(PBLKFILE_t * file,long blockno)3090 static PBLBLOCK_t * pblBlockGet( PBLKFILE_t * file, long blockno )
3091 {
3092 PBLBLOCK_t * block;
3093 long rc;
3094
3095 /*
3096 * check if block is in memory
3097 */
3098 block = pblBlockFind( file, blockno );
3099 if( block )
3100 {
3101 return( block );
3102 }
3103
3104 /*
3105 * block is not in memory, we have to load it; get an empty block
3106 */
3107 block = pblBlockGetVictim( file );
3108 if( !block )
3109 {
3110 return( block );
3111 }
3112
3113 /*
3114 * read the data from file
3115 */
3116 rc = pbf_blockread( file->bf, blockno, block->data );
3117 if( rc < 0 )
3118 {
3119 return( ( PBLBLOCK_t * ) 0 );
3120 }
3121
3122 /*
3123 * block has been read successfully, so it belongs to this file from now on
3124 */
3125 pblBlockToData( block );
3126
3127 block->blockno = blockno;
3128 block->bf = file->bf;
3129 block->filesettag = file->filesettag;
3130
3131 /*
3132 * insert the reference into the hash table
3133 */
3134 if( pblBlockHashInsert( block->blockno, block->bf, block ) )
3135 {
3136 pbl_errno = PBL_ERROR_PROGRAM;
3137 return( 0 );
3138 }
3139 return( block );
3140 }
3141
3142 /*
3143 * get a version of block we can write to to the writeable list of the file
3144 */
pblBlockGetWriteable(PBLKFILE_t * file,long blockno)3145 static PBLBLOCK_t * pblBlockGetWriteable( PBLKFILE_t * file, long blockno )
3146 {
3147 PBLBLOCK_t * newblock;
3148 PBLBLOCK_t * block;
3149
3150 /*
3151 * get the block to memory
3152 */
3153 block = pblBlockGet( file, blockno );
3154 if( !block || block->writeable )
3155 {
3156 return( block );
3157 }
3158
3159 if( !block->dirty )
3160 {
3161 /*
3162 * move the block over to the writeable list
3163 */
3164 pblnblocks--;
3165 PBL_LIST_UNLINK( blockListHead, blockListTail, block, next, prev );
3166 pblBlockHashRemove( block->blockno, block->bf );
3167
3168 block->writeable = 1;
3169 PBL_LIST_PUSH( file->writeableListHead,
3170 file->writeableListTail, block, next, prev );
3171
3172 return( block );
3173 }
3174
3175 /*
3176 * create a copy of the block in the writeable block list
3177 */
3178 newblock = pbl_memdup( "pblBlockGetWriteable block",
3179 block, sizeof( *block ) );
3180 if( !newblock )
3181 {
3182 return( newblock );
3183 }
3184
3185 newblock->writeable = 1;
3186 PBL_LIST_PUSH( file->writeableListHead, file->writeableListTail,
3187 newblock, next, prev );
3188
3189 /*
3190 * clear the references of the block to its cached items
3191 */
3192 memset( block->cachedItems, 0, sizeof( block->cachedItems ));
3193 block->maxItemCacheIndex = 0;
3194
3195 return( newblock );
3196 }
3197
pblBlockFree(PBLKFILE_t * file,long blockno)3198 static int pblBlockFree( PBLKFILE_t * file, long blockno )
3199 {
3200 PBLBLOCK_t * rootblock;
3201 PBLBLOCK_t * block;
3202 PBLBLOCK_t * nblock = 0;
3203 PBLBLOCK_t * pblock = 0;
3204
3205 /*
3206 * get the root block to memory
3207 */
3208 rootblock = pblBlockGetWriteable( file, 0 );
3209 if( !rootblock )
3210 {
3211 return( -1 );
3212 }
3213
3214 /*
3215 * read the block to be freed
3216 */
3217 block = pblBlockGetWriteable( file, blockno );
3218 if( !block )
3219 {
3220 return( -1 );
3221 }
3222
3223 /*
3224 * read the previous and next block if they exists
3225 */
3226 if( block->nblock )
3227 {
3228 nblock = pblBlockGetWriteable( file, block->nblock );
3229 if( !nblock )
3230 {
3231 return( -1 );
3232 }
3233 }
3234
3235 if( block->pblock )
3236 {
3237 pblock = pblBlockGetWriteable( file, block->pblock );
3238 if( !pblock )
3239 {
3240 return( -1 );
3241 }
3242 }
3243
3244 if( nblock )
3245 {
3246 nblock->pblock = block->pblock;
3247 nblock->dirty = 1;
3248 }
3249
3250 if( pblock )
3251 {
3252 pblock->nblock = block->nblock;
3253 pblock->dirty = 1;
3254 }
3255
3256 pblBlockCachedItemsRelease( block );
3257
3258 /*
3259 * set the values of the free block
3260 */
3261 block->level = 254;
3262 block->nblock = rootblock->pblock;
3263
3264 /*
3265 * blocks freed always have their predecessor set to 0
3266 */
3267 block->pblock = 0;
3268 block->nentries = 0;
3269 block->free = PBLHEADERSIZE; /* offset of first free byte */
3270
3271 memset( block->data, 0, PBLDATASIZE );
3272
3273 block->dirty = 1;
3274
3275 /*
3276 * set the link from the rootblock to the block
3277 */
3278 rootblock->pblock = blockno;
3279 rootblock->dirty = 1;
3280
3281 return( 0 );
3282 }
3283
pblBlockConcat(PBLKFILE_t * file,PBLBLOCK_t * block,PBLBLOCK_t * from,unsigned char * key,unsigned int keylen)3284 static int pblBlockConcat(
3285 PBLKFILE_t * file,
3286 PBLBLOCK_t * block,
3287 PBLBLOCK_t * from,
3288 unsigned char * key,
3289 unsigned int keylen
3290 )
3291 {
3292 PBLBLOCK_t tmpblock;
3293 unsigned char predkey[ PBLKEYLENGTH ];
3294 unsigned int predkeylen = 0;
3295 PBLITEM_t item;
3296 int rc;
3297 unsigned int i;
3298 int nentries;
3299
3300 if( !block->writeable || !from->writeable )
3301 {
3302 pbl_errno = PBL_ERROR_PROGRAM;
3303 return( -1 );
3304 }
3305
3306 /*
3307 * read the last item of left block
3308 */
3309 nentries = block->nentries;
3310 if( block->nentries > 0 )
3311 {
3312 pblItemGet( block, block->nentries - 1, &item );
3313
3314 predkeylen = item.keylen;
3315 if( predkeylen )
3316 {
3317 pbl_memlcpy( predkey, sizeof( predkey ), item.key, predkeylen );
3318 }
3319 }
3320
3321 /*
3322 * create a local copy to concatenate to
3323 */
3324 tmpblock = *block;
3325
3326 /*
3327 * copy all items to be merged to the temporary block
3328 */
3329 for( i = 0; i < from->nentries; i++ )
3330 {
3331 pblItemGet( from, i, &item );
3332
3333 /*
3334 * the first item can have an empty key, if so we use
3335 * the key given as parameter
3336 */
3337 if( i == 0 && keylen > 0 && item.keylen < 1 )
3338 {
3339 item.key = key;
3340 item.keylen = keylen;
3341 }
3342 rc = pblItemAppend( &tmpblock, predkey, predkeylen, &item );
3343 if( rc )
3344 {
3345 if( pbl_errno == PBL_ERROR_NOFIT )
3346 {
3347 pbl_errno = 0;
3348 return( 0 );
3349 }
3350
3351 return( rc );
3352 }
3353
3354 predkeylen = item.keylen;
3355 if( predkeylen > 0 )
3356 {
3357 pbl_memlcpy( predkey, sizeof( predkey ), item.key, predkeylen );
3358 }
3359 }
3360
3361 /*
3362 * copy the values back to our original block
3363 */
3364 block->nentries = tmpblock.nentries;
3365 block->free = tmpblock.free;
3366 memcpy( block->data, tmpblock.data, PBLDATASIZE );
3367
3368 block->dirty = 1;
3369
3370 /*
3371 * change values to the current record if they point to the right block
3372 */
3373 if( file->blockno == from->blockno )
3374 {
3375 /*
3376 * set the current record values to the left block
3377 */
3378 file->blockno = block->blockno;
3379 file->index += nentries;
3380 }
3381
3382 return( 1 );
3383 }
3384
pblBlockAppend(PBLKFILE_t * file,int level,long nblock,long pblock)3385 static long pblBlockAppend(
3386 PBLKFILE_t * file,
3387 int level,
3388 long nblock,
3389 long pblock
3390 )
3391 {
3392 PBLBLOCK_t * rootblock = 0;
3393 PBLBLOCK_t * block = 0;
3394 long freeblockno = 0;
3395
3396 /*
3397 * if nblock is 1, we are called to create the first block of a file
3398 * no need to try to read any block of the file
3399 */
3400 if( nblock != 1 )
3401 {
3402 /*
3403 * get the root block to memory
3404 */
3405 rootblock = pblBlockGetWriteable( file, 0 );
3406 if( !rootblock )
3407 {
3408 pbl_errno = PBL_ERROR_BAD_FILE;
3409 return( -1 );
3410 }
3411
3412 /*
3413 * read block number of first free block of file
3414 */
3415 freeblockno = rootblock->pblock;
3416 if( freeblockno )
3417 {
3418 /*
3419 * read the free block
3420 */
3421 block = pblBlockGetWriteable( file, freeblockno );
3422 if( block )
3423 {
3424 if( block->level != 254 )
3425 {
3426 pbl_errno = PBL_ERROR_BAD_FILE;
3427 return( -1 );
3428 }
3429
3430 /*
3431 * set the next free block to the rootblock
3432 */
3433 rootblock->pblock = block->nblock;
3434 rootblock->dirty = 1;
3435 }
3436 else
3437 {
3438 pbl_errno = PBL_ERROR_BAD_FILE;
3439 return( -1 );
3440 }
3441 }
3442 }
3443
3444 if( !block )
3445 {
3446 PBLBLOCK_t newblock;
3447
3448 /*
3449 * init the new block
3450 */
3451 memset( &newblock, 0, sizeof( newblock ));
3452
3453 /*
3454 * add a free block
3455 */
3456 newblock.level = ( char ) 254 & 0xff;
3457
3458 /*
3459 * init new block
3460 */
3461 newblock.nblock = nblock;
3462 newblock.pblock = pblock;
3463 newblock.free = PBLHEADERSIZE;
3464
3465 /*
3466 * prepare the new block for writing
3467 */
3468 pblDataToBlock( &newblock );
3469
3470 /*
3471 * append a new block to the file
3472 */
3473 freeblockno = pbf_blockappend( file->bf, newblock.data );
3474 if( freeblockno < 0 )
3475 {
3476 pbl_errno = PBL_ERROR_BAD_FILE;
3477 return( -1 );
3478 }
3479
3480 /*
3481 * read the free block
3482 */
3483 block = pblBlockGetWriteable( file, freeblockno );
3484 if( !block || block->level != 254 )
3485 {
3486 pbl_errno = PBL_ERROR_BAD_FILE;
3487 return( -1 );
3488 }
3489 }
3490
3491 /*
3492 * init the new block
3493 */
3494 memset( block->data, 0, PBLDATASIZE );
3495
3496 block->level = ( char ) level & 0xff;
3497 block->nentries = 0;
3498 block->nblock = nblock;
3499 block->pblock = pblock;
3500 block->free = PBLHEADERSIZE;
3501 block->dirty = 1;
3502
3503 return( block->blockno );
3504 }
3505
pblBlockMerge(PBLKFILE_t * file,long parentblockno,int parentindex,long blockno)3506 static int pblBlockMerge(
3507 PBLKFILE_t * file,
3508 long parentblockno,
3509 int parentindex,
3510 long blockno
3511 )
3512 {
3513 int merged = 0;
3514 PBLBLOCK_t * parentblock;
3515 PBLBLOCK_t * block;
3516 PBLBLOCK_t * peerblock;
3517 PBLITEM_t item;
3518 int rc;
3519 unsigned char key[ PBLKEYLENGTH ];
3520 unsigned int keylen;
3521
3522 /*
3523 * read the parentblock
3524 */
3525 parentblock = pblBlockGet( file, parentblockno );
3526 if( !parentblock )
3527 {
3528 /*
3529 * no error because the parent block might have been split
3530 */
3531 pbl_errno = 0;
3532 return( merged );
3533 }
3534
3535 /*
3536 * check the parentindex because the parentblock might have been
3537 * split without the child knowing about it
3538 */
3539 if( parentindex >= (int)parentblock->nentries )
3540 {
3541 return( merged );
3542 }
3543
3544 /*
3545 * read the item pointing to blockno
3546 */
3547 if( pblItemGet( parentblock, parentindex, &item ))
3548 {
3549 return( -1 );
3550 }
3551
3552 /*
3553 * check the pointer to the child, because the parentblock might have been
3554 * split without the child knowing about it
3555 */
3556 if( blockno != item.datablock )
3557 {
3558 return( merged );
3559 }
3560
3561 /*
3562 * if there is a block to the left
3563 */
3564 while( parentindex > 0 )
3565 {
3566 /*
3567 * check the parentindex because the parentblock might have been
3568 * split without the child knowing about it
3569 */
3570 if( parentindex >= (int)parentblock->nentries )
3571 {
3572 return( merged );
3573 }
3574
3575 /*
3576 * read the item pointing to blockno
3577 */
3578 if( pblItemGet( parentblock, parentindex, &item ))
3579 {
3580 return( -1 );
3581 }
3582
3583 /*
3584 * set the pointer to the child
3585 */
3586 blockno = item.datablock;
3587
3588 /*
3589 * read the child block
3590 */
3591 block = pblBlockGet( file, blockno );
3592 if( !block )
3593 {
3594 return( -1 );
3595 }
3596
3597 /*
3598 * read the item pointing to the peer
3599 */
3600 if( pblItemGet( parentblock, parentindex - 1, &item ))
3601 {
3602 return( -1 );
3603 }
3604
3605 /*
3606 * read the peerblock
3607 */
3608 peerblock = pblBlockGet( file, item.datablock );
3609 if( !peerblock )
3610 {
3611 return( -1 );
3612 }
3613
3614 /*
3615 * see how much empty space we have on the two blocks
3616 */
3617 rc = PBLINDEXBLOCKNFREE( block ) + PBLINDEXBLOCKNFREE( peerblock );
3618 if( rc < ( PBLDATASIZE + 6 + PBLKEYLENGTH ))
3619 {
3620 /*
3621 * we do not merge
3622 */
3623 break;
3624 }
3625
3626 /*
3627 * read the child block
3628 */
3629 block = pblBlockGetWriteable( file, blockno );
3630 if( !block )
3631 {
3632 return( -1 );
3633 }
3634
3635 /*
3636 * read the peerblock
3637 */
3638 peerblock = pblBlockGetWriteable( file, item.datablock );
3639 if( !peerblock )
3640 {
3641 return( -1 );
3642 }
3643
3644 /*
3645 * read the first key of the right block to merge
3646 */
3647 parentblock = pblBlockGetWriteable( file, parentblockno );
3648 if( !parentblock )
3649 {
3650 return( -1 );
3651 }
3652
3653 /*
3654 * check the parentindex
3655 */
3656 if( parentindex >= (int)parentblock->nentries )
3657 {
3658 return( merged );
3659 }
3660
3661 /*
3662 * read the item pointing to blockno
3663 */
3664 if( pblItemGet( parentblock, parentindex, &item ))
3665 {
3666 return( -1 );
3667 }
3668
3669 if( item.keylen < 1 )
3670 {
3671 pbl_errno = PBL_ERROR_BAD_FILE;
3672 return( -1 );
3673 }
3674
3675 keylen = item.keylen;
3676 pbl_memlcpy( key, sizeof( key ), item.key, keylen );
3677
3678 /*
3679 * concatenate the two blocks
3680 */
3681 rc = pblBlockConcat( file, peerblock, block, key, keylen );
3682 if( rc < 0 )
3683 {
3684 return( rc );
3685 }
3686 else if( rc == 0 )
3687 {
3688 /*
3689 * we could not merge, break the loop
3690 */
3691 break;
3692 }
3693
3694 /*
3695 * the two blocks were merged
3696 */
3697 merged += 1;
3698
3699 /*
3700 * free the block
3701 */
3702 rc = pblBlockFree( file, blockno );
3703 if( rc )
3704 {
3705 return( rc );
3706 }
3707
3708 rc = pblItemRemove( parentblock, parentindex );
3709 if( rc )
3710 {
3711 return( rc );
3712 }
3713 }
3714
3715 /*
3716 * if there is a block to the left
3717 */
3718 while( parentindex < (int)parentblock->nentries - 1 )
3719 {
3720 /*
3721 * read the item pointing to blockno
3722 */
3723 if( pblItemGet( parentblock, parentindex, &item ))
3724 {
3725 return( -1 );
3726 }
3727
3728 /*
3729 * set the pointer to the child
3730 */
3731 blockno = item.datablock;
3732
3733 /*
3734 * read the child block
3735 */
3736 block = pblBlockGet( file, blockno );
3737 if( !block )
3738 {
3739 return( -1 );
3740 }
3741
3742 /*
3743 * read the item pointing to the peer
3744 */
3745 if( pblItemGet( parentblock, parentindex + 1, &item ))
3746 {
3747 return( -1 );
3748 }
3749
3750 /*
3751 * read the peerblock
3752 */
3753 peerblock = pblBlockGet( file, item.datablock );
3754 if( !peerblock )
3755 {
3756 return( -1 );
3757 }
3758
3759 /*
3760 * see how much empty space we have on the two blocks
3761 */
3762 rc = PBLINDEXBLOCKNFREE( block ) + PBLINDEXBLOCKNFREE( peerblock );
3763 if( rc < ( PBLDATASIZE + 6 + PBLKEYLENGTH ))
3764 {
3765 /*
3766 * we do not merge
3767 */
3768 break;
3769 }
3770
3771 /*
3772 * read the child block
3773 */
3774 block = pblBlockGetWriteable( file, blockno );
3775 if( !block )
3776 {
3777 return( -1 );
3778 }
3779
3780 /*
3781 * read the peerblock
3782 */
3783 blockno = item.datablock;
3784 peerblock = pblBlockGetWriteable( file, blockno );
3785 if( !peerblock )
3786 {
3787 return( -1 );
3788 }
3789
3790 /*
3791 * read the first key of the right block to merge
3792 */
3793 parentblock = pblBlockGetWriteable( file, parentblockno );
3794 if( !parentblock )
3795 {
3796 return( -1 );
3797 }
3798
3799 /*
3800 * check the parentindex
3801 */
3802 if( parentindex >= (int)parentblock->nentries - 1 )
3803 {
3804 return( merged );
3805 }
3806
3807 /*
3808 * read the item pointing to blockno
3809 */
3810 if( pblItemGet( parentblock, parentindex + 1, &item ))
3811 {
3812 return( -1 );
3813 }
3814
3815 if( item.keylen < 1 )
3816 {
3817 pbl_errno = PBL_ERROR_BAD_FILE;
3818 return( -1 );
3819 }
3820
3821 keylen = item.keylen;
3822 pbl_memlcpy( key, sizeof( key ), item.key, keylen );
3823
3824 /*
3825 * concatenate the two blocks
3826 */
3827 rc = pblBlockConcat( file, block, peerblock, key, keylen );
3828 if( rc < 0 )
3829 {
3830 return( rc );
3831 }
3832 else if( rc == 0 )
3833 {
3834 /*
3835 * we could not merge, break the loop
3836 */
3837 break;
3838 }
3839
3840 /*
3841 * the two blocks were merged
3842 */
3843 merged += 1;
3844
3845 /*
3846 * free the block
3847 */
3848 rc = pblBlockFree( file, blockno );
3849 if( rc )
3850 {
3851 return( rc );
3852 }
3853
3854 rc = pblItemRemove( parentblock, parentindex + 1 );
3855 if( rc )
3856 {
3857 return( rc );
3858 }
3859 }
3860
3861 return( merged );
3862 }
3863
3864 /*
3865 * truncate the blocklist to the number of blocks allowed
3866 */
pblBlockListTruncate(void)3867 static int pblBlockListTruncate( void )
3868 {
3869 PBLBLOCK_t * block;
3870 int rc;
3871
3872 /*
3873 * truncate the list of blocks we have in memory
3874 */
3875 while( pblnblocks >= 8 + ( pblblocksperfile * pblnfiles ) )
3876 {
3877 block = blockListTail;
3878 if( !block )
3879 {
3880 pblnblocks = 0;
3881 break;
3882 }
3883
3884 if( block->bf != -1 )
3885 {
3886 if( block->dirty )
3887 {
3888 /*
3889 * if one block of a file is dirty, all blocks are flushed
3890 */
3891 rc = pblBlockFlush( block->bf, 0 );
3892 if( rc )
3893 {
3894 return( rc );
3895 }
3896 }
3897
3898 pblBlockHashRemove( block->blockno, block->bf );
3899 }
3900
3901 PBL_LIST_UNLINK( blockListHead, blockListTail, block, next, prev );
3902
3903 pblBlockCachedItemsRelease( block );
3904
3905 PBL_FREE( block );
3906
3907 pblnblocks--;
3908 }
3909
3910 return( 0 );
3911 }
3912
3913 /**
3914 * change the number of cache blocks used per open key file
3915 *
3916 * the default number is 64, a memory block uses about 4096 bytes of heap memory
3917 *
3918 * @return int rc: the number of blocks used after the call
3919 *
3920 */
3921
pblKfInit(int nblocks)3922 int pblKfInit(
3923 int nblocks /* number of blocks used per open file */
3924 )
3925 {
3926 pbl_errno = 0;
3927
3928 if( nblocks < 1 )
3929 {
3930 return( pblnblocks );
3931 }
3932
3933 if( nblocks < 8 )
3934 {
3935 nblocks = 8;
3936 }
3937
3938 pblblocksperfile = nblocks;
3939
3940 return( pblblocksperfile );
3941 }
3942
3943 /*
3944 * FILE functions
3945 */
pblDataAppend(PBLKFILE_t * file,unsigned char * data,long datalen,long * offset)3946 static long pblDataAppend(
3947 PBLKFILE_t * file,
3948 unsigned char * data,
3949 long datalen,
3950 long * offset
3951 )
3952 {
3953 long blockno;
3954 long returnoffset;
3955 long returnblock;
3956 long diff;
3957 long bytesWritten = 0;
3958 int nbytes;
3959 PBLBLOCK_t * rootblock = 0;
3960 PBLBLOCK_t * datablock = 0;
3961
3962 rootblock = pblBlockGet( file, 0 );
3963 if( !rootblock )
3964 {
3965 return( -1 );
3966 }
3967
3968 /*
3969 * rootblock->nblock always contains the number of the last datablock
3970 */
3971 datablock = pblBlockGetWriteable( file, rootblock->nblock );
3972 if( !datablock )
3973 {
3974 return( -1 );
3975 }
3976
3977 if( datablock->level != 255 )
3978 {
3979 pbl_errno = PBL_ERROR_BAD_FILE;
3980 return( -1 );
3981 }
3982
3983 if( PBLDATABLOCKNFREE( datablock ) > PBLDATABLOCKMAXFREE)
3984 {
3985 pbl_errno = PBL_ERROR_BAD_FILE;
3986 return( -1 );
3987 }
3988
3989 /*
3990 * Since version 1.04, only one data record is stored on a data block,
3991 * if there is some data on the block already, a new empty block
3992 * is appended
3993 */
3994 if( PBLDATABLOCKNFREE( datablock ) < PBLDATABLOCKMAXFREE)
3995 {
3996 /*
3997 * make a new data block
3998 */
3999 blockno = pblBlockAppend( file, -1, 0, datablock->blockno );
4000 if( blockno < 0 )
4001 {
4002 return( -1 );
4003 }
4004
4005 datablock->nblock = blockno;
4006 datablock->dirty = 1;
4007
4008 /*
4009 * get the new datablock to memory
4010 */
4011 datablock = pblBlockGetWriteable( file, blockno );
4012 if( !datablock )
4013 {
4014 return( -1 );
4015 }
4016
4017 /*
4018 * set address to rootblock
4019 */
4020 rootblock = pblBlockGetWriteable( file, 0 );
4021 if( !rootblock )
4022 {
4023 return( -1 );
4024 }
4025
4026 rootblock->nblock = blockno;
4027 rootblock->dirty = 1;
4028 }
4029
4030 returnoffset = datablock->free;
4031 returnblock = datablock->blockno;
4032
4033 while( bytesWritten < datalen )
4034 {
4035 diff = datalen - bytesWritten;
4036 if( diff > PBLDATABLOCKNFREE( datablock ))
4037 {
4038 nbytes = PBLDATABLOCKNFREE( datablock );
4039 }
4040 else
4041 {
4042 nbytes = (( int )( diff % PBLDATASIZE));
4043 }
4044
4045 if( nbytes > 0 )
4046 {
4047 memcpy((void *) &(datablock->data[ datablock->free ]),
4048 (void *) data,
4049 nbytes );
4050 datablock->dirty = 1;
4051 }
4052
4053 bytesWritten += nbytes;
4054 data += nbytes;
4055 datablock->free += nbytes;
4056
4057 if( PBLDATABLOCKNFREE( datablock ) < 1 )
4058 {
4059 /*
4060 * make a new data block
4061 */
4062 blockno = pblBlockAppend( file, -1, 0, datablock->blockno );
4063 if( blockno < 0 )
4064 {
4065 return( -1 );
4066 }
4067
4068 datablock->nblock = blockno;
4069 datablock->dirty = 1;
4070
4071 /*
4072 * get the new datablock to memory
4073 */
4074 datablock = pblBlockGetWriteable( file, blockno );
4075 if( !datablock )
4076 {
4077 return( -1 );
4078 }
4079
4080 /*
4081 * set address to rootblock
4082 */
4083 rootblock = pblBlockGetWriteable( file, 0 );
4084 if( !rootblock )
4085 {
4086 return( -1 );
4087 }
4088
4089 rootblock->nblock = blockno;
4090 rootblock->dirty = 1;
4091 }
4092 }
4093
4094 *offset = returnoffset;
4095
4096 return( returnblock );
4097 }
4098
4099 /*
4100 * Remove a data record from a key file.
4101 *
4102 * Only removes the data record if it is the only data record
4103 * on the data block.
4104 *
4105 * Since 1.04, 4 Nov 2008 23:02:03 CET
4106 */
pblDataRemove(PBLKFILE_t * file,long blockno,long blockoffset,long datalen)4107 static long pblDataRemove(
4108 PBLKFILE_t * file,
4109 long blockno,
4110 long blockoffset,
4111 long datalen
4112 )
4113 {
4114 long diff;
4115 long bytesRemoved = 0;
4116 int nbytes;
4117 PBLBLOCK_t * datablock = (PBLBLOCK_t *) 0;
4118 long nextBlockNo = 0;
4119 long prevBlockNo = -1;
4120
4121 while( bytesRemoved < datalen )
4122 {
4123 datablock = pblBlockGetWriteable( file, blockno );
4124 if( !datablock )
4125 {
4126 return( -1 );
4127 }
4128 nextBlockNo = datablock->nblock;
4129
4130 if( prevBlockNo == -1 )
4131 {
4132 prevBlockNo = datablock->pblock;
4133 }
4134
4135 if( datablock->level != 255 )
4136 {
4137 pbl_errno = PBL_ERROR_BAD_FILE;
4138 return( -1 );
4139 }
4140
4141 /*
4142 * Only data records that start at the beginning
4143 * of a block are removed
4144 */
4145 if( blockoffset != PBLHEADERSIZE)
4146 {
4147 return 0;
4148 }
4149
4150 diff = datalen - bytesRemoved;
4151 if( diff > ( PBLDATASIZE - blockoffset ) )
4152 {
4153 nbytes = PBLDATASIZE - blockoffset;
4154 }
4155 else
4156 {
4157 nbytes = ((int ) ( diff % PBLDATASIZE));
4158 }
4159
4160 if( nbytes > 0 )
4161 {
4162 if( nbytes != PBLDATABLOCKMAXFREE - PBLDATABLOCKNFREE( datablock ))
4163 {
4164 return 0;
4165 }
4166
4167 if( pblBlockFree(file, datablock->blockno))
4168 {
4169 return( -1 );
4170 }
4171 else
4172 {
4173 /*
4174 * If the last of the data blocks is freed,
4175 * we also need to update the root block
4176 */
4177 PBLBLOCK_t * rootblock = pblBlockGetWriteable( file, 0 );
4178 if( !rootblock )
4179 {
4180 return( -1 );
4181 }
4182
4183 if( rootblock->nblock == blockno)
4184 {
4185 rootblock->nblock = prevBlockNo;
4186 rootblock->dirty = 1;
4187 }
4188 }
4189
4190 bytesRemoved += nbytes;
4191 }
4192
4193 if( bytesRemoved < datalen )
4194 {
4195 /*
4196 * Set offset of next block and set blockoffset to beginning of
4197 * data
4198 */
4199 blockno = nextBlockNo;
4200 if( blockno < 1 )
4201 {
4202 pbl_errno = PBL_ERROR_BAD_FILE;
4203 return( -1 );
4204 }
4205
4206 blockoffset = PBLHEADERSIZE;
4207 }
4208 }
4209
4210 return( bytesRemoved );
4211 }
4212
4213 /**
4214 * create a key file with the name specified by path.
4215 *
4216 * a file set tag can be attached to the file,
4217 * if a file having a non NULL file set tag is flushed
4218 * to disk all files having the same file set tag attached
4219 * are flushed as well.
4220 *
4221 * <P>
4222 * <B>RESTRICTIONS</B>:
4223 * <BR> - the file to create must not exists.
4224 * <BR> - the current record of the file will not be set
4225 *
4226 * @return pblKeyFile_t * retptr == NULL: an error occured, see pbl_errno
4227 * @return pblKeyFile_t * retptr != NULL: a pointer to a key file descriptor
4228 */
4229
pblKfCreate(char * path,void * filesettag)4230 pblKeyFile_t * pblKfCreate(
4231 char * path, /** path of file to create */
4232 void * filesettag /** file set tag, for flushing multiple files consistently */
4233 )
4234 {
4235 pblKeyFile_t * k = NULL;
4236 PBLKFILE_t * kf = NULL;
4237 PBLBLOCK_t * rootblock = NULL;
4238 PBLITEM_t item;
4239 int fh;
4240 int bf;
4241 long blockno;
4242 int rc;
4243
4244 pbl_errno = 0;
4245
4246 /*
4247 * make sure we have one filehandle for the create, close one file
4248 */
4249 if( pbf_ft_tail )
4250 {
4251 pbf_fh_close( pbf_ft_tail->bf, pbf_ft_tail->n );
4252 }
4253
4254 /*
4255 * do a exclusive create open, make sure the file does not exist yet
4256 */
4257 fh = open( path, O_CREAT | O_EXCL | O_BINARY | O_RDWR, S_IREAD | S_IWRITE );
4258 if( -1 == fh )
4259 {
4260 pbl_errno = PBL_ERROR_CREATE;
4261 return( 0 );
4262 }
4263 close( fh );
4264
4265 /*
4266 * open the file
4267 */
4268 bf = pbf_open( path, 1, PBLFILEBLOCKS, PBLDATASIZE );
4269 if( bf < 0 )
4270 {
4271 return( 0 );
4272 }
4273
4274 /*
4275 * get and init file structure
4276 */
4277 kf = (PBLKFILE_t *)pbl_malloc0( "pblKfCreate FILE", sizeof( PBLKFILE_t ));
4278 if( !kf )
4279 {
4280 goto errout;
4281 }
4282
4283 /*
4284 * we have a key file set the return value
4285 */
4286 k = ( pblKeyFile_t * )kf;
4287 kf->magic = pblkf_c_id;
4288 kf->bf = bf;
4289 kf->update = 1;
4290 kf->filesettag = filesettag;
4291
4292 /*
4293 * start a transaction on the file
4294 */
4295 pblKfStartTransaction( k );
4296
4297 /*
4298 * make the root block, next offset is first data block
4299 */
4300 blockno = pblBlockAppend( kf, 0, 1, 0 );
4301 if( blockno < 0 )
4302 {
4303 goto errout;
4304 }
4305
4306 rootblock = pblBlockGet( kf, 0 );
4307 if( !rootblock )
4308 {
4309 goto errout;
4310 }
4311
4312 /*
4313 * make the first data block
4314 */
4315 blockno = pblBlockAppend( kf, -1, 0, 0 );
4316 if( blockno != 1 )
4317 {
4318 goto errout;
4319 }
4320
4321 /*
4322 * init the first item we insert into each file
4323 */
4324 item.level = 0;
4325 item.key = ( unsigned char * ) 0;
4326 item.keylen = 0;
4327 item.keycommon = 0;
4328 item.datalen = strlen( magic ) + 1;
4329 item.data = (unsigned char *)magic;
4330
4331 /*
4332 * append the magic string as first data item
4333 */
4334 if( item.datalen > PBLDATALENGTH )
4335 {
4336 item.datablock = pblDataAppend( kf, item.data,
4337 item.datalen, &item.dataoffset );
4338 if( item.datablock < 1 )
4339 {
4340 goto errout;
4341 }
4342 item.data = 0;
4343 }
4344
4345 /*
4346 * insert the first item into the root block
4347 */
4348 rootblock = pblBlockGetWriteable( kf, 0 );
4349 if( !rootblock )
4350 {
4351 goto errout;
4352 }
4353
4354 rc = pblItemAdd( kf, rootblock, &item );
4355 if( rc )
4356 {
4357 goto errout;
4358 }
4359
4360 /*
4361 * no current record yet
4362 */
4363 kf->blockno = -1;
4364 kf->index = -1;
4365
4366 /*
4367 * commit the changes
4368 */
4369 if( pblKfCommit( k, 0 ))
4370 {
4371 goto errout;
4372 }
4373
4374 if( pblBlockFlush( kf->bf, 0 ))
4375 {
4376 goto errout;
4377 }
4378
4379 pblnfiles++;
4380
4381 return( k );
4382
4383 errout:
4384
4385 if( kf )
4386 {
4387 if( kf->bf >= 0 )
4388 {
4389 pblKfCommit( k, 1 );
4390 }
4391 PBL_FREE( kf );
4392 }
4393
4394 if( -1 != bf )
4395 {
4396 pblBlocksRelease( bf );
4397 close( fh );
4398 unlink( path );
4399 }
4400
4401 return( 0 );
4402 }
4403
4404 /**
4405 * open an existing key file
4406 *
4407 * if update is 0, the file is opened for read access only,
4408 * if update is not 0 the file is opened for reading and writing
4409 *
4410 * a file set tag can be attached to the file,
4411 * if a file having a non NULL file set tag is flushed
4412 * to disk all files having the same file set tag attached
4413 * are flushed as well.
4414 *
4415 * <P>
4416 * <B>RESTRICTIONS</B>:
4417 * <BR> - the file must exist already
4418 * <BR> - the current record of the file will not be set
4419 *
4420 * @return pblKeyFile_t * retptr == NULL: an error occured, see pbl_errno
4421 * @return pblKeyFile_t * retptr != NULL: a pointer to a key file descriptor
4422 */
4423
pblKfOpen(char * path,int update,void * filesettag)4424 pblKeyFile_t * pblKfOpen(
4425 char * path, /** path of file to create */
4426 int update, /** flag: should file be opened for update? */
4427 void * filesettag /** file set tag, for flushing multiple files consistently */
4428 )
4429 {
4430 PBLKFILE_t * kf;
4431 PBLBLOCK_t * datablock;
4432 int bf;
4433
4434 pbl_errno = 0;
4435
4436 bf = pbf_open( path, update, PBLFILEBLOCKS, PBLDATASIZE );
4437 if( -1 == bf )
4438 {
4439 return( 0 );
4440 }
4441
4442 /*
4443 * get and init file structure
4444 */
4445 kf = (PBLKFILE_t *)pbl_malloc0( "pblKfOpen FILE", sizeof( PBLKFILE_t ));
4446 if( !kf )
4447 {
4448 pbf_close( bf );
4449 return( 0 );
4450 }
4451 kf->magic = pblkf_c_id;
4452 kf->bf = bf;
4453 kf->update = update;
4454 kf->filesettag = filesettag;
4455 kf->blockno = -1;
4456 kf->index = -1;
4457
4458 /*
4459 * read and check the first datablock
4460 */
4461 datablock = pblBlockGet( kf, 1 );
4462 if( !datablock || ( datablock->level != 255 ))
4463 {
4464 pblBlocksRelease( bf );
4465 pbf_close( bf );
4466 PBL_FREE( kf );
4467 pbl_errno = PBL_ERROR_BAD_FILE;
4468 return( 0 );
4469 }
4470
4471 pblnfiles++;
4472
4473 return( ( pblKeyFile_t * ) kf );
4474 }
4475
4476 /**
4477 * close a key file
4478 *
4479 * all changes are flushed to disk before,
4480 * all memory allocated for the file is released.
4481 *
4482 * @return int rc == 0: call went ok, file is closed
4483 * @return int rc != 0: some error, see pbl_errno
4484 */
4485
pblKfClose(pblKeyFile_t * k)4486 int pblKfClose(
4487 pblKeyFile_t * k /** key file to close */
4488 )
4489 {
4490 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4491 int rc = 0;
4492
4493 pbl_errno = 0;
4494
4495 if( kf->update )
4496 {
4497 rc = pblBlockFlush( kf->bf, 1 );
4498 }
4499 else
4500 {
4501 pblBlocksRelease( kf->bf );
4502 }
4503
4504 pbf_close( kf->bf );
4505 PBL_FREE( kf );
4506
4507 pblnfiles--;
4508
4509 if( pblBlockListTruncate())
4510 {
4511 rc = -1;
4512 }
4513
4514 return( rc );
4515 }
4516
4517 /**
4518 * set an application specific compare function for the keys of a key file
4519 *
4520 * an application specific compare function can be used in order to
4521 * implement special orderings of the values of an index, e.g.
4522 * because of the use of european "umlauts" in names
4523 *
4524 * the default compare function is the c-library memcmp function
4525 * the keycompare function should behave like memcmp
4526 *
4527 * @return void
4528 */
4529
pblKfSetCompareFunction(pblKeyFile_t * k,int (* keycompare)(void * left,size_t llen,void * right,size_t rlen))4530 void pblKfSetCompareFunction(
4531 pblKeyFile_t * k, /** key file to set compare function for */
4532 int ( *keycompare ) /** compare function to set */
4533 (
4534 void* left, /** "left" buffer for compare */
4535 size_t llen, /** length of that buffer */
4536 void* right, /** "right" buffer for compare */
4537 size_t rlen /** length of that buffer */
4538 )
4539 )
4540 {
4541 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4542
4543 kf->keycompare = keycompare;
4544 }
4545
4546 /**
4547 * flush a key file
4548 *
4549 * all changes are flushed to disk,
4550 *
4551 * @return int rc == 0: call went ok
4552 * @return int rc != 0: some error, see pbl_errno
4553 */
4554
pblKfFlush(pblKeyFile_t * k)4555 int pblKfFlush(
4556 pblKeyFile_t * k /** key file to flush */
4557 )
4558 {
4559 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4560 int rc;
4561
4562 pbl_errno = 0;
4563
4564 rc = pblBlockFlush( kf->bf, 0 );
4565 if( rc )
4566 {
4567 return( rc );
4568 }
4569
4570 rc = pblBlockListTruncate();
4571
4572 return( rc );
4573 }
4574
4575 /**
4576 * commit or rollback changes done during a transaction.
4577 *
4578 * transactions can be nested, if so the commit
4579 * only happens when the outermost transaction
4580 * calls a commit.
4581 *
4582 * the commit only happens to process space buffer cache,
4583 * call \Ref{pblKfFlush}() after \Ref{pblKfCommit}() if you want to
4584 * flush to kernel space buffer cache.
4585 *
4586 * @return int rc == 0: the commit went ok
4587 * @return int rc > 0: a rollback happened, either because the caller
4588 * requested it or because an inner transaction resulted
4589 * in a rollback
4590 * @return int rc < 0: some error, see pbl_errno
4591 */
4592
pblKfCommit(pblKeyFile_t * k,int rollback)4593 int pblKfCommit(
4594 pblKeyFile_t * k, /** key file to commit */
4595 int rollback /** != 0: roll back the changes, == 0: commit the changes */
4596 )
4597 {
4598 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4599 PBLBLOCK_t * block;
4600 PBLBLOCK_t * b;
4601
4602 pbl_errno = 0;
4603
4604 /*
4605 * if there is no transaction active for the file
4606 */
4607 if( !rollback && ( kf->transactions < 1 ))
4608 {
4609 pbl_errno = PBL_ERROR_PROGRAM;
4610 return( -1 );
4611 }
4612 kf->transactions--;
4613
4614 /*
4615 * if a rollback is requested for this commit
4616 */
4617 if( rollback )
4618 {
4619 /*
4620 * remember that at least one rollback is requested for the file
4621 */
4622 kf->rollback = 1;
4623 }
4624
4625 /*
4626 * if there is an outer transaction active for the file
4627 */
4628 if( kf->transactions > 0 )
4629 {
4630 return( kf->rollback );
4631 }
4632
4633 /*
4634 * there is no more transaction active, rollback or commit
4635 */
4636 if( kf->rollback )
4637 {
4638 /*
4639 * release all blocks that were changed without putting
4640 * them back into the blocklist buffer cache
4641 */
4642 while(( block = kf->writeableListTail ))
4643 {
4644 PBL_LIST_UNLINK( kf->writeableListHead, kf->writeableListTail,
4645 block, next, prev );
4646
4647 pblBlockCachedItemsRelease( block );
4648
4649 PBL_FREE( block );
4650 continue;
4651 }
4652
4653 /*
4654 * reset the transaction and the rollback value
4655 */
4656 kf->transactions = 0;
4657 kf->rollback = 0;
4658 return( 1 );
4659 }
4660
4661 /*
4662 * commit the changed blocks
4663 */
4664 while(( block = kf->writeableListTail ))
4665 {
4666 /*
4667 * commit all blocks that were changed by rechaining
4668 * them into the blocklist buffer cache
4669 */
4670 PBL_LIST_UNLINK( kf->writeableListHead, kf->writeableListTail,
4671 block, next, prev );
4672
4673 /*
4674 * find a potential copy of the block in the LRU list
4675 */
4676 b = pblBlockFind( kf, block->blockno );
4677 if( b )
4678 {
4679 /*
4680 * delete the copy from the LRU list
4681 */
4682 PBL_LIST_UNLINK( blockListHead, blockListTail, b, next, prev );
4683
4684 pblBlockCachedItemsRelease( b );
4685
4686 PBL_FREE( b );
4687 }
4688 else
4689 {
4690 /*
4691 * we add a block to the LRU list
4692 */
4693 pblnblocks++;
4694 }
4695
4696 /*
4697 * blocks in the buffer cache are not writeable
4698 */
4699 block->writeable = 0;
4700 PBL_LIST_PUSH( blockListHead, blockListTail, block, next, prev );
4701
4702 /*
4703 * insert or update the reference in the hash table
4704 */
4705 if( pblBlockHashInsert( block->blockno, block->bf, block ) < 0 )
4706 {
4707 pbl_errno = PBL_ERROR_PROGRAM;
4708 return( 0 );
4709 }
4710 }
4711
4712 /*
4713 * reset the transaction and the rollback value
4714 */
4715 kf->transactions = 0;
4716 kf->rollback = 0;
4717
4718 return( 0 );
4719 }
4720
4721 /**
4722 * start a transaction on a key file
4723 *
4724 * transactions can be nested
4725 *
4726 * @return int rc == 0: the transaction was started successfully
4727 * @return int rc > 0: the transaction was started
4728 * but another transaction has resulted in
4729 * a rollback request on the file already
4730 */
4731
pblKfStartTransaction(pblKeyFile_t * k)4732 int pblKfStartTransaction(
4733 pblKeyFile_t * k /** key file to start transaction on */
4734 )
4735 {
4736 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4737 pbl_errno = 0;
4738
4739 /*
4740 * if there is no transaction active for the file
4741 */
4742 if( kf->transactions < 1 )
4743 {
4744 kf->transactions = 1;
4745 kf->rollback = 0;
4746 return( 0 );
4747 }
4748 kf->transactions++;
4749
4750 return( kf->rollback );
4751 }
4752
4753 /**
4754 * save the position of the current record for later restore
4755 *
4756 * @return int rc == 0: the position was saved
4757 * @return int rc < 0: an error, see pbl_errno
4758 */
pblKfSavePosition(pblKeyFile_t * k)4759 int pblKfSavePosition(
4760 pblKeyFile_t * k /** key file to save position for */
4761 )
4762 {
4763 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4764
4765 pbl_errno = 0;
4766
4767 /*
4768 * save the block number and the index
4769 */
4770 kf->saveblockno = kf->blockno;
4771 kf->saveindex = kf->index;
4772
4773 return( 0 );
4774 }
4775
4776 /**
4777 * restore the position of the current record saved by the
4778 * last previous call to \Ref{pblKfSavePosition}().
4779 *
4780 * @return int rc == 0: the position was restored
4781 * @return int rc < 0: an error, see pbl_errno
4782 */
4783
pblKfRestorePosition(pblKeyFile_t * k)4784 int pblKfRestorePosition(
4785 pblKeyFile_t * k /** key file to restore position for */
4786 )
4787 {
4788 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
4789
4790 /*
4791 * restore the block number and the index
4792 */
4793 kf->blockno = kf->saveblockno;
4794 kf->index = kf->saveindex;
4795
4796 return( 0 );
4797 }
4798
4799 /*
4800 * INSERT functions
4801 */
pblItemSave(PBLITEM_t * item)4802 static int pblItemSave( PBLITEM_t * item )
4803 {
4804 PBLITEM_t * newitem = ( PBLITEM_t * ) 0;
4805
4806 newitem = (PBLITEM_t *)pbl_malloc0( "pblItemSave ITEM", sizeof( PBLITEM_t ));
4807 if( !newitem )
4808 {
4809 return( -1 );
4810 }
4811
4812 /*
4813 * save the values of the item
4814 */
4815 *newitem = *item;
4816
4817 /*
4818 * save the key
4819 */
4820 if( newitem->keylen > 0 )
4821 {
4822 newitem->key = pbl_memdup( "pblItemSave item->key",
4823 item->key, newitem->keylen );
4824 if( !newitem->key )
4825 {
4826 PBL_FREE( newitem );
4827 return( -1 );
4828 }
4829 }
4830 else
4831 {
4832 newitem->key = 0;
4833 }
4834
4835 /*
4836 * save the data
4837 */
4838 if( newitem->datalen < 1 || newitem->datalen > PBLDATALENGTH )
4839 {
4840 newitem->data = 0;
4841 }
4842
4843 /*
4844 * push the new item to top of list
4845 */
4846 PBL_LIST_PUSH( itemListHead, itemListTail, newitem, next, prev );
4847
4848 return( 0 );
4849 }
4850
pblItemRelease(void)4851 static void pblItemRelease( void )
4852 {
4853 PBLITEM_t * item;
4854
4855 if(( item = itemListHead ))
4856 {
4857 PBL_LIST_UNLINK( itemListHead, itemListTail, item, next, prev );
4858
4859 if( item->key )
4860 {
4861 PBL_FREE( item->key );
4862 }
4863 PBL_FREE( item );
4864 }
4865 }
4866
pblItemReleaseAll(void)4867 static void pblItemReleaseAll( void )
4868 {
4869 while( itemListHead )
4870 {
4871 pblItemRelease( );
4872 }
4873 }
4874
4875 #if 1
4876
pblSplit(PBLKFILE_t * file,PBLBLOCK_t * block)4877 static int pblSplit( PBLKFILE_t *file, PBLBLOCK_t * block )
4878 {
4879 unsigned int index;
4880 PBLITEM_t splititem;
4881 PBLITEM_t item;
4882 PBLBLOCK_t tmpblock;
4883 PBLBLOCK_t *newblock;
4884 PBLBLOCK_t *target;
4885 unsigned char predkey[ PBLKEYLENGTH + 1 ];
4886 unsigned int predkeylen = 0;
4887 long newblockno;
4888 int rc;
4889
4890 /*
4891 * create a new block
4892 */
4893 newblockno = pblBlockAppend( file, block->level,
4894 block->nblock, block->blockno );
4895 if( newblockno < 0 )
4896 {
4897 return( -1 );
4898 }
4899
4900 /*
4901 * set backward pointer in successor block of block
4902 */
4903 if( block->nblock )
4904 {
4905 PBLBLOCK_t * nextBlock = pblBlockGetWriteable( file, block->nblock );
4906 if( !nextBlock )
4907 {
4908 return( -1 );
4909 }
4910
4911 nextBlock->pblock = newblockno;
4912 nextBlock->dirty = 1;
4913 }
4914
4915 /*
4916 * get the new block to memory
4917 */
4918 newblock = pblBlockGetWriteable( file, newblockno );
4919 if( !newblock )
4920 {
4921 return( -1 );
4922 }
4923
4924 /*
4925 * copy the block to split onto the stack
4926 */
4927 pblBlockCachedItemsRelease( block );
4928
4929 tmpblock = *block;
4930
4931 /*
4932 * prepare the block for split
4933 */
4934 block->nblock = newblockno;
4935 block->nentries = 0;
4936 block->free = PBLHEADERSIZE;
4937 block->dirty = 1;
4938 memset( block->data, 0, PBLDATASIZE );
4939 memset( block->cachedItems, 0, sizeof( block->cachedItems ));
4940
4941 /*
4942 * copy the items from tmpblock to our two real blocks
4943 */
4944 for( target = block, index = 0; index < tmpblock.nentries; index++ )
4945 {
4946 rc = pblItemGet( &tmpblock, index, &item );
4947 if( rc )
4948 {
4949 pblBlockCachedItemsRelease( &tmpblock );
4950
4951 return( -1 );
4952 }
4953
4954 /*
4955 * if first block we copy to is more than half full
4956 */
4957 if( ( target == block )
4958 && (( PBLINDEXBLOCKNFREE( block ) < ( PBLDATASIZE / 2 ))
4959 || ( index == tmpblock.nentries - 1 )))
4960 {
4961 /*
4962 * the first item that goes to the new second block has to be
4963 * saved for later insert into the father block of the new block
4964 */
4965 splititem = item;
4966 splititem.datalen = 0;
4967 splititem.datablock = newblockno;
4968 splititem.dataoffset = 0;
4969 splititem.level++;
4970
4971 rc = pblItemSave( &splititem );
4972 if( rc )
4973 {
4974 pblBlockCachedItemsRelease( &tmpblock );
4975
4976 return( -1 );
4977 }
4978
4979 /*
4980 * for blocks of level greater than 0 the first item on each block
4981 * has keylength 0
4982 */
4983 if( tmpblock.level > 0 )
4984 {
4985 item.keylen = 0;
4986 }
4987
4988 /*
4989 * from now on copy to the second block
4990 */
4991 target = newblock;
4992 predkeylen = 0;
4993 }
4994
4995 rc = pblItemAppend( target, predkey, predkeylen, &item );
4996 if( rc < 0 )
4997 {
4998 pblBlockCachedItemsRelease( &tmpblock );
4999
5000 return( -1 );
5001 }
5002
5003 predkeylen = item.keylen;
5004 if( predkeylen > 0 )
5005 {
5006 memcpy(predkey, item.key, item.keylen);
5007 }
5008 else
5009 {
5010 predkey[ 0 ] = 0;
5011 }
5012 }
5013
5014 pblBlockCachedItemsRelease( &tmpblock );
5015
5016 /*
5017 * set the parent pointers to the new block
5018 */
5019 newblock->parentblock = block->parentblock;
5020 newblock->parentindex = block->parentindex + 1;
5021
5022 return( 0 );
5023 }
5024
5025 #else
5026
pblSplit(PBLKFILE_t * file,PBLBLOCK_t * block)5027 static int pblSplit( PBLKFILE_t * file, PBLBLOCK_t * block )
5028 {
5029 unsigned int index;
5030 int splitindex = 0;
5031 PBLITEM_t splititem;
5032 PBLITEM_t item;
5033 PBLBLOCK_t *newblock;
5034 PBLBLOCK_t *target;
5035 unsigned char *predkey = "";
5036 unsigned int predkeylen = 0;
5037 long newblockno;
5038 int rc;
5039 int blockfree = PBLHEADERSIZE;
5040
5041 /*
5042 * create a new block
5043 */
5044 newblockno = pblBlockAppend( file, block->level,
5045 block->nblock, block->blockno );
5046 if( newblockno < 0 )
5047 {
5048 return( -1 );
5049 }
5050
5051 /*
5052 * set backward pointer in successor block of block
5053 */
5054 if( block->nblock )
5055 {
5056 newblock = pblBlockGetWriteable( file, block->nblock );
5057 if( !newblock )
5058 {
5059 return( -1 );
5060 }
5061
5062 newblock->pblock = newblockno;
5063 newblock->dirty = 1;
5064 }
5065
5066 /*
5067 * get the new block to memory
5068 */
5069 newblock = pblBlockGetWriteable( file, newblockno );
5070 if( !newblock )
5071 {
5072 return( -1 );
5073 }
5074
5075 /*
5076 * prepare the block for split
5077 */
5078 block->nblock = newblockno;
5079
5080 /*
5081 * copy the items from the block to our new block
5082 */
5083 for( target = block, index = 0; index < block->nentries; index++ )
5084 {
5085 rc = pblItemGet( block, index, &item );
5086 if( rc )
5087 {
5088 return( -1 );
5089 }
5090
5091 if( target == block )
5092 {
5093 /*
5094 * calculate the size the items need on the block so far
5095 */
5096 blockfree += pblItemSize( block, &item );
5097
5098 /*
5099 * if first block we copy to is more than half full
5100 */
5101 if( ( blockfree > ( PBLDATASIZE / 2 ))
5102 || ( index == block->nentries - 1 ))
5103 {
5104 /*
5105 * the first item that goes to the new second block has to be
5106 * saved for later insert into the father block of the new block
5107 */
5108 splitindex = index;
5109 splititem = item;
5110 splititem.datalen = 0;
5111 splititem.datablock = newblockno;
5112 splititem.dataoffset = 0;
5113 splititem.level++;
5114
5115 rc = pblItemSave( &splititem );
5116 if( rc )
5117 {
5118 return( -1 );
5119 }
5120
5121 /*
5122 * for blocks of level greater than 0 the first item
5123 * on each block has keylength 0
5124 */
5125 if( block->level > 0 )
5126 {
5127 item.keylen = 0;
5128 }
5129
5130 /*
5131 * from now on copy to the second block
5132 */
5133 target = newblock;
5134 predkeylen = 0;
5135 }
5136 }
5137
5138 /*
5139 * only copy to the new block if the target is right
5140 */
5141 if( target == newblock )
5142 {
5143 rc = pblItemAppend( target, predkey, predkeylen, &item );
5144 if( rc < 0 )
5145 {
5146 return( -1 );
5147 }
5148
5149 /*
5150 * remember the key of the predecessor item
5151 */
5152 predkeylen = item.keylen;
5153 if( predkeylen > 0 )
5154 {
5155 predkey = item.key;
5156 }
5157 else
5158 {
5159 predkey = "";
5160 }
5161 }
5162 }
5163
5164 /*
5165 * delete the items that were copied from the block
5166 */
5167 for( index = block->nentries - 1; index >= splitindex; index-- )
5168 {
5169 rc = pblItemDelete( block, index );
5170 if( rc )
5171 {
5172 return( -1 );
5173 }
5174 }
5175
5176 /*
5177 * set the parent pointers to the new block
5178 */
5179 newblock->parentblock = block->parentblock;
5180 newblock->parentindex = block->parentindex + 1;
5181
5182 return( 0 );
5183 }
5184
5185 #endif
5186
pblSplitRoot(PBLKFILE_t * file)5187 static int pblSplitRoot( PBLKFILE_t *file )
5188 {
5189 PBLBLOCK_t * rootblock;
5190 PBLITEM_t item;
5191 PBLBLOCK_t * newblock;
5192 long newblockno;
5193 int rc;
5194
5195 /*
5196 * get the root block to memory
5197 */
5198 rootblock = pblBlockGetWriteable( file, 0 );
5199 if( !rootblock )
5200 {
5201 return( -1 );
5202 }
5203
5204 /*
5205 * create a new block and get it to memory
5206 */
5207 newblockno = pblBlockAppend( file, rootblock->level, 0, 0 );
5208 if( newblockno < 0 )
5209 {
5210 return( -1 );
5211 }
5212
5213 newblock = pblBlockGetWriteable( file, newblockno );
5214 if( !newblock )
5215 {
5216 return( -1 );
5217 }
5218
5219 /*
5220 * copy some data of the root block to the new block
5221 */
5222 newblock->nentries = rootblock->nentries;
5223 newblock->free = rootblock->free;
5224 memcpy( newblock->data, rootblock->data, PBLDATASIZE );
5225
5226 newblock->dirty = 1;
5227
5228 /*
5229 * get the root block to memory
5230 */
5231 rootblock = pblBlockGetWriteable( file, 0 );
5232 if( !rootblock )
5233 {
5234 return( -1 );
5235 }
5236
5237 /*
5238 * clear the root block
5239 */
5240 rootblock->level += 1;
5241 rootblock->nentries = 0;
5242 rootblock->free = PBLHEADERSIZE;
5243 rootblock->dirty = 1;
5244 memset( rootblock->data, 0, PBLDATASIZE );
5245 pblBlockCachedItemsRelease( rootblock );
5246
5247 newblock = pblBlockGetWriteable( file, newblockno );
5248 if( !newblock )
5249 {
5250 return( -1 );
5251 }
5252
5253 /*
5254 * copy the first item from new block to the root block
5255 */
5256 rc = pblItemGet( newblock, 0, &item );
5257 if( rc )
5258 {
5259 return( -1 );
5260 }
5261
5262 item.level = rootblock->level;
5263 item.keylen = 0;
5264 item.datalen = 0;
5265 item.datablock = newblockno;
5266 item.dataoffset = 0;
5267
5268 rc = pblItemAppend( rootblock, 0, 0, &item );
5269 if( rc < 0 )
5270 {
5271 return( -1 );
5272 }
5273
5274 /*
5275 * set the parent pointers to the new block
5276 */
5277 newblock->parentblock = 0;
5278 newblock->parentindex = 0;
5279
5280 /*
5281 * split the new block
5282 */
5283 return( pblSplit( file, newblock ));
5284 }
5285
5286 /**
5287 * insert a new record with the given key and data into a key file,
5288 *
5289 * multiple records with the same key are allowed,
5290 * if there are already records with the same key the new
5291 * record will be inserted behind all records with the same key,
5292 *
5293 * the current record of the file will be set to the new record
5294 *
5295 * <P>
5296 * <B>RESTRICTIONS</B>:
5297 * <BR> - the file must be open for update,
5298 * <BR> - key must point to the key to be inserted,
5299 * <BR> - keylen must be bigger than 0 and smaller than 256,
5300 * <BR> - data must point to the data be inserted,
5301 * <BR> - datalen must not be negative,
5302 * <BR> - if datalen == 0, the pointer data is not evaluated at all
5303 *
5304 * @return int rc == 0: call went ok
5305 * @return int rc != 0: some error occured, see pbl_errno
5306 */
5307
pblKfInsert(pblKeyFile_t * k,void * key,size_t keylen,void * data,size_t datalen)5308 int pblKfInsert(
5309 pblKeyFile_t * k, /** key file to insert to */
5310 void * key, /** key to insert */
5311 size_t keylen, /** length of the key */
5312 void * data, /** data to insert */
5313 size_t datalen /** length of the data */
5314 )
5315 {
5316 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
5317 PBLITEM_t item;
5318 PBLITEM_t * insertitem;
5319 PBLBLOCK_t * block;
5320 long blockno;
5321 int index;
5322 int saveerrno;
5323 int rc;
5324
5325 long parentblock = -1;
5326 int parentindex = -1;
5327 int split = 0;
5328
5329 pbl_errno = 0;
5330
5331 /*
5332 * start a transaction on the key file
5333 */
5334 pblKfStartTransaction( k );
5335 if( pblBlockListTruncate())
5336 {
5337 pblKfCommit( k, 1 );
5338 return( -1 );
5339 }
5340
5341 if( !kf->update )
5342 {
5343 pblKfCommit( k, 1 );
5344 pbl_errno = PBL_ERROR_NOT_ALLOWED;
5345 return( -1 );
5346 }
5347
5348 rc = pblParamsCheck( key, keylen, data, datalen );
5349 if( rc )
5350 {
5351 pblKfCommit( k, 1 );
5352 return( -1 );
5353 }
5354
5355 /*
5356 * only data that is longer than PBLDATALENGTH
5357 * bytes is written to data blocks
5358 */
5359 if( datalen > PBLDATALENGTH )
5360 {
5361 /*
5362 * append the data to the file
5363 */
5364 item.datablock = pblDataAppend( kf, data, datalen, &item.dataoffset );
5365 if( item.datablock < 1 )
5366 {
5367 pblKfCommit( k, 1 );
5368 return( -1 );
5369 }
5370 item.data = 0;
5371 }
5372 else
5373 {
5374 item.datablock = 0;
5375 item.dataoffset = 0;
5376 item.data = data;
5377 }
5378
5379 /*
5380 * prepare the data item to be inserted
5381 */
5382 item.level = 0;
5383 item.keylen = keylen;
5384 item.keycommon = 0;
5385 item.key = key;
5386 item.datalen = datalen;
5387
5388 /*
5389 * push the item to the insert stack of the file
5390 */
5391 rc = pblItemSave( &item );
5392 if( rc )
5393 {
5394 pblKfCommit( k, 1 );
5395 return( -1 );
5396 }
5397
5398 /*
5399 * insert all items that are on the insert stack
5400 */
5401 while( itemListHead )
5402 {
5403 insertitem = itemListHead;
5404
5405 /*
5406 * we always start the insert at the root block
5407 */
5408 blockno = 0;
5409 parentblock = -1;
5410 parentindex = -1;
5411
5412 /*
5413 * handle all levels of the tree
5414 */
5415 while( !pbl_errno )
5416 {
5417 block = pblBlockGet( kf, blockno );
5418 if( !block )
5419 {
5420 break;
5421 }
5422
5423 /*
5424 * set the links to the parentblock of the block
5425 */
5426 block->parentblock = parentblock;
5427 block->parentindex = parentindex;
5428
5429 /*
5430 * if the item has to be inserted in this level
5431 */
5432 if( block->level <= insertitem->level )
5433 {
5434 block = pblBlockGetWriteable( kf, blockno );
5435 if( !block )
5436 {
5437 break;
5438 }
5439
5440 index = pblItemAdd( kf, block, insertitem );
5441 if( index < 0 )
5442 {
5443 if( pbl_errno == PBL_ERROR_NOFIT )
5444 {
5445 pbl_errno = 0;
5446
5447 /*
5448 * split the root block or a normal block
5449 */
5450 if( blockno )
5451 {
5452 rc = pblSplit( kf, block );
5453 }
5454 else
5455 {
5456 rc = pblSplitRoot( kf );
5457 }
5458 if( !rc )
5459 {
5460 split = 1;
5461 }
5462 }
5463 break;
5464 }
5465
5466 /*
5467 * insert was successful
5468 */
5469 if( block->level == 0 )
5470 {
5471 /*
5472 * set values of current record
5473 */
5474 kf->blockno = block->blockno;
5475 kf->index = index;
5476 }
5477
5478 /*
5479 * release the item that was inserted
5480 */
5481 pblItemRelease( );
5482
5483 break;
5484 }
5485
5486 for(;;)
5487 {
5488 block = pblBlockGet( kf, blockno );
5489 if( !block )
5490 {
5491 break;
5492 }
5493
5494 /*
5495 * set the links to the parentblock of the block
5496 */
5497 block->parentblock = parentblock;
5498 block->parentindex = parentindex;
5499
5500 /*
5501 * item has to be inserted on a lower level, find out where
5502 *
5503 * we either insert into the last subtree, or into the
5504 * greatest smaller subtree
5505 */
5506 index = pblItemFind( kf, block, insertitem, PBLLA );
5507 if( index < 0 )
5508 {
5509 if( pbl_errno == PBL_ERROR_NOT_FOUND )
5510 {
5511 pbl_errno = 0;
5512 index = pblItemFind( kf, block, insertitem, PBLLT );
5513 }
5514
5515 if( index < 0 )
5516 {
5517 break;
5518 }
5519 }
5520
5521 rc = pblItemGet( block, index, &item );
5522 if( rc )
5523 {
5524 break;
5525 }
5526
5527 /*
5528 * see if we can merge blocks before the insert
5529 */
5530 if( !split )
5531 {
5532 rc = pblBlockMerge( kf, blockno,
5533 index, item.datablock );
5534 if( rc > 0 )
5535 {
5536 continue;
5537 }
5538 else if( rc < 0 )
5539 {
5540 break;
5541 }
5542 }
5543
5544 /*
5545 * get the blockno of the relevant child block
5546 */
5547 blockno = item.datablock;
5548 parentblock = block->blockno;
5549 parentindex = index;
5550
5551 pbl_errno = 0;
5552 break;
5553 }
5554 }
5555
5556 /*
5557 * if an error occurred during this insert
5558 */
5559 if( pbl_errno )
5560 {
5561 break;
5562 }
5563 }
5564
5565 saveerrno = pbl_errno;
5566
5567 pblItemReleaseAll( );
5568
5569 if( saveerrno )
5570 {
5571 kf->blockno = -1;
5572 kf->index = -1;
5573 pblKfCommit( k, 1 );
5574 pbl_errno = saveerrno;
5575 return( -1 );
5576 }
5577
5578 pblKfCommit( k, 0 );
5579 return( 0 );
5580 }
5581
5582 /*
5583 * UPDATE functions
5584 */
pblPositionCheck(PBLKFILE_t * kf)5585 static PBLBLOCK_t * pblPositionCheck( PBLKFILE_t *kf )
5586 {
5587 PBLBLOCK_t * block;
5588 int index;
5589
5590 /*
5591 * check if the current block is set for the file
5592 */
5593 if( kf->blockno < 0 )
5594 {
5595 pbl_errno = PBL_ERROR_POSITION;
5596 return( 0 );
5597 }
5598
5599 /*
5600 * get the current block to memory
5601 */
5602 block = pblBlockGet( kf, kf->blockno );
5603 if( !block )
5604 {
5605 return( 0 );
5606 }
5607 index = kf->index;
5608
5609 /*
5610 * if we are positioned on our pseudo magic item, we set to next item
5611 */
5612 if(( index == 0 ) && ( !block->pblock || !block->blockno ))
5613 {
5614 index = 1;
5615 }
5616
5617 /*
5618 * if the index is negative, we actually are set on the last item of
5619 * the predecessor of the current block, or if the there is no predecessor
5620 * on the first item of the current block
5621 */
5622 while( index < 0 )
5623 {
5624 /*
5625 * if we are on the first block, we need the second item, because the
5626 * the first item is our pseudo magic item
5627 */
5628 if( !block->pblock || !block->blockno )
5629 {
5630 index = 1;
5631 }
5632 else
5633 {
5634 block = pblBlockGet( kf, block->pblock );
5635 if( !block )
5636 {
5637 return( 0 );
5638 }
5639
5640 if( block->nentries )
5641 {
5642 index = block->nentries - 1;
5643 }
5644 }
5645 }
5646
5647 while( ( int )index >= ( int )block->nentries )
5648 {
5649 /*
5650 * if there is no successor of the current block, we have to stay here
5651 * the rootblock never has a successor !
5652 */
5653 if( !block->nblock || !block->blockno )
5654 {
5655 break;
5656 }
5657 else
5658 {
5659 block = pblBlockGet( kf, block->nblock );
5660 if( !block )
5661 {
5662 return( 0 );
5663 }
5664
5665 if( block->nentries )
5666 {
5667 index = 0;
5668 }
5669 }
5670 }
5671
5672 while( ( int )index >= ( int )block->nentries )
5673 {
5674 /*
5675 * if the block has entries, we take the last one
5676 */
5677 if( block->nentries )
5678 {
5679 index = block->nentries - 1;
5680 }
5681 else if( !block->pblock || !block->blockno )
5682 {
5683 /*
5684 * this is a structure error, because the first block always has
5685 * at least one item, our pseudo magic item
5686 */
5687 pbl_errno = PBL_ERROR_BAD_FILE;
5688 kf->blockno = -1;
5689 return( 0 );
5690 }
5691 else
5692 {
5693 block = pblBlockGet( kf, block->pblock );
5694 if( !block )
5695 {
5696 return( 0 );
5697 }
5698
5699 if( block->nentries )
5700 {
5701 index = block->nentries - 1;
5702 }
5703 }
5704 }
5705
5706 /*
5707 * if we ended up positioning at our pseudo item, the file does not
5708 * have any other items
5709 */
5710 if(( index == 0 ) && ( !block->pblock || !block->blockno ))
5711 {
5712 pbl_errno = PBL_ERROR_NOT_FOUND;
5713 kf->blockno = -1;
5714 return( 0 );
5715 }
5716
5717 kf->blockno = block->blockno;
5718 kf->index = index;
5719
5720 return( block );
5721 }
5722
pblDataWrite(PBLKFILE_t * file,unsigned char * data,long blockno,long blockoffset,long datalen)5723 static long pblDataWrite(
5724 PBLKFILE_t * file,
5725 unsigned char * data,
5726 long blockno,
5727 long blockoffset,
5728 long datalen
5729 )
5730 {
5731 long diff;
5732 long bytesWritten = 0;
5733 int nbytes;
5734 PBLBLOCK_t * datablock = (PBLBLOCK_t *) 0;
5735
5736 while( bytesWritten < datalen )
5737 {
5738 datablock = pblBlockGetWriteable( file, blockno );
5739 if( !datablock )
5740 {
5741 return( -1 );
5742 }
5743
5744 if( datablock->level != 255 )
5745 {
5746 pbl_errno = PBL_ERROR_BAD_FILE;
5747 return( -1 );
5748 }
5749
5750 diff = datalen - bytesWritten;
5751 if( diff > ( PBLDATASIZE - blockoffset ) )
5752 {
5753 nbytes = PBLDATASIZE - blockoffset;
5754 }
5755 else
5756 {
5757 nbytes = ((int ) ( diff % PBLDATASIZE));
5758 }
5759
5760 if( nbytes > 0 )
5761 {
5762 memcpy((void *) &(datablock->data[ blockoffset ]),
5763 (void *) data,
5764 nbytes );
5765 datablock->dirty = 1;
5766
5767 bytesWritten += nbytes;
5768 data += nbytes;
5769 }
5770
5771 if( bytesWritten < datalen )
5772 {
5773 /*
5774 * get offset of next block and set blockoffset to beginning of
5775 * data
5776 */
5777 blockno = datablock->nblock;
5778 blockoffset = PBLHEADERSIZE;
5779 }
5780 }
5781
5782 return( bytesWritten );
5783 }
5784
5785 /**
5786 * delete the current record of the key file.
5787 *
5788 * the current record of the file is set to the next record or
5789 * if the last record is deleted, to the previous record,
5790 *
5791 * if there are no more records in the file after the delete
5792 * the current record is of course unpositioned
5793 *
5794 * <P>
5795 * <B>RESTRICTIONS</B>:
5796 * <BR> - the file must be open for update,
5797 * <BR> - no space will be given back to the file system,
5798 * <BR> - if an index block and its successor or its predeccessor
5799 * together use less than half of a block the two blocks are merged
5800 *
5801 * @return int rc == 0: call went ok
5802 * @return int rc != 0: some error occured, see pbl_errno
5803 */
5804
pblKfDelete(pblKeyFile_t * k)5805 int pblKfDelete(
5806 pblKeyFile_t * k /** key file to delete record from */
5807 )
5808 {
5809 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
5810 long parentblock;
5811 PBLBLOCK_t * block;
5812 PBLITEM_t item;
5813 int rc;
5814
5815 pbl_errno = 0;
5816
5817 /*
5818 * start a transaction on the key file
5819 */
5820 pblKfStartTransaction( k );
5821 if( pblBlockListTruncate())
5822 {
5823 pblKfCommit( k, 1 );
5824 return( -1 );
5825 }
5826
5827 if( !kf->update )
5828 {
5829 pblKfCommit( k, 1 );
5830 pbl_errno = PBL_ERROR_NOT_ALLOWED;
5831 return( -1 );
5832 }
5833
5834 /*
5835 * make sure current record of the file is positioned
5836 */
5837 block = pblPositionCheck( kf );
5838 if( !block )
5839 {
5840 pblKfCommit( k, 1 );
5841 return( -1 );
5842 }
5843
5844 /*
5845 * read the block the current item is on
5846 */
5847 block = pblBlockGetWriteable( kf, kf->blockno );
5848 if( !block )
5849 {
5850 pblKfCommit( k, 1 );
5851 return( -1 );
5852 }
5853
5854 /*
5855 * read the item
5856 */
5857 rc = pblItemGet( block, kf->index, &item );
5858 if( rc )
5859 {
5860 return( -1 );
5861 }
5862
5863 /*
5864 * Only data that is longer than PBLDATALENGTH
5865 * bytes is written to data blocks
5866 */
5867 if( item.datalen > PBLDATALENGTH )
5868 {
5869 /*
5870 * Since 1.04, 4 Nov 2008 23:02:03 CET, the data is also deleted
5871 */
5872 rc = pblDataRemove(kf, item.datablock, item.dataoffset, item.datalen);
5873 if (rc < 0)
5874 {
5875 return rc;
5876 }
5877
5878 /*
5879 * The block might have become a cache victim,
5880 * make sure it is in memory,
5881 * read the block the current item is on
5882 */
5883 block = pblBlockGetWriteable( kf, kf->blockno );
5884 if( !block )
5885 {
5886 pblKfCommit( k, 1 );
5887 return( -1 );
5888 }
5889
5890 /*
5891 * read the item
5892 */
5893 rc = pblItemGet( block, kf->index, &item );
5894 if( rc )
5895 {
5896 return( -1 );
5897 }
5898 }
5899
5900 /*
5901 * delete the current item
5902 */
5903 rc = pblItemRemove( block, kf->index );
5904 if( rc )
5905 {
5906 pblKfCommit( k, 1 );
5907 return( rc );
5908 }
5909
5910 /*
5911 * we deleted an item, now see if we can merge some blocks
5912 */
5913 for(;;)
5914 {
5915 if( block->parentblock < 0 || block->parentindex < 0 )
5916 {
5917 rc = 0;
5918 break;
5919 }
5920
5921 /*
5922 * remember the blocknumber of the parent block
5923 */
5924 parentblock = block->parentblock;
5925
5926 /*
5927 * see whether some blocks can be merged because of the delete
5928 */
5929 rc = pblBlockMerge( kf, block->parentblock,
5930 block->parentindex, block->blockno );
5931 if( rc < 1 )
5932 {
5933 break;
5934 }
5935
5936 /*
5937 * the merge deleted an item on the parent block, read that block
5938 */
5939 block = pblBlockGetWriteable( kf, parentblock );
5940 if( !block )
5941 {
5942 pblKfCommit( k, 1 );
5943 return( -1 );
5944 }
5945 }
5946
5947 if( rc )
5948 {
5949 pblKfCommit( k, 1 );
5950 return( -1 );
5951 }
5952
5953 pblKfCommit( k, 0 );
5954 return( rc );
5955 }
5956
5957 /**
5958 * update the data of the current record
5959 *
5960 * the current record of the file is updated with the new data given
5961 *
5962 *
5963 * <P>
5964 * <B>RESTRICTIONS</B>:
5965 * <BR> - the file must be open for update,
5966 * <BR> - if the new datalen of the record is not bigger than the old datalen,
5967 * the data will be updated in place, otherwise the new data of the
5968 * record will be appended to the file, the space previously used for
5969 * the data of the record will not be reused in this case,
5970 * <BR> - data must point to the new data be inserted,
5971 * <BR> - datalen must not be negative,
5972 * <BR> - if datalen == 0, the pointer data is not evaluated at all
5973 *
5974 * @return int rc == 0: call went ok
5975 * @return int rc != 0: some error occured, see pbl_errno
5976 */
5977
pblKfUpdate(pblKeyFile_t * k,void * data,size_t datalen)5978 int pblKfUpdate(
5979 pblKeyFile_t * k, /** key file to delete record from */
5980 void * data, /** new data to update with */
5981 size_t datalen /** length of the new data */
5982 )
5983 {
5984 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
5985 PBLITEM_t item;
5986 PBLBLOCK_t * block;
5987 long rc;
5988 unsigned char key[ PBLKEYLENGTH ];
5989
5990 pbl_errno = 0;
5991
5992 /*
5993 * start a transaction on the key file
5994 */
5995 pblKfStartTransaction( k );
5996 if( pblBlockListTruncate())
5997 {
5998 pblKfCommit( k, 1 );
5999 return( -1 );
6000 }
6001
6002 if( !kf->update )
6003 {
6004 pblKfCommit( k, 1 );
6005 pbl_errno = PBL_ERROR_NOT_ALLOWED;
6006 return( -1 );
6007 }
6008
6009 if( pblParamsCheck( (unsigned char*)1, 1, data, datalen ))
6010 {
6011 pblKfCommit( k, 1 );
6012 return( -1 );
6013 }
6014
6015 /*
6016 * make sure current record of the file is positioned
6017 */
6018 block = pblPositionCheck( kf );
6019 if( !block )
6020 {
6021 pblKfCommit( k, 1 );
6022 return( -1 );
6023 }
6024
6025 /*
6026 * read the block the current item is on
6027 */
6028 block = pblBlockGetWriteable( kf, kf->blockno );
6029 if( !block )
6030 {
6031 pblKfCommit( k, 1 );
6032 return( -1 );
6033 }
6034
6035 /*
6036 * read the item
6037 */
6038 rc = pblItemGet( block, kf->index, &item );
6039 if( rc )
6040 {
6041 pblKfCommit( k, 1 );
6042 return( -1 );
6043 }
6044
6045 if( datalen == item.datalen )
6046 {
6047 /*
6048 * if the data is to be stored on an index block
6049 */
6050 if( datalen <= PBLDATALENGTH )
6051 {
6052 /*
6053 * update in place
6054 */
6055 if( datalen > 0 )
6056 {
6057 memcpy( item.data, data, datalen );
6058 block->dirty = 1;
6059 }
6060
6061 pblKfCommit( k, 0 );
6062 return( 0 );
6063 }
6064
6065 /*
6066 * update the data in place
6067 */
6068 rc = pblDataWrite( kf, data, item.datablock, item.dataoffset, datalen );
6069 if( rc != datalen )
6070 {
6071 pblKfCommit( k, 1 );
6072 return( -1 );
6073 }
6074
6075 pblKfCommit( k, 0 );
6076 return( 0 );
6077 }
6078
6079 if( item.keycommon )
6080 {
6081 /*
6082 * read the item to get its real key
6083 */
6084 rc = pblItemGet( block, kf->index, &item );
6085 if( rc )
6086 {
6087 pblKfCommit( k, 1 );
6088 return( -1 );
6089 }
6090 }
6091
6092 /*
6093 * we do a delete and an insert of the record
6094 */
6095 item.keylen &= 0xff;
6096 pbl_memlcpy( key, sizeof( key ), item.key, item.keylen );
6097
6098 rc = pblKfDelete( k );
6099 if( rc )
6100 {
6101 pblKfCommit( k, 1 );
6102 return( rc );
6103 }
6104
6105 rc = pblKfInsert( k, key, item.keylen, data, datalen );
6106 if( rc )
6107 {
6108 pblKfCommit( k, 1 );
6109 return( rc );
6110 }
6111
6112 pblKfCommit( k, 0 );
6113
6114 return( rc );
6115 }
6116
6117 /*
6118 * READ functions
6119 */
6120 /*
6121 * recursive find procedure for records
6122 */
pblFindRec(PBLKFILE_t * kf,int mode,long blockno,long parentblock,int parentindex,PBLITEM_t * item)6123 static long pblFindRec(
6124 PBLKFILE_t * kf,
6125 int mode,
6126 long blockno,
6127 long parentblock,
6128 int parentindex,
6129 PBLITEM_t * item
6130 )
6131 {
6132 PBLITEM_t curitem;
6133 PBLBLOCK_t * block;
6134 int index;
6135 long rc;
6136 int which;
6137 int direction;
6138
6139 /*
6140 * get the block to memory
6141 */
6142 block = pblBlockGet( kf, blockno );
6143 if( !block )
6144 {
6145 return( -1 );
6146 }
6147
6148 block->parentblock = parentblock;
6149 block->parentindex = parentindex;
6150
6151 /*
6152 * level 0, terminate the recursion
6153 */
6154 if( block->level == 0 )
6155 {
6156 /*
6157 * find the item on the block, first that matches
6158 */
6159 index = pblItemFind( kf, block, item, mode );
6160 if( index < 0 )
6161 {
6162 return( -1 );
6163 }
6164
6165 /*
6166 * make sure nobody is finding our pseudo record
6167 */
6168 if(( index == 0 ) && ( !block->pblock || !block->blockno ))
6169 {
6170 pbl_errno = PBL_ERROR_NOT_FOUND;
6171 return( -1 );
6172 }
6173
6174 rc = pblItemGet( block, index, &curitem );
6175 if( rc )
6176 {
6177 return( -1 );
6178 }
6179
6180 /*
6181 * find was successful set values of current record
6182 */
6183 kf->blockno = block->blockno;
6184 kf->index = index;
6185
6186 /*
6187 * we return the datalength of the item
6188 */
6189 return( curitem.datalen );
6190 }
6191
6192 direction = 1;
6193 switch( mode )
6194 {
6195 case PBLLT:
6196 which = PBLLT;
6197 direction = -1;
6198 break;
6199
6200 case PBLFI:
6201 case PBLEQ:
6202 which = PBLLT;
6203 break;
6204
6205 case PBLLA:
6206 case PBLGT:
6207 which = PBLLA;
6208 break;
6209
6210 default:
6211 pbl_errno = PBL_ERROR_PARAM_MODE;
6212 return( -1 );
6213 }
6214
6215 /*
6216 * find the subtree where to continue the find
6217 */
6218 index = pblItemFind( kf, block, item, which );
6219 if( index < 0 )
6220 {
6221 if( which == PBLLA )
6222 {
6223 if( pbl_errno == PBL_ERROR_NOT_FOUND )
6224 {
6225 pbl_errno = 0;
6226 index = pblItemFind( kf, block, item, PBLLT );
6227 }
6228 }
6229 }
6230
6231 /*
6232 * search in all possible subtrees
6233 */
6234 for( ; index >= 0 && index < (int)block->nentries; index += direction )
6235 {
6236 /*
6237 * check if subtree can contain the item
6238 */
6239 rc = pblItemGet( block, index, &curitem );
6240 if( rc )
6241 {
6242 return( -1 );
6243 }
6244
6245 rc = pblItemCompare( kf, &curitem, item );
6246 if(( rc > 0 ) && ( mode != PBLGT ))
6247 {
6248 pbl_errno = PBL_ERROR_NOT_FOUND;
6249 return( -1 );
6250 }
6251
6252 /*
6253 * recursive call to find procedure
6254 */
6255 rc = pblFindRec( kf, mode, curitem.datablock, blockno, index, item );
6256 if( rc >= 0 )
6257 {
6258 /*
6259 * find was successful
6260 */
6261 return( rc );
6262 }
6263
6264 /*
6265 * if an error other than PBL_ERROR_NOT_FOUND occured, we give up
6266 */
6267 if( pbl_errno != PBL_ERROR_NOT_FOUND )
6268 {
6269 return( -1 );
6270 }
6271 else
6272 {
6273 pbl_errno = 0;
6274 }
6275
6276 /*
6277 * get the block to memory because during the recursive call
6278 * it might have become a victim
6279 */
6280 block = pblBlockGet( kf, blockno );
6281 if( !block )
6282 {
6283 return( -1 );
6284 }
6285
6286 block->parentblock = parentblock;
6287 block->parentindex = parentindex;
6288 }
6289
6290 /*
6291 * couldn't find the item, tell the caller
6292 */
6293 pbl_errno = PBL_ERROR_NOT_FOUND;
6294 return( -1 );
6295 }
6296
pblDataGet(PBLKFILE_t * file,unsigned char * data,long blockno,long blockoffset,long datalen)6297 static long pblDataGet(
6298 PBLKFILE_t * file,
6299 unsigned char * data,
6300 long blockno,
6301 long blockoffset,
6302 long datalen
6303 )
6304 {
6305 long diff;
6306 long bytesRead = 0;
6307 int nbytes;
6308 PBLBLOCK_t * datablock = (PBLBLOCK_t *) 0;
6309
6310 while( bytesRead < datalen )
6311 {
6312 datablock = pblBlockGet( file, blockno );
6313 if( !datablock )
6314 {
6315 return( -1 );
6316 }
6317
6318 if( datablock->level != 255 )
6319 {
6320 pbl_errno = PBL_ERROR_BAD_FILE;
6321 return( -1 );
6322 }
6323
6324 diff = datalen - bytesRead;
6325 if( diff > ( PBLDATASIZE - blockoffset ) )
6326 {
6327 nbytes = PBLDATASIZE - blockoffset;
6328 }
6329 else
6330 {
6331 nbytes = ((int ) ( diff % PBLDATASIZE));
6332 }
6333
6334 if( nbytes > 0 )
6335 {
6336 memcpy((void *) data,
6337 (void *) &(datablock->data[ blockoffset ]),
6338 nbytes );
6339
6340 bytesRead += nbytes;
6341 data += nbytes;
6342 }
6343
6344 if( bytesRead < datalen )
6345 {
6346 /*
6347 * get number of next block and set blockoffset to beginning of
6348 * data
6349 */
6350 blockno = datablock->nblock;
6351 blockoffset = PBLHEADERSIZE;
6352 }
6353 }
6354
6355 return( bytesRead );
6356 }
6357
6358 /**
6359 * find a record in a key file, set the current record
6360 *
6361 * parameter mode specifies which record to find relative
6362 * to the search key specified by skey and skeylen.
6363 * the following values for mode are possible
6364 *
6365 * <BR><B> PBLEQ </B> - find a record whose key is equal to skey
6366 * <BR><B> PBLFI </B> - find the first record that is equal
6367 * <BR><B> PBLLA </B> - find the last record that is equal
6368 * <BR><B> PBLGE </B> - find the last record that is equal or the smallest
6369 * record that is greater
6370 * <BR><B> PBLGT </B> - find the smallest record that is greater
6371 * <BR><B> PBLLE </B> - find the first record that is equal or the biggest
6372 * record that is smaller
6373 * <BR><B> PBLLT </B> - find the biggest record that is smaller
6374 *
6375 * keep in mind that PBL allows multiple records with the same key.
6376 *
6377 * <P>
6378 * <B>RESTRICTIONS</B>:
6379 * <BR> - the out parameter okey must point to a memory area that is
6380 * big enough to hold any possible key, i.e 255 bytes
6381 *
6382 * @return long rc >= 0:
6383 * <UL>
6384 * <LI> call went ok,
6385 * the value returned is the length
6386 * of the data of the record found,
6387 * <LI> the length of the key of the record is set in
6388 * the out parameter okeylen,
6389 * <LI> the key of the record is copied to okey,
6390 * <LI> the current record of the file is set to the
6391 * record found
6392 * </UL>
6393 *
6394 * @return long rc < 0:
6395 * <UL>
6396 * <LI> some error occured, see pbl_errno
6397 * especially PBL_ERROR_NOT_FOUND, if there is no
6398 * matching record
6399 * </UL>
6400 */
pblKfFind(pblKeyFile_t * k,int mode,void * skey,size_t skeylen,void * okey,size_t * okeylen)6401 long pblKfFind(
6402 pblKeyFile_t * k, /** key file to search in */
6403 int mode, /** mode to use for search */
6404 void * skey, /** key to use for search */
6405 size_t skeylen, /** length of search key */
6406 void * okey, /** buffer for result key */
6407 size_t * okeylen /** length of the result key after return */
6408 )
6409 {
6410 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
6411 PBLBLOCK_t * block;
6412 PBLITEM_t item;
6413 long rc;
6414 int which;
6415
6416 pbl_errno = 0;
6417
6418 rc = pblParamsCheck( skey, skeylen, (unsigned char*)0, 0 );
6419 if( rc )
6420 {
6421 return( -1 );
6422 }
6423
6424 /*
6425 * prepare the data item to be found
6426 */
6427 memset( &item, 0, sizeof( item ));
6428 item.keylen = skeylen;
6429 item.key = skey;
6430
6431 if( mode == PBLLE )
6432 {
6433 which = PBLFI;
6434 }
6435 else if( mode == PBLGE )
6436 {
6437 which = PBLLA;
6438 }
6439 else
6440 {
6441 which = mode;
6442 }
6443
6444 /*
6445 * we always start the find at the root block
6446 */
6447 rc = pblFindRec( kf, which, 0, -1, -1, &item );
6448 if( rc < 0 )
6449 {
6450 if( pbl_errno == PBL_ERROR_NOT_FOUND )
6451 {
6452 if( mode == PBLLE )
6453 {
6454 rc = pblFindRec( kf, PBLLT, 0, -1, -1, &item );
6455 }
6456 else if( mode == PBLGE )
6457 {
6458 rc = pblFindRec( kf, PBLGT, 0, -1, -1, &item );
6459 }
6460 }
6461 }
6462
6463 if( rc < 0 )
6464 {
6465 return( -1 );
6466 }
6467
6468 /*
6469 * get the current block to memory
6470 */
6471 block = pblBlockGet( kf, kf->blockno );
6472 if( !block )
6473 {
6474 return( -1 );
6475 }
6476
6477 /*
6478 * read the item
6479 */
6480 rc = pblItemGet( block, kf->index, &item );
6481 if( rc )
6482 {
6483 return( -1 );
6484 }
6485
6486 /*
6487 * set the out parameters, if a buffer is supplied
6488 */
6489 if( okey && okeylen )
6490 {
6491 *okeylen = item.keylen;
6492 pbl_memlcpy( okey, PBLKEYLENGTH, item.key, item.keylen );
6493 }
6494
6495 return( item.datalen );
6496 }
6497
6498 /**
6499 * read the data of the current record of the file
6500 *
6501 * the caller can restrict the number of bytes read by
6502 * specifying the maximum number of bytes to read by parameter
6503 * datalen, if datalen is 0, all bytes stored for the
6504 * current record are copied to the buffer pointed to by data.
6505 * <P>
6506 * <B>RESTRICTIONS</B>:
6507 * <BR> - data must point to an area of memory being big enough to hold
6508 * the bytes copied
6509 * <BR> - datalen must not be negative, it is ignored otherwise
6510 *
6511 * @return int rc == 0: call went ok, rc is the number of bytes copied
6512 * @return int rc != 0: some error occured, see pbl_errno
6513 */
6514
pblKfRead(pblKeyFile_t * k,void * data,long datalen)6515 long pblKfRead(
6516 pblKeyFile_t * k, /** key file to read from */
6517 void * data, /** data to insert */
6518 long datalen /** length of the data */
6519 )
6520 {
6521 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
6522 PBLITEM_t item;
6523 PBLBLOCK_t * block;
6524 long rc;
6525
6526 pbl_errno = 0;
6527
6528 rc = pblParamsCheck( (unsigned char*)1, 1, (unsigned char*)data, datalen );
6529 if( rc )
6530 {
6531 return( -1 );
6532 }
6533
6534 /*
6535 * check position of current record
6536 */
6537 block = pblPositionCheck( kf );
6538 if( !block )
6539 {
6540 return( -1 );
6541 }
6542
6543 /*
6544 * read the item
6545 */
6546 rc = pblItemGet( block, kf->index, &item );
6547 if( rc )
6548 {
6549 return( -1 );
6550 }
6551
6552 /*
6553 * the caller can restrict the number of bytes read
6554 */
6555 if( datalen > 0 )
6556 {
6557 if( datalen > item.datalen )
6558 {
6559 datalen = item.datalen;
6560 }
6561 }
6562 else
6563 {
6564 datalen = item.datalen;
6565 }
6566
6567 /*
6568 * if the data is stored on an index block
6569 */
6570 if( datalen <= PBLDATALENGTH )
6571 {
6572 memcpy( data, item.data, datalen );
6573 return( datalen );
6574 }
6575
6576 /*
6577 * the data is stored on a data block, read it from the file
6578 */
6579 rc = pblDataGet( kf, data, item.datablock, item.dataoffset, datalen );
6580 if( rc != datalen )
6581 {
6582 return( -1 );
6583 }
6584
6585 return( datalen );
6586 }
6587
6588 /**
6589 * set current record to a record with a relative position index
6590 *
6591 * this function is only to be used through the macro functions:
6592 *
6593 * <BR><B> \Ref{pblKfThis}( k, okey, okeylen ) </B> read key of current record
6594 * <BR><B> \Ref{pblKfNext}( k, okey, okeylen ) </B> read key of next record
6595 * <BR><B> \Ref{pblKfPrev}( k, okey, okeylen ) </B> read key of previous record
6596 *
6597 * @return long rc >= 0:
6598 * <UL>
6599 * <LI> call went ok,
6600 * the value returned is the length
6601 * of the data of the record found,
6602 * <LI> the length of the key of the record is set in
6603 * the out parameter okeylen,
6604 * <LI> the key of the record is copied to okey,
6605 * <LI> the current record of the file is set to the
6606 * record found
6607 * </UL>
6608 *
6609 * @return long rc < 0:
6610 * <UL>
6611 * <LI> some error occured, see pbl_errno
6612 * </UL>
6613 */
6614
pblKfGetRel(pblKeyFile_t * k,long relindex,void * okey,size_t * okeylen)6615 long pblKfGetRel(
6616 pblKeyFile_t * k, /** key file to position in */
6617 long relindex, /** index relative to current record */
6618 void * okey, /** buffer for result key */
6619 size_t * okeylen /** length of the result key after return */
6620 )
6621 {
6622 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
6623 PBLITEM_t item;
6624 PBLBLOCK_t * block;
6625 int index;
6626 long rc;
6627
6628 pbl_errno = 0;
6629
6630 /*
6631 * check position of current record
6632 */
6633 block = pblPositionCheck( kf );
6634 if( !block )
6635 {
6636 return( -1 );
6637 }
6638
6639 /*
6640 * start searching at current block and current index
6641 */
6642 index = kf->index;
6643
6644 /*
6645 * if we want an item that is to the left of the current item
6646 */
6647 while( !pbl_errno && relindex < 0 )
6648 {
6649 relindex++;
6650
6651 /*
6652 * as long as we can go to the left on current block
6653 */
6654 if( index > 0 )
6655 {
6656 index--;
6657 continue;
6658 }
6659
6660 /*
6661 * find a block that has entries
6662 */
6663 for(;;)
6664 {
6665 /*
6666 * go to previous block
6667 */
6668 if( !block->pblock || !block->blockno )
6669 {
6670 pbl_errno = PBL_ERROR_NOT_FOUND;
6671 break;
6672 }
6673
6674 block = pblBlockGet( kf, block->pblock );
6675 if( !block )
6676 {
6677 break;
6678 }
6679
6680 if( block->nentries )
6681 {
6682 index = block->nentries - 1;
6683 break;
6684 }
6685 }
6686 }
6687
6688 /*
6689 * if we want an item that is to the right of the current item
6690 */
6691 while( !pbl_errno && relindex > 0 )
6692 {
6693 relindex--;
6694
6695 /*
6696 * as long as we can go to the right on this block
6697 */
6698 if(( int )( index + 1 ) < ( int )block->nentries )
6699 {
6700 index++;
6701 continue;
6702 }
6703
6704 /*
6705 * find a block that has at least one entry
6706 */
6707 for(;;)
6708 {
6709 /*
6710 * go to next block, but beware that rootblock has no next
6711 */
6712 if( !block->nblock || !block->blockno )
6713 {
6714 pbl_errno = PBL_ERROR_NOT_FOUND;
6715 break;
6716 }
6717
6718 block = pblBlockGet( kf, block->nblock );
6719 if( !block )
6720 {
6721 break;
6722 }
6723
6724 if( block->nentries )
6725 {
6726 index = 0;
6727 break;
6728 }
6729 }
6730 }
6731
6732 /*
6733 * if an error occured we tell the caller
6734 */
6735 if( pbl_errno )
6736 {
6737 return( -1 );
6738 }
6739
6740 /*
6741 * read the item
6742 */
6743 rc = pblItemGet( block, index, &item );
6744 if( rc )
6745 {
6746 return( -1 );
6747 }
6748
6749 /*
6750 * if the item we are standing on is our first record, we have reached the
6751 * end of file while reading backward
6752 */
6753 if( item.keylen == 0 )
6754 {
6755 pbl_errno = PBL_ERROR_NOT_FOUND;
6756 return( -1 );
6757 }
6758
6759 /*
6760 * set the out parameters, if a buffer is supplied
6761 */
6762 if( okey && okeylen )
6763 {
6764 *okeylen = item.keylen;
6765 pbl_memlcpy( okey, PBLKEYLENGTH, item.key, item.keylen );
6766 }
6767
6768 kf->blockno = block->blockno;
6769 kf->index = index;
6770
6771 return( item.datalen );
6772 }
6773
6774 /**
6775 * set current record to a record with an absolute position index
6776 *
6777 * this function is only to be used through the macro functions:
6778 *
6779 * <BR><B> \Ref{pblKfFirst}( k, okey, okeylen ) </B> read key of first record
6780 * <BR><B> \Ref{pblKfLast}( k, okey, okeylen ) </B> read key of last record
6781 *
6782 * @return long rc >= 0:
6783 * <UL>
6784 * <LI> call went ok,
6785 * the value returned is the length
6786 * of the data of the record found,
6787 * <LI> the length of the key of the record is set in
6788 * the out parameter okeylen,
6789 * <LI> the key of the record is copied to okey,
6790 * <LI> the current record of the file is set to the
6791 * record found
6792 * </UL>
6793 *
6794 * @return long rc < 0:
6795 * <UL>
6796 * <LI> some error occured, see pbl_errno
6797 * </UL>
6798 */
6799
pblKfGetAbs(pblKeyFile_t * k,long absindex,void * okey,size_t * okeylen)6800 long pblKfGetAbs(
6801 pblKeyFile_t * k, /** key file to position in */
6802 long absindex, /** index of record to positon to */
6803 void * okey, /** buffer for result key */
6804 size_t * okeylen /** length of the result key after return */
6805 )
6806 {
6807 PBLKFILE_t * kf = ( PBLKFILE_t * ) k;
6808 PBLITEM_t item;
6809 PBLBLOCK_t * block;
6810 int index;
6811 long rc;
6812
6813 pbl_errno = 0;
6814
6815 /*
6816 * start searching at rootblock
6817 */
6818 block = pblBlockGet( kf, 0 );
6819 if( !block )
6820 {
6821 return( -1 );
6822 }
6823
6824 /*
6825 * step down through tree to level 0
6826 */
6827 while( !pbl_errno && block->level )
6828 {
6829 if( absindex >= 0 )
6830 {
6831 index = 0;
6832 }
6833 else
6834 {
6835 index = block->nentries - 1;
6836 }
6837
6838 rc = pblItemGet( block, index, &item );
6839 if( rc )
6840 {
6841 break;
6842 }
6843
6844 /*
6845 * get the relevant child block
6846 */
6847 block = pblBlockGet( kf, item.datablock );
6848 if( !block )
6849 {
6850 return( -1 );
6851 }
6852 }
6853
6854 /*
6855 * if no error yet, we do a relative get
6856 */
6857 if( !pbl_errno )
6858 {
6859 /*
6860 * prepare relative get
6861 */
6862 kf->blockno = block->blockno;
6863
6864 if( absindex >= 0 )
6865 {
6866 kf->index = -1;
6867 return( pblKfGetRel( k, absindex, okey, okeylen ));
6868 }
6869 else
6870 {
6871 kf->index = block->nentries;
6872 return( pblKfGetRel( k, absindex + 1, okey, okeylen ));
6873 }
6874 }
6875
6876 return( -1 );
6877 }
6878
6879 /*
6880 ------------------------------------------------------------------------------
6881 FUNCTION: pblKfXXX
6882
6883 DESCRIPTION: These macros allow to position the current record and
6884 to read the key, the keylen and the datalen of the new
6885 current record
6886
6887 The following macros exist:
6888
6889 pblKfFirst: set the current record to the first record of the
6890 file
6891
6892 pblKfLast: set the current record to the last record of the
6893 file
6894
6895 pblKfNext: set the current record to the record of the
6896 file after the old current record, of course the
6897 record of the file must be positioned before that
6898
6899 pblKfPrev: set the current record to the record of the
6900 file before the old current record, of course the
6901 record of the file must be positioned before that
6902
6903 pblKfThis: this function can be used to read the key, keylen
6904 and datalen of the current record, the current
6905 record is not changed by this
6906
6907 RESTRICTIONS: the out parameter okey must point to a memory area that is
6908 big enough to hold any possible key, i.e 255 bytes
6909
6910 RETURNS: long rc >= 0: call went ok, the value returned is the length
6911 of the data of the current record,
6912 the length of the key of the record is set in
6913 the out parameter okeylen,
6914 the key of the record is copied to okey,
6915
6916 long rc < 0: some error occured, see pbl_errno
6917 PBL_ERROR_NOT_FOUND, there is no matching record
6918 PBL_ERROR_POSITION, current record not set yet
6919 ------------------------------------------------------------------------------
6920 */
6921
6922
pblKfBlockPrint(char * path,long blockno)6923 int pblKfBlockPrint(
6924 char * path, /** path of file to create */
6925 long blockno /** number of block to print */
6926 )
6927 {
6928 PBLITEM_t item;
6929 PBLKFILE_t * kf;
6930 PBLBLOCK_t * block;
6931 int bf;
6932 int i;
6933
6934 pbl_errno = 0;
6935 memset( &item, 0, sizeof( item ));
6936
6937 printf( "FILE %s, BLOCK %ld\n", path, blockno );
6938
6939 bf = pbf_open( path, 0, PBLFILEBLOCKS, PBLDATASIZE );
6940 if( -1 == bf )
6941 {
6942 printf( "pbf_open failed, pbl_errno %d\n", pbl_errno );
6943 return( -1 );
6944 }
6945
6946 /*
6947 * get and init file structure
6948 */
6949 kf = (PBLKFILE_t *)pbl_malloc0( "pblKfBlockPrint FILE", sizeof( PBLKFILE_t ));
6950 if( !kf )
6951 {
6952 printf( "pbl_malloc0 failed, pbl_errno %d\n", pbl_errno );
6953 pbf_close( bf );
6954 return( -1 );
6955 }
6956 kf->magic = pblkf_c_id;
6957 kf->bf = bf;
6958 kf->update = 0;
6959 kf->filesettag = NULL;
6960 kf->blockno = -1;
6961 kf->index = -1;
6962
6963 pblnfiles++;
6964
6965 /*
6966 * get the block
6967 */
6968 block = pblBlockGet( kf, blockno );
6969 if( !block )
6970 {
6971 printf( "pblBlockGet failed, pbl_errno %d\n", pbl_errno );
6972 pblKfClose( ( pblKeyFile_t * ) kf );
6973 return( -1 );
6974 }
6975
6976 if( block->level == 255 )
6977 {
6978 printf( "datablock\n" );
6979 pblKfClose( ( pblKeyFile_t * ) kf );
6980 return( 0 );
6981 }
6982
6983 printf( "level %d, pblock %ld, nblock %ld, nentries %d, free %d\n",
6984 block->level, block->pblock, block->nblock,
6985 (int)block->nentries, block->free );
6986
6987 if( block->nentries < 1 )
6988 {
6989 pblKfClose( ( pblKeyFile_t * ) kf );
6990 return( 0 );
6991 }
6992
6993 for( i = 0; i < (int)block->nentries; i++ )
6994 {
6995 unsigned char * ptr;
6996
6997 pblItemGet( block, i, &item );
6998
6999 if( item.key )
7000 {
7001 ptr = item.key;
7002 }
7003 else
7004 {
7005 ptr = (unsigned char *) "NULL";
7006 }
7007
7008 printf( "%03d %d %.*s, common %d, datalen %ld, block %ld, offset %ld\n",
7009 i, item.keylen,
7010 item.keylen, ptr,
7011 item.keycommon, item.datalen,
7012 item.datablock, item.dataoffset );
7013 }
7014
7015 pblKfClose( ( pblKeyFile_t * ) kf );
7016 return( 0 );
7017 }
7018
7019