slow start on isam-d
[idzebra-moved-to-github.git] / isamc / isamd.c
1 /*
2  * Copyright (c) 1995-1998, Index Data.
3  * See the file LICENSE for details.
4  * Heikki Levanto
5  * 
6  * Isamd - isam with diffs 
7  *
8  * todo
9  *   most of it, this is just a copy of isamh
10  *
11  */
12
13
14
15
16 #include <stdlib.h>
17 #include <assert.h>
18 #include <string.h>
19 #include <stdio.h>
20
21 #include <log.h>
22 #include "isamd-p.h"
23
24 #include "../index/index.h" /* for dump */
25
26 static void flush_block (ISAMD is, int cat);
27 static void release_fc (ISAMD is, int cat);
28 static void init_fc (ISAMD is, int cat);
29
30 #define ISAMD_FREELIST_CHUNK 1
31
32 #define SMALL_TEST 1
33
34 ISAMD_M isamd_getmethod (ISAMD_M me)
35 {
36     static struct ISAMD_filecat_s def_cat[] = {
37 #if SMALL_TEST
38 /*        blocksz,   max keys before switching size */
39         {    32,   40 },
40         {   128,    0 },
41 #else
42         {    24,   40 },
43         {  2048, 2048 },
44         { 16384,    0 },
45
46 #endif 
47
48 /* old values from isamc, long time ago...
49         {    24,   40 },
50         {   128,  256 },
51         {   512, 1024 },
52         {  2048, 4096 },
53         {  8192,16384 },
54         { 32768,   0  },
55 */
56
57 /* assume about 2 bytes per pointer, when compressed. The head uses */
58 /* 16 bytes, and other blocks use 8 for header info... If you want 3 */
59 /* blocks of 32 bytes, say max 16+24+24 = 64 keys */
60
61     };
62     ISAMD_M m = (ISAMD_M) xmalloc (sizeof(*m));
63     m->filecat = def_cat;
64
65     m->code_start = NULL;
66     m->code_item = NULL;
67     m->code_stop = NULL;
68     m->code_reset = NULL;
69
70     m->compare_item = NULL;
71
72     m->debug = 1;
73
74     m->max_blocks_mem = 10;
75
76     return m;
77 }
78
79
80
81 ISAMD isamd_open (BFiles bfs, const char *name, int writeflag, ISAMD_M method)
82 {
83     ISAMD is;
84     ISAMD_filecat filecat;
85     int i = 0;
86
87     is = (ISAMD) xmalloc (sizeof(*is));
88
89     is->method = (ISAMD_M) xmalloc (sizeof(*is->method));
90     memcpy (is->method, method, sizeof(*method));
91     filecat = is->method->filecat;
92     assert (filecat);
93
94     /* determine number of block categories */
95     if (is->method->debug)
96         logf (LOG_LOG, "isamd: bsize  maxkeys");
97     do
98     {
99         if (is->method->debug)
100             logf (LOG_LOG, "isamd:%6d %6d",
101                   filecat[i].bsize, filecat[i].mblocks);
102     } while (filecat[i++].mblocks);
103     is->no_files = i;
104     is->max_cat = --i;
105
106     assert (is->no_files > 0);
107     is->files = (ISAMD_file) xmalloc (sizeof(*is->files)*is->no_files);
108     if (writeflag)
109     {
110       /* TODO - what ever needs to be done here... */
111     }
112     else
113     {
114     }
115
116     for (i = 0; i<is->no_files; i++)
117     {
118         char fname[512];
119
120         sprintf (fname, "%s%c", name, i+'A');
121         is->files[i].bf = bf_open (bfs, fname, is->method->filecat[i].bsize,
122                                    writeflag);
123         is->files[i].head_is_dirty = 0;
124         if (!bf_read (is->files[i].bf, 0, 0, sizeof(ISAMD_head),
125                      &is->files[i].head))
126         {
127             is->files[i].head.lastblock = 1;
128             is->files[i].head.freelist = 0;
129         }
130         is->files[i].alloc_entries_num = 0;
131         is->files[i].alloc_entries_max =
132             is->method->filecat[i].bsize / sizeof(int) - 1;
133         is->files[i].alloc_buf = (char *)
134             xmalloc (is->method->filecat[i].bsize);
135         is->files[i].no_writes = 0; /* clear statistics */
136         is->files[i].no_reads = 0;
137         is->files[i].no_skip_writes = 0;
138         is->files[i].no_allocated = 0;
139         is->files[i].no_released = 0;
140         is->files[i].no_remap = 0;
141         is->files[i].no_forward = 0;
142         is->files[i].no_backward = 0;
143         is->files[i].sum_forward = 0;
144         is->files[i].sum_backward = 0;
145         is->files[i].no_next = 0;
146         is->files[i].no_prev = 0;
147
148         init_fc (is, i);
149     }
150     return is;
151 }
152
153 int isamd_block_used (ISAMD is, int type)
154 {
155     if (type < 0 || type >= is->no_files)
156         return -1;
157     return is->files[type].head.lastblock-1;
158 }
159
160 int isamd_block_size (ISAMD is, int type)
161 {
162     ISAMD_filecat filecat = is->method->filecat;
163     if (type < 0 || type >= is->no_files)
164         return -1;
165     return filecat[type].bsize;
166 }
167
168 int isamd_close (ISAMD is)
169 {
170     int i;
171
172     if (is->method->debug)
173     {
174         logf (LOG_LOG, "isamd:    next    forw   mid-f    prev   backw   mid-b");
175         for (i = 0; i<is->no_files; i++)
176             logf (LOG_LOG, "isamd:%8d%8d%8.1f%8d%8d%8.1f",
177                   is->files[i].no_next,
178                   is->files[i].no_forward,
179                   is->files[i].no_forward ?
180                   (double) is->files[i].sum_forward/is->files[i].no_forward
181                   : 0.0,
182                   is->files[i].no_prev,
183                   is->files[i].no_backward,
184                   is->files[i].no_backward ?
185                   (double) is->files[i].sum_backward/is->files[i].no_backward
186                   : 0.0);
187     }
188     if (is->method->debug)
189         logf (LOG_LOG, "isamd:  writes   reads skipped   alloc released  remap");
190     for (i = 0; i<is->no_files; i++)
191     {
192         release_fc (is, i);
193         assert (is->files[i].bf);
194         if (is->files[i].head_is_dirty)
195             bf_write (is->files[i].bf, 0, 0, sizeof(ISAMD_head),
196                  &is->files[i].head);
197         if (is->method->debug)
198             logf (LOG_LOG, "isamd:%8d%8d%8d%8d%8d%8d",
199                   is->files[i].no_writes,
200                   is->files[i].no_reads,
201                   is->files[i].no_skip_writes,
202                   is->files[i].no_allocated,
203                   is->files[i].no_released,
204                   is->files[i].no_remap);
205         xfree (is->files[i].fc_list);
206         flush_block (is, i);
207         bf_close (is->files[i].bf);
208     }
209     xfree (is->files);
210     xfree (is->method);
211     xfree (is);
212     return 0;
213 }
214
215 int isamd_read_block (ISAMD is, int cat, int pos, char *dst)
216 {
217     ++(is->files[cat].no_reads);
218     return bf_read (is->files[cat].bf, pos, 0, 0, dst);
219 }
220
221 int isamd_write_block (ISAMD is, int cat, int pos, char *src)
222 {
223     ++(is->files[cat].no_writes);
224     if (is->method->debug > 2)
225         logf (LOG_LOG, "isamd: write_block %d %d", cat, pos);
226     return bf_write (is->files[cat].bf, pos, 0, 0, src);
227 }
228
229 int isamd_write_dblock (ISAMD is, int cat, int pos, char *src,
230                       int nextpos, int offset)
231 {
232     ISAMD_BLOCK_SIZE size = offset + ISAMD_BLOCK_OFFSET_N;
233     if (is->method->debug > 2)
234         logf (LOG_LOG, "isamd: write_dblock. size=%d nextpos=%d",
235               (int) size, nextpos);
236     src -= ISAMD_BLOCK_OFFSET_N;
237     assert( ISAMD_BLOCK_OFFSET_N == sizeof(int)+sizeof(int) );
238     memcpy (src, &nextpos, sizeof(int));
239     memcpy (src + sizeof(int), &size, sizeof(size));
240     return isamd_write_block (is, cat, pos, src);
241 }
242
243 #if ISAMD_FREELIST_CHUNK
244 static void flush_block (ISAMD is, int cat)
245 {
246     char *abuf = is->files[cat].alloc_buf;
247     int block = is->files[cat].head.freelist;
248     if (block && is->files[cat].alloc_entries_num)
249     {
250         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
251         bf_write (is->files[cat].bf, block, 0, 0, abuf);
252         is->files[cat].alloc_entries_num = 0;
253     }
254     xfree (abuf);
255 }
256
257 static int alloc_block (ISAMD is, int cat)
258 {
259     int block = is->files[cat].head.freelist;
260     char *abuf = is->files[cat].alloc_buf;
261
262     (is->files[cat].no_allocated)++;
263
264     if (!block)
265     {
266         block = (is->files[cat].head.lastblock)++;   /* no free list */
267         is->files[cat].head_is_dirty = 1;
268     }
269     else
270     {
271         if (!is->files[cat].alloc_entries_num) /* read first time */
272         {
273             bf_read (is->files[cat].bf, block, 0, 0, abuf);
274             memcpy (&is->files[cat].alloc_entries_num, abuf,
275                     sizeof(is->files[cat].alloc_entries_num));
276             assert (is->files[cat].alloc_entries_num > 0);
277         }
278         /* have some free blocks now */
279         assert (is->files[cat].alloc_entries_num > 0);
280         is->files[cat].alloc_entries_num--;
281         if (!is->files[cat].alloc_entries_num)  /* last one in block? */
282         {
283             memcpy (&is->files[cat].head.freelist, abuf + sizeof(int),
284                     sizeof(int));
285             is->files[cat].head_is_dirty = 1;
286
287             if (is->files[cat].head.freelist)
288             {
289                 bf_read (is->files[cat].bf, is->files[cat].head.freelist,
290                          0, 0, abuf);
291                 memcpy (&is->files[cat].alloc_entries_num, abuf,
292                         sizeof(is->files[cat].alloc_entries_num));
293                 assert (is->files[cat].alloc_entries_num);
294             }
295         }
296         else
297             memcpy (&block, abuf + sizeof(int) + sizeof(int) *
298                     is->files[cat].alloc_entries_num, sizeof(int));
299     }
300     return block;
301 }
302
303 static void release_block (ISAMD is, int cat, int pos)
304 {
305     char *abuf = is->files[cat].alloc_buf;
306     int block = is->files[cat].head.freelist;
307
308     (is->files[cat].no_released)++;
309
310     if (block && !is->files[cat].alloc_entries_num) /* must read block */
311     {
312         bf_read (is->files[cat].bf, block, 0, 0, abuf);
313         memcpy (&is->files[cat].alloc_entries_num, abuf,
314                 sizeof(is->files[cat].alloc_entries_num));
315         assert (is->files[cat].alloc_entries_num > 0);
316     }
317     assert (is->files[cat].alloc_entries_num <= is->files[cat].alloc_entries_max);
318     if (is->files[cat].alloc_entries_num == is->files[cat].alloc_entries_max)
319     {
320         assert (block);
321         memcpy (abuf, &is->files[cat].alloc_entries_num, sizeof(int));
322         bf_write (is->files[cat].bf, block, 0, 0, abuf);
323         is->files[cat].alloc_entries_num = 0;
324     }
325     if (!is->files[cat].alloc_entries_num) /* make new buffer? */
326     {
327         memcpy (abuf + sizeof(int), &block, sizeof(int));
328         is->files[cat].head.freelist = pos;
329         is->files[cat].head_is_dirty = 1; 
330     }
331     else
332     {
333         memcpy (abuf + sizeof(int) +
334                 is->files[cat].alloc_entries_num*sizeof(int),
335                 &pos, sizeof(int));
336     }
337     is->files[cat].alloc_entries_num++;
338 }
339 #else
340 static void flush_block (ISAMD is, int cat)
341 {
342     char *abuf = is->files[cat].alloc_buf;
343     xfree (abuf);
344 }
345
346 static int alloc_block (ISAMD is, int cat)
347 {
348     int block;
349     char buf[sizeof(int)];
350
351     is->files[cat].head_is_dirty = 1;
352     (is->files[cat].no_allocated)++;
353     if ((block = is->files[cat].head.freelist))
354     {
355         bf_read (is->files[cat].bf, block, 0, sizeof(int), buf);
356         memcpy (&is->files[cat].head.freelist, buf, sizeof(int));
357     }
358     else
359         block = (is->files[cat].head.lastblock)++;
360     return block;
361 }
362
363 static void release_block (ISAMD is, int cat, int pos)
364 {
365     char buf[sizeof(int)];
366    
367     (is->files[cat].no_released)++;
368     is->files[cat].head_is_dirty = 1; 
369     memcpy (buf, &is->files[cat].head.freelist, sizeof(int));
370     is->files[cat].head.freelist = pos;
371     bf_write (is->files[cat].bf, pos, 0, sizeof(int), buf);
372 }
373 #endif
374
375 int isamd_alloc_block (ISAMD is, int cat)
376 {
377     int block = 0;
378
379     if (is->files[cat].fc_list)
380     {
381         int j, nb;
382         for (j = 0; j < is->files[cat].fc_max; j++)
383             if ((nb = is->files[cat].fc_list[j]) && (!block || nb < block))
384             {
385                 is->files[cat].fc_list[j] = 0;
386                 block = nb;
387                 break;
388             }
389     }
390     if (!block)
391         block = alloc_block (is, cat);
392     if (is->method->debug > 3)
393         logf (LOG_LOG, "isamd: alloc_block in cat %d: %d", cat, block);
394     return block;
395 }
396
397 void isamd_release_block (ISAMD is, int cat, int pos)
398 {
399     if (is->method->debug > 3)
400         logf (LOG_LOG, "isamd: release_block in cat %d: %d", cat, pos);
401     if (is->files[cat].fc_list)
402     {
403         int j;
404         for (j = 0; j<is->files[cat].fc_max; j++)
405             if (!is->files[cat].fc_list[j])
406             {
407                 is->files[cat].fc_list[j] = pos;
408                 return;
409             }
410     }
411     release_block (is, cat, pos);
412 }
413
414 static void init_fc (ISAMD is, int cat)
415 {
416     int j = 100;
417         
418     is->files[cat].fc_max = j;
419     is->files[cat].fc_list = (int *)
420         xmalloc (sizeof(*is->files[0].fc_list) * j);
421     while (--j >= 0)
422         is->files[cat].fc_list[j] = 0;
423 }
424
425 static void release_fc (ISAMD is, int cat)
426 {
427     int b, j = is->files[cat].fc_max;
428
429     while (--j >= 0)
430         if ((b = is->files[cat].fc_list[j]))
431         {
432             release_block (is, cat, b);
433             is->files[cat].fc_list[j] = 0;
434         }
435 }
436
437 void isamd_pp_close (ISAMD_PP pp)
438 {
439     ISAMD is = pp->is;
440
441     (*is->method->code_stop)(ISAMD_DECODE, pp->decodeClientData);
442     xfree (pp->buf);
443     xfree (pp);
444 }
445
446 ISAMD_PP isamd_pp_open (ISAMD is, ISAMD_P ipos)
447 {
448     ISAMD_PP pp = (ISAMD_PP) xmalloc (sizeof(*pp));
449     char *src;
450    
451     pp->cat = isamd_type(ipos);
452     pp->pos = isamd_block(ipos); 
453
454     src = pp->buf = (char *) xmalloc (is->method->filecat[pp->cat].bsize);
455
456     pp->next = 0;
457     pp->size = 0;
458     pp->offset = 0;
459     pp->is = is;
460     pp->decodeClientData = (*is->method->code_start)(ISAMD_DECODE);
461     //pp->deleteFlag = 0;
462     pp->numKeys = 0;
463     pp->diffs=0;
464     
465     if (pp->pos)
466     {
467         src = pp->buf;
468         isamd_read_block (is, pp->cat, pp->pos, src);
469         memcpy (&pp->next, src, sizeof(pp->next));
470         src += sizeof(pp->next);
471         memcpy (&pp->size, src, sizeof(pp->size));
472         src += sizeof(pp->size);
473         memcpy (&pp->numKeys, src, sizeof(pp->numKeys));
474         src += sizeof(pp->numKeys);
475         memcpy (&pp->diffs, src, sizeof(pp->diffs));
476         src += sizeof(pp->diffs);
477         assert (pp->next != pp->pos);
478         pp->offset = src - pp->buf; 
479         assert (pp->offset == ISAMD_BLOCK_OFFSET_1);
480         if (is->method->debug > 2)
481             logf (LOG_LOG, "isamd_pp_open sz=%d c=%d p=%d n=%d",
482                  pp->size, pp->cat, pp->pos, isamd_block(pp->next));
483     }
484     return pp;
485 }
486
487
488
489 void isamd_buildfirstblock(ISAMD_PP pp){
490   char *dst=pp->buf;
491   assert(pp->buf);
492   assert(pp->next != pp->pos); 
493   memcpy(dst, &pp->next, sizeof(pp->next) );
494   dst += sizeof(pp->next);
495   memcpy(dst, &pp->size,sizeof(pp->size));
496   dst += sizeof(pp->size);
497   memcpy(dst, &pp->numKeys, sizeof(pp->numKeys));
498   dst += sizeof(pp->numKeys);
499   memcpy(dst, &pp->diffs, sizeof(pp->diffs));
500   dst += sizeof(pp->diffs);  
501   assert (dst - pp->buf  == ISAMD_BLOCK_OFFSET_1);
502   if (pp->is->method->debug > 2)
503      logf (LOG_LOG, "isamd: first: sz=%d  p=%d/%d>%d/%d nk=%d d=%d",
504            pp->size, 
505            pp->cat, pp->pos, 
506            isamd_type(pp->next), isamd_block(pp->next),
507            pp->numKeys, pp->diffs);
508 }
509
510 void isamd_buildlaterblock(ISAMD_PP pp){
511   char *dst=pp->buf;
512   assert(pp->buf);
513   assert(pp->next != isamd_addr(pp->pos,pp->cat)); 
514   memcpy(dst, &pp->next, sizeof(pp->next) );
515   dst += sizeof(pp->next);
516   memcpy(dst, &pp->size,sizeof(pp->size));
517   dst += sizeof(pp->size);
518   assert (dst - pp->buf  == ISAMD_BLOCK_OFFSET_N);
519   if (pp->is->method->debug > 2)
520      logf (LOG_LOG, "isamd: l8r: sz=%d  p=%d/%d>%d/%d",
521            pp->size, 
522            pp->pos, pp->cat, 
523            isamd_block(pp->next), isamd_type(pp->next) );
524 }
525
526
527
528 /* returns non-zero if item could be read; 0 otherwise */
529 int isamd_pp_read (ISAMD_PP pp, void *buf)
530 {
531     return isamd_read_item (pp, (char **) &buf);
532 }
533
534 /* read one item from file - decode and store it in *dst.
535    Returns
536      0 if end-of-file
537      1 if item could be read ok and NO boundary
538      2 if item could be read ok and boundary */
539 int isamd_read_item (ISAMD_PP pp, char **dst)
540 {
541     ISAMD is = pp->is;
542     char *src = pp->buf + pp->offset;
543     int newcat;
544
545     if (pp->offset >= pp->size)
546     {
547         if (!pp->next)
548         {
549             pp->pos = 0;
550             return 0; /* end of file */
551         }
552         if (pp->next > pp->pos)
553         {
554             if (pp->next == pp->pos + 1)
555                 is->files[pp->cat].no_next++;
556             else
557             {
558                 is->files[pp->cat].no_forward++;
559                 is->files[pp->cat].sum_forward += pp->next - pp->pos;
560             }
561         }
562         else
563         {
564             if (pp->next + 1 == pp->pos)
565                 is->files[pp->cat].no_prev++;
566             else
567             {
568                 is->files[pp->cat].no_backward++;
569                 is->files[pp->cat].sum_backward += pp->pos - pp->next;
570             }
571         }
572         /* out new block position */
573         newcat = isamd_type(pp->next);
574         if (pp->cat != newcat ) {
575           pp->buf = xrealloc(pp->buf, is->method->filecat[newcat].bsize);
576         }
577         pp->pos = isamd_block(pp->next);
578         pp->cat = isamd_type(pp->next);
579         
580         src = pp->buf;
581         /* read block and save 'next' and 'size' entry */
582         isamd_read_block (is, pp->cat, pp->pos, src);
583         memcpy (&pp->next, src, sizeof(pp->next));
584         src += sizeof(pp->next);
585         memcpy (&pp->size, src, sizeof(pp->size));
586         src += sizeof(pp->size);
587         /* assume block is non-empty */
588         assert (src - pp->buf == ISAMD_BLOCK_OFFSET_N);
589         assert (pp->next != isamd_addr(pp->pos,pp->cat));
590         //if (pp->deleteFlag)
591         //    isamd_release_block (is, pp->cat, pp->pos);
592         (*is->method->code_reset)(pp->decodeClientData);
593         (*is->method->code_item)(ISAMD_DECODE, pp->decodeClientData, dst, &src);
594         pp->offset = src - pp->buf; 
595         if (is->method->debug > 2)
596             logf (LOG_LOG, "isamd: read_block size=%d %d %d next=%d",
597                  pp->size, pp->cat, pp->pos, pp->next);
598         return 2;
599     }
600     (*is->method->code_item)(ISAMD_DECODE, pp->decodeClientData, dst, &src);
601     pp->offset = src - pp->buf; 
602     return 1;
603 }
604
605 int isamd_pp_num (ISAMD_PP pp)
606 {
607     return pp->numKeys;
608 }
609
610 static char *hexdump(unsigned char *p, int len, char *buff) {
611   static char localbuff[128];
612   char bytebuff[8];
613   if (!buff) buff=localbuff;
614   *buff='\0';
615   while (len--) {
616     sprintf(bytebuff,"%02x",*p);
617     p++;
618     strcat(buff,bytebuff);
619     if (len) strcat(buff," ");
620   }
621   return buff;
622 }
623
624
625 void isamd_pp_dump (ISAMD is, ISAMD_P ipos)
626 {
627   ISAMD_PP pp;
628   ISAMD_P oldaddr=0;
629   struct it_key key;
630   int i,n;
631   int occur =0;
632   int oldoffs;
633   char hexbuff[64];
634   
635   logf(LOG_LOG,"dumping isamd block %d (%d:%d)",
636                   (int)ipos, isamd_type(ipos), isamd_block(ipos) );
637   pp=isamd_pp_open(is,ipos);
638   logf(LOG_LOG,"numKeys=%d,  ofs=%d d=%d",
639        pp->numKeys, 
640        pp->offset, pp->diffs);
641   oldoffs= pp->offset;
642   while(isamd_pp_read(pp, &key))
643   {
644      if (oldaddr != isamd_addr(pp->pos,pp->cat) )
645      {
646         oldaddr = isamd_addr(pp->pos,pp->cat); 
647         logf(LOG_LOG,"block %d (%d:%d) sz=%d nx=%d (%d:%d) ofs=%d",
648                   isamd_addr(pp->pos,pp->cat), 
649                   pp->cat, pp->pos, pp->size,
650                   pp->next, isamd_type(pp->next), isamd_block(pp->next),
651                   pp->offset);
652         i=0;      
653         while (i<pp->size) {
654           n=pp->size-i;
655           if (n>8) n=8;
656           logf(LOG_LOG,"  %05x: %s",i,hexdump(pp->buf+i,n,hexbuff));
657           i+=n;
658         }
659         if (oldoffs >  ISAMD_BLOCK_OFFSET_N)
660            oldoffs=ISAMD_BLOCK_OFFSET_N;
661      } /* new block */
662      occur++;
663      logf (LOG_LOG,"    got %d:%d=%x:%x from %s at %d=%x",
664                   key.sysno, key.seqno,
665                   key.sysno, key.seqno,
666                   hexdump(pp->buf+oldoffs, pp->offset-oldoffs, hexbuff),
667                   oldoffs, oldoffs);
668      oldoffs = pp->offset;
669   }
670   /*!*/ /*TODO: dump diffs too!!! */
671   isamd_pp_close(pp);
672 } /* dump */
673
674 /*
675  * $Log: isamd.c,v $
676  * Revision 1.2  1999-07-14 15:05:30  heikki
677  * slow start on isam-d
678  *
679  * Revision 1.1  1999/07/14 12:34:43  heikki
680  * Copied from isamh, starting to change things...
681  *
682  *
683  */