1 /* $Id: kinput.c,v 1.56 2003-06-23 15:35:25 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
5 This file is part of the Zebra server.
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra. If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
38 #define KEY_SIZE (1+sizeof(struct it_key))
39 #define INP_NAME_MAX 768
40 #define INP_BUF_START 60000
41 #define INP_BUF_ADD 400000
46 off_t offset; /* file offset */
47 unsigned char *buf; /* buffer block */
48 size_t buf_size; /* number of read bytes in block */
49 size_t chunk; /* number of bytes allocated */
50 size_t buf_ptr; /* current position in buffer */
51 char *prev_name; /* last word read */
52 int sysno; /* last sysno */
53 int seqno; /* last seqno */
54 off_t length; /* length of file */
55 /* handler invoked in each read */
56 void (*readHandler)(struct key_file *keyp, void *rinfo);
61 void getFnameTmp (Res res, char *fname, int no)
65 pre = res_get_def (res, "keyTmpDir", ".");
66 sprintf (fname, "%s/key%d.tmp", pre, no);
69 void extract_get_fname_tmp (ZebraHandle zh, char *fname, int no)
73 pre = res_get_def (zh->res, "keyTmpDir", ".");
74 sprintf (fname, "%s/key%d.tmp", pre, no);
77 void key_file_chunk_read (struct key_file *f)
79 int nr = 0, r = 0, fd;
81 getFnameTmp (f->res, fname, f->no);
82 fd = open (fname, O_BINARY|O_RDONLY);
88 logf (LOG_WARN|LOG_ERRNO, "cannot open %s", fname);
93 if ((f->length = lseek (fd, 0L, SEEK_END)) == (off_t) -1)
95 logf (LOG_WARN|LOG_ERRNO, "cannot seek %s", fname);
100 if (lseek (fd, f->offset, SEEK_SET) == -1)
102 logf (LOG_WARN|LOG_ERRNO, "cannot seek %s", fname);
106 while (f->chunk - nr > 0)
108 r = read (fd, f->buf + nr, f->chunk - nr);
115 logf (LOG_WARN|LOG_ERRNO, "read of %s", fname);
121 (*f->readHandler)(f, f->readInfo);
125 void key_file_destroy (struct key_file *f)
128 xfree (f->prev_name);
132 struct key_file *key_file_init (int no, int chunk, Res res)
136 f = (struct key_file *) xmalloc (sizeof(*f));
144 f->readHandler = NULL;
145 f->buf = (unsigned char *) xmalloc (f->chunk);
146 f->prev_name = (char *) xmalloc (INP_NAME_MAX);
147 *f->prev_name = '\0';
148 key_file_chunk_read (f);
152 int key_file_getc (struct key_file *f)
154 if (f->buf_ptr < f->buf_size)
155 return f->buf[(f->buf_ptr)++];
156 if (f->buf_size < f->chunk)
158 f->offset += f->buf_size;
159 key_file_chunk_read (f);
160 if (f->buf_ptr < f->buf_size)
161 return f->buf[(f->buf_ptr)++];
166 int key_file_decode (struct key_file *f)
170 c = key_file_getc (f);
177 d = ((c&63) << 8) + (key_file_getc (f) & 0xff);
180 d = ((c&63) << 8) + (key_file_getc (f) & 0xff);
181 d = (d << 8) + (key_file_getc (f) & 0xff);
184 d = ((c&63) << 8) + (key_file_getc (f) & 0xff);
185 d = (d << 8) + (key_file_getc (f) & 0xff);
186 d = (d << 8) + (key_file_getc (f) & 0xff);
192 int key_file_read (struct key_file *f, char *key)
197 c = key_file_getc (f);
200 strcpy (key, f->prev_name);
209 while ((key[i++] = key_file_getc (f)))
211 strcpy (f->prev_name, key);
214 d = key_file_decode (f);
217 itkey.sysno = d + f->sysno;
220 f->sysno = itkey.sysno;
223 d = key_file_decode (f);
224 itkey.seqno = d + f->seqno;
225 f->seqno = itkey.seqno;
226 memcpy (key + i, &itkey, sizeof(struct it_key));
227 return i + sizeof (struct it_key);
232 struct key_file **file;
237 int (*cmp)(const void *p1, const void *p2);
238 struct zebra_register *reg;
247 struct heap_info *key_heap_init (int nkeys,
248 int (*cmp)(const void *p1, const void *p2))
250 struct heap_info *hi;
253 hi = (struct heap_info *) xmalloc (sizeof(*hi));
254 hi->info.file = (struct key_file **)
255 xmalloc (sizeof(*hi->info.file) * (1+nkeys));
256 hi->info.buf = (char **) xmalloc (sizeof(*hi->info.buf) * (1+nkeys));
258 hi->ptr = (int *) xmalloc (sizeof(*hi->ptr) * (1+nkeys));
260 for (i = 0; i<= nkeys; i++)
263 hi->info.buf[i] = (char *) xmalloc (INP_NAME_MAX);
268 hi->no_deletions = 0;
269 hi->no_insertions = 0;
270 hi->no_iterations = 0;
274 void key_heap_destroy (struct heap_info *hi, int nkeys)
277 yaz_log (LOG_DEBUG, "key_heap_destroy");
278 for (i = 0; i<=nkeys; i++)
279 xfree (hi->info.buf[i]);
281 xfree (hi->info.buf);
283 xfree (hi->info.file);
287 static void key_heap_swap (struct heap_info *hi, int i1, int i2)
292 hi->ptr[i1] = hi->ptr[i2];
297 static void key_heap_delete (struct heap_info *hi)
299 int cur = 1, child = 2;
301 assert (hi->heapnum > 0);
303 key_heap_swap (hi, 1, hi->heapnum);
305 while (child <= hi->heapnum) {
306 if (child < hi->heapnum &&
307 (*hi->cmp)(&hi->info.buf[hi->ptr[child]],
308 &hi->info.buf[hi->ptr[child+1]]) > 0)
310 if ((*hi->cmp)(&hi->info.buf[hi->ptr[cur]],
311 &hi->info.buf[hi->ptr[child]]) > 0)
313 key_heap_swap (hi, cur, child);
322 static void key_heap_insert (struct heap_info *hi, const char *buf, int nbytes,
327 cur = ++(hi->heapnum);
328 memcpy (hi->info.buf[hi->ptr[cur]], buf, nbytes);
329 hi->info.file[hi->ptr[cur]] = kf;
332 while (parent && (*hi->cmp)(&hi->info.buf[hi->ptr[parent]],
333 &hi->info.buf[hi->ptr[cur]]) > 0)
335 key_heap_swap (hi, cur, parent);
341 static int heap_read_one (struct heap_info *hi, char *name, char *key)
344 char rbuf[INP_NAME_MAX];
350 strcpy (name, hi->info.buf[n]);
351 kf = hi->info.file[n];
353 memcpy (key, hi->info.buf[n] + r+1, KEY_SIZE);
354 key_heap_delete (hi);
355 if ((r = key_file_read (kf, rbuf)))
356 key_heap_insert (hi, rbuf, r, kf);
364 static void pkey(const char *b, int mode)
366 struct it_key *key = (struct it_key *) b;
367 printf ("%c %d:%d\n", mode + 48, key->sysno, key->seqno);
371 struct heap_cread_info {
372 char prev_name[INP_NAME_MAX];
373 char cur_name[INP_NAME_MAX];
378 struct heap_info *hi;
384 static int heap_cread_item (void *vp, char **dst, int *insertMode);
386 int heap_cread_item2 (void *vp, char **dst, int *insertMode)
388 struct heap_cread_info *p = (struct heap_cread_info *) vp;
391 if (p->ret == 0) /* lookahead was 0?. Return that in read next round */
396 else if (p->ret == -1) /* Must read new item ? */
398 char *dst_1 = p->key_1;
399 p->ret = heap_cread_item(vp, &dst_1, &p->mode_1);
400 p->sz_1 = dst_1 - p->key_1;
403 { /* lookahead in 2 . Now in 1. */
405 p->mode_1 = p->mode_2;
406 memcpy (p->key_1, p->key_2, p->sz_2);
409 level = 1; /* insert */
411 level = -1; /* delete */
414 char *dst_2 = p->key_2;
415 p->ret = heap_cread_item(vp, &dst_2, &p->mode_2);
423 p->sz_2 = dst_2 - p->key_2;
424 if (p->sz_1 == p->sz_2 && memcmp(p->key_1, p->key_2, p->sz_1) == 0)
426 if (p->mode_2) /* adjust level according to deletes/inserts */
435 /* all the same. new round .. */
437 p->mode_1 = p->mode_2;
438 memcpy (p->key_1, p->key_2, p->sz_1);
440 level = 1; /* insert */
442 level = -1; /* delete */
445 /* outcome is insert (1) or delete (0) depending on final level */
450 memcpy (*dst, p->key_1, p->sz_1);
453 pkey(*dst, *insertMode); fflush(stdout);
459 int heap_cread_item (void *vp, char **dst, int *insertMode)
461 struct heap_cread_info *p = (struct heap_cread_info *) vp;
462 struct heap_info *hi = p->hi;
464 if (p->first_in_list)
466 *insertMode = p->key[0];
467 memcpy (*dst, p->key+1, sizeof(struct it_key));
470 pkey(*dst, *insertMode);
472 (*dst) += sizeof(struct it_key);
473 p->first_in_list = 0;
476 strcpy (p->prev_name, p->cur_name);
477 if (!(p->more = heap_read_one (hi, p->cur_name, p->key)))
479 if (*p->cur_name && strcmp (p->cur_name, p->prev_name))
481 p->first_in_list = 1;
484 *insertMode = p->key[0];
485 memcpy (*dst, p->key+1, sizeof(struct it_key));
488 pkey(*dst, *insertMode);
490 (*dst) += sizeof(struct it_key);
494 int heap_inpc (struct heap_info *hi)
496 struct heap_cread_info hci;
497 ISAMC_I *isamc_i = (ISAMC_I *) xmalloc (sizeof(*isamc_i));
499 hci.key = (char *) xmalloc (KEY_SIZE);
500 hci.key_1 = (char *) xmalloc (KEY_SIZE);
501 hci.key_2 = (char *) xmalloc (KEY_SIZE);
503 hci.first_in_list = 1;
505 hci.more = heap_read_one (hi, hci.cur_name, hci.key);
507 isamc_i->clientData = &hci;
508 isamc_i->read_item = heap_cread_item2;
512 char this_name[INP_NAME_MAX];
513 ISAMC_P isamc_p, isamc_p2;
516 strcpy (this_name, hci.cur_name);
517 assert (hci.cur_name[1]);
519 if ((dict_info = dict_lookup (hi->reg->dict, hci.cur_name)))
521 memcpy (&isamc_p, dict_info+1, sizeof(ISAMC_P));
522 isamc_p2 = isc_merge (hi->reg->isamc, isamc_p, isamc_i);
526 if (!dict_delete (hi->reg->dict, this_name))
532 if (isamc_p2 != isamc_p)
533 dict_insert (hi->reg->dict, this_name,
534 sizeof(ISAMC_P), &isamc_p2);
539 isamc_p = isc_merge (hi->reg->isamc, 0, isamc_i);
541 dict_insert (hi->reg->dict, this_name, sizeof(ISAMC_P), &isamc_p);
552 /* for debugging only */
553 static void print_dict_item (ZebraMaps zm, const char *s)
556 char keybuf[IT_MAX_WORD+1];
558 const char *from = s + 2;
562 const char *res = zebra_maps_output (zm, reg_type, &from);
570 yaz_log (LOG_LOG, "%s", keybuf);
574 int heap_inpb (struct heap_info *hi)
576 struct heap_cread_info hci;
577 ISAMC_I *isamc_i = (ISAMC_I *) xmalloc (sizeof(*isamc_i));
579 hci.key = (char *) xmalloc (KEY_SIZE);
580 hci.key_1 = (char *) xmalloc (KEY_SIZE);
581 hci.key_2 = (char *) xmalloc (KEY_SIZE);
583 hci.first_in_list = 1;
585 hci.more = heap_read_one (hi, hci.cur_name, hci.key);
587 isamc_i->clientData = &hci;
588 isamc_i->read_item = heap_cread_item2;
592 char this_name[INP_NAME_MAX];
593 ISAMC_P isamc_p, isamc_p2;
596 strcpy (this_name, hci.cur_name);
597 assert (hci.cur_name[1]);
601 print_dict_item (hi->reg->zebra_maps, hci.cur_name);
603 if ((dict_info = dict_lookup (hi->reg->dict, hci.cur_name)))
605 memcpy (&isamc_p, dict_info+1, sizeof(ISAMC_P));
606 isamc_p2 = isamb_merge (hi->reg->isamb, isamc_p, isamc_i);
610 if (!dict_delete (hi->reg->dict, this_name))
616 if (isamc_p2 != isamc_p)
617 dict_insert (hi->reg->dict, this_name,
618 sizeof(ISAMC_P), &isamc_p2);
623 isamc_p = isamb_merge (hi->reg->isamb, 0, isamc_i);
625 dict_insert (hi->reg->dict, this_name, sizeof(ISAMC_P), &isamc_p);
635 int heap_inpd (struct heap_info *hi)
637 struct heap_cread_info hci;
638 ISAMD_I isamd_i = (ISAMD_I) xmalloc (sizeof(*isamd_i));
640 hci.key = (char *) xmalloc (KEY_SIZE);
641 hci.key_1 = (char *) xmalloc (KEY_SIZE);
642 hci.key_2 = (char *) xmalloc (KEY_SIZE);
644 hci.first_in_list = 1;
646 hci.more = heap_read_one (hi, hci.cur_name, hci.key);
648 isamd_i->clientData = &hci;
649 isamd_i->read_item = heap_cread_item;
653 char this_name[INP_NAME_MAX];
655 char dictentry[ISAMD_MAX_DICT_LEN+1];
658 strcpy (this_name, hci.cur_name);
660 /* print_dict_item (hi->reg->zebra_maps, hci.cur_name); */
661 /*!*/ /* FIXME: depend on isamd-debug */
663 assert (hci.cur_name[1]);
665 if ((dict_info = dict_lookup (hi->reg->dict, hci.cur_name)))
667 dictlen=dict_info[0];
668 memcpy (dictentry, dict_info+1, dictlen );
670 logf(LOG_LOG,"dictentry before. len=%d: %d %d %d %d %d %d %d %d %d",
671 dictlen,dictentry[0], dictentry[1], dictentry[2],
672 dictentry[3], dictentry[4], dictentry[5],
673 dictentry[6], dictentry[7], dictentry[8]); /*!*/
675 dictlen= isamd_append(hi->reg->isamd, dictentry, dictlen, isamd_i);
676 /* logf dictentry after */
680 if ( (dictlen!=dict_info[0]) ||
681 (0!=memcmp(dictentry, dict_info+1, dictlen)) )
683 dict_insert(hi->reg->dict, this_name,
690 if (!dict_delete (hi->reg->dict, this_name))
692 logf (LOG_FATAL, "dict_delete failed");
700 memset (dictentry, '\0', ISAMD_MAX_DICT_LEN);
701 dictlen= isamd_append(hi->reg->isamd, dictentry, dictlen, isamd_i);
702 /* logf dictentry first */
705 dict_insert(hi->reg->dict, this_name,
716 int heap_inp (struct heap_info *hi)
719 char next_name[INP_NAME_MAX];
720 char cur_name[INP_NAME_MAX];
721 int key_buf_size = INP_BUF_START;
727 next_key = (char *) xmalloc (KEY_SIZE);
728 key_buf = (char *) xmalloc (key_buf_size);
729 more = heap_read_one (hi, cur_name, key_buf);
730 while (more) /* EOF ? */
733 key_buf_ptr = KEY_SIZE;
736 if (!(more = heap_read_one (hi, next_name, next_key)))
738 if (*next_name && strcmp (next_name, cur_name))
740 memcpy (key_buf + key_buf_ptr, next_key, KEY_SIZE);
741 key_buf_ptr += KEY_SIZE;
742 if (key_buf_ptr+(int) KEY_SIZE >= key_buf_size)
745 new_key_buf = (char *) xmalloc (key_buf_size + INP_BUF_ADD);
746 memcpy (new_key_buf, key_buf, key_buf_size);
747 key_buf_size += INP_BUF_ADD;
749 key_buf = new_key_buf;
753 nmemb = key_buf_ptr / KEY_SIZE;
754 assert (nmemb * (int) KEY_SIZE == key_buf_ptr);
755 if ((info = dict_lookup (hi->reg->dict, cur_name)))
757 ISAM_P isam_p, isam_p2;
758 memcpy (&isam_p, info+1, sizeof(ISAM_P));
759 isam_p2 = is_merge (hi->reg->isam, isam_p, nmemb, key_buf);
763 if (!dict_delete (hi->reg->dict, cur_name))
769 if (isam_p2 != isam_p)
770 dict_insert (hi->reg->dict, cur_name,
771 sizeof(ISAM_P), &isam_p2);
778 isam_p = is_merge (hi->reg->isam, 0, nmemb, key_buf);
779 dict_insert (hi->reg->dict, cur_name, sizeof(ISAM_P), &isam_p);
781 memcpy (key_buf, next_key, KEY_SIZE);
782 strcpy (cur_name, next_name);
787 int heap_inps (struct heap_info *hi)
789 struct heap_cread_info hci;
790 ISAMS_I isams_i = (ISAMS_I) xmalloc (sizeof(*isams_i));
792 hci.key = (char *) xmalloc (KEY_SIZE);
793 hci.key_1 = (char *) xmalloc (KEY_SIZE);
794 hci.key_2 = (char *) xmalloc (KEY_SIZE);
795 hci.first_in_list = 1;
798 hci.more = heap_read_one (hi, hci.cur_name, hci.key);
800 isams_i->clientData = &hci;
801 isams_i->read_item = heap_cread_item;
805 char this_name[INP_NAME_MAX];
809 strcpy (this_name, hci.cur_name);
810 assert (hci.cur_name[1]);
812 if (!(dict_info = dict_lookup (hi->reg->dict, hci.cur_name)))
814 isams_p = isams_merge (hi->reg->isams, isams_i);
816 dict_insert (hi->reg->dict, this_name, sizeof(ISAMS_P), &isams_p);
820 logf (LOG_FATAL, "isams doesn't support this kind of update");
828 struct progressInfo {
835 void progressFunc (struct key_file *keyp, void *info)
837 struct progressInfo *p = (struct progressInfo *) info;
838 time_t now, remaining;
840 if (keyp->buf_size <= 0 || p->totalBytes <= 0)
844 if (now >= p->lastTime+10)
847 remaining = (time_t) ((now - p->startTime)*
848 ((double) p->totalBytes/p->totalOffset - 1.0));
849 if (remaining <= 130)
850 logf (LOG_LOG, "Merge %2.1f%% completed; %ld seconds remaining",
851 (100.0*p->totalOffset) / p->totalBytes, (long) remaining);
853 logf (LOG_LOG, "Merge %2.1f%% completed; %ld minutes remaining",
854 (100.0*p->totalOffset) / p->totalBytes, (long) remaining/60);
856 p->totalOffset += keyp->buf_size;
863 void zebra_index_merge (ZebraHandle zh)
865 struct key_file **kf;
868 struct heap_info *hi;
869 struct progressInfo progressInfo;
870 int nkeys = zh->reg->key_file_no;
878 extract_get_fname_tmp (zh, fname, nkeys+1);
879 if (access (fname, R_OK) == -1)
886 kf = (struct key_file **) xmalloc ((1+nkeys) * sizeof(*kf));
887 progressInfo.totalBytes = 0;
888 progressInfo.totalOffset = 0;
889 time (&progressInfo.startTime);
890 time (&progressInfo.lastTime);
891 for (i = 1; i<=nkeys; i++)
893 kf[i] = key_file_init (i, 8192, zh->res);
894 kf[i]->readHandler = progressFunc;
895 kf[i]->readInfo = &progressInfo;
896 progressInfo.totalBytes += kf[i]->length;
897 progressInfo.totalOffset += kf[i]->buf_size;
899 hi = key_heap_init (nkeys, key_qsort_compare);
902 for (i = 1; i<=nkeys; i++)
903 if ((r = key_file_read (kf[i], rbuf)))
904 key_heap_insert (hi, rbuf, r, kf[i]);
916 for (i = 1; i<=nkeys; i++)
918 extract_get_fname_tmp (zh, rbuf, i);
921 logf (LOG_LOG, "Iterations . . .%7d", hi->no_iterations);
922 logf (LOG_LOG, "Distinct words .%7d", hi->no_diffs);
923 logf (LOG_LOG, "Updates. . . . .%7d", hi->no_updates);
924 logf (LOG_LOG, "Deletions. . . .%7d", hi->no_deletions);
925 logf (LOG_LOG, "Insertions . . .%7d", hi->no_insertions);
926 zh->reg->key_file_no = 0;
928 key_heap_destroy (hi, nkeys);
929 for (i = 1; i<=nkeys; i++)
930 key_file_destroy (kf[i]);