/* Bbuuzzb low level sort module.
   Rick Smereka, Copyright (C) 2002-2005.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, get a copy via the Internet at
   http://gnu.org/copyleft/gpl.html or write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston,
   MA 02111-1307 USA

   You can contact the author via email at rsmereka@future-lab.com

   This sort module works by loading the contents of a table into
   memory until out of memory or the end of the table. Each time
   allocated memory is at the maximum allowed, the contents of 
   the sort node link list is sorted using a link list insertion 
   sort and a 'bin' table is written. If more than one 'bin' table 
   was written, the 'bin' tables are then merged. A sort 
   specification link list stores any number of sort specifications.

   Original Debian Linux version. Dec/2002, Rick Smereka

   Ported to DOS, 32bit Windows and QNX. Jan/2003, Rick Smereka

   Changed to use the specified amount of sort memory and
   specified number of open bin tables. Mar/2003, Rick Smereka

   Changed all logging calls from 'sys_log' to 'logman'.
   Mar/2004, Rick Smereka

   Changed 'dbeng_sort_compare' to allow sort fields to be empty.
   Jan/2005, Rick Smereka */

#include "stdhead.h"
#include "dbeng.h"
#include "dbmess.h"
#include "dbengcfg.h"
#include "dbiocode.h"
#include "dbengsrt.h"

/* global data */
/* list head pointers */

struct dbeng_sort_node *dbeng_sort_head = DBENGSRT_ROT_NULL;
struct dbeng_sort_spec *dbeng_spec_head = DBENGSRT_SOT_NULL;
struct dbeng_sort_bin *dbeng_bin_head = DBENGSRT_BOT_NULL;

long dbengsrt_record_count = 0L;           /* bin record counter */
long dbengsrt_total_records = 0L;          /* total number of records */
int dbengsrt_total_files = 0;              /* total bin files in use */
long dbengsrt_sort_memory_in_use = 0L;     /* bytes in use by record data */

/* private function prototypes */

static int dbeng_sort_flush_rec(void);
static int dbeng_sort_ll(void);
static int dbeng_sort_compare(char *, char *, int *);
static int dbeng_sort_set_cval(struct dbeng_sort_spec *, int *);
static int dbeng_sort_write_sort_data(int);
static int dbeng_sort_set_final(struct dbeng_table *);
static int dbeng_sort_match_bin(void);
static int dbeng_sort_match_tables(int);
static int dbeng_sort_read_bin(struct dbeng_sort_bin *, int);
static int dbeng_sort_is_active_input_bin(struct dbeng_sort_bin *, int);
static int dbeng_sort_alloc_bin(int *);
static int dbeng_sort_sll_load(char *);
static int dbeng_sort_rll_add(struct dbeng_table *);
static void dbeng_sort_rll_delete(void);
static int dbeng_sort_sll_add(char *);
static void dbeng_sort_sll_delete(void);
static int dbeng_sort_bll_delete_all(void);
static int dbeng_sort_bll_delete(struct dbeng_sort_bin *, int);
static void dbeng_sort_sll_dump(void);
static void dbeng_sort_rll_dump(void);
static void dbeng_sort_term(void);

