Added end record marker
[idzebra-moved-to-github.git] / isam / isam.c
1 /*
2  * Copyright (C) 1994, Index Data I/S 
3  * All rights reserved.
4  * Sebastian Hammer, Adam Dickmeiss
5  *
6  * $Log: isam.c,v $
7  * Revision 1.21  1996-03-29 14:11:47  quinn
8  * Change to is_merge
9  *
10  * Revision 1.20  1996/03/19  13:14:57  quinn
11  * Moved an xfree()
12  *
13  * Revision 1.19  1996/02/10  12:20:56  quinn
14  * *** empty log message ***
15  *
16  * Revision 1.18  1996/02/06  10:19:56  quinn
17  * Attempt at fixing bug. Not all blocks were read before they were unlinked
18  * prior to a remap operation.
19  *
20  * Revision 1.17  1995/12/06  15:48:44  quinn
21  * Fixed update-problem.
22  *
23  * Revision 1.16  1995/12/06  14:48:26  quinn
24  * Fixed some strange bugs.
25  *
26  * Revision 1.15  1995/12/06  09:59:45  quinn
27  * Fixed memory-consumption bug in memory.c
28  * Added more blocksizes to the default ISAM configuration.
29  *
30  * Revision 1.14  1995/11/24  17:26:19  quinn
31  * Mostly about making some ISAM stuff in the config file optional.
32  *
33  * Revision 1.13  1995/10/17  18:03:15  adam
34  * Commented out qsort in is_merge.
35  *
36  * Revision 1.12  1995/09/06  16:11:41  adam
37  * Keysize parameter to is_open (if non-zero).
38  *
39  * Revision 1.11  1995/09/04  12:33:46  adam
40  * Various cleanup. YAZ util used instead.
41  *
42  * Revision 1.10  1994/09/28  16:58:32  quinn
43  * Small mod.
44  *
45  * Revision 1.9  1994/09/28  12:56:15  quinn
46  * Added access functions (ISPT)
47  *
48  * Revision 1.8  1994/09/28  12:32:17  quinn
49  * Trivial
50  *
51  * Revision 1.7  1994/09/28  11:56:25  quinn
52  * Added sort of input to is_merge
53  *
54  * Revision 1.6  1994/09/28  11:29:33  quinn
55  * Added cmp parameter.
56  *
57  * Revision 1.5  1994/09/27  20:03:50  quinn
58  * Seems relatively bug-free.
59  *
60  * Revision 1.4  1994/09/26  17:11:29  quinn
61  * Trivial
62  *
63  * Revision 1.3  1994/09/26  17:06:35  quinn
64  * Back again...
65  *
66  * Revision 1.1  1994/09/12  08:02:13  quinn
67  * Not functional yet
68  *
69  */
70
71 #include <stdio.h>
72 #include <stdlib.h>
73 #include <string.h>
74 #include <ctype.h>
75
76 #include <alexutil.h>
77 #include <bfile.h>
78 #include <isam.h>
79 #include <common.h>
80 #include "isutil.h"
81 #include "rootblk.h"
82 #include "keyops.h"
83
84 static ispt_struct *ispt_freelist = 0;
85
86 static struct
87 {
88     int total_merge_operations;
89     int total_items;
90     int dub_items_removed;
91     int new_items;
92     int failed_deletes;
93     int skipped_inserts;
94     int delete_insert_noop;
95     int delete_replace;
96     int delete;
97     int remaps;
98     int block_jumps;
99     int tab_deletes;
100     int new_tables;
101 } statistics;
102
103 static ISPT ispt_alloc()
104 {
105     ISPT p;
106
107     if (ispt_freelist)
108     {
109         p = ispt_freelist;
110         ispt_freelist = ispt_freelist->next;
111     }
112     else
113         p = xmalloc(sizeof(ispt_struct));
114     return p;
115 }
116
117 static void ispt_free(ISPT pt)
118 {
119     pt->next = ispt_freelist;
120     ispt_freelist = pt;
121 }
122
123 static int splitargs(const char *s, char *bf[], int max)
124 {
125     int ct = 0;
126     for (;;)
127     {
128         while (*s && isspace(*s))
129             s++;
130         bf[ct] = (char *) s;
131         if (!*s)
132                 return ct;
133         ct++;
134         if (ct > max)
135         {
136             logf (LOG_WARN, "Ignoring extra args to is resource");
137             bf[ct] = '\0';
138             return(ct - 1);
139         }
140         while (*s && !isspace(*s))
141             s++;
142     }
143 }
144
145 /*
146  * Open isam file.
147  * Process resources.
148  */
149 ISAM is_open(const char *name, int (*cmp)(const void *p1, const void *p2),
150     int writeflag, int keysize)
151 {
152     ISAM new;
153     char *nm, *r, *pp[IS_MAX_BLOCKTYPES+1], m[2];
154     int num, size, rs, tmp, i;
155     is_type_header th;
156
157     logf (LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY");
158     if (writeflag)
159     {
160         statistics.total_merge_operations = 0;
161         statistics.total_items = 0;
162         statistics.dub_items_removed = 0;
163         statistics.new_items = 0;
164         statistics.failed_deletes = 0;
165         statistics.skipped_inserts = 0;
166         statistics.delete_insert_noop = 0;
167         statistics.delete_replace = 0;
168         statistics.delete = 0;
169         statistics.remaps = 0;
170         statistics.new_tables = 0;
171         statistics.block_jumps = 0;
172         statistics.tab_deletes = 0;
173     }
174
175     new = xmalloc(sizeof(*new));
176     new->writeflag = writeflag;
177     for (i = 0; i < IS_MAX_BLOCKTYPES; i++)
178         new->types[i].index = 0;                        /* dummy */
179
180     /* determine number and size of blocktypes */
181     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".",
182         "blocktypes", 0), "64 512 4K 32K")) ||
183         !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
184     {
185         logf (LOG_FATAL, "Failed to locate resource %s", nm);
186         return 0;
187     }
188     new->num_types = num;
189     for (i = 0; i < num; i++)
190     {
191         if ((rs = sscanf(pp[i], "%d%1[bBkKmM]", &size, m)) < 1)
192         {
193             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
194             return 0;
195         }
196         if (rs == 1)
197                 *m = 'b';
198         switch (*m)
199         {
200                 case 'b': case 'B':
201                     new->types[i].blocksize = size; break;
202                 case 'k': case 'K':
203                     new->types[i].blocksize = size * 1024; break;
204                 case 'm': case 'M':
205                     new->types[i].blocksize = size * 1048576; break;
206                 default:
207                     logf (LOG_FATAL, "Illegal size suffix: %c", *m);
208                     return 0;
209         }
210         new->types[i].dbuf = xmalloc(new->types[i].blocksize);
211         m[0] = 'A' + i;
212         m[1] = '\0';
213         if (!(new->types[i].bf = bf_open(strconcat(name, m, 0), 
214             new->types[i].blocksize, writeflag)))
215         {
216             logf (LOG_FATAL, "bf_open failed");
217             return 0;
218         }
219         if ((rs = is_rb_read(&new->types[i], &th)) > 0)
220         {
221             if (th.blocksize != new->types[i].blocksize)
222             {
223                 logf (LOG_FATAL, "File blocksize mismatch in %s", name);
224                 exit(1);
225             }
226             new->types[i].freelist = th.freelist;
227             new->types[i].top = th.top;
228         }
229         else if (writeflag) /* write dummy superblock to determine top */
230         {
231             if ((rs = is_rb_write(&new->types[i], &th)) <=0)  /* dummy */
232             {
233                 logf (LOG_FATAL, "Failed to write initial superblock.");
234                 exit(1);
235             }
236             new->types[i].freelist = -1;
237             new->types[i].top = rs;
238         }
239         /* ELSE: this is an empty file opened in read-only mode. */
240     }
241     if (keysize > 0)
242         new->keysize = keysize;
243     else
244     {
245         if (!(r = res_get_def(common_resource, nm = strconcat(name, ".",
246                                                               "keysize",
247                                                               0), "4")))
248         {
249             logf (LOG_FATAL, "Failed to locate resource %s", nm);
250             return 0;
251         }
252         if ((new->keysize = atoi(r)) <= 0)
253         {
254             logf (LOG_FATAL, "Must specify positive keysize.");
255             return 0;
256         }
257     }
258
259     /* determine repack percent */
260     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".", "repack",
261         0), IS_DEF_REPACK_PERCENT)))
262     {
263         logf (LOG_FATAL, "Failed to locate resource %s", nm);
264         return 0;
265     }
266     new->repack = atoi(r);
267
268     /* determine max keys/blocksize */
269     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".",
270         "maxkeys", 0), "50 640 10000")) || !(num = splitargs(r, pp,
271         IS_MAX_BLOCKTYPES)))
272     {
273         logf (LOG_FATAL, "Failed to locate resource %s", nm);
274         return 0;
275     }
276     if (num < new->num_types -1)
277     {
278         logf (LOG_FATAL, "Not enough elements in %s", nm);
279         return 0;
280     }
281     for (i = 0; i < num; i++)
282     {
283         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
284         {
285             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
286             return 0;
287         }
288         new->types[i].max_keys = tmp;
289     }
290
291     /* determine max keys/block */
292     for (i = 0; i < new->num_types; i++)
293     {
294         if (!new->types[i].index)
295         {
296             new->types[i].max_keys_block = (new->types[i].blocksize - 2 *
297                 sizeof(int)) / new->keysize;
298             new->types[i].max_keys_block0 = (new->types[i].blocksize - 3 *
299                 sizeof(int)) / new->keysize;
300         }
301         else
302             new->types[i].max_keys_block = new->types[i].max_keys_block0 /
303                 new->keysize;
304         if (new->types[i].max_keys_block0 < 1)
305         {
306             logf (LOG_FATAL, "Blocksize too small in %s", name);
307             exit(1);
308         }
309     }
310
311     /* determine nice fill rates */
312     if (!(r = res_get_def(common_resource, nm = strconcat(name, ".",
313         "nicefill", 0), "90 90 90 95")) || !(num = splitargs(r, pp,
314         IS_MAX_BLOCKTYPES)))
315     {
316         logf (LOG_FATAL, "Failed to locate resource %s", nm);
317         return 0;
318     }
319     if (num < new->num_types)
320     {
321         logf (LOG_FATAL, "Not enough elements in %s", nm);
322         return 0;
323     }
324     for (i = 0; i < num; i++)
325     {
326         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
327         {
328             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
329             return 0;
330         }
331         new->types[i].nice_keys_block = (new->types[i].max_keys_block0 * tmp) /
332             100;
333         if (new->types[i].nice_keys_block < 1)
334                 new->types[i].nice_keys_block = 1;
335     }
336
337     new->cmp = cmp ? cmp : is_default_cmp;
338     return new;
339 }
340
341 /*
342  * Close isam file.
343  */
344 int is_close(ISAM is)
345 {
346     int i;
347     is_type_header th;
348
349     logf (LOG_DEBUG, "is_close()");
350     for (i = 0; i < is->num_types; i++)
351     {
352         if (is->types[i].bf)
353         {
354             if (is->writeflag)
355             {
356                 th.blocksize = is->types[i].blocksize;
357                 th.keysize = is->keysize;
358                 th.freelist = is->types[i].freelist;
359                 th.top = is->types[i].top;
360                 if (is_rb_write(&is->types[i], &th) < 0)
361                 {
362                     logf (LOG_FATAL, "Failed to write headerblock");
363                     exit(1);
364                 }
365             }
366             bf_close(is->types[i].bf);
367         }
368     }
369     if (is->writeflag)
370     {
371         logf(LOG_LOG, "ISAM statistics:");
372         logf(LOG_LOG, "total_merge_operations      %d",
373             statistics.total_merge_operations);
374         logf(LOG_LOG, "total_items                 %d", statistics.total_items);
375         logf(LOG_LOG, "dub_items_removed           %d",
376             statistics.dub_items_removed);
377         logf(LOG_LOG, "new_items                   %d", statistics.new_items);
378         logf(LOG_LOG, "failed_deletes              %d",
379             statistics.failed_deletes);
380         logf(LOG_LOG, "skipped_inserts             %d",
381             statistics.skipped_inserts);
382         logf(LOG_LOG, "delete_insert_noop          %d",
383             statistics.delete_insert_noop);
384         logf(LOG_LOG, "delete_replace              %d",
385             statistics.delete_replace);
386         logf(LOG_LOG, "delete                      %d", statistics.delete);
387         logf(LOG_LOG, "remaps                      %d", statistics.remaps);
388         logf(LOG_LOG, "block_jumps                 %d", statistics.block_jumps);
389         logf(LOG_LOG, "tab_deletes                 %d", statistics.tab_deletes);
390     }
391     xfree(is);
392     return 0;
393 }
394
395 static ISAM_P is_address(int type, int pos)
396 {
397     ISAM_P r;
398
399     r = pos << 2;
400     r |= type;
401     return r;
402 }
403
404 ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data)
405 {
406     is_mtable tab;
407     int res;
408     char keybuf[IS_MAX_RECORD];
409     int oldnum, oldtype, i;
410     char operation, *record;
411
412     statistics.total_merge_operations++;
413     statistics.total_items += num;
414     if (!pos)
415         statistics.new_tables++;
416
417     is_m_establish_tab(is, &tab, pos);
418     if (pos)
419         if (is_m_read_full(&tab, tab.data) < 0)
420         {
421             logf (LOG_FATAL, "read_full failed");
422             exit(1);
423         }
424     oldnum = tab.num_records;
425     oldtype = tab.pos_type;
426     while (num)
427     {
428         operation = *(data)++;
429         record = (char*) data;
430         data += is_keysize(is);
431         num--;
432         while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1))
433         {
434             data += 1 + is_keysize(is);
435             num--;
436             statistics.dub_items_removed++;
437         }
438         if ((res = is_m_seek_record(&tab, record)) > 0)  /* no match */
439         {
440             if (operation == KEYOP_INSERT)
441             {
442                 logf (LOG_DEBUG, "XXInserting new record.");
443                 is_m_write_record(&tab, record);
444                 statistics.new_items++;
445             }
446             else
447             {
448                 logf (LOG_DEBUG, "XXDeletion failed to find match.");
449                 statistics.failed_deletes++;
450             }
451         }
452         else /* match found */
453         {
454             if (operation == KEYOP_INSERT)
455             {
456                 logf (LOG_DEBUG, "XXSkipping insertion - match found.");
457                 statistics.skipped_inserts++;
458                 continue;
459             }
460             else if (operation == KEYOP_DELETE)
461             {
462                 /* try to avoid needlessly moving data */
463                 if (num && *(data) == KEYOP_INSERT)
464                 {
465                     /* next key is identical insert? - NOOP - skip it */
466                     if (!memcmp(record, data + 1, is_keysize(is)))
467                     {
468                         logf (LOG_DEBUG, "XXNoop delete. skipping.");
469                         data += 1 + is_keysize(is);
470                         num--;
471                         while (num && !memcmp(data, data + is_keysize(tab.is) +
472                             1, is_keysize(tab.is) + 1))
473                         {
474                             data += 1 + is_keysize(is);
475                             num--;
476                             statistics.dub_items_removed++;
477                         }
478                         statistics.delete_insert_noop++;
479                         continue;
480                     }
481                     /* else check if next key can fit in this position */
482                     if (is_m_peek_record(&tab, keybuf) &&
483                         (*is->cmp)(data + 1, keybuf) < 0)
484                     {
485                         logf (LOG_DEBUG, "XXReplacing record.");
486                         is_m_replace_record(&tab, data + 1);
487                         data += 1 + is_keysize(is);
488                         num--;
489                         while (num && !memcmp(data, data + is_keysize(tab.is) +
490                             1, is_keysize(tab.is) + 1))
491                         {
492                             data += 1 + is_keysize(is);
493                             num--;
494                             statistics.dub_items_removed++;
495                         }
496                         statistics.delete_replace++;
497                         continue;
498                     }
499                 }
500                 logf (LOG_DEBUG, "Deleting record.");
501                 is_m_delete_record(&tab);
502                 statistics.delete++;
503             }
504         }
505     }
506     i = tab.pos_type;
507     while (i < tab.is->num_types - 1 && tab.num_records >
508         tab.is->types[i].max_keys)
509         i++;
510     if (i != tab.pos_type)
511     {
512         /* read remaining blocks */
513         for (; tab.cur_mblock; tab.cur_mblock = tab.cur_mblock->next)
514             if (tab.cur_mblock->state < IS_MBSTATE_CLEAN)
515                 is_m_read_full(&tab, tab.cur_mblock);
516         is_p_unmap(&tab);
517         tab.pos_type = i;
518         if (pos)
519             statistics.block_jumps++;
520     }
521     if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) *
522         100) / oldnum > tab.is->repack)
523     {
524         is_p_remap(&tab);
525         statistics.remaps++;
526     }
527     else
528         is_p_align(&tab);
529     if (tab.data)
530     {
531         is_p_sync(&tab);
532         pos = is_address(tab.pos_type, tab.data->diskpos);
533     }
534     else
535     {
536         pos = 0;
537         statistics.tab_deletes++;
538     }
539     is_m_release_tab(&tab);
540     return pos;
541 }
542
543 /*
544  * Locate a table of keys in an isam file. The ISPT is an individual
545  * position marker for that table.
546  */
547 ISPT is_position(ISAM is, ISAM_P pos)
548 {
549     ispt_struct *p;
550
551     p = ispt_alloc();
552     is_m_establish_tab(is, &p->tab, pos);
553     return p;
554 }
555
556 /*
557  * Release ISPT.
558  */
559 void is_pt_free(ISPT ip)
560 {
561     is_m_release_tab(&ip->tab);
562     ispt_free(ip);
563 }
564
565 /*
566  * Read a key from a table.
567  */
568 int is_readkey(ISPT ip, void *buf)
569 {
570     return is_m_read_record(&ip->tab, buf, 0);
571 }    
572
573 int is_numkeys(ISPT ip)
574 {
575     return is_m_num_records(&ip->tab);
576 }
577
578 void is_rewind(ISPT ip)
579 {
580     is_m_rewind(&ip->tab);
581 }