开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
pack_isam.c
资源名称：mysql-3.23.35.tar.gz　[点击查看]
上传用户：tsgydb
上传日期：2007-04-14
资源大小：10674k
文件大小：56k
源码类别：

MySQL数据库

开发平台：

Visual C++

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