int dbeng_sort(struct dbeng_table *ot, char *specs)
{
   /* Sort a table. The parameter 'specs' must contain
      a list (delimited by 'DBENG_LIST_DELIM') of sort
      specifications. A single sort specification is in
      the form:

         field_num[,A|D]

      The sort specification starts with the field number
      followed by an optional order ('A' for ascending,
      'D' for desending). A comma must separate the field
      number from the sort order. If no order is given, an
      ascending sort is assumed for that field.
      The sorted table contents replace the unsorted
      contents. Function returns a 'dbeng' code. */

   struct dbeng_sort_bin *lbin;
   char mname[] = "dbeng_sort";
   int ret, done, delete_flag;

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (specs == (char *)NULL || !strlen(specs))
      {
      dbeng_io_code_log(mname, "null or empty[specs]",
                        DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   logman("%s:enter:tid=%d,specs=%s", mname, ot->tid, specs);

   /* check for locked table */

   if (ot->is_table_locked)
      {
      dbeng_io_code_log(mname, "table is locked", DBENG_TABLE_LOCKED);
      return(DBENG_TABLE_LOCKED);
      }

   /* check for changed record */

   if (ot->enforce_change_rec_flag && ot->change_rec_flag)
      {
      dbeng_io_code_log(mname, "record changed", DBENG_RECORD_CHANGED);
      return(DBENG_RECORD_CHANGED);
      }

   if ((ret = dbeng_goto_top(ot)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_goto_top", ret);
      return(ret);
      }

   /* build link list of sort specifications */

   if ((ret = dbeng_sort_sll_load(specs)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_sll_load", ret);
      dbeng_sort_term();
      return(ret);
      }

   /* force source 'process_deleted' flag down (save prev value) */

   delete_flag = ot->process_deleted;
   ot->process_deleted = FALSE;
   dbeng_bin_head = DBENGSRT_BOT_NULL;
   dbengsrt_record_count = dbengsrt_total_records = 0L;
   dbengsrt_total_files = 0;
   done = FALSE;

   /* get first record */

   ret = dbeng_get_recd(ot);

   if (ret != DBENG_OK)
      {
      ot->process_deleted = delete_flag;
      dbeng_sort_term();

      if (ret == DBENG_EOF)
         {
         dbeng_io_code_log(mname, "source table empty", DBENG_OK);
         return(DBENG_OK);
         }

      dbeng_io_code_log(mname, "error getting first sourc rec", ret);
      return(ret);
      }

   /* loop to load each active record into the
      sort record node link list */

   while(!done)
      {
      /* if allocated memory for record data is at its max, flush */

      if (dbengsrt_sort_memory_in_use > ot->sort_max_mem)
         {
         logman("%s:alloc rec memory at max,flushing", mname);

         if ((ret = dbeng_sort_flush_rec()) != DBENG_OK)
            {
            dbeng_io_code_log(mname, "bad rc from dbeng_sort_flush_rec", ret);
            dbeng_sort_term();
            (void)dbeng_goto_top(ot);
            ot->process_deleted = delete_flag;
            return(ret);
            }

         dbengsrt_total_records += dbengsrt_record_count;
         dbengsrt_record_count = 0L;
         }

      if ((ret = dbeng_sort_rll_add(ot)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_rll_add", ret);
         ot->process_deleted = delete_flag;
         dbeng_sort_term();
         (void)dbeng_goto_top(ot);
         return(ret);
         }

      dbengsrt_record_count++;

      /* get next source record */

      ret = dbeng_get_recd(ot);

      switch(ret)
         {
         case DBENG_EOF:
            done = TRUE;
            break;

         case DBENG_OK:
            done = FALSE;
            break;

         /* we should never get here, just in case */

         default:
            dbeng_io_code_log(mname, "error getting record", ret);
            ot->process_deleted = delete_flag;
            dbeng_sort_term();
            (void)dbeng_goto_top(ot);
            return(ret);
         };
      }

   /* close input table but retain table structure */

   if ((ret = dbeng_ll_close(ot)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "error closing input table", ret);
      dbeng_sort_term();
      ot->process_deleted = delete_flag;
      return(ret);
      }

   /* sort/flush whatever is left in memory */

   if ((ret = dbeng_sort_flush_rec()) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_flush_rec", ret);
      dbeng_sort_term();
      (void)dbeng_ll_open(ot);
      ot->process_deleted = delete_flag;
      return(ret);
      }

   if (dbengsrt_total_files == 0)
      {
      logman("%s:no bin tables after load", mname);
      dbengsrt_total_records = dbengsrt_record_count;
      }
   else
      {
      logman("%s:%d bin tables after load,matching", mname,
                    dbengsrt_total_files);

      if ((ret = dbeng_sort_match_bin()) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_match_bin", ret);
         dbeng_sort_term();
         (void)dbeng_ll_open(ot);
         ot->process_deleted = delete_flag;
         return(ret);
         }
      }

   /* change single bin table to source table */

   if ((ret = dbeng_sort_set_final(ot)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_set_final", ret);
      ot->process_deleted = delete_flag;
      dbeng_sort_term();
      return(ret);
      }
      
   ot->process_deleted = delete_flag;
   dbeng_sort_term();

   // force a count

   if ((ret = dbeng_count_rec(ot, &ot->active_record_count,
        &ot->deleted_record_count)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_count_rec",
                        DBENG_INTERNAL_ERROR);
      return(DBENG_INTERNAL_ERROR);
      }

   // fix-up record count

   if ((ret = dbeng_set_record_count(ot)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_set_record_count",
                        DBENG_INTERNAL_ERROR);
      return(DBENG_INTERNAL_ERROR);
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

int dbeng_sort_get_max_mem(struct dbeng_table *ot, long *mem)
{
   /* Obtain the current value of the 'dbeng_table' member
      'sort_max_mem'. Function returns the current allowable
      maximum allocated sort memory in 'mem' upon success.
      Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_get_max_mem";

   logman("%s:enter", mname);

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (mem == (long *)NULL)
      {
      dbeng_io_code_log(mname, "null[mem]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   *mem = ot->sort_max_mem;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

int dbeng_sort_set_max_mem(struct dbeng_table *ot, long mem)
{
   /* Set the current value of the 'dbeng_table' member
      'sort_max_mem'. Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_set_max_mem";

   logman("%s:enter", mname);

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   /* acceptable range is >= 2000 bytes */

   if (mem < 2000L)
      {
      dbeng_io_code_log(mname, "out of range[mem]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   ot->sort_max_mem = mem;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

int dbeng_sort_get_max_open_bin(struct dbeng_table *ot, int *open_bin)
{
   /* Obtain the current value of the 'dbeng_table' member
      'sort_max_open_bin'. Function returns the current allowable
      maximum number of open bin table in 'open_bin' upon success.
      Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_get_max_open_bin";

   logman("%s:enter", mname);

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (open_bin == (int *)NULL)
      {
      dbeng_io_code_log(mname, "null[open_bin]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   *open_bin = ot->sort_max_open_bin;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

int dbeng_sort_set_max_open_bin(struct dbeng_table *ot, int open_bin)
{
   /* Set the current value of the 'dbeng_table' member
      'sort_max_open_bin'. Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_set_max_open_bin";

   logman("%s:enter", mname);

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   /* acceptable range is >= 3 */

   if (open_bin < 3)
      {
      dbeng_io_code_log(mname, "out of range[open_bin]", 
                        DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   ot->sort_max_open_bin = open_bin;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

/* private functions */

static int dbeng_sort_flush_rec(void)
{
   /* Sort and write out the contents of memory to a bin file.
      Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_flush_rec";
   int ret, tid;

   logman("%s:enter:rcount=%ld", mname, dbengsrt_record_count);

   if ((ret = dbeng_sort_ll()) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_ll", ret);
      return(ret);
      }

   if ((ret = dbeng_sort_alloc_bin(&tid)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_alloc_bin", ret);
      return(ret);
      }

   if ((ret = dbeng_sort_write_sort_data(tid)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_write_sort_data", ret);
      return(ret);
      }

   dbeng_sort_rll_delete();
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_ll(void)
{
   /* Sort record contents. The link list must have already
      been loaded. */

   struct dbeng_sort_node *i, *j;
   char mname[] = "dbeng_sort_ll";
   int cval, ret;
   
   logman("%s:enter", mname);

   if (dbeng_sort_head == DBENGSRT_ROT_NULL)
      {
      dbeng_io_code_log(mname, "link list empty", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   for (i = dbeng_sort_head; i != DBENGSRT_ROT_NULL; i = i->next)
      {
      /* logman("%s:outer", mname); */

      for (j = i->next; j != DBENGSRT_ROT_NULL; j = j->next)
         {
         if ((ret = dbeng_sort_compare(i->arec, j->arec, &cval)) != DBENG_OK)
            {
            dbeng_io_code_log(mname, "bad rc from dbeng_sort_compare", ret);
            return(ret);
            }

         /* logman("%s:inner:i=%s,j=%s,cval=%d", mname, i->arec, 
                       j->arec, cval); */

         if (cval > 0)
            {
            /* swap (char pointers only) */

            char *temp;
            temp = i->arec;
            i->arec = j->arec;
            j->arec = temp;
            }
         }
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_compare(char *l, char *r, int *cval)
{
   /* Compare two strings according to sort specifications.
      Function returns 'DBENG_OK' upon success with the result
      of the comparison in 'cval'. Function returns a 'dbeng'
      code. */

   struct dbeng_sort_spec *rov = dbeng_spec_head;
   char mname[] = "dbeng_sort_compare", *lfield, *rfield;
   int len, ret;

   /* logman("%s:enter", mname); */
   
   if (rov == DBENGSRT_SOT_NULL)
      {
      dbeng_io_code_log(mname, "null[dbeng_spec_head]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (cval == (int *)NULL)
      {
      dbeng_io_code_log(mname, "null[cval]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   *cval = 0;

   /* loop through all sort specifications comparing until
      not equal */

   while(rov != DBENGSRT_SOT_NULL)
      {
      /* get contents of both fields */

      len = ll_wordlen(l, rov->field_num, DBENG_FM);

      /* it is an error if any of the fields are empty or do
         not exist */

      /* if (len <= 0)
         {
         dbeng_io_code_log(mname, "null or empty field[l]",
                           DBENG_NO_SUCH_FIELD);
         return(DBENG_NO_SUCH_FIELD);
         } */

      if ((lfield = (char *)malloc(len + 1)) == (char *)NULL)
         {
         dbeng_io_code_log(mname, "alloc fail[lfield]", DBENG_MEMORY_FAIL);
         return(DBENG_MEMORY_FAIL);
         }

      if (!ll_word(l, lfield, rov->field_num, DBENG_FM))
         {
         dbeng_io_code_log(mname, "bad rc[FALSE] from ll_word",
                           DBENG_INTERNAL_ERROR);
         free(lfield);
         return(DBENG_INTERNAL_ERROR);
         }

      len = ll_wordlen(r, rov->field_num, DBENG_FM);

      /* if (len <= 0)
         {
         dbeng_io_code_log(mname, "null or empty field[r]",
                           DBENG_NO_SUCH_FIELD);
         free(lfield);
         return(DBENG_NO_SUCH_FIELD);
         } */

      if ((rfield = (char *)malloc(len + 1)) == (char *)NULL)
         {
         dbeng_io_code_log(mname, "alloc fail[rfield]", DBENG_MEMORY_FAIL);
         free(lfield);
         return(DBENG_MEMORY_FAIL);
         }

      if (!ll_word(r, rfield, rov->field_num, DBENG_FM))
         {
         dbeng_io_code_log(mname, "bad rc[FALSE] from ll_word",
                           DBENG_INTERNAL_ERROR);
         free(lfield);
         free(rfield);
         return(DBENG_INTERNAL_ERROR);
         }

      /* compare and exit if not equal */

      if ((*cval = strcmp(lfield, rfield)) != 0)
         {
         free(lfield);
         free(rfield);

         if ((ret = dbeng_sort_set_cval(rov, cval)) != DBENG_OK)
            {
            dbeng_io_code_log(mname, "bad rc from dbeng_sort_set_cval", ret);
            return(ret);
            }

         // logman("%s:normal exit:cval=%d", mname, *cval);
         return(DBENG_OK);
         }

      free(lfield);
      free(rfield);
      rov = rov->next;
      }

   /* if we made it here, all fields are equal */

   *cval = 0;
   // logman("%s:normal exit:all equal", mname);
   return(DBENG_OK);
}

static int dbeng_sort_set_cval(struct dbeng_sort_spec *rov, int *cval)
{
   /* Set the comparison result based on the sort spec order
      and the initial value of 'cval'. Function returns a 
      'dbeng' code with the comparison result in 'cval'.

   char mname[] = "dbeng_sort_set_cval";

   if (rov == DBENGSRT_SOT_NULL)
      {
      dbeng_io_code_log(mname, "null[rov]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (cval == (int *)NULL)
      {
      dbeng_io_code_log(mname, "null[cval]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   /* if the initial value is zero, leave alone */

   if (*cval == 0)
      return(DBENG_OK);

   /* if sort spec is descending order, reverse value */

   if (rov->order == DBENGSRT_ORDER_DESCENDING)
      *cval = (*cval > 0) ? -1 : 1;

   return(DBENG_OK);
}

static int dbeng_sort_write_sort_data(int tid)
{
   /* Write the contents of the sorted record link list
      to a temp system table. The table is assumed to be
      open. The output table will be closed (with the
      'dbeng_table' structure retained) once all records
      have been written. Function returns a 'dbeng' code. */

   struct dbeng_sort_node *rov = dbeng_sort_head;
   struct dbeng_table *ot;
   char mname[] = "dbeng_sort_write_sort_data";
   int ret;

   logman("%s:enter", mname);

   if (rov == DBENGSRT_ROT_NULL)
      {
      dbeng_io_code_log(mname, "sort record link list empty",
                        DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if ((ot = dbeng_atid_lookup(tid)) == DBENG_OT_NULL)
      {
      logman("%s:unable to resolve tid[%d]", mname, tid);
      return(DBENG_NO_SUCH_TID);
      }

   while(rov != DBENGSRT_ROT_NULL)
      {
      if ((ret = dbeng_write_string_recd(ot, rov->arec)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_write_string_recd", ret);
         return(ret);
         }

      rov = rov->next;
      }

   if ((ret = dbeng_ll_close(ot)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "error closing bin table", ret);
      return(ret);
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_set_final(struct dbeng_table *source)
{
   /* Take a single bin table and make it the source table.
      Function returns a 'dbeng' code. */

   struct dbeng_sort_bin *lbin = dbeng_bin_head;
   char mname[] = "dbeng_sort_set_final";
   int ret;

   if (dbengsrt_total_files != 1)
      {
      dbeng_io_code_log(mname, "dbengsrt_total_files not one",
                        DBENG_INVALID_FUNCTION);
      (void)dbeng_ll_open(source);
      return(DBENG_INVALID_FUNCTION);
      }

   if (lbin == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "null[lbin]", DBENG_INVALID_FUNCTION);
      (void)dbeng_ll_open(source);
      return(DBENG_INVALID_FUNCTION);
      }

   if (source == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      (void)dbeng_ll_open(source);
      return(DBENG_INVALID_FUNCTION);
      }

   /* blow away the original table and perform a rename from
      the only bin table to the original table name */

   unlink(source->name);
   
   if (!qrename(lbin->abin->name, source->name))
      {
      dbeng_io_code_log(mname, "bad rc from qrename[FALSE]",
                        DBENG_INTERNAL_ERROR);
      return(DBENG_INTERNAL_ERROR);
      }

   /* eliminate the only bin link list member */

   if ((ret = dbeng_sort_bll_delete(lbin, DBENGSRT_NDELBIN)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_sort_bll_delete", ret);
      (void)dbeng_ll_open(source);
      return(ret);
      }

   /* re-open input table (now sorted) */

   if ((ret = dbeng_ll_open(source)) != DBENG_OK)
      dbeng_io_code_log(mname, "bad rc from dbeng_ll_open", ret);

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

/* bin table management functions */

static int dbeng_sort_match_bin(void)
{
   /* Create a single table from all the bin tables.
      Function returns a 'dbeng' code. */

   struct dbeng_sort_bin *brov;
   struct dbeng_sort_bin *start_bin = dbeng_bin_head;
   struct dbeng_table *ot;
   char mname[] = "dbeng_sort_match_bin";
   int ret, tid, len, files_open;

   logman("%s:enter", mname);

   if (start_bin == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "link list empty", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   /* main loop which consolidates multiple bin tables into one
      bin table */

   while(1)
      {
      start_bin = dbeng_bin_head;

      /* check for single bin file */

      if (start_bin->next == DBENGSRT_BOT_NULL)
         {
         logman("%s:top of loop single bin tid=%d", mname, 
                        start_bin->abin->tid);
         dbeng_io_code_log(mname, "exit:single bin after match", DBENG_OK);
         return(DBENG_OK);
         }

      /* alloc an output bin table */

      if ((ret = dbeng_sort_alloc_bin(&tid)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_alloc_bin", ret);
         return(ret);
         }

      brov = start_bin;
      files_open = 0;

      /* loop through the bin link list, opening */

      while(brov != DBENGSRT_BOT_NULL)
         {
         /* open up to max input tables */

         if (files_open >= brov->abin->sort_max_open_bin)
            {
            logman("%s:max bin files opened", mname);
            break;
            }

         /* ignore our output bin table */

         if (brov->abin->tid != tid)
            {
            if ((ret = dbeng_ll_open(brov->abin)) != DBENG_OK)
               {
               logman("%s:error[%d] opening:tid=%d", mname,
                             ret, brov->abin->tid);
               dbeng_sort_bll_delete_all();
               return(ret);
               }

            files_open++;
            }

         brov = brov->next;
         }

      /* match tables */

      if ((ret = dbeng_sort_match_tables(tid)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_match_tables", ret);
         dbeng_sort_bll_delete_all();
         return(ret);
         }

      /* convert output tid to table pointer */

      if ((ot = dbeng_atid_lookup(tid)) == NULL)
         {
         logman("%s:unable to resolve tid[%d]", mname, tid);
         dbeng_sort_bll_delete_all();
         return(DBENG_NO_SUCH_TID);
         }

      /* close output bin table */

      if ((ret = dbeng_ll_close(ot)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_ll_close", ret);
         dbeng_sort_bll_delete_all();
         return(ret);
         }
      }

   dbeng_io_code_log(mname, "abnormal exit", DBENG_INTERNAL_ERROR);
   return(DBENG_INTERNAL_ERROR);
}

static int dbeng_sort_match_tables(int out_tid)
{
   /* Consolidate all open
      bin tables into a single table. Function returns
      a 'dbeng' code. */

   struct dbeng_sort_bin *rov, *which;
   struct dbeng_table *ot;
   char mname[] = "dbeng_sort_match_tables";
   int ret, cval, default_tid = 0, done = FALSE;

   logman("%s:enter,out_tid=%d", mname, out_tid);

   /* convert output tid to table pointer */

   if ((ot = dbeng_atid_lookup(out_tid)) == NULL)
      {
      logman("%s:unable to resolve tid[%d]", mname, out_tid);
      return(DBENG_NO_SUCH_TID);
      }

   rov = dbeng_bin_head;

   /* obtain the first record of each input table */

   while(rov != DBENGSRT_BOT_NULL)
      {
      /* go after only open tables except output table */

      if (dbeng_sort_is_active_input_bin(rov, out_tid))
         if ((ret = dbeng_goto_record(rov->abin, 1L)) != DBENG_OK)
            {
            /* this should not happen, just in case (not fatal) */

            (void)dbeng_sort_bll_delete(rov, DBENGSRT_DELBIN);
            logman("%s:bad rc[%d] from dbeng_goto_record(1),"
                          "deleting bin table,tid=%d", mname, ret, 
                          rov->abin->tid);
            rov = dbeng_bin_head;
            }
         else
            rov = rov->next;
      else
         rov = rov->next;
      }

   while(!done)
      {
      rov = dbeng_bin_head;

      /* set initial default to first input bin table */

      while(rov != DBENGSRT_BOT_NULL)
         {
         if (dbeng_sort_is_active_input_bin(rov, out_tid))
            {
            which = rov;
            default_tid = which->abin->tid;
            break;
            }

         rov = rov->next;
         }

      if (!default_tid)
         {
         /* this should never happen, just in case */

         dbeng_io_code_log(mname, "default_tid is zero:no bin tables?",
                           DBENG_INTERNAL_ERROR);
         return(DBENG_INTERNAL_ERROR);
         }

      logman("%s:default tid=%d", mname, default_tid);
      rov = dbeng_bin_head;

      while(rov != DBENGSRT_BOT_NULL)
         {
         /* don't compare the initial default bin record */

         if (rov->abin->tid != default_tid && 
             dbeng_sort_is_active_input_bin(rov, out_tid))
            {
            if ((ret = dbeng_sort_compare(rov->abin->rec, which->abin->rec, 
                &cval)) != DBENG_OK)
               {
               logman("%s:bad rc[%d] from dbeng_sort_compare(%d,%d)",
                             mname, ret, rov->abin->tid, which->abin->tid);
               return(ret);
               }

            logman("%s:compare:rov[%d],which[%d],cval=%d", mname,
                   rov->abin->tid, which->abin->tid, cval);

            if (cval < 0)
               which = rov;
            }

         rov = rov->next;
         }

      logman("%s:after compare:which=%d", mname, which->abin->tid);

      /* output chosen record */

      if ((ret = dbeng_write_string_recd(ot, which->abin->rec)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_write_string_recd", ret);
         return(ret);
         }

      /* read next record of the chosen bin table */

      if ((ret = dbeng_sort_read_bin(which, out_tid)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_read_bin", ret);
         return(ret);
         }

      /* if only one open bin table left (the output), we are done */

      rov = dbeng_bin_head;
      ret = 0;

      while(rov != DBENGSRT_BOT_NULL)
         {
         if (dbeng_sort_is_active_input_bin(rov, out_tid))
            ret++;

         rov = rov->next;
         }

      if (ret == 0)
         done = TRUE;
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_read_bin(struct dbeng_sort_bin *rov, int out_tid)
{
   /* Read the next record of the indicated bin table. If EOF
      is encountered, close and delete the bin table. Function
      returns a 'dbeng' code. */

   struct dbeng_table *ot;
   char mname[] = "dbeng_sort_read_bin";
   int ret;

   
   if (rov == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "null[rov]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (out_tid <= 0)
      {
      dbeng_io_code_log(mname, "out of range[out_tid]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   ot = rov->abin;
   logman("%s:enter:tid=%d,out_tid=%d", mname, ot->tid, out_tid);

   if (!dbeng_sort_is_active_input_bin(rov, out_tid))
      {
      logman("%s:bin[%d] is not an active input bin", mname, ot->tid);
      return(DBENG_INVALID_FUNCTION);
      }

   /* read the next record, if EOF, close and delete the bin table */

   if ((ret = dbeng_get_recd(ot)) != DBENG_OK)
      {
      if (ret == DBENG_EOF)
         {
         logman("%s:bin[%d] eof,deleting", mname, ot->tid);
         (void)dbeng_sort_bll_delete(rov, DBENGSRT_DELBIN);
         return(DBENG_OK);
         }

      dbeng_io_code_log(mname, "bad rc from dbeng_get_recd", ret);
      return(ret);
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_is_active_input_bin(struct dbeng_sort_bin *rov, int tid)
{
   /* Determine whether the bin table 'rov' is open and is not an
      output table. Function returns 'TRUE' if the table table
      is open and for input, 'FALSE' otherwise. */

   if (rov == DBENGSRT_BOT_NULL)
      return(FALSE);

   if (tid <= 0)
      return(FALSE);

   return((rov->abin->tid != tid && rov->abin->handle != (FILE *)NULL) ?
          TRUE : FALSE);
}

static int dbeng_sort_alloc_bin(int *bintid)
{
   /* Allocate a bin member and open a temporary system table for it. 
      New structure member will be added to the end of the bin list.
      Upon success, the tid of the temp sys table will be returned in
      'bintid'. Function returns a 'dbeng' code. */

   struct dbeng_table *ot;
   struct dbeng_sort_bin *tmp, *new;
   char mname[] = "dbeng_sort_alloc_bin";
   int tid, ret;

   logman("%s:enter", mname);

   /* create a new system table for the bin file */

   if ((ret = dbeng_tmp_systable(&tid)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_tmp_systable", ret);
      return(ret);
      }

   /* fetch link list pointer from tid */

   if ((ot = dbeng_atid_lookup(tid)) == NULL)
      {
      logman("%s:cannot locate tmp table[%d]", mname, tid);
      return(DBENG_CANNOT_CREATE_TABLE);
      }

   *bintid = tid;
   tmp = dbeng_bin_head;

   /* find last entry in the link list */

   if (tmp != DBENGSRT_BOT_NULL)
      while(tmp->next != DBENGSRT_BOT_NULL)
         tmp = tmp->next;

   /* allocate bin file struct */

   if ((new = (struct dbeng_sort_bin *)malloc(sizeof(struct dbeng_sort_bin)))
             == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "alloc fail[new]", DBENG_MEMORY_FAIL);
      return(DBENG_MEMORY_FAIL);
      }

   /* check for first member and set base pointer */

   if (tmp == DBENGSRT_BOT_NULL)
      {
      logman("%s:start of bin list", mname);
      dbeng_bin_head = new;
      }

   dbengsrt_total_files++;
   logman("%s:total_files=%d", mname, dbengsrt_total_files);
   new->next = DBENGSRT_BOT_NULL;          /* this member is last */
   new->abin = ot;

   if (tmp != DBENGSRT_BOT_NULL)
      tmp->next = new;                     /* point to this member */

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

/* link list functions */

static int dbeng_sort_sll_load(char *specs)
{
   /* Load all sort specifications into the link list.
      Function returns a 'dbeng' code. */

   char mname[] = "dbeng_sort_sll_load", tmp[10];
   int ret, nwords, i;

   if (specs == (char *)NULL || !strlen(specs))
      {
      dbeng_io_code_log(mname, "null or empty[specs]",
                        DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   logman("%s:enter:specs=%s", mname, specs);
   nwords = ll_words(specs, DBENG_LIST_DELIM);

   for(i = 1; i <= nwords; i++)
      {
      if (!ll_word(specs, tmp, i, DBENG_LIST_DELIM))
         {
         dbeng_io_code_log(mname, "bad rc from ll_word",
                           DBENG_INTERNAL_ERROR);
         return(DBENG_INTERNAL_ERROR);
         }

      if ((ret = dbeng_sort_sll_add(tmp)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_sll_add", ret);
         return(ret);
         }
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_rll_add(struct dbeng_table *ot)
{
   /* Add the contents of the current record to the link list. 
      Function returns DBENG'_OK' upon success, a 'dbeng' code 
      otherwise. */

   struct dbeng_sort_node *dbengsrt_entry;
   struct dbeng_sort_node *rov;
   char mname[] = "dbeng_sort_rll_add";
   int ret, len, size;

   size = sizeof(struct dbeng_sort_node);

   /* reasonableness checks */

   if (ot == DBENG_OT_NULL)
      {
      dbeng_io_code_log(mname, "null[ot]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if ((ret = dbeng_rec_size(ot, &len)) != DBENG_OK)
      {
      dbeng_io_code_log(mname, "bad rc from dbeng_rec_size", ret);
      return(ret);
      }

   logman("%s:enter:tid=%d,reclen=%d", mname, ot->tid, len);

   if ((dbengsrt_entry = (struct dbeng_sort_node *)malloc(size))
       == DBENGSRT_ROT_NULL)
      {
      dbeng_io_code_log(mname, "alloc fail[dbengsrt_entry]",
                        DBENG_MEMORY_FAIL);
      return(DBENG_MEMORY_FAIL);
      }

   if ((dbengsrt_entry->arec = (char *)malloc(len + 1)) == (char *)NULL)
      {
      dbeng_io_code_log(mname, "alloc fail[dbengsrt_entry->arec]",
                        DBENG_MEMORY_FAIL);
      free(dbengsrt_entry);
      return(DBENG_MEMORY_FAIL);
      }

   if ((ret = dbeng_get_rec(ot, dbengsrt_entry->arec)) != DBENG_OK)
      {
      free(dbengsrt_entry->arec);
      free(dbengsrt_entry);
      dbeng_io_code_log(mname, "bad rc from dbeng_get_rec", ret);
      return(ret);
      }

   dbengsrt_entry->next = DBENGSRT_ROT_NULL;
   dbengsrt_sort_memory_in_use += (long)(size + len + 1);

   /* set head of list if this is the first entry */

   if (dbeng_sort_head == DBENGSRT_ROT_NULL)
      {
      dbeng_sort_head = dbengsrt_entry;
      dbeng_io_code_log(mname, "normal exit at head of list", DBENG_OK);
      return(DBENG_OK);
      }

   /* find last entry and hook into it */

   rov = dbeng_sort_head;

   while(rov->next != DBENGSRT_ROT_NULL)
      rov = rov->next;

   rov->next = dbengsrt_entry;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static void dbeng_sort_rll_delete(void)
{
   /* Delete all sort link list nodes. Function returns a
      'dbeng' code. */

   struct dbeng_sort_node *rov, *tmp;
   char mname[] = "dbeng_sort_rll_delete";

   logman("%s:enter", mname);

   /* if link list is empty, it's ok */

   if (dbeng_sort_head == DBENGSRT_ROT_NULL)
      {
      logman("%s:exit:sort node link list empty", mname);
      return;
      }

   rov = dbeng_sort_head;

   while(rov != DBENGSRT_ROT_NULL)
      {
      if (rov->arec != (char *)NULL)
         free(rov->arec);

      tmp = rov->next;
      free(rov);
      rov = tmp;
      }

   dbeng_sort_head = DBENGSRT_ROT_NULL;
   dbengsrt_sort_memory_in_use = 0L;
   logman("%s:normal exit", mname);
   return;
}

static int dbeng_sort_sll_add(char *spec)
{
   /* Add a sort specification to the link list.
      Function returns DBENG'_OK' upon success, a 'dbeng' code 
      otherwise. */

   struct dbeng_sort_spec *dbengsrt_entry;
   struct dbeng_sort_spec *rov;
   char mname[] = "dbeng_sort_sll_add", tmp[10];
   int nwords, fnum, ret, len, size;

   size = sizeof(struct dbeng_sort_spec);

   if (spec == (char *)NULL || !strlen(spec))
      {
      dbeng_io_code_log(mname, "null or empty[spec]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   logman("%s:enter:spec=%s", mname, spec);
   nwords = ll_words(spec, ',');

   if ((dbengsrt_entry = (struct dbeng_sort_spec *)malloc(size))
       == DBENGSRT_SOT_NULL)
      {
      dbeng_io_code_log(mname, "alloc fail[dbengsrt_entry]",
                        DBENG_MEMORY_FAIL);
      return(DBENG_MEMORY_FAIL);
      }

   (void)ll_word(spec, tmp, 1, ',');
   dbengsrt_entry->order = 0;

   if (!qatoi(tmp, &fnum))
      {
      dbeng_io_code_log(mname, "non-numeric field number",
                        DBENG_INVALID_FUNCTION);
      free(dbengsrt_entry);
      return(DBENG_INVALID_FUNCTION);
      }

   dbengsrt_entry->field_num = fnum;

   if (nwords > 1)
      {
      ret = FALSE;
      (void)ll_word(spec, tmp, 2, ',');

      if (!stricmp(tmp, "A"))
         {
         ret = TRUE;
         dbengsrt_entry->order = DBENGSRT_ORDER_ASCENDING;
         }

      if (!stricmp(tmp, "D"))
         {
         ret = TRUE;
         dbengsrt_entry->order = DBENGSRT_ORDER_DESCENDING;
         }

      if (!ret)
         {
         dbeng_io_code_log(mname, "unknown sort order",
                           DBENG_INVALID_FUNCTION);
         free(dbengsrt_entry);
         return(DBENG_INVALID_FUNCTION);
         }
      }

   if (!dbengsrt_entry->order)
      dbengsrt_entry->order = DBENGSRT_ORDER_ASCENDING;

   dbengsrt_entry->next = DBENGSRT_SOT_NULL;

   /* set head of list if this is the first entry */

   if (dbeng_spec_head == DBENGSRT_SOT_NULL)
      {
      dbeng_spec_head = dbengsrt_entry;
      dbeng_io_code_log(mname, "normal exit at head of list", DBENG_OK);
      return(DBENG_OK);
      }

   /* find last entry and hook into it */

   rov = dbeng_spec_head;

   while(rov->next != DBENGSRT_SOT_NULL)
      rov = rov->next;

   rov->next = dbengsrt_entry;
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static void dbeng_sort_sll_delete(void)
{
   /* Delete all sort spec link list nodes. Function returns a
      'dbeng' code. */

   struct dbeng_sort_spec *rov, *tmp;
   char mname[] = "dbeng_sort_sll_delete";

   logman("%s:enter", mname);

   /* if link list is empty, it's ok */

   if (dbeng_spec_head == DBENGSRT_SOT_NULL)
      {
      logman("%s:exit:sort spec link list empty", mname);
      return;
      }

   rov = dbeng_spec_head;

   while(rov != DBENGSRT_SOT_NULL)
      {
      tmp = rov->next;
      free(rov);
      rov = tmp;
      }

   dbeng_spec_head = DBENGSRT_SOT_NULL;
   logman("%s:normal exit", mname);
   return;
}

static int dbeng_sort_bll_delete_all(void)
{
   /* Delete all members of the bin table link list
      and also delete all physical bin files. */

   struct dbeng_sort_bin *rov = dbeng_bin_head;
   char mname[] = "dbeng_sort_bll_delete_all";
   int ret;

   logman("%s:enter", mname);

   while(rov != DBENGSRT_BOT_NULL)
      {
      if ((ret = dbeng_sort_bll_delete(rov, DBENGSRT_DELBIN)) != DBENG_OK)
         {
         dbeng_io_code_log(mname, "bad rc from dbeng_sort_bll_delete", ret);
         return(ret);
         }

      rov = dbeng_bin_head;
      }

   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static int dbeng_sort_bll_delete(struct dbeng_sort_bin *lbin, 
                                 int delete_flag)
{
   /* Delete a bin file link list entry with or without
      deleting the physical bin file. Function returns
      a 'dbeng' code. */

   struct dbeng_sort_bin *rov;
   struct dbeng_sort_bin *prev;
   char mname[] = "dbengsrt_bll_delete";
   int ret;

   if (lbin == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "null[lbin]", DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   if (delete_flag != DBENGSRT_NDELBIN && delete_flag != DBENGSRT_DELBIN)
      {
      dbeng_io_code_log(mname, "out of range[delete_flag]", 
                        DBENG_INVALID_FUNCTION);
      return(DBENG_INVALID_FUNCTION);
      }

   logman("%s:enter,tid=%d", mname, lbin->abin->tid);
   rov = prev = dbeng_bin_head;

   while(rov != DBENGSRT_BOT_NULL)
      {
      if (lbin->abin->tid == rov->abin->tid)
         break;
      else
         {
         prev = rov;
         rov = rov->next;
         }
      }

   /* if no match, error */

   if (rov == DBENGSRT_BOT_NULL)
      {
      dbeng_io_code_log(mname, "entry not found", DBENG_NOT_EXIST);
      return(DBENG_NOT_EXIST);
      }

   /* if we are deleting the head entry, set new head */

   if (rov == dbeng_bin_head)
      dbeng_bin_head = rov->next;
   else
      prev->next = rov->next;


   if (delete_flag == DBENGSRT_DELBIN)
      {
      (void)dbeng_ll_close(rov->abin);
      unlink(rov->abin->name);
      }

   if ((ret = dbeng_close_table(rov->abin)) != DBENG_OK)
      dbeng_io_code_log(mname, "bad rc from dbeng_close_table", ret);

   dbengsrt_total_files--;
   free(rov);
   dbeng_io_code_log(mname, "normal exit", DBENG_OK);
   return(DBENG_OK);
}

static void dbeng_sort_sll_dump(void)
{
   /* Output the contents of the sort specification link
      list to the system log. */

   struct dbeng_sort_spec *rov = dbeng_spec_head;
   char mname[] = "dbeng_sort_sll_dump";
   int i = 1;

   logman("%s:enter", mname);

   while(rov != DBENGSRT_SOT_NULL)
      {
      logman("%s:spec[%d]:field_num=%d,order=%d", mname, i,
                    rov->field_num, rov->order);
      rov = rov->next;
      i++;
      }

   logman("%s:normal exit", mname);
}

static void dbeng_sort_rll_dump(void)
{
   /* Output the contents of the sort node link
      list to the system log. */

   struct dbeng_sort_node *rov = dbeng_sort_head;
   char mname[] = "dbeng_sort_rll_dump";
   int i = 1;

   logman("%s:enter", mname);

   while(rov != DBENGSRT_ROT_NULL)
      {
      logman("%s:srec[%d]=%s", mname, i, rov->arec);
      rov = rov->next;
      i++;
      }

   logman("%s:normal exit", mname);
}

static void dbeng_sort_term(void)
{
   /* De-allocate all memory used by the sort module. */

   dbeng_sort_sll_delete();
   dbeng_sort_rll_delete();
   dbeng_sort_bll_delete_all();
}
