home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / myisampack / myisampack.c next >
C/C++ Source or Header  |  2000-10-15  |  60KB  |  2,146 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.    
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2 of the License, or
  6.    (at your option) any later version.
  7.    
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  12.    
  13.    You should have received a copy of the GNU General Public License
  14.    along with this program; if not, write to the Free Software
  15.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  16.  
  17. /* Pack MyISAM file */
  18.  
  19. #ifndef USE_MY_FUNC
  20. #define USE_MY_FUNC            /* We need at least my_malloc */
  21. #endif
  22.  
  23. #include "myisamdef.h"
  24. #include <queues.h>
  25. #include <my_tree.h>
  26. #include "mysys_err.h"
  27. #ifdef MSDOS
  28. #include <io.h>
  29. #endif
  30. #ifndef __GNU_LIBRARY__
  31. #define __GNU_LIBRARY__            /* Skip warnings in getopt.h */
  32. #endif
  33. #include <getopt.h>
  34.  
  35. #if INT_MAX > 32767
  36. #define BITS_SAVED 32
  37. #else
  38. #define BITS_SAVED 16
  39. #endif
  40.  
  41. #define IS_OFFSET ((uint) 32768)    /* Bit if offset or char in tree */
  42. #define HEAD_LENGTH    32
  43. #define ALLOWED_JOIN_DIFF    256    /* Diff allowed to join trees */
  44.  
  45. #define DATA_TMP_EXT        ".TMD"
  46. #define OLD_EXT            ".OLD"
  47. #define WRITE_COUNT        MY_HOW_OFTEN_TO_WRITE
  48.  
  49. struct st_file_buffer {
  50.   File file;
  51.   char *buffer,*pos,*end;
  52.   my_off_t pos_in_file;
  53.   int bits;
  54.   uint byte;
  55. };
  56.  
  57. struct st_huff_tree;
  58. struct st_huff_element;
  59.  
  60. typedef struct st_huff_counts {
  61.   uint    field_length,max_zero_fill;
  62.   uint    pack_type;
  63.   uint    max_end_space,max_pre_space,length_bits,min_space;
  64.   ulong max_length;
  65.   enum en_fieldtype field_type;
  66.   struct st_huff_tree *tree;        /* Tree for field */
  67.   my_off_t counts[256];
  68.   my_off_t end_space[8];
  69.   my_off_t pre_space[8];
  70.   my_off_t tot_end_space,tot_pre_space,zero_fields,empty_fields,bytes_packed;
  71.   TREE    int_tree;
  72.   byte *tree_buff;
  73.   byte *tree_pos;
  74. } HUFF_COUNTS;
  75.  
  76. typedef struct st_huff_element HUFF_ELEMENT;
  77.  
  78. struct st_huff_element {
  79.   my_off_t count;
  80.   union un_element {
  81.     struct st_nod {
  82.       HUFF_ELEMENT *left,*right;
  83.     } nod;
  84.     struct st_leaf {
  85.       HUFF_ELEMENT *null;
  86.       uint    element_nr;        /* Number of element */
  87.     } leaf;
  88.   } a;
  89. };
  90.  
  91.  
  92. typedef struct st_huff_tree {
  93.   HUFF_ELEMENT *root,*element_buffer;
  94.   HUFF_COUNTS *counts;
  95.   uint tree_number;
  96.   uint elements;
  97.   my_off_t bytes_packed;
  98.   uint tree_pack_length;
  99.   uint min_chr,max_chr,char_bits,offset_bits,max_offset,height;
  100.   ulong *code;
  101.   uchar *code_len;
  102. } HUFF_TREE;
  103.  
  104.  
  105. typedef struct st_isam_mrg {
  106.   MI_INFO **file,**current,**end;
  107.   uint free_file;
  108.   uint count;
  109.   uint    min_pack_length;        /* Theese is used by packed data */
  110.   uint    max_pack_length;
  111.   uint    ref_length;
  112.   uint    max_blob_length;
  113.   my_off_t records;
  114. } MRG_INFO;
  115.  
  116.  
  117. extern int main(int argc,char * *argv);
  118. static void get_options(int *argc,char ***argv);
  119. static MI_INFO *open_isam_file(char *name,int mode);
  120. static bool open_isam_files(MRG_INFO *mrg,char **names,uint count);
  121. static int compress(MRG_INFO *file,char *join_name);
  122. static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records);
  123. static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees,
  124.                        uint trees,
  125.                        HUFF_COUNTS *huff_counts,
  126.                        uint fields);
  127. static int compare_tree(const uchar *s,const uchar *t);
  128. static int get_statistic(MRG_INFO *mrg,HUFF_COUNTS *huff_counts);
  129. static void check_counts(HUFF_COUNTS *huff_counts,uint trees,
  130.              my_off_t records);
  131. static int test_space_compress(HUFF_COUNTS *huff_counts,my_off_t records,
  132.                    uint max_space_length,my_off_t *space_counts,
  133.                    my_off_t tot_space_count,
  134.                    enum en_fieldtype field_type);
  135. static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts,uint trees);
  136. static int make_huff_tree(HUFF_TREE *tree,HUFF_COUNTS *huff_counts);
  137. static int compare_huff_elements(void *not_used, byte *a,byte *b);
  138. static int save_counts_in_queue(byte *key,element_count count,
  139.                     HUFF_TREE *tree);
  140. static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,uint flag);
  141. static uint join_same_trees(HUFF_COUNTS *huff_counts,uint trees);
  142. static int make_huff_decode_table(HUFF_TREE *huff_tree,uint trees);
  143. static void make_traverse_code_tree(HUFF_TREE *huff_tree,
  144.                     HUFF_ELEMENT *element,uint size,
  145.                     ulong code);
  146. static int write_header(MRG_INFO *isam_file, uint header_length,uint trees,
  147.             my_off_t tot_elements,my_off_t filelength);
  148. static void write_field_info(HUFF_COUNTS *counts, uint fields,uint trees);
  149. static my_off_t write_huff_tree(HUFF_TREE *huff_tree,uint trees);
  150. static uint *make_offset_code_tree(HUFF_TREE *huff_tree,
  151.                        HUFF_ELEMENT *element,
  152.                        uint *offset);
  153. static uint max_bit(uint value);
  154. static int compress_isam_file(MRG_INFO *file,HUFF_COUNTS *huff_counts);
  155. static char *make_new_name(char *new_name,char *old_name);
  156. static char *make_old_name(char *new_name,char *old_name);
  157. static void init_file_buffer(File file,pbool read_buffer);
  158. static int flush_buffer(ulong neaded_length);
  159. static void end_file_buffer(void);
  160. static void write_bits(ulong value,uint bits);
  161. static void flush_bits(void);
  162. static int save_state(MI_INFO *isam_file,MRG_INFO *mrg,my_off_t new_length,
  163.               ha_checksum crc);
  164. static int save_state_mrg(File file,MRG_INFO *isam_file,my_off_t new_length,
  165.               ha_checksum crc);
  166. static int mrg_close(MRG_INFO *mrg);
  167. static int mrg_rrnd(MRG_INFO *info,byte *buf);
  168. static void mrg_reset(MRG_INFO *mrg);
  169.  
  170.  
  171. static int backup=0,error_on_write=0,test_only=0,verbose=0,silent=0,
  172.        write_loop=0,force_pack=0,opt_wait=0,isamchk_neaded=0;
  173. static int tmpfile_createflag=O_RDWR | O_TRUNC | O_EXCL;
  174. static uint tree_buff_length=8196-MALLOC_OVERHEAD;
  175. static char tmp_dir[FN_REFLEN]={0},*join_table;
  176. static my_off_t intervall_length;
  177. static ha_checksum glob_crc;
  178. static struct st_file_buffer file_buffer;
  179. static QUEUE queue;
  180. static HUFF_COUNTS *global_count;
  181. static char zero_string[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  182. static const char *load_default_groups[]= { "myisampack",0 };
  183.  
  184.     /* The main program */
  185.  
  186. int main(int argc, char **argv)
  187. {
  188.   int error,ok;
  189.   MRG_INFO merge;
  190.   char **default_argv;
  191.   MY_INIT(argv[0]);
  192.  
  193.   load_defaults("my",load_default_groups,&argc,&argv);
  194.   default_argv= argv;
  195.   get_options(&argc,&argv);
  196.  
  197.   error=ok=isamchk_neaded=0;
  198.   if (join_table)
  199.   {                        /* Join files into one */
  200.     if (open_isam_files(&merge,argv,(uint) argc) ||
  201.     compress(&merge,join_table))
  202.       error=1;
  203.   }
  204.   else while (argc--)
  205.   {
  206.     MI_INFO *isam_file;
  207.     if (!(isam_file=open_isam_file(*argv++,O_RDWR)))
  208.       error=1;
  209.     else
  210.     {
  211.       merge.file= &isam_file;
  212.       merge.current=0;
  213.       merge.free_file=0;
  214.       merge.count=1;
  215.       if (compress(&merge,0))
  216.     error=1;
  217.       else
  218.     ok=1;
  219.     }
  220.   }
  221.   if (ok && isamchk_neaded && !silent)
  222.     puts("Remember to run myisamchk -rq on compressed tables");
  223.   VOID(fflush(stdout)); VOID(fflush(stderr));
  224.   free_defaults(default_argv);
  225.   my_end(verbose ? MY_CHECK_ERROR | MY_GIVE_INFO : MY_CHECK_ERROR);
  226.   exit(error ? 2 : 0);
  227. #ifndef _lint
  228.   return 0;                    /* No compiler warning */
  229. #endif
  230. }
  231.  
  232.  
  233. static struct option long_options[] =
  234. {
  235.   {"backup",    no_argument,       0, 'b'},
  236.   {"debug",    optional_argument, 0, '#'},
  237.   {"force",    no_argument,       0, 'f'},
  238.   {"join",    required_argument, 0, 'j'},
  239.   {"help",    no_argument,       0, '?'},
  240.   {"packlength",required_argument, 0, 'p'},
  241.   {"silent",    no_argument,       0, 's'},
  242.   {"tmpdir",    required_argument, 0, 'T'},
  243.   {"test",    no_argument,       0, 't'},
  244.   {"verbose",    no_argument,       0, 'v'},
  245.   {"version",    no_argument,       0, 'V'},
  246.   {"wait",    no_argument,       0, 'w'},
  247.   {0, 0, 0, 0}
  248. };
  249.  
  250. static void print_version(void)
  251. {
  252.   printf("%s  Ver 1.8 for %s on %s\n",my_progname,SYSTEM_TYPE,MACHINE_TYPE);
  253. }
  254.  
  255. static void usage(void)
  256. {
  257.   print_version();
  258.   puts("Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB");
  259.   puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,");
  260.   puts("and you are welcome to modify and redistribute it under the GPL license\n");
  261.  
  262.   puts("Pack a MyISAM-table to take much less space.");
  263.   puts("Keys are not updated, you must run myisamchk -rq on the datafile");
  264.   puts("afterwards to update the keys.");
  265.   puts("You should give the .MSI file as the filename argument.");
  266.  
  267.   printf("\nUsage: %s [OPTIONS] filename...\n", my_progname);
  268.   puts("\n\
  269.   -b, --backup        Make a backup of the table as table_name.OLD\n\
  270.   -f, --force        Force packing of table even if it gets bigger or if\n\
  271.             tempfile exists.\n\
  272.   -j, --join='new_table_name'\n\
  273.             Join all given tables into 'new_table_name'.\n\
  274.             All tables MUST have identical layouts.\n\
  275.   -s, --silent        Be more silent.\n\
  276.   -t, --test        Don't pack table, only test packing it.\n\
  277.   -v, --verbose        Write info about progress and packing result.\n\
  278.   -w, --wait        Wait and retry if table is in use.\n\
  279.   -T, --tmpdir=...    Use temporary directory to store temporary table.\n\
  280.   -#, --debug=...       Output debug log. Often this is 'd:t:o,filename`\n\
  281.   -?, --help        Display this help and exit.\n\
  282.   -V, --version        Output version information and exit.");
  283.   print_defaults("my",load_default_groups);
  284. };
  285.  
  286.     /* reads options */
  287.     /* Initiates DEBUG - but no debugging here ! */
  288.  
  289. static void get_options(int *argc,char ***argv)
  290. {
  291.   int c,option_index=0;
  292.   uint length;
  293.  
  294.   my_progname= argv[0][0];
  295.   if (isatty(fileno(stdout)))
  296.     write_loop=1;
  297.  
  298.   while ((c=getopt_long(*argc,*argv,"bfj:stvwT:#::?V",long_options,
  299.             &option_index)) != EOF)
  300.   {
  301.     switch(c) {
  302.     case 'b':
  303.       backup=1;
  304.       break;
  305.     case 'f':
  306.       force_pack=1;
  307.       tmpfile_createflag=O_RDWR | O_TRUNC;
  308.       break;
  309.     case 'j':
  310.       join_table=optarg;
  311.       break;
  312.     case 's':
  313.       write_loop=verbose=0; silent=1;
  314.       break;
  315.     case 't':
  316.       test_only=verbose=1;
  317.       break;
  318.     case 'T':
  319.       length=(uint) (strmov(tmp_dir,optarg)-tmp_dir);
  320.       if (length != dirname_length(tmp_dir))
  321.       {
  322.     tmp_dir[length]=FN_LIBCHAR;
  323.     tmp_dir[length+1]=0;
  324.       }
  325.       break;
  326.     case 'v':
  327.       verbose=1; silent=0;
  328.       break;
  329.     case 'w':
  330.       opt_wait=1;
  331.       break;
  332.     case '#':
  333.       DBUG_PUSH(optarg ? optarg : "d:t:o");
  334.       break;
  335.     case 'V': print_version(); exit(0);
  336.     case 'I':
  337.     case '?':
  338.       usage();
  339.       exit(0);
  340.     default:
  341.       fprintf(stderr,"%s: Illegal option: -%c\n",my_progname,opterr);
  342.       usage();
  343.       exit(1);
  344.     }
  345.   }
  346.   (*argc)-=optind;
  347.   (*argv)+=optind;
  348.   if (!*argc)
  349.   {
  350.     usage();
  351.     exit(1);
  352.   }
  353.   if (join_table)
  354.   {
  355.     backup=0;                    /* Not needed */
  356.     tmp_dir[0]=0;
  357.   }
  358.   return;
  359. }
  360.  
  361.  
  362. static MI_INFO *open_isam_file(char *name,int mode)
  363. {
  364.   MI_INFO *isam_file;
  365.   MYISAM_SHARE *share;
  366.   DBUG_ENTER("open_isam_file");
  367.  
  368.   if (!(isam_file=mi_open(name,mode,
  369.               (opt_wait ? HA_OPEN_WAIT_IF_LOCKED :
  370.                HA_OPEN_ABORT_IF_LOCKED))))
  371.   {
  372.     VOID(fprintf(stderr,"%s gave error %d on open\n",name,my_errno));
  373.     DBUG_RETURN(0);
  374.   }
  375.   share=isam_file->s;
  376.   if (share->options & HA_OPTION_COMPRESS_RECORD && !join_table)
  377.   {
  378.     if (!force_pack)
  379.     {
  380.       VOID(fprintf(stderr,"%s is already compressed\n",name));
  381.       VOID(mi_close(isam_file));
  382.       DBUG_RETURN(0);
  383.     }
  384.     if (verbose)
  385.       puts("Recompressing already compressed table");
  386.     share->options&= ~HA_OPTION_READ_ONLY_DATA; /* We are modifing it */
  387.   }
  388.   if (! force_pack && share->state.state.records != 0 &&
  389.       (share->state.state.records <= 1 ||
  390.        share->state.state.data_file_length < 1024))
  391.   {
  392.     VOID(fprintf(stderr,"%s is too small to compress\n",name));
  393.     VOID(mi_close(isam_file));
  394.     DBUG_RETURN(0);
  395.   }
  396.   VOID(mi_lock_database(isam_file,F_WRLCK));
  397.   DBUG_RETURN(isam_file);
  398. }
  399.  
  400.  
  401. static bool open_isam_files(MRG_INFO *mrg,char **names,uint count)
  402. {
  403.   uint i,j;
  404.   mrg->count=0;
  405.   mrg->current=0;
  406.   mrg->file=(MI_INFO**) my_malloc(sizeof(MI_INFO*)*count,MYF(MY_FAE));
  407.   mrg->free_file=1;
  408.   for (i=0; i < count ; i++)
  409.   {
  410.     if (!(mrg->file[i]=open_isam_file(names[i],O_RDONLY)))
  411.       goto error;
  412.   }
  413.   /* Check that files are identical */
  414.   for (j=0 ; j < count-1 ; j++)
  415.   {
  416.     MI_COLUMNDEF *m1,*m2,*end;
  417.     if (mrg->file[j]->s->base.reclength != mrg->file[j+1]->s->base.reclength ||
  418.     mrg->file[j]->s->base.fields != mrg->file[j+1]->s->base.fields)
  419.       goto diff_file;
  420.     m1=mrg->file[j]->s->rec;
  421.     end=m1+mrg->file[j]->s->base.fields;
  422.     m2=mrg->file[j+1]->s->rec;
  423.     for ( ; m1 != end ; m1++,m2++)
  424.     {
  425.       if (m1->type != m2->type || m1->length != m2->length)
  426.     goto diff_file;
  427.     }
  428.   }
  429.   mrg->count=count;
  430.   return 0;
  431.  
  432.  diff_file:
  433.   fprintf(stderr,"%s: Tables '%s' and '%s' are not identical\n",
  434.       my_progname,names[j],names[j+1]);
  435.  error:
  436.   while (i--)
  437.     mi_close(mrg->file[i]);
  438.   my_free((gptr) mrg->file,MYF(0));
  439.   return 1;
  440. }
  441.  
  442.  
  443. static int compress(MRG_INFO *mrg,char *result_table)
  444. {
  445.   int error;
  446.   File new_file,join_isam_file;
  447.   MI_INFO *isam_file;
  448.   MYISAM_SHARE *share;
  449.   char org_name[FN_REFLEN],new_name[FN_REFLEN],temp_name[FN_REFLEN];
  450.   uint i,header_length,fields,trees,used_trees;
  451.   my_off_t old_length,new_length,tot_elements;
  452.   HUFF_COUNTS *huff_counts;
  453.   HUFF_TREE *huff_trees;
  454.   DBUG_ENTER("compress");
  455.  
  456.   isam_file=mrg->file[0];            /* Take this as an example */
  457.   share=isam_file->s;
  458.   new_file=join_isam_file= -1;
  459.   trees=fields=0;
  460.   huff_trees=0;
  461.   huff_counts=0;
  462.  
  463.   /* Create temporary or join file */
  464.  
  465.   if (backup)
  466.     VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2));
  467.   else
  468.     VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2+4+16));
  469.   if (!test_only && result_table)
  470.   {
  471.     /* Make a new indexfile based on first file in list */
  472.     uint length;
  473.     char *buff;
  474.     strmov(org_name,result_table);        /* Fix error messages */
  475.     VOID(fn_format(new_name,result_table,"",MI_NAME_IEXT,2));
  476.     if ((join_isam_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME)))
  477.     < 0)
  478.       goto err;
  479.     length=(uint) share->base.keystart;
  480.     if (!(buff=my_malloc(length,MYF(MY_WME))))
  481.       goto err;
  482.     if (my_pread(share->kfile,buff,length,0L,MYF(MY_WME | MY_NABP)) ||
  483.     my_write(join_isam_file,buff,length,
  484.          MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
  485.     {
  486.       my_free(buff,MYF(0));
  487.       goto err;
  488.     }
  489.     my_free(buff,MYF(0));
  490.     VOID(fn_format(new_name,result_table,"",MI_NAME_DEXT,2));
  491.   }
  492.   else if (!tmp_dir[0])
  493.     VOID(make_new_name(new_name,org_name));
  494.   else
  495.     VOID(fn_format(new_name,org_name,tmp_dir,DATA_TMP_EXT,1+2+4));
  496.   if (!test_only &&
  497.       (new_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME))) < 0)
  498.     goto err;
  499.  
  500.   /* Start calculating statistics */
  501.  
  502.   mrg->records=0;
  503.   for (i=0 ; i < mrg->count ; i++)
  504.     mrg->records+=mrg->file[i]->s->state.state.records;
  505.   if (write_loop || verbose)
  506.   {
  507.     printf("Compressing %s: (%lu records)\n",
  508.        result_table ? new_name : org_name,(ulong) mrg->records);
  509.   }
  510.   trees=fields=share->base.fields;
  511.   huff_counts=init_huff_count(isam_file,mrg->records);
  512.   QUICK_SAFEMALLOC;
  513.   if (write_loop || verbose)
  514.     printf("- Calculating statistics\n");
  515.   if (get_statistic(mrg,huff_counts))
  516.     goto err;
  517.   NORMAL_SAFEMALLOC;
  518.   old_length=0;
  519.   for (i=0; i < mrg->count ; i++)
  520.     old_length+= (mrg->file[i]->s->state.state.data_file_length -
  521.           mrg->file[i]->s->state.state.empty);
  522.  
  523.   if (init_queue(&queue,256,0,0,compare_huff_elements,0))
  524.     goto err;
  525.   check_counts(huff_counts,fields,mrg->records);
  526.   huff_trees=make_huff_trees(huff_counts,trees);
  527.   if ((int) (used_trees=join_same_trees(huff_counts,trees)) < 0)
  528.     goto err;
  529.   if (make_huff_decode_table(huff_trees,fields))
  530.     goto err;
  531.  
  532.   init_file_buffer(new_file,0);
  533.   file_buffer.pos_in_file=HEAD_LENGTH;
  534.   if (! test_only)
  535.     VOID(my_seek(new_file,file_buffer.pos_in_file,MY_SEEK_SET,MYF(0)));
  536.  
  537.   write_field_info(huff_counts,fields,used_trees);
  538.   if (!(tot_elements=write_huff_tree(huff_trees,trees)))
  539.     goto err;
  540.   header_length=(uint) file_buffer.pos_in_file+
  541.     (uint) (file_buffer.pos-file_buffer.buffer);
  542.  
  543.   /* Compress file */
  544.   if (write_loop || verbose)
  545.     printf("- Compressing file\n");
  546.   error=compress_isam_file(mrg,huff_counts);
  547.   new_length=file_buffer.pos_in_file;
  548.   if (!error && !test_only)
  549.   {
  550.     char buff[MEMMAP_EXTRA_MARGIN];        /* End marginal for memmap */
  551.     bzero(buff,sizeof(buff));
  552.     error=my_write(file_buffer.file,buff,sizeof(buff),
  553.            MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
  554.   }
  555.   if (!error)
  556.     error=write_header(mrg,header_length,used_trees,tot_elements,
  557.                new_length);
  558.   end_file_buffer();
  559.  
  560.   if (verbose && mrg->records)
  561.     printf("Min record length: %6d   Max length: %6d   Mean total length: %6ld\n",
  562.        mrg->min_pack_length,mrg->max_pack_length,
  563.        (ulong) (new_length/mrg->records));
  564.  
  565.   if (!test_only)
  566.   {
  567.     error|=my_close(new_file,MYF(MY_WME));
  568.     if (!result_table)
  569.     {
  570.       error|=my_close(isam_file->dfile,MYF(MY_WME));
  571.       isam_file->dfile= -1;        /* Tell mi_close file is closed */
  572.     }
  573.   }
  574.  
  575.   free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
  576.   if (! test_only && ! error)
  577.   {
  578.     if (result_table)
  579.     {
  580.       error=save_state_mrg(join_isam_file,mrg,new_length,glob_crc);
  581.     }
  582.     else
  583.     {
  584.       if (backup)
  585.       {
  586.     if (my_rename(org_name,make_old_name(temp_name,isam_file->filename),
  587.               MYF(MY_WME)))
  588.       error=1;
  589.     else
  590.     {
  591.       if (tmp_dir[0])
  592.       {
  593.         if (!(error=my_copy(new_name,org_name,MYF(MY_WME))))
  594.           VOID(my_delete(new_name,MYF(MY_WME)));
  595.       }
  596.       else
  597.         error=my_rename(new_name,org_name,MYF(MY_WME));
  598.       if (!error)
  599.         VOID(my_copystat(temp_name,org_name,MYF(MY_COPYTIME)));
  600.     }
  601.       }
  602.       else
  603.       {
  604.     if (tmp_dir[0])
  605.     {
  606.  
  607.       if (!(error=my_copy(new_name,org_name,
  608.                   MYF(MY_WME | MY_HOLD_ORIGINAL_MODES
  609.                   | MY_COPYTIME))))
  610.         VOID(my_delete(new_name,MYF(MY_WME)));
  611.     }
  612.     else
  613.       error=my_redel(org_name,new_name,MYF(MY_WME | MY_COPYTIME));
  614.       }
  615.       if (! error)
  616.     error=save_state(isam_file,mrg,new_length,glob_crc);
  617.     }
  618.   }
  619.   error|=mrg_close(mrg);
  620.   if (join_isam_file >= 0)
  621.     error|=my_close(join_isam_file,MYF(MY_WME));
  622.   if (error)
  623.   {
  624.     VOID(fprintf(stderr,"Aborting: %s is not compressed\n",org_name));
  625.     DBUG_RETURN(-1);
  626.   }
  627.   if (write_loop || verbose)
  628.   {
  629.     if (old_length)
  630.       printf("%.4g%%     \n", (((longlong) (old_length -new_length))*100.0/
  631.                    (longlong) old_length));
  632.     else
  633.       puts("Empty file saved in compressed format");
  634.   }
  635.   DBUG_RETURN(0);
  636.  
  637.  err:
  638.   free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
  639.   if (new_file >= 0)
  640.     VOID(my_close(new_file,MYF(0)));
  641.   if (join_isam_file >= 0)
  642.     VOID(my_close(join_isam_file,MYF(0)));
  643.   mrg_close(mrg);
  644.   VOID(fprintf(stderr,"Aborted: %s is not compressed\n",org_name));
  645.   DBUG_RETURN(-1);
  646. }
  647.  
  648.     /* Init a huff_count-struct for each field and init it */
  649.  
  650. static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records)
  651. {
  652.   reg2 uint i;
  653.   reg1 HUFF_COUNTS *count;
  654.   if ((count = (HUFF_COUNTS*) my_malloc(info->s->base.fields*
  655.                     sizeof(HUFF_COUNTS),
  656.                     MYF(MY_ZEROFILL | MY_WME))))
  657.   {
  658.     for (i=0 ; i < info->s->base.fields ; i++)
  659.     {
  660.       enum en_fieldtype type;
  661.       count[i].field_length=info->s->rec[i].length;
  662.       type= count[i].field_type= (enum en_fieldtype) info->s->rec[i].type;
  663.       if (type == FIELD_INTERVALL ||
  664.       type == FIELD_CONSTANT ||
  665.       type == FIELD_ZERO)
  666.     type = FIELD_NORMAL;
  667.       if (count[i].field_length <= 8 &&
  668.       (type == FIELD_NORMAL ||
  669.        type == FIELD_SKIPP_ZERO))
  670.     count[i].max_zero_fill= count[i].field_length;
  671.       init_tree(&count[i].int_tree,0,-1,(qsort_cmp) compare_tree,0,NULL);
  672.       if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
  673.     count[i].tree_pos=count[i].tree_buff =
  674.       my_malloc(count[i].field_length > 1 ? tree_buff_length : 2,
  675.             MYF(MY_WME));
  676.     }
  677.   }
  678.   return count;
  679. }
  680.  
  681.  
  682.     /* Free memory used by counts and trees */
  683.  
  684. static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees, uint trees,
  685.                        HUFF_COUNTS *huff_counts,
  686.                        uint fields)
  687. {
  688.   register uint i;
  689.  
  690.   if (huff_trees)
  691.   {
  692.     for (i=0 ; i < trees ; i++)
  693.     {
  694.       if (huff_trees[i].element_buffer)
  695.     my_free((gptr) huff_trees[i].element_buffer,MYF(0));
  696.       if (huff_trees[i].code)
  697.     my_free((gptr) huff_trees[i].code,MYF(0));
  698.     }
  699.     my_free((gptr) huff_trees,MYF(0));
  700.   }
  701.   if (huff_counts)
  702.   {
  703.     for (i=0 ; i < fields ; i++)
  704.     {
  705.       if (huff_counts[i].tree_buff)
  706.       {
  707.     my_free((gptr) huff_counts[i].tree_buff,MYF(0));
  708.     delete_tree(&huff_counts[i].int_tree);
  709.       }
  710.     }
  711.     my_free((gptr) huff_counts,MYF(0));
  712.   }
  713.   delete_queue(&queue);        /* This is safe to free */
  714.   return;
  715. }
  716.  
  717.     /* Read through old file and gather some statistics */
  718.  
  719. static int get_statistic(MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
  720. {
  721.   int error;
  722.   uint length;
  723.   ulong reclength,max_blob_length;
  724.   byte *record,*pos,*next_pos,*end_pos,*start_pos;
  725.   ha_rows record_count;
  726.   my_bool static_row_size;
  727.   HUFF_COUNTS *count,*end_count;
  728.   TREE_ELEMENT *element;
  729.   DBUG_ENTER("get_statistic");
  730.  
  731.   reclength=mrg->file[0]->s->base.reclength;
  732.   record=(byte*) my_alloca(reclength);
  733.   end_count=huff_counts+mrg->file[0]->s->base.fields;
  734.   record_count=0; glob_crc=0;
  735.   max_blob_length=0;
  736.  
  737.   /* Check how to calculate checksum */
  738.   static_row_size=1;
  739.   for (count=huff_counts ; count < end_count ; count++)
  740.   {
  741.     if (count->field_type == FIELD_BLOB || count->field_type == FIELD_VARCHAR)
  742.     {
  743.       static_row_size=0;
  744.       break;
  745.     }
  746.   }
  747.  
  748.   mrg_reset(mrg);
  749.   while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
  750.   {
  751.     ulong tot_blob_length=0;
  752.     if (! error)
  753.     {
  754.       if (static_row_size)
  755.     glob_crc+=mi_static_checksum(mrg->file[0],record);
  756.       else
  757.     glob_crc+=mi_checksum(mrg->file[0],record);
  758.       for (pos=record,count=huff_counts ;
  759.        count < end_count ;
  760.        count++,
  761.        pos=next_pos)
  762.       {
  763.     next_pos=end_pos=(start_pos=pos)+count->field_length;
  764.  
  765.     /* Put value in tree if there is room for it */
  766.     if (count->tree_buff)
  767.     {
  768.       global_count=count;
  769.       if (!(element=tree_insert(&count->int_tree,pos,0)) ||
  770.           (element->count == 1 &&
  771.            count->tree_buff + tree_buff_length <
  772.            count->tree_pos + count->field_length) ||
  773.           (count->field_length == 1 &&
  774.            count->int_tree.elements_in_tree > 1))
  775.       {
  776.         delete_tree(&count->int_tree);
  777.         my_free(count->tree_buff,MYF(0));
  778.         count->tree_buff=0;
  779.       }
  780.       else
  781.       {
  782.         if (element->count == 1)
  783.         {                /* New element */
  784.           memcpy(count->tree_pos,pos,(size_t) count->field_length);
  785.           tree_set_pointer(element,count->tree_pos);
  786.           count->tree_pos+=count->field_length;
  787.         }
  788.       }
  789.     }
  790.  
  791.     /* Save character counters and space-counts and zero-field-counts */
  792.     if (count->field_type == FIELD_NORMAL ||
  793.         count->field_type == FIELD_SKIPP_ENDSPACE)
  794.     {
  795.       for ( ; end_pos > pos ; end_pos--)
  796.         if (end_pos[-1] != ' ')
  797.           break;
  798.       if (end_pos == pos)
  799.       {
  800.         count->empty_fields++;
  801.         count->max_zero_fill=0;
  802.         continue;
  803.       }
  804.       length= (uint) (next_pos-end_pos);
  805.       count->tot_end_space+=length;
  806.       if (length < 8)
  807.         count->end_space[length]++;
  808.       if (count->max_end_space < length)
  809.         count->max_end_space = length;
  810.     }
  811.     if (count->field_type == FIELD_NORMAL ||
  812.         count->field_type == FIELD_SKIPP_PRESPACE)
  813.     {
  814.       for (pos=start_pos; pos < end_pos ; pos++)
  815.         if (pos[0] != ' ')
  816.           break;
  817.       if (end_pos == pos)
  818.       {
  819.         count->empty_fields++;
  820.         count->max_zero_fill=0;
  821.         continue;
  822.       }
  823.       length= (uint) (pos-start_pos);
  824.       count->tot_pre_space+=length;
  825.       if (length < 8)
  826.         count->pre_space[length]++;
  827.       if (count->max_pre_space < length)
  828.         count->max_pre_space = length;
  829.     }
  830.     if (count->field_type == FIELD_BLOB)
  831.     {
  832.       uint field_length=count->field_length -mi_portable_sizeof_char_ptr;
  833.       ulong blob_length= _mi_calc_blob_length(field_length, start_pos);
  834.       memcpy_fixed((char*) &pos,  start_pos+field_length,sizeof(char*));
  835.       end_pos=pos+blob_length;
  836.       tot_blob_length+=blob_length;
  837.       set_if_bigger(count->max_length,blob_length);
  838.     }
  839.     else if (count->field_type == FIELD_VARCHAR)
  840.     {
  841.       length=uint2korr(start_pos);
  842.       pos=start_pos+2;
  843.       end_pos=start_pos+length;
  844.       set_if_bigger(count->max_length,length);
  845.     }
  846.     if (count->field_length <= 8 &&
  847.         (count->field_type == FIELD_NORMAL ||
  848.          count->field_type == FIELD_SKIPP_ZERO))
  849.     {
  850.       uint i;
  851.       if (!memcmp((byte*) start_pos,zero_string,count->field_length))
  852.       {
  853.         count->zero_fields++;
  854.         continue;
  855.       }
  856.       for (i =0 ; i < count->max_zero_fill && ! end_pos[-1 - (int) i] ;
  857.            i++) ;
  858.       if (i < count->max_zero_fill)
  859.         count->max_zero_fill=i;
  860.     }
  861.     if (count->field_type == FIELD_ZERO ||
  862.         count->field_type == FIELD_CHECK)
  863.       continue;
  864.     for ( ; pos < end_pos ; pos++)
  865.       count->counts[(uchar) *pos]++;
  866.       }
  867.       if (tot_blob_length > max_blob_length)
  868.     max_blob_length=tot_blob_length;
  869.       record_count++;
  870.       if (write_loop && record_count % WRITE_COUNT == 0)
  871.       {
  872.     printf("%lu\r",(ulong) record_count); VOID(fflush(stdout));
  873.       }
  874.     }
  875.     else if (error != HA_ERR_RECORD_DELETED)
  876.     {
  877.       fprintf(stderr,"Got error %d while reading rows",error);
  878.       break;
  879.     }
  880.   }
  881.   if (write_loop)
  882.   {
  883.     printf("            \r"); VOID(fflush(stdout));
  884.   }
  885.   mrg->records=record_count;
  886.   mrg->max_blob_length=max_blob_length;
  887.   my_afree((gptr) record);
  888.   DBUG_RETURN(error != HA_ERR_END_OF_FILE);
  889. }
  890.  
  891. static int compare_huff_elements(void *not_used, byte *a, byte *b)
  892. {
  893.   return *((my_off_t*) a) < *((my_off_t*) b) ? -1 :
  894.     (*((my_off_t*) a) == *((my_off_t*) b)  ? 0 : 1);
  895. }
  896.  
  897.     /* Check each tree if we should use pre-space-compress, end-space-
  898.        compress, empty-field-compress or zero-field-compress */
  899.  
  900. static void check_counts(HUFF_COUNTS *huff_counts, uint trees,
  901.              my_off_t records)
  902. {
  903.   uint space_fields,fill_zero_fields,field_count[(int) FIELD_VARCHAR+1];
  904.   my_off_t old_length,new_length,length;
  905.   DBUG_ENTER("check_counts");
  906.  
  907.   bzero((gptr) field_count,sizeof(field_count));
  908.   space_fields=fill_zero_fields=0;
  909.  
  910.   for (; trees-- ; huff_counts++)
  911.   {
  912.     if (huff_counts->field_type == FIELD_BLOB)
  913.     {
  914.       huff_counts->length_bits=max_bit(huff_counts->max_length);
  915.       goto found_pack;
  916.     }
  917.     else if (huff_counts->field_type == FIELD_VARCHAR)
  918.     {
  919.       huff_counts->length_bits=max_bit(huff_counts->max_length);
  920.       goto found_pack;
  921.     }
  922.     else if (huff_counts->field_type == FIELD_CHECK)
  923.     {
  924.       huff_counts->bytes_packed=0;
  925.       huff_counts->counts[0]=0;
  926.       goto found_pack;
  927.     }
  928.  
  929.     huff_counts->field_type=FIELD_NORMAL;
  930.     huff_counts->pack_type=0;
  931.  
  932.     if (huff_counts->zero_fields || ! records)
  933.     {
  934.       my_off_t old_space_count;
  935.       if (huff_counts->zero_fields == records)
  936.       {
  937.     huff_counts->field_type= FIELD_ZERO;
  938.     huff_counts->bytes_packed=0;
  939.     huff_counts->counts[0]=0;
  940.     goto found_pack;
  941.       }
  942.       old_space_count=huff_counts->counts[' '];
  943.       huff_counts->counts[' ']+=huff_counts->tot_end_space+
  944.     huff_counts->tot_pre_space +
  945.       huff_counts->empty_fields * huff_counts->field_length;
  946.       old_length=calc_packed_length(huff_counts,0)+records/8;
  947.       length=huff_counts->zero_fields*huff_counts->field_length;
  948.       huff_counts->counts[0]+=length;
  949.       new_length=calc_packed_length(huff_counts,0);
  950.       if (old_length < new_length && huff_counts->field_length > 1)
  951.       {
  952.     huff_counts->field_type=FIELD_SKIPP_ZERO;
  953.     huff_counts->counts[0]-=length;
  954.     huff_counts->bytes_packed=old_length- records/8;
  955.     goto found_pack;
  956.       }
  957.       huff_counts->counts[' ']=old_space_count;
  958.     }
  959.     huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
  960.     if (huff_counts->empty_fields)
  961.     {
  962.       if (huff_counts->field_length > 2 &&
  963.       huff_counts->empty_fields + (records - huff_counts->empty_fields)*
  964.       (1+max_bit(max(huff_counts->max_pre_space,
  965.              huff_counts->max_end_space))) <
  966.       records * max_bit(huff_counts->field_length))
  967.       {
  968.     huff_counts->pack_type |= PACK_TYPE_SPACE_FIELDS;
  969.       }
  970.       else
  971.       {
  972.     length=huff_counts->empty_fields*huff_counts->field_length;
  973.     if (huff_counts->tot_end_space || ! huff_counts->tot_pre_space)
  974.     {
  975.       huff_counts->tot_end_space+=length;
  976.       huff_counts->max_end_space=huff_counts->field_length;
  977.       if (huff_counts->field_length < 8)
  978.         huff_counts->end_space[huff_counts->field_length]+=
  979.           huff_counts->empty_fields;
  980.     }
  981.     else
  982.     {
  983.       huff_counts->tot_pre_space+=length;
  984.       huff_counts->max_pre_space=huff_counts->field_length;
  985.       if (huff_counts->field_length < 8)
  986.         huff_counts->pre_space[huff_counts->field_length]+=
  987.           huff_counts->empty_fields;
  988.     }
  989.       }
  990.     }
  991.     if (huff_counts->tot_end_space)
  992.     {
  993.       huff_counts->counts[' ']+=huff_counts->tot_pre_space;
  994.       if (test_space_compress(huff_counts,records,huff_counts->max_end_space,
  995.                   huff_counts->end_space,
  996.                   huff_counts->tot_end_space,FIELD_SKIPP_ENDSPACE))
  997.     goto found_pack;
  998.       huff_counts->counts[' ']-=huff_counts->tot_pre_space;
  999.     }
  1000.     if (huff_counts->tot_pre_space)
  1001.     {
  1002.       if (test_space_compress(huff_counts,records,huff_counts->max_pre_space,
  1003.                   huff_counts->pre_space,
  1004.                   huff_counts->tot_pre_space,FIELD_SKIPP_PRESPACE))
  1005.     goto found_pack;
  1006.     }
  1007.  
  1008.   found_pack:            /* Found field-packing */
  1009.  
  1010.     /* Test if we can use zero-fill */
  1011.  
  1012.     if (huff_counts->max_zero_fill &&
  1013.     (huff_counts->field_type == FIELD_NORMAL ||
  1014.      huff_counts->field_type == FIELD_SKIPP_ZERO))
  1015.     {
  1016.       huff_counts->counts[0]-=huff_counts->max_zero_fill*
  1017.     (huff_counts->field_type == FIELD_SKIPP_ZERO ?
  1018.      records - huff_counts->zero_fields : records);
  1019.       huff_counts->pack_type|=PACK_TYPE_ZERO_FILL;
  1020.       huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
  1021.     }
  1022.  
  1023.     /* Test if intervall-field is better */
  1024.  
  1025.     if (huff_counts->tree_buff)
  1026.     {
  1027.       HUFF_TREE tree;
  1028.  
  1029.       tree.element_buffer=0;
  1030.       if (!make_huff_tree(&tree,huff_counts) &&
  1031.       tree.bytes_packed+tree.tree_pack_length < huff_counts->bytes_packed)
  1032.       {
  1033.     if (tree.elements == 1)
  1034.       huff_counts->field_type=FIELD_CONSTANT;
  1035.     else
  1036.       huff_counts->field_type=FIELD_INTERVALL;
  1037.     huff_counts->pack_type=0;
  1038.       }
  1039.       else
  1040.       {
  1041.     my_free((gptr) huff_counts->tree_buff,MYF(0));
  1042.     delete_tree(&huff_counts->int_tree);
  1043.     huff_counts->tree_buff=0;
  1044.       }
  1045.       if (tree.element_buffer)
  1046.     my_free((gptr) tree.element_buffer,MYF(0));
  1047.     }
  1048.     if (huff_counts->pack_type & PACK_TYPE_SPACE_FIELDS)
  1049.       space_fields++;
  1050.     if (huff_counts->pack_type & PACK_TYPE_ZERO_FILL)
  1051.       fill_zero_fields++;
  1052.     field_count[huff_counts->field_type]++;
  1053.   }
  1054.   if (verbose)
  1055.     printf("\nnormal:    %3d  empty-space:     %3d  empty-zero:       %3d  empty-fill: %3d\npre-space: %3d  end-space:       %3d  intervall-fields: %3d  zero:       %3d\n",
  1056.        field_count[FIELD_NORMAL],space_fields,
  1057.        field_count[FIELD_SKIPP_ZERO],fill_zero_fields,
  1058.        field_count[FIELD_SKIPP_PRESPACE],
  1059.        field_count[FIELD_SKIPP_ENDSPACE],
  1060.        field_count[FIELD_INTERVALL],
  1061.        field_count[FIELD_ZERO]);
  1062.   DBUG_VOID_RETURN;
  1063. }
  1064.  
  1065.     /* Test if we can use space-compression and empty-field-compression */
  1066.  
  1067. static int
  1068. test_space_compress(HUFF_COUNTS *huff_counts, my_off_t records,
  1069.             uint max_space_length, my_off_t *space_counts,
  1070.             my_off_t tot_space_count, enum en_fieldtype field_type)
  1071. {
  1072.   int min_pos;
  1073.   uint length_bits,i;
  1074.   my_off_t space_count,min_space_count,min_pack,new_length,skipp;
  1075.  
  1076.   length_bits=max_bit(max_space_length);
  1077.  
  1078.         /* Default no end_space-packing */
  1079.   space_count=huff_counts->counts[(uint) ' '];
  1080.   min_space_count= (huff_counts->counts[(uint) ' ']+= tot_space_count);
  1081.   min_pack=calc_packed_length(huff_counts,0);
  1082.   min_pos= -2;
  1083.   huff_counts->counts[(uint) ' ']=space_count;
  1084.  
  1085.     /* Test with allways space-count */
  1086.   new_length=huff_counts->bytes_packed+length_bits*records/8;
  1087.   if (new_length+1 < min_pack)
  1088.   {
  1089.     min_pos= -1;
  1090.     min_pack=new_length;
  1091.     min_space_count=space_count;
  1092.   }
  1093.     /* Test with length-flag */
  1094.   for (skipp=0L, i=0 ; i < 8 ; i++)
  1095.   {
  1096.     if (space_counts[i])
  1097.     {
  1098.       if (i)
  1099.     huff_counts->counts[(uint) ' ']+=space_counts[i];
  1100.       skipp+=huff_counts->pre_space[i];
  1101.       new_length=calc_packed_length(huff_counts,0)+
  1102.     (records+(records-skipp)*(1+length_bits))/8;
  1103.       if (new_length < min_pack)
  1104.       {
  1105.     min_pos=(int) i;
  1106.     min_pack=new_length;
  1107.     min_space_count=huff_counts->counts[(uint) ' '];
  1108.       }
  1109.     }
  1110.   }
  1111.  
  1112.   huff_counts->counts[(uint) ' ']=min_space_count;
  1113.   huff_counts->bytes_packed=min_pack;
  1114.   switch (min_pos) {
  1115.   case -2:
  1116.     return(0);                /* No space-compress */
  1117.   case -1:                /* Always space-count */
  1118.     huff_counts->field_type=field_type;
  1119.     huff_counts->min_space=0;
  1120.     huff_counts->length_bits=max_bit(max_space_length);
  1121.     break;
  1122.   default:
  1123.     huff_counts->field_type=field_type;
  1124.     huff_counts->min_space=(uint) min_pos;
  1125.     huff_counts->pack_type|=PACK_TYPE_SELECTED;
  1126.     huff_counts->length_bits=max_bit(max_space_length);
  1127.     break;
  1128.   }
  1129.   return(1);                /* Using space-compress */
  1130. }
  1131.  
  1132.  
  1133.     /* Make a huff_tree of each huff_count */
  1134.  
  1135. static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts, uint trees)
  1136. {
  1137.   uint tree;
  1138.   HUFF_TREE *huff_tree;
  1139.   DBUG_ENTER("make_huff_trees");
  1140.  
  1141.   if (!(huff_tree=(HUFF_TREE*) my_malloc(trees*sizeof(HUFF_TREE),
  1142.                      MYF(MY_WME | MY_ZEROFILL))))
  1143.     DBUG_RETURN(0);
  1144.  
  1145.   for (tree=0 ; tree < trees ; tree++)
  1146.   {
  1147.     if (make_huff_tree(huff_tree+tree,huff_counts+tree))
  1148.     {
  1149.       while (tree--)
  1150.     my_free((gptr) huff_tree[tree].element_buffer,MYF(0));
  1151.       my_free((gptr) huff_tree,MYF(0));
  1152.       DBUG_RETURN(0);
  1153.     }
  1154.   }
  1155.   DBUG_RETURN(huff_tree);
  1156. }
  1157.  
  1158.     /* Update huff_tree according to huff_counts->counts or
  1159.        huff_counts->tree_buff */
  1160.  
  1161. static int make_huff_tree(HUFF_TREE *huff_tree, HUFF_COUNTS *huff_counts)
  1162. {
  1163.   uint i,found,bits_packed,first,last;
  1164.   my_off_t bytes_packed;
  1165.   HUFF_ELEMENT *a,*b,*new;
  1166.  
  1167.   first=last=0;
  1168.   if (huff_counts->tree_buff)
  1169.   {
  1170.     found= (uint) (huff_counts->tree_pos - huff_counts->tree_buff) /
  1171.       huff_counts->field_length;
  1172.     first=0; last=found-1;
  1173.   }
  1174.   else
  1175.   {
  1176.     for (i=found=0 ; i < 256 ; i++)
  1177.     {
  1178.       if (huff_counts->counts[i])
  1179.       {
  1180.     if (! found++)
  1181.       first=i;
  1182.     last=i;
  1183.       }
  1184.     }
  1185.     if (found < 2)
  1186.       found=2;
  1187.   }
  1188.  
  1189.   if (queue.max_elements < found)
  1190.   {
  1191.     delete_queue(&queue);
  1192.     if (init_queue(&queue,found,0,0,compare_huff_elements,0))
  1193.       return -1;
  1194.   }
  1195.  
  1196.   if (!huff_tree->element_buffer)
  1197.   {
  1198.     if (!(huff_tree->element_buffer=
  1199.      (HUFF_ELEMENT*) my_malloc(found*2*sizeof(HUFF_ELEMENT),MYF(MY_WME))))
  1200.       return 1;
  1201.   }
  1202.   else
  1203.   {
  1204.     HUFF_ELEMENT *temp;
  1205.     if (!(temp=
  1206.       (HUFF_ELEMENT*) my_realloc((gptr) huff_tree->element_buffer,
  1207.                      found*2*sizeof(HUFF_ELEMENT),
  1208.                      MYF(MY_WME))))
  1209.       return 1;
  1210.     huff_tree->element_buffer=temp;
  1211.   }
  1212.  
  1213.   huff_counts->tree=huff_tree;
  1214.   huff_tree->counts=huff_counts;
  1215.   huff_tree->min_chr=first;
  1216.   huff_tree->max_chr=last;
  1217.   huff_tree->char_bits=max_bit(last-first);
  1218.   huff_tree->offset_bits=max_bit(found-1)+1;
  1219.  
  1220.   if (huff_counts->tree_buff)
  1221.   {
  1222.     huff_tree->elements=0;
  1223.     tree_walk(&huff_counts->int_tree,
  1224.           (int (*)(void*, element_count,void*)) save_counts_in_queue,
  1225.           (gptr) huff_tree, left_root_right);
  1226.     huff_tree->tree_pack_length=(1+15+16+5+5+
  1227.                  (huff_tree->char_bits+1)*found+
  1228.                  (huff_tree->offset_bits+1)*
  1229.                  (found-2)+7)/8 +
  1230.                    (uint) (huff_tree->counts->tree_pos-
  1231.                        huff_tree->counts->tree_buff);
  1232.   }
  1233.   else
  1234.   {
  1235.     huff_tree->elements=found;
  1236.     huff_tree->tree_pack_length=(9+9+5+5+
  1237.                  (huff_tree->char_bits+1)*found+
  1238.                  (huff_tree->offset_bits+1)*
  1239.                  (found-2)+7)/8;
  1240.  
  1241.     for (i=first, found=0 ; i <= last ; i++)
  1242.     {
  1243.       if (huff_counts->counts[i])
  1244.       {
  1245.     new=huff_tree->element_buffer+(found++);
  1246.     new->count=huff_counts->counts[i];
  1247.     new->a.leaf.null=0;
  1248.     new->a.leaf.element_nr=i;
  1249.     queue.root[found]=(byte*) new;
  1250.       }
  1251.     }
  1252.     while (found < 2)
  1253.     {            /* Our huff_trees request at least 2 elements */
  1254.       new=huff_tree->element_buffer+(found++);
  1255.       new->count=0;
  1256.       new->a.leaf.null=0;
  1257.       if (last)
  1258.     new->a.leaf.element_nr=huff_tree->min_chr=last-1;
  1259.       else
  1260.     new->a.leaf.element_nr=huff_tree->max_chr=last+1;
  1261.       queue.root[found]=(byte*) new;
  1262.     }
  1263.   }
  1264.   queue.elements=found;
  1265.  
  1266.   for (i=found/2 ; i > 0 ; i--)
  1267.     _downheap(&queue,i);
  1268.   bytes_packed=0; bits_packed=0;
  1269.   for (i=1 ; i < found ; i++)
  1270.   {
  1271.     a=(HUFF_ELEMENT*) queue_remove(&queue,0);
  1272.     b=(HUFF_ELEMENT*) queue.root[1];
  1273.     new=huff_tree->element_buffer+found+i;
  1274.     new->count=a->count+b->count;
  1275.     bits_packed+=(uint) (new->count & 7);
  1276.     bytes_packed+=new->count/8;
  1277.     new->a.nod.left=a;            /* lesser in left  */
  1278.     new->a.nod.right=b;
  1279.     queue.root[1]=(byte*) new;
  1280.     queue_replaced(&queue);
  1281.   }
  1282.   huff_tree->root=(HUFF_ELEMENT*) queue.root[1];
  1283.   huff_tree->bytes_packed=bytes_packed+(bits_packed+7)/8;
  1284.   return 0;
  1285. }
  1286.  
  1287. static int compare_tree(register const uchar *s, register const uchar *t)
  1288. {
  1289.   uint length;
  1290.   for (length=global_count->field_length; length-- ;)
  1291.     if (*s++ != *t++)
  1292.       return (int) s[-1] - (int) t[-1];
  1293.   return 0;
  1294. }
  1295.  
  1296.     /* Used by make_huff_tree to save intervall-counts in queue */
  1297.  
  1298. static int save_counts_in_queue(byte *key, element_count count,
  1299.                 HUFF_TREE *tree)
  1300. {
  1301.   HUFF_ELEMENT *new;
  1302.  
  1303.   new=tree->element_buffer+(tree->elements++);
  1304.   new->count=count;
  1305.   new->a.leaf.null=0;
  1306.   new->a.leaf.element_nr= (uint) (key- tree->counts->tree_buff) /
  1307.     tree->counts->field_length;
  1308.   queue.root[tree->elements]=(byte*) new;
  1309.   return 0;
  1310. }
  1311.  
  1312.  
  1313.     /* Calculate length of file if given counts should be used */
  1314.     /* Its actually a faster version of make_huff_tree */
  1315.  
  1316. static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,
  1317.                    uint add_tree_lenght)
  1318. {
  1319.   uint i,found,bits_packed,first,last;
  1320.   my_off_t bytes_packed;
  1321.   HUFF_ELEMENT element_buffer[256];
  1322.   DBUG_ENTER("calc_packed_length");
  1323.  
  1324.   first=last=0;
  1325.   for (i=found=0 ; i < 256 ; i++)
  1326.   {
  1327.     if (huff_counts->counts[i])
  1328.     {
  1329.       if (! found++)
  1330.     first=i;
  1331.       last=i;
  1332.       queue.root[found]=(byte*) &huff_counts->counts[i];
  1333.     }
  1334.   }
  1335.   if (!found)
  1336.     DBUG_RETURN(0);            /* Empty tree */
  1337.   if (found < 2)
  1338.     queue.root[++found]=(byte*) &huff_counts->counts[last ? 0 : 1];
  1339.  
  1340.   queue.elements=found;
  1341.  
  1342.   bytes_packed=0; bits_packed=0;
  1343.   if (add_tree_lenght)
  1344.     bytes_packed=(8+9+5+5+(max_bit(last-first)+1)*found+
  1345.           (max_bit(found-1)+1+1)*(found-2) +7)/8;
  1346.   for (i=(found+1)/2 ; i > 0 ; i--)
  1347.     _downheap(&queue,i);
  1348.   for (i=0 ; i < found-1 ; i++)
  1349.   {
  1350.     HUFF_ELEMENT *a,*b,*new;
  1351.     a=(HUFF_ELEMENT*) queue_remove(&queue,0);
  1352.     b=(HUFF_ELEMENT*) queue.root[1];
  1353.     new=element_buffer+i;
  1354.     new->count=a->count+b->count;
  1355.     bits_packed+=(uint) (new->count & 7);
  1356.     bytes_packed+=new->count/8;
  1357.     queue.root[1]=(byte*) new;
  1358.     queue_replaced(&queue);
  1359.   }
  1360.   DBUG_RETURN(bytes_packed+(bits_packed+7)/8);
  1361. }
  1362.  
  1363.  
  1364.     /* Remove trees that don't give any compression */
  1365.  
  1366. static uint join_same_trees(HUFF_COUNTS *huff_counts, uint trees)
  1367. {
  1368.   uint k,tree_number;
  1369.   HUFF_COUNTS count,*i,*j,*last_count;
  1370.  
  1371.   last_count=huff_counts+trees;
  1372.   for (tree_number=0, i=huff_counts ; i < last_count ; i++)
  1373.   {
  1374.     if (!i->tree->tree_number)
  1375.     {
  1376.       i->tree->tree_number= ++tree_number;
  1377.       if (i->tree_buff)
  1378.     continue;            /* Don't join intervall */
  1379.       for (j=i+1 ; j < last_count ; j++)
  1380.       {
  1381.     if (! j->tree->tree_number && ! j->tree_buff)
  1382.     {
  1383.       for (k=0 ; k < 256 ; k++)
  1384.         count.counts[k]=i->counts[k]+j->counts[k];
  1385.       if (calc_packed_length(&count,1) <=
  1386.           i->tree->bytes_packed + j->tree->bytes_packed+
  1387.           i->tree->tree_pack_length+j->tree->tree_pack_length+
  1388.           ALLOWED_JOIN_DIFF)
  1389.       {
  1390.         memcpy_fixed((byte*) i->counts,(byte*) count.counts,
  1391.              sizeof(count.counts[0])*256);
  1392.         my_free((gptr) j->tree->element_buffer,MYF(0));
  1393.         j->tree->element_buffer=0;
  1394.         j->tree=i->tree;
  1395.         bmove((byte*) i->counts,(byte*) count.counts,
  1396.           sizeof(count.counts[0])*256);
  1397.         if (make_huff_tree(i->tree,i))
  1398.           return (uint) -1;
  1399.       }
  1400.     }
  1401.       }
  1402.     }
  1403.   }
  1404.   if (verbose)
  1405.     printf("Original trees:  %d  After join: %d\n",trees,tree_number);
  1406.   return tree_number;            /* Return trees left */
  1407. }
  1408.  
  1409.  
  1410.     /* Fill in huff_tree decode tables */
  1411.  
  1412. static int make_huff_decode_table(HUFF_TREE *huff_tree, uint trees)
  1413. {
  1414.   uint elements;
  1415.   for ( ; trees-- ; huff_tree++)
  1416.   {
  1417.     if (huff_tree->tree_number > 0)
  1418.     {
  1419.       elements=huff_tree->counts->tree_buff ? huff_tree->elements : 256;
  1420.       if (!(huff_tree->code =
  1421.         (ulong*) my_malloc(elements*
  1422.                    (sizeof(ulong)+sizeof(uchar)),
  1423.                    MYF(MY_WME | MY_ZEROFILL))))
  1424.     return 1;
  1425.       huff_tree->code_len=(uchar*) (huff_tree->code+elements);
  1426.       make_traverse_code_tree(huff_tree,huff_tree->root,32,0);
  1427.     }
  1428.   }
  1429.   return 0;
  1430. }
  1431.  
  1432.  
  1433. static void make_traverse_code_tree(HUFF_TREE *huff_tree,
  1434.                     HUFF_ELEMENT *element,
  1435.                     uint size, ulong code)
  1436. {
  1437.   uint chr;
  1438.   if (!element->a.leaf.null)
  1439.   {
  1440.     chr=element->a.leaf.element_nr;
  1441.     huff_tree->code_len[chr]=(uchar) (32-size);
  1442.     huff_tree->code[chr]=    (code >> size);
  1443.     if (huff_tree->height < 32-size)
  1444.       huff_tree->height= 32-size;
  1445.   }
  1446.   else
  1447.   {
  1448.     size--;
  1449.     make_traverse_code_tree(huff_tree,element->a.nod.left,size,code);
  1450.     make_traverse_code_tree(huff_tree,element->a.nod.right,size,
  1451.                 code+((ulong) 1L << size));
  1452.   }
  1453.   return;
  1454. }
  1455.  
  1456.  
  1457.     /* Write header to new packed data file */
  1458.  
  1459. static int write_header(MRG_INFO *mrg,uint head_length,uint trees,
  1460.             my_off_t tot_elements,my_off_t filelength)
  1461. {
  1462.   byte *buff=file_buffer.pos;
  1463.  
  1464.   bzero(buff,HEAD_LENGTH);
  1465.   memcpy_fixed(buff,myisam_pack_file_magic,4);
  1466.   int4store(buff+4,head_length);
  1467.   int4store(buff+8, mrg->min_pack_length);
  1468.   int4store(buff+12,mrg->max_pack_length);
  1469.   int4store(buff+16,tot_elements);
  1470.   int4store(buff+20,intervall_length);
  1471.   int2store(buff+24,trees);
  1472.   buff[26]=(char) mrg->ref_length;
  1473.     /* Save record pointer length */
  1474.   buff[27]= (uchar) mi_get_pointer_length((ulonglong) filelength,2);
  1475.   if (test_only)
  1476.     return 0;
  1477.   VOID(my_seek(file_buffer.file,0L,MY_SEEK_SET,MYF(0)));
  1478.   return my_write(file_buffer.file,file_buffer.pos,HEAD_LENGTH,
  1479.           MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
  1480. }
  1481.  
  1482.     /* Write fieldinfo to new packed file */
  1483.  
  1484. static void write_field_info(HUFF_COUNTS *counts, uint fields, uint trees)
  1485. {
  1486.   reg1 uint i;
  1487.   uint huff_tree_bits;
  1488.   huff_tree_bits=max_bit(trees ? trees-1 : 0);
  1489.  
  1490.   for (i=0 ; i++ < fields ; counts++)
  1491.   {
  1492.     write_bits((ulong) (int) counts->field_type,5);
  1493.     write_bits(counts->pack_type,6);
  1494.     if (counts->pack_type & PACK_TYPE_ZERO_FILL)
  1495.       write_bits(counts->max_zero_fill,5);
  1496.     else
  1497.       write_bits(counts->length_bits,5);
  1498.     write_bits((ulong) counts->tree->tree_number-1,huff_tree_bits);
  1499.   }
  1500.   flush_bits();
  1501.   return;
  1502. }
  1503.  
  1504.     /* Write all huff_trees to new datafile. Return tot count of
  1505.        elements in all trees
  1506.        Returns 0 on error */
  1507.  
  1508. static my_off_t write_huff_tree(HUFF_TREE *huff_tree, uint trees)
  1509. {
  1510.   uint i,int_length;
  1511.   uint *packed_tree,*offset,length;
  1512.   my_off_t elements;
  1513.  
  1514.   for (i=length=0 ; i < trees ; i++)
  1515.     if (huff_tree[i].tree_number > 0 && huff_tree[i].elements > length)
  1516.       length=huff_tree[i].elements;
  1517.   if (!(packed_tree=(uint*) my_alloca(sizeof(uint)*length*2)))
  1518.   {
  1519.     my_error(EE_OUTOFMEMORY,MYF(ME_BELL),sizeof(uint)*length*2);
  1520.     return 0;
  1521.   }
  1522.  
  1523.   intervall_length=0;
  1524.   for (elements=0; trees-- ; huff_tree++)
  1525.   {
  1526.     if (huff_tree->tree_number == 0)
  1527.       continue;                /* Deleted tree */
  1528.     elements+=huff_tree->elements;
  1529.     huff_tree->max_offset=2;
  1530.     if (huff_tree->elements <= 1)
  1531.       offset=packed_tree;
  1532.     else
  1533.       offset=make_offset_code_tree(huff_tree,huff_tree->root,packed_tree);
  1534.     huff_tree->offset_bits=max_bit(huff_tree->max_offset);
  1535.     if (huff_tree->max_offset >= IS_OFFSET)
  1536.     {                /* This should be impossible */
  1537.       VOID(fprintf(stderr,"Tree offset got too big: %d, aborted\n",
  1538.           huff_tree->max_offset));
  1539.       my_afree((gptr) packed_tree);
  1540.       return 0;
  1541.     }
  1542.  
  1543. #ifdef EXTRA_DBUG
  1544.     printf("pos: %d  elements: %d  tree-elements: %d  char_bits: %d\n",
  1545.        (uint) (file_buffer.pos-file_buffer.buffer),
  1546.        huff_tree->elements,  (offset-packed_tree),huff_tree->char_bits);
  1547. #endif
  1548.     if (!huff_tree->counts->tree_buff)
  1549.     {
  1550.       write_bits(0,1);
  1551.       write_bits(huff_tree->min_chr,8);
  1552.       write_bits(huff_tree->elements,9);
  1553.       write_bits(huff_tree->char_bits,5);
  1554.       write_bits(huff_tree->offset_bits,5);
  1555.       int_length=0;
  1556.     }
  1557.     else
  1558.     {
  1559.       int_length=(uint) (huff_tree->counts->tree_pos -
  1560.              huff_tree->counts->tree_buff);
  1561.       write_bits(1,1);
  1562.       write_bits(huff_tree->elements,15);
  1563.       write_bits(int_length,16);
  1564.       write_bits(huff_tree->char_bits,5);
  1565.       write_bits(huff_tree->offset_bits,5);
  1566.       intervall_length+=int_length;
  1567.     }
  1568.     length=(uint) (offset-packed_tree);
  1569.     if (length != huff_tree->elements*2-2)
  1570.       printf("error: Huff-tree-length: %d != calc_length: %d\n",
  1571.          length,huff_tree->elements*2-2);
  1572.  
  1573.     for (i=0 ; i < length ; i++)
  1574.     {
  1575.       if (packed_tree[i] & IS_OFFSET)
  1576.     write_bits(packed_tree[i] - IS_OFFSET+ (1 << huff_tree->offset_bits),
  1577.            huff_tree->offset_bits+1);
  1578.       else
  1579.     write_bits(packed_tree[i]-huff_tree->min_chr,huff_tree->char_bits+1);
  1580.     }
  1581.     flush_bits();
  1582.     if (huff_tree->counts->tree_buff)
  1583.     {
  1584.       for (i=0 ; i < int_length ; i++)
  1585.     write_bits((uint) (uchar) huff_tree->counts->tree_buff[i],8);
  1586.     }
  1587.     flush_bits();
  1588.   }
  1589.   my_afree((gptr) packed_tree);
  1590.   return elements;
  1591. }
  1592.  
  1593.  
  1594. static uint *make_offset_code_tree(HUFF_TREE *huff_tree, HUFF_ELEMENT *element,
  1595.                    uint *offset)
  1596. {
  1597.   uint *prev_offset;
  1598.  
  1599.   prev_offset= offset;
  1600.   if (!element->a.nod.left->a.leaf.null)
  1601.   {
  1602.     offset[0] =(uint) element->a.nod.left->a.leaf.element_nr;
  1603.     offset+=2;
  1604.   }
  1605.   else
  1606.   {
  1607.     prev_offset[0]= IS_OFFSET+2;
  1608.     offset=make_offset_code_tree(huff_tree,element->a.nod.left,offset+2);
  1609.   }
  1610.   if (!element->a.nod.right->a.leaf.null)
  1611.   {
  1612.     prev_offset[1]=element->a.nod.right->a.leaf.element_nr;
  1613.     return offset;
  1614.   }
  1615.   else
  1616.   {
  1617.     uint temp=(uint) (offset-prev_offset-1);
  1618.     prev_offset[1]= IS_OFFSET+ temp;
  1619.     if (huff_tree->max_offset < temp)
  1620.       huff_tree->max_offset = temp;
  1621.     return make_offset_code_tree(huff_tree,element->a.nod.right,offset);
  1622.   }
  1623. }
  1624.  
  1625.     /* Get number of bits neaded to represent value */
  1626.  
  1627. static uint max_bit(register uint value)
  1628. {
  1629.   reg2 uint power=1;
  1630.  
  1631.   while ((value>>=1))
  1632.     power++;
  1633.   return (power);
  1634. }
  1635.  
  1636.  
  1637. static int compress_isam_file(MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
  1638. {
  1639.   int error;
  1640.   uint i,max_calc_length,pack_ref_length,min_record_length,max_record_length,
  1641.     intervall,field_length,max_pack_length,pack_blob_length;
  1642.   my_off_t record_count;
  1643.   ulong length,pack_length;
  1644.   byte *record,*pos,*end_pos,*record_pos,*start_pos;
  1645.   HUFF_COUNTS *count,*end_count;
  1646.   HUFF_TREE *tree;
  1647.   MI_INFO *isam_file=mrg->file[0];
  1648.   DBUG_ENTER("compress_isam_file");
  1649.  
  1650.   if (!(record=(byte*) my_alloca(isam_file->s->base.reclength)))
  1651.     return -1;
  1652.   end_count=huff_counts+isam_file->s->base.fields;
  1653.   min_record_length= (uint) ~0;
  1654.   max_record_length=0;
  1655.  
  1656.   for (i=max_calc_length=0 ; i < isam_file->s->base.fields ; i++)
  1657.   {
  1658.     if (!(huff_counts[i].pack_type & PACK_TYPE_ZERO_FILL))
  1659.       huff_counts[i].max_zero_fill=0;
  1660.     if (huff_counts[i].field_type == FIELD_CONSTANT ||
  1661.     huff_counts[i].field_type == FIELD_ZERO ||
  1662.     huff_counts[i].field_type == FIELD_CHECK)
  1663.       continue;
  1664.     if (huff_counts[i].field_type == FIELD_INTERVALL)
  1665.       max_calc_length+=huff_counts[i].tree->height;
  1666.     else if (huff_counts[i].field_type == FIELD_BLOB ||
  1667.          huff_counts[i].field_type == FIELD_VARCHAR)
  1668.       max_calc_length=huff_counts[i].tree->height*huff_counts[i].max_length + huff_counts[i].length_bits +1;
  1669.     else
  1670.       max_calc_length+=
  1671.     (huff_counts[i].field_length - huff_counts[i].max_zero_fill)*
  1672.       huff_counts[i].tree->height+huff_counts[i].length_bits;
  1673.   }
  1674.   max_calc_length/=8;
  1675.   if (max_calc_length < 254)
  1676.     pack_ref_length=1;
  1677.   else if (max_calc_length <= 65535)
  1678.     pack_ref_length=3;
  1679.   else
  1680.     pack_ref_length=4;
  1681.   record_count=0;
  1682.   pack_blob_length=0;
  1683.   if (isam_file->s->base.blobs)
  1684.   {
  1685.     if (mrg->max_blob_length < 254)
  1686.       pack_blob_length=1;
  1687.     else if (mrg->max_blob_length <= 65535)
  1688.       pack_blob_length=3;
  1689.     else
  1690.       pack_blob_length=4;
  1691.   }
  1692.   max_pack_length=pack_ref_length+pack_blob_length;
  1693.  
  1694.   mrg_reset(mrg);
  1695.   while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
  1696.   {
  1697.     ulong tot_blob_length=0;
  1698.     if (! error)
  1699.     {
  1700.       if (flush_buffer(max_calc_length+max_pack_length))
  1701.     break;
  1702.       record_pos=file_buffer.pos;
  1703.       file_buffer.pos+=max_pack_length;
  1704.       for (start_pos=record, count= huff_counts; count < end_count ; count++)
  1705.       {
  1706.     end_pos=start_pos+(field_length=count->field_length);
  1707.     tree=count->tree;
  1708.  
  1709.     if (count->pack_type & PACK_TYPE_SPACE_FIELDS)
  1710.     {
  1711.       for (pos=start_pos ; *pos == ' ' && pos < end_pos; pos++) ;
  1712.       if (pos == end_pos)
  1713.       {
  1714.         write_bits(1,1);
  1715.         start_pos=end_pos;
  1716.         continue;
  1717.       }
  1718.       write_bits(0,1);
  1719.     }
  1720.     end_pos-=count->max_zero_fill;
  1721.     field_length-=count->max_zero_fill;
  1722.  
  1723.     switch(count->field_type) {
  1724.     case FIELD_SKIPP_ZERO:
  1725.       if (!memcmp((byte*) start_pos,zero_string,field_length))
  1726.       {
  1727.         write_bits(1,1);
  1728.         start_pos=end_pos;
  1729.         break;
  1730.       }
  1731.       write_bits(0,1);
  1732.       /* Fall through */
  1733.     case FIELD_NORMAL:
  1734.       for ( ; start_pos < end_pos ; start_pos++)
  1735.         write_bits(tree->code[(uchar) *start_pos],
  1736.                (uint) tree->code_len[(uchar) *start_pos]);
  1737.       break;
  1738.     case FIELD_SKIPP_ENDSPACE:
  1739.       for (pos=end_pos ; pos > start_pos && pos[-1] == ' ' ; pos--) ;
  1740.       length=(uint) (end_pos-pos);
  1741.       if (count->pack_type & PACK_TYPE_SELECTED)
  1742.       {
  1743.         if (length > count->min_space)
  1744.         {
  1745.           write_bits(1,1);
  1746.           write_bits(length,count->length_bits);
  1747.         }
  1748.         else
  1749.         {
  1750.           write_bits(0,1);
  1751.           pos=end_pos;
  1752.         }
  1753.       }
  1754.       else
  1755.         write_bits(length,count->length_bits);
  1756.       for ( ; start_pos < pos ; start_pos++)
  1757.         write_bits(tree->code[(uchar) *start_pos],
  1758.                (uint) tree->code_len[(uchar) *start_pos]);
  1759.       start_pos=end_pos;
  1760.       break;
  1761.     case FIELD_SKIPP_PRESPACE:
  1762.       for (pos=start_pos ; pos < end_pos && pos[0] == ' ' ; pos++) ;
  1763.       length=(uint) (pos-start_pos);
  1764.       if (count->pack_type & PACK_TYPE_SELECTED)
  1765.       {
  1766.         if (length > count->min_space)
  1767.         {
  1768.           write_bits(1,1);
  1769.           write_bits(length,count->length_bits);
  1770.         }
  1771.         else
  1772.         {
  1773.           pos=start_pos;
  1774.           write_bits(0,1);
  1775.         }
  1776.       }
  1777.       else
  1778.         write_bits(length,count->length_bits);
  1779.       for (start_pos=pos ; start_pos < end_pos ; start_pos++)
  1780.         write_bits(tree->code[(uchar) *start_pos],
  1781.                (uint) tree->code_len[(uchar) *start_pos]);
  1782.       break;
  1783.     case FIELD_CONSTANT:
  1784.     case FIELD_ZERO:
  1785.     case FIELD_CHECK:
  1786.       start_pos=end_pos;
  1787.       break;
  1788.     case FIELD_INTERVALL:
  1789.       global_count=count;
  1790.       pos=(byte*) tree_search(&count->int_tree,start_pos);
  1791.       intervall=(uint) (pos - count->tree_buff)/field_length;
  1792.       write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
  1793.       start_pos=end_pos;
  1794.       break;
  1795.     case FIELD_BLOB:
  1796.     {
  1797.       ulong blob_length=_mi_calc_blob_length(field_length-
  1798.                          mi_portable_sizeof_char_ptr,
  1799.                          start_pos);
  1800.       if (!blob_length)
  1801.       {
  1802.         write_bits(1,1);            /* Empty blob */
  1803.       }
  1804.       else
  1805.       {
  1806.         byte *blob,*blob_end;
  1807.         write_bits(0,1);
  1808.         write_bits(blob_length,count->length_bits);
  1809.         memcpy_fixed(&blob,end_pos-mi_portable_sizeof_char_ptr,
  1810.              sizeof(char*));
  1811.         blob_end=blob+blob_length;
  1812.         for ( ; blob < blob_end ; blob++)
  1813.           write_bits(tree->code[(uchar) *blob],
  1814.              (uint) tree->code_len[(uchar) *blob]);
  1815.         tot_blob_length+=blob_length;
  1816.       }
  1817.       start_pos= end_pos;
  1818.       break;
  1819.     }
  1820.     case FIELD_VARCHAR:
  1821.     {
  1822.       ulong col_length= uint2korr(start_pos);
  1823.       if (!col_length)
  1824.       {
  1825.         write_bits(1,1);            /* Empty varchar */
  1826.       }
  1827.       else
  1828.       {
  1829.         byte *end=start_pos+2+col_length;
  1830.         write_bits(0,1);
  1831.         write_bits(col_length,count->length_bits);
  1832.         for (start_pos+=2 ; start_pos < end ; start_pos++)
  1833.           write_bits(tree->code[(uchar) *start_pos],
  1834.              (uint) tree->code_len[(uchar) *start_pos]);
  1835.       }
  1836.       start_pos= end_pos;
  1837.       break;
  1838.     }
  1839.     case FIELD_LAST:
  1840.       abort();                /* Impossible */
  1841.     }
  1842.     start_pos+=count->max_zero_fill;
  1843.       }
  1844.       flush_bits();
  1845.       length=(ulong) (file_buffer.pos-record_pos)-max_pack_length;
  1846.       pack_length=save_pack_length(record_pos,length);
  1847.       if (pack_blob_length)
  1848.     pack_length+=save_pack_length(record_pos+pack_length,tot_blob_length);
  1849.  
  1850.       /* Correct file buffer if the header was smaller */
  1851.       if (pack_length != max_pack_length)
  1852.       {
  1853.     bmove(record_pos+pack_length,record_pos+max_pack_length,length);
  1854.     file_buffer.pos-= (max_pack_length-pack_length);
  1855.       }
  1856.       if (length < (ulong) min_record_length)
  1857.     min_record_length=(uint) length;
  1858.       if (length > (ulong) max_record_length)
  1859.     max_record_length=(uint) length;
  1860.       if (write_loop && ++record_count % WRITE_COUNT == 0)
  1861.       {
  1862.     printf("%lu\r",(ulong) record_count); VOID(fflush(stdout));
  1863.       }
  1864.     }
  1865.     else if (error != HA_ERR_RECORD_DELETED)
  1866.       break;
  1867.   }
  1868.   if (error == HA_ERR_END_OF_FILE)
  1869.     error=0;
  1870.   else
  1871.   {
  1872.     fprintf(stderr,"%s: Got error %d reading records\n",my_progname,error);
  1873.   }
  1874.  
  1875.   my_afree((gptr) record);
  1876.   mrg->ref_length=max_pack_length;
  1877.   mrg->min_pack_length=max_record_length ? min_record_length : 0;
  1878.   mrg->max_pack_length=max_record_length;
  1879.   DBUG_RETURN(error || error_on_write || flush_buffer(~(ulong) 0));
  1880. }
  1881.  
  1882.  
  1883. static char *make_new_name(char *new_name, char *old_name)
  1884. {
  1885.   return fn_format(new_name,old_name,"",DATA_TMP_EXT,2+4);
  1886. }
  1887.  
  1888. static char *make_old_name(char *new_name, char *old_name)
  1889. {
  1890.   return fn_format(new_name,old_name,"",OLD_EXT,2+4);
  1891. }
  1892.  
  1893.     /* rutines for bit writing buffer */
  1894.  
  1895. static void init_file_buffer(File file, pbool read_buffer)
  1896. {
  1897.   file_buffer.file=file;
  1898.   file_buffer.buffer=my_malloc(ALIGN_SIZE(RECORD_CACHE_SIZE),MYF(MY_WME));
  1899.   file_buffer.end=file_buffer.buffer+ALIGN_SIZE(RECORD_CACHE_SIZE)-8;
  1900.   file_buffer.pos_in_file=0;
  1901.   error_on_write=0;
  1902.   if (read_buffer)
  1903.   {
  1904.  
  1905.     file_buffer.pos=file_buffer.end;
  1906.     file_buffer.bits=0;
  1907.   }
  1908.   else
  1909.   {
  1910.     file_buffer.pos=file_buffer.buffer;
  1911.     file_buffer.bits=BITS_SAVED;
  1912.   }
  1913.   file_buffer.byte=0;
  1914. }
  1915.  
  1916.  
  1917. static int flush_buffer(ulong neaded_length)
  1918. {
  1919.   ulong length;
  1920.   if ((ulong) (file_buffer.end - file_buffer.pos) > neaded_length)
  1921.     return 0;
  1922.   length=(ulong) (file_buffer.pos-file_buffer.buffer);
  1923.   file_buffer.pos=file_buffer.buffer;
  1924.   file_buffer.pos_in_file+=length;
  1925.   if (test_only)
  1926.     return 0;
  1927.   if (error_on_write|| my_write(file_buffer.file,file_buffer.buffer,
  1928.                 length,
  1929.                 MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
  1930.   {
  1931.     error_on_write=1;
  1932.     return 1;
  1933.   }
  1934.  
  1935.   if (neaded_length != ~(ulong) 0 &&
  1936.       (ulong) (file_buffer.end-file_buffer.buffer) < neaded_length)
  1937.   {
  1938.     char *tmp;
  1939.     neaded_length+=256;                /* some margin */
  1940.     tmp=my_realloc(file_buffer.buffer, neaded_length,MYF(MY_WME));
  1941.     if (!tmp)
  1942.       return 1;
  1943.     file_buffer.pos= tmp + (ulong) (file_buffer.pos - file_buffer.buffer);
  1944.     file_buffer.buffer=tmp;
  1945.     file_buffer.end=tmp+neaded_length-8;
  1946.   }
  1947.   return 0;
  1948. }
  1949.  
  1950.  
  1951. static void end_file_buffer(void)
  1952. {
  1953.   my_free((gptr) file_buffer.buffer,MYF(0));
  1954. }
  1955.  
  1956.     /* output `bits` low bits of `value' */
  1957.  
  1958. static void write_bits (register ulong value, register uint bits)
  1959. {
  1960.   if ((file_buffer.bits-=(int) bits) >= 0)
  1961.   {
  1962.     file_buffer.byte|=value << file_buffer.bits;
  1963.   }
  1964.   else
  1965.   {
  1966.     reg3 uint byte_buff;
  1967.     bits= (uint) -file_buffer.bits;
  1968.     byte_buff=file_buffer.byte | (uint) (value >> bits);
  1969. #if BITS_SAVED == 32
  1970.     *file_buffer.pos++= (byte) (byte_buff >> 24) ;
  1971.     *file_buffer.pos++= (byte) (byte_buff >> 16) ;
  1972. #endif
  1973.     *file_buffer.pos++= (byte) (byte_buff >> 8) ;
  1974.     *file_buffer.pos++= (byte) byte_buff;
  1975.  
  1976.     value&=(1 << bits)-1;
  1977. #if BITS_SAVED == 16
  1978.     if (bits >= sizeof(uint))
  1979.     {
  1980.       bits-=8;
  1981.       *file_buffer.pos++= (uchar) (value >> bits);
  1982.       value&= (1 << bits)-1;
  1983.       if (bits >= sizeof(uint))
  1984.       {
  1985.     bits-=8;
  1986.     *file_buffer.pos++= (uchar) (value >> bits);
  1987.     value&= (1 << bits)-1;
  1988.       }
  1989.     }
  1990. #endif
  1991.     if (file_buffer.pos >= file_buffer.end)
  1992.       VOID(flush_buffer((uint) ~0));
  1993.     file_buffer.bits=(int) (BITS_SAVED - bits);
  1994.     file_buffer.byte=(uint) (value << (BITS_SAVED - bits));
  1995.   }
  1996.   return;
  1997. }
  1998.  
  1999.     /* Flush bits in bit_buffer to buffer */
  2000.  
  2001. static void flush_bits (void)
  2002. {
  2003.   uint bits,byte_buff;
  2004.  
  2005.   bits=(file_buffer.bits) & ~7;
  2006.   byte_buff = file_buffer.byte >> bits;
  2007.   bits=BITS_SAVED - bits;
  2008.   while (bits > 0)
  2009.   {
  2010.     bits-=8;
  2011.     *file_buffer.pos++= (byte) (uchar) (byte_buff >> bits) ;
  2012.   }
  2013.   file_buffer.bits=BITS_SAVED;
  2014.   file_buffer.byte=0;
  2015.   return;
  2016. }
  2017.  
  2018.  
  2019. /****************************************************************************
  2020. ** functions to handle the joined files
  2021. ****************************************************************************/
  2022.  
  2023. static int save_state(MI_INFO *isam_file,MRG_INFO *mrg,my_off_t new_length,
  2024.               ha_checksum crc)
  2025. {
  2026.   MYISAM_SHARE *share=isam_file->s;
  2027.   uint options=mi_uint2korr(share->state.header.options);
  2028.   uint key;
  2029.   DBUG_ENTER("save_state");
  2030.  
  2031.   options|= HA_OPTION_COMPRESS_RECORD | HA_OPTION_READ_ONLY_DATA;
  2032.   mi_int2store(share->state.header.options,options);
  2033.  
  2034.   share->state.state.data_file_length=new_length;
  2035.   share->state.state.del=0;
  2036.   share->state.state.empty=0;
  2037.   share->state.dellink= HA_OFFSET_ERROR;
  2038.   share->state.split=(ha_rows) mrg->records;
  2039.   share->state.version=(ulong) time((time_t*) 0);
  2040.   share->state.key_map=0;
  2041.   share->state.state.key_file_length=share->base.keystart;
  2042.   for (key=0 ; key < share->base.keys ; key++)
  2043.     share->state.key_root[key]= HA_OFFSET_ERROR;
  2044.   for (key=0 ; key < share->state.header.max_block_size ; key++)
  2045.     share->state.key_del[key]= HA_OFFSET_ERROR;
  2046.   share->state.checksum=crc;        /* Save crc here */
  2047.   share->changed=1;            /* Force write of header */
  2048.   share->state.open_count=0;
  2049.   share->global_changed=0;
  2050.   VOID(my_chsize(share->kfile,share->state.state.key_file_length,
  2051.          MYF(0)));
  2052.   if (share->base.keys)
  2053.     isamchk_neaded=1;
  2054.   DBUG_RETURN(mi_state_info_write(share->kfile,&share->state,1+2));
  2055. }
  2056.  
  2057.  
  2058. static int save_state_mrg(File file,MRG_INFO *mrg,my_off_t new_length,
  2059.               ha_checksum crc)
  2060. {
  2061.   MI_STATE_INFO state;
  2062.   MI_INFO *isam_file=mrg->file[0];
  2063.   uint options;
  2064.   DBUG_ENTER("save_state_mrg");
  2065.  
  2066.   state= isam_file->s->state;
  2067.   options= (mi_uint2korr(state.header.options) | HA_OPTION_COMPRESS_RECORD |
  2068.         HA_OPTION_READ_ONLY_DATA);
  2069.   mi_int2store(state.header.options,options);
  2070.   state.state.data_file_length=new_length;
  2071.   state.state.del=0;
  2072.   state.state.empty=0;
  2073.   state.state.records=state.split=(ha_rows) mrg->records;
  2074.   state.state.key_file_length=isam_file->s->base.keystart;
  2075.   state.dellink= HA_OFFSET_ERROR;
  2076.   state.version=(ulong) time((time_t*) 0);
  2077.   state.key_map=0;
  2078.   state.checksum=crc;
  2079.   if (isam_file->s->base.keys)
  2080.     isamchk_neaded=1;
  2081.   state.changed=STATE_CHANGED | STATE_NOT_ANALYZED; /* Force check of table */
  2082.   DBUG_RETURN (mi_state_info_write(file,&state,1+2));
  2083. }
  2084.  
  2085.  
  2086. /* reset for mrg_rrnd */
  2087.  
  2088. static void mrg_reset(MRG_INFO *mrg)
  2089. {
  2090.   if (mrg->current)
  2091.   {
  2092.     mi_extra(*mrg->current,HA_EXTRA_NO_CACHE);
  2093.     mrg->current=0;
  2094.   }
  2095. }
  2096.  
  2097. static int mrg_rrnd(MRG_INFO *info,byte *buf)
  2098. {
  2099.   int error;
  2100.   MI_INFO *isam_info;
  2101.   my_off_t filepos;
  2102.  
  2103.   if (!info->current)
  2104.   {
  2105.     isam_info= *(info->current=info->file);
  2106.     info->end=info->current+info->count;
  2107.     mi_extra(isam_info,HA_EXTRA_RESET);
  2108.     mi_extra(isam_info,HA_EXTRA_CACHE);
  2109.     filepos=isam_info->s->pack.header_length;
  2110.   }
  2111.   else
  2112.   {
  2113.     isam_info= *info->current;
  2114.     filepos= isam_info->nextpos;
  2115.   }
  2116.  
  2117.   for (;;)
  2118.   {
  2119.     isam_info->update&= HA_STATE_CHANGED;
  2120.     if (!(error=(*isam_info->s->read_rnd)(isam_info,(byte*) buf,
  2121.                       filepos, 1)) ||
  2122.     error != HA_ERR_END_OF_FILE)
  2123.       return (error);
  2124.     mi_extra(isam_info,HA_EXTRA_NO_CACHE);
  2125.     if (info->current+1 == info->end)
  2126.       return(HA_ERR_END_OF_FILE);
  2127.     info->current++;
  2128.     isam_info= *info->current;
  2129.     filepos=isam_info->s->pack.header_length;
  2130.     mi_extra(isam_info,HA_EXTRA_RESET);
  2131.     mi_extra(isam_info,HA_EXTRA_CACHE);
  2132.   }
  2133. }
  2134.  
  2135.  
  2136. static int mrg_close(MRG_INFO *mrg)
  2137. {
  2138.   uint i;
  2139.   int error=0;
  2140.   for (i=0 ; i < mrg->count ; i++)
  2141.     error|=mi_close(mrg->file[i]);
  2142.   if (mrg->free_file)
  2143.     my_free((gptr) mrg->file,MYF(0));
  2144.   return error;
  2145. }
  2146.