From 3003d747565b03bac252b43eca48bb691d1adbfc Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Thu, 28 Sep 1995 14:22:56 +0000 Subject: [PATCH] Sort uses smaller temporary files. --- index/extract.c | 179 ++++++++++++++++++++++++++++++++++--------------------- index/index.h | 10 +++- index/kinput.c | 7 ++- index/main.c | 20 ++++--- 4 files changed, 136 insertions(+), 80 deletions(-) diff --git a/index/extract.c b/index/extract.c index a7169f1..3560d13 100644 --- a/index/extract.c +++ b/index/extract.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: extract.c,v $ - * Revision 1.11 1995-09-28 12:10:31 adam + * Revision 1.12 1995-09-28 14:22:56 adam + * Sort uses smaller temporary files. + * + * Revision 1.11 1995/09/28 12:10:31 adam * Bug fixes. Field prefix used in queries. * * Revision 1.10 1995/09/28 09:19:41 adam @@ -54,27 +57,44 @@ static Dict file_idx; static SYSNO sysno_next; -static int key_fd = -1; static int sys_idx_fd = -1; -static char *key_buf; -static int key_offset, key_buf_size; + static int key_cmd; static int key_sysno; +static char **key_buf; +static size_t ptr_top; +static size_t ptr_i; +static size_t kused; +static int key_file_no; -void key_open (const char *fname) +static int sort_compare (const void *p1, const void *p2) +{ + int r; + size_t l; + char *cp1 = *(char**) p1; + char *cp2 = *(char**) p2; + + if ((r = strcmp (cp1, cp2))) + return r; + l = strlen(cp1); + if ((r = key_compare (cp1+l, cp2+l))) + return r; + return cp1[l+sizeof(struct it_key)] - + cp2[l+sizeof(struct it_key)]; +} + +void key_open (int mem) { void *file_key; - if (key_fd != -1) - return; - if ((key_fd = open (fname, O_RDWR|O_CREAT, 0666)) == -1) - { - logf (LOG_FATAL|LOG_ERRNO, "open %s", fname); - exit (1); - } - logf (LOG_DEBUG, "key_open of %s", fname); - key_buf_size = 49100; - key_buf = xmalloc (key_buf_size); - key_offset = 0; + + if (mem < 50000) + mem = 50000; + key_buf = xmalloc (mem); + ptr_top = mem/sizeof(char*); + ptr_i = 0; + kused = 0; + key_file_no = 0; + if (!(file_idx = dict_open (FNAME_FILE_DICT, 40, 1))) { logf (LOG_FATAL, "dict_open fail of %s", "fileidx"); @@ -91,41 +111,76 @@ void key_open (const char *fname) exit (1); } } - -int key_close (void) + +void key_flush (void) { - if (key_fd == -1) - { - logf (LOG_DEBUG, "key_close - but no file"); - return 0; - } - close (key_fd); - close (sys_idx_fd); - dict_insert (file_idx, ".", sizeof(sysno_next), &sysno_next); - dict_close (file_idx); - key_fd = -1; - xfree (key_buf); - return 1; -} + FILE *outf; + char out_fname[200]; + char *prevcp, *cp; + + if (ptr_i <= 0) + return; + + key_file_no++; + logf (LOG_LOG, "sorting section %d", key_file_no); + qsort (key_buf + ptr_top-ptr_i, ptr_i, sizeof(char*), sort_compare); + sprintf (out_fname, TEMP_FNAME, key_file_no); -void wordFlush (int sysno) -{ - size_t i = 0; - int w; - if (key_fd == -1) - return; - while (i < key_offset) + if (!(outf = fopen (out_fname, "w"))) + { + logf (LOG_FATAL|LOG_ERRNO, "fopen (4) %s", out_fname); + exit (1); + } + logf (LOG_LOG, "writing section %d", key_file_no); + prevcp = cp = key_buf[ptr_top-ptr_i]; + + if (fwrite (cp, strlen (cp)+2+sizeof(struct it_key), 1, outf) != 1) { - w = write (key_fd, key_buf + i, key_offset - i); - if (w == -1) + logf (LOG_FATAL|LOG_ERRNO, "fwrite %s", out_fname); + exit (1); + } + while (--ptr_i > 0) + { + cp = key_buf[ptr_top-ptr_i]; + if (strcmp (cp, prevcp)) + { + if (fwrite (cp, strlen (cp)+2+sizeof(struct it_key), 1, + outf) != 1) + { + logf (LOG_FATAL|LOG_ERRNO, "fwrite %s", out_fname); + exit (1); + } + prevcp = cp; + } + else { - logf (LOG_FATAL|LOG_ERRNO, "Write key fail"); - exit (1); + cp = strlen (cp) + cp; + if (fwrite (cp, 2+sizeof(struct it_key), 1, outf) != 1) + { + logf (LOG_FATAL|LOG_ERRNO, "fwrite %s", out_fname); + exit (1); + } } - i += w; } - key_offset = 0; + if (fclose (outf)) + { + logf (LOG_FATAL|LOG_ERRNO, "fclose %s", out_fname); + exit (1); + } + logf (LOG_LOG, "finished section %d", key_file_no); + ptr_i = 0; + kused = 0; +} + +int key_close (void) +{ + key_flush (); + xfree (key_buf); + close (sys_idx_fd); + dict_insert (file_idx, ".", sizeof(sysno_next), &sysno_next); + dict_close (file_idx); + return key_file_no; } static void wordInit (RecWord *p) @@ -138,39 +193,30 @@ static void wordInit (RecWord *p) static void wordAdd (const RecWord *p) { struct it_key key; - char x; size_t i; - if (key_offset + 1000 > key_buf_size) - { - char *new_key_buf; - - key_buf_size *= 2; - new_key_buf = xmalloc (2*key_buf_size); - memcpy (new_key_buf, key_buf, key_offset); - xfree (key_buf); - key_buf = new_key_buf; - } - key_offset += index_word_prefix (key_buf + key_offset, - p->attrSet, p->attrUse); + if (kused + 1024 > (ptr_top-ptr_i)*sizeof(char*)) + key_flush (); + ++ptr_i; + key_buf[ptr_top-ptr_i] = (char*)key_buf + kused; + kused += index_word_prefix ((char*)key_buf + kused, + p->attrSet, p->attrUse); switch (p->which) { case Word_String: for (i = 0; p->u.string[i]; i++) - key_buf[key_offset++] = index_char_cvt (p->u.string[i]); - key_buf[key_offset++] = '\0'; + ((char*)key_buf) [kused++] = index_char_cvt (p->u.string[i]); + ((char*)key_buf) [kused++] = '\0'; break; default: return ; } - x = (key_cmd == 'a') ? 1 : 0; - memcpy (key_buf + key_offset, &x, 1); - key_offset++; - key.sysno = key_sysno; key.seqno = p->seqno; - memcpy (key_buf + key_offset, &key, sizeof(key)); - key_offset += sizeof(key); + memcpy ((char*)key_buf + kused, &key, sizeof(key)); + kused += sizeof(key); + + ((char*) key_buf)[kused++] = ((key_cmd == 'a') ? 1 : 0); } void file_extract (int cmd, const char *fname, const char *kname) @@ -227,7 +273,4 @@ void file_extract (int cmd, const char *fname, const char *kname) key_cmd = cmd; (*rt->extract)(&extractCtrl); fclose (inf); - wordFlush (sysno); } - - diff --git a/index/index.h b/index/index.h index 5352205..1d8ea48 100644 --- a/index/index.h +++ b/index/index.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: index.h,v $ - * Revision 1.12 1995-09-28 12:10:32 adam + * Revision 1.13 1995-09-28 14:22:56 adam + * Sort uses smaller temporary files. + * + * Revision 1.12 1995/09/28 12:10:32 adam * Bug fixes. Field prefix used in queries. * * Revision 1.11 1995/09/27 12:22:28 adam @@ -69,15 +72,16 @@ void repository (int cmd, const char *rep, const char *base_path); void file_extract (int cmd, const char *fname, const char *kname); -void key_open (const char *fname); +void key_open (int mem); int key_close (void); void key_write (int cmd, struct it_key *k, const char *str); int key_compare (const void *p1, const void *p2); void key_logdump (int mask, const void *p); void key_input (const char *dict_fname, const char *isam_fname, const char *key_fname, int cache); -int key_sort (const char *key_fname, size_t mem); +int merge_sort (char **buf, int from, int to); +#define TEMP_FNAME "keys%d.tmp" #define FNAME_WORD_DICT "worddict" #define FNAME_WORD_ISAM "wordisam" #define FNAME_FILE_DICT "filedict" diff --git a/index/kinput.c b/index/kinput.c index 9f834a9..889a641 100644 --- a/index/kinput.c +++ b/index/kinput.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: kinput.c,v $ - * Revision 1.3 1995-09-06 16:11:17 adam + * Revision 1.4 1995-09-28 14:22:57 adam + * Sort uses smaller temporary files. + * + * Revision 1.3 1995/09/06 16:11:17 adam * Option: only one word key per file. * * Revision 1.2 1995/09/04 12:33:42 adam @@ -79,7 +82,7 @@ static int inp (Dict dict, ISAM isam, const char *name) { if (!read_one (inf, next_name, next_key)) break; - if (strcmp (next_name, cur_name)) + if (*next_name && strcmp (next_name, cur_name)) break; memcpy (key_buf + key_buf_ptr, next_key, KEY_SIZE); key_buf_ptr += KEY_SIZE; diff --git a/index/main.c b/index/main.c index a270a89..0616499 100644 --- a/index/main.c +++ b/index/main.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: main.c,v $ - * Revision 1.9 1995-09-14 07:48:24 adam + * Revision 1.10 1995-09-28 14:22:57 adam + * Sort uses smaller temporary files. + * + * Revision 1.9 1995/09/14 07:48:24 adam * Record control management. * * Revision 1.8 1995/09/06 16:11:18 adam @@ -50,6 +53,8 @@ int main (int argc, char **argv) char *arg; char *base_name = NULL; char *base_path = NULL; + int nsections; + char **mbuf; prog = *argv; while ((ret = options ("r:v:", argv, argc, &arg)) != -2) @@ -86,7 +91,7 @@ int main (int argc, char **argv) else { unlink ("keys.tmp"); - key_open ("keys.tmp"); + key_open (3000000); repository (cmd, arg, base_path); cmd = 0; } @@ -111,13 +116,14 @@ int main (int argc, char **argv) "base cmd1 dir1 cmd2 dir2 ...\n"); exit (1); } - if (!key_close ()) - exit (0); - logf (LOG_LOG, "Sorting"); - if (!key_sort ("keys.tmp", 3000000)) + nsections = key_close (); + if (!nsections) exit (0); + logf (LOG_LOG, "Merge sorting"); + mbuf = xmalloc (100000); + merge_sort (mbuf, 1, nsections+1); logf (LOG_LOG, "Input"); - key_input (FNAME_WORD_DICT, FNAME_WORD_ISAM, "keys.tmp", 60); + key_input (FNAME_WORD_DICT, FNAME_WORD_ISAM, "keys1.tmp", 60); exit (0); } -- 1.7.10.4