1
/* Copyright (C) 2000-2006 MySQL AB
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; version 2 of the License.
7
This program is distributed in the hope that it will be useful,
8
but WITHOUT ANY WARRANTY; without even the implied warranty of
9
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10
GNU General Public License for more details.
12
You should have received a copy of the GNU General Public License
13
along with this program; if not, write to the Free Software
14
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
16
/* Pack MyISAM file */
19
#define USE_MY_FUNC /* We need at least my_malloc */
22
#include "myisamdef.h"
25
#include "mysys_err.h"
26
#ifndef __GNU_LIBRARY__
27
#define __GNU_LIBRARY__ /* Skip warnings in getopt.h */
29
#include <my_getopt.h>
32
#if SIZEOF_LONG_LONG > 4
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
struct st_file_buffer {
48
uchar *buffer,*pos,*end;
55
struct st_huff_element;
57
typedef struct st_huff_counts {
58
uint field_length,max_zero_fill;
60
uint max_end_space,max_pre_space,length_bits,min_space;
62
enum en_fieldtype field_type;
63
struct st_huff_tree *tree; /* Tree for field */
65
my_off_t end_space[8];
66
my_off_t pre_space[8];
67
my_off_t tot_end_space,tot_pre_space,zero_fields,empty_fields,bytes_packed;
68
TREE int_tree; /* Tree for detecting distinct column values. */
69
uchar *tree_buff; /* Column values, 'field_length' each. */
70
uchar *tree_pos; /* Points to end of column values in 'tree_buff'. */
73
typedef struct st_huff_element HUFF_ELEMENT;
76
WARNING: It is crucial for the optimizations in calc_packed_length()
77
that 'count' is the first element of 'HUFF_ELEMENT'.
79
struct st_huff_element {
83
HUFF_ELEMENT *left,*right;
87
uint element_nr; /* Number of element */
93
typedef struct st_huff_tree {
94
HUFF_ELEMENT *root,*element_buffer;
98
my_off_t bytes_packed;
99
uint tree_pack_length;
100
uint min_chr,max_chr,char_bits,offset_bits,max_offset,height;
106
typedef struct st_isam_mrg {
107
MI_INFO **file,**current,**end;
110
uint min_pack_length; /* Theese is used by packed data */
111
uint max_pack_length;
113
uint max_blob_length;
115
/* true if at least one source file has at least one disabled index */
116
my_bool src_file_has_indexes_disabled;
120
extern int main(int argc,char * *argv);
121
static void get_options(int *argc,char ***argv);
122
static MI_INFO *open_isam_file(char *name,int mode);
123
static my_bool open_isam_files(PACK_MRG_INFO *mrg,char **names,uint count);
124
static int compress(PACK_MRG_INFO *file,char *join_name);
125
static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records);
126
static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees,
128
HUFF_COUNTS *huff_counts,
130
static int compare_tree(void* cmp_arg __attribute__((unused)),
131
const uchar *s,const uchar *t);
132
static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts);
133
static void check_counts(HUFF_COUNTS *huff_counts,uint trees,
135
static int test_space_compress(HUFF_COUNTS *huff_counts,my_off_t records,
136
uint max_space_length,my_off_t *space_counts,
137
my_off_t tot_space_count,
138
enum en_fieldtype field_type);
139
static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts,uint trees);
140
static int make_huff_tree(HUFF_TREE *tree,HUFF_COUNTS *huff_counts);
141
static int compare_huff_elements(void *not_used, uchar *a,uchar *b);
142
static int save_counts_in_queue(uchar *key,element_count count,
144
static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,uint flag);
145
static uint join_same_trees(HUFF_COUNTS *huff_counts,uint trees);
146
static int make_huff_decode_table(HUFF_TREE *huff_tree,uint trees);
147
static void make_traverse_code_tree(HUFF_TREE *huff_tree,
148
HUFF_ELEMENT *element,uint size,
150
static int write_header(PACK_MRG_INFO *isam_file, uint header_length,uint trees,
151
my_off_t tot_elements,my_off_t filelength);
152
static void write_field_info(HUFF_COUNTS *counts, uint fields,uint trees);
153
static my_off_t write_huff_tree(HUFF_TREE *huff_tree,uint trees);
154
static uint *make_offset_code_tree(HUFF_TREE *huff_tree,
155
HUFF_ELEMENT *element,
157
static uint max_bit(uint value);
158
static int compress_isam_file(PACK_MRG_INFO *file,HUFF_COUNTS *huff_counts);
159
static char *make_new_name(char *new_name,char *old_name);
160
static char *make_old_name(char *new_name,char *old_name);
161
static void init_file_buffer(File file,bool read_buffer);
162
static int flush_buffer(ulong neaded_length);
163
static void end_file_buffer(void);
164
static void write_bits(uint64_t value, uint bits);
165
static void flush_bits(void);
166
static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
168
static int save_state_mrg(File file,PACK_MRG_INFO *isam_file,my_off_t new_length,
170
static int mrg_close(PACK_MRG_INFO *mrg);
171
static int mrg_rrnd(PACK_MRG_INFO *info,uchar *buf);
172
static void mrg_reset(PACK_MRG_INFO *mrg);
173
#if !defined(DBUG_OFF)
174
static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count);
175
static int fakecmp(my_off_t **count1, my_off_t **count2);
179
static int error_on_write=0,test_only=0,verbose=0,silent=0,
180
write_loop=0,force_pack=0, isamchk_neaded=0;
181
static int tmpfile_createflag=O_RDWR | O_TRUNC | O_EXCL;
182
static my_bool backup, opt_wait;
184
tree_buff_length is somewhat arbitrary. The bigger it is the better
185
the chance to win in terms of compression factor. On the other hand,
186
this table becomes part of the compressed file header. And its length
187
is coded with 16 bits in the header. Hence the limit is 2**16 - 1.
189
static uint tree_buff_length= 65536 - MALLOC_OVERHEAD;
190
static char tmp_dir[FN_REFLEN]={0},*join_table;
191
static my_off_t intervall_length;
192
static ha_checksum glob_crc;
193
static struct st_file_buffer file_buffer;
195
static HUFF_COUNTS *global_count;
196
static char zero_string[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
197
static const char *load_default_groups[]= { "myisampack",0 };
199
/* The main program */
201
int main(int argc, char **argv)
208
load_defaults("my",load_default_groups,&argc,&argv);
210
get_options(&argc,&argv);
212
error=ok=isamchk_neaded=0;
214
{ /* Join files into one */
215
if (open_isam_files(&merge,argv,(uint) argc) ||
216
compress(&merge,join_table))
222
if (!(isam_file=open_isam_file(*argv++,O_RDWR)))
226
merge.file= &isam_file;
230
if (compress(&merge,0))
236
if (ok && isamchk_neaded && !silent)
237
puts("Remember to run myisamchk -rq on compressed tables");
238
VOID(fflush(stdout));
239
VOID(fflush(stderr));
240
free_defaults(default_argv);
241
my_end(verbose ? MY_CHECK_ERROR | MY_GIVE_INFO : MY_CHECK_ERROR);
244
return 0; /* No compiler warning */
248
enum options_mp {OPT_CHARSETS_DIR_MP=256, OPT_AUTO_CLOSE};
250
static struct my_option my_long_options[] =
253
{"autoclose", OPT_AUTO_CLOSE, "Auto close the screen on exit for Netware.",
254
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
256
{"backup", 'b', "Make a backup of the table as table_name.OLD.",
257
(char**) &backup, (char**) &backup, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
258
{"character-sets-dir", OPT_CHARSETS_DIR_MP,
259
"Directory where character sets are.", (char**) &charsets_dir,
260
(char**) &charsets_dir, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
261
{"debug", '#', "Output debug log. Often this is 'd:t:o,filename'.",
262
0, 0, 0, GET_STR, OPT_ARG, 0, 0, 0, 0, 0, 0},
264
"Force packing of table even if it gets bigger or if tempfile exists.",
265
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
267
"Join all given tables into 'new_table_name'. All tables MUST have identical layouts.",
268
(char**) &join_table, (char**) &join_table, 0, GET_STR, REQUIRED_ARG, 0, 0, 0,
270
{"help", '?', "Display this help and exit.",
271
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
272
{"silent", 's', "Be more silent.",
273
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
274
{"tmpdir", 'T', "Use temporary directory to store temporary table.",
275
0, 0, 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0},
276
{"test", 't', "Don't pack table, only test packing it.",
277
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
278
{"verbose", 'v', "Write info about progress and packing result. Use many -v for more verbosity!",
279
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
280
{"version", 'V', "Output version information and exit.",
281
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
282
{"wait", 'w', "Wait and retry if table is in use.", (char**) &opt_wait,
283
(char**) &opt_wait, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
284
{ 0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
287
#include <help_start.h>
289
static void print_version(void)
291
VOID(printf("%s Ver 1.23 for %s on %s\n",
292
my_progname, SYSTEM_TYPE, MACHINE_TYPE));
296
static void usage(void)
299
puts("Copyright (C) 2002 MySQL AB");
300
puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,");
301
puts("and you are welcome to modify and redistribute it under the GPL license\n");
303
puts("Pack a MyISAM-table to take much less space.");
304
puts("Keys are not updated, you must run myisamchk -rq on the datafile");
305
puts("afterwards to update the keys.");
306
puts("You should give the .MYI file as the filename argument.");
308
VOID(printf("\nUsage: %s [OPTIONS] filename...\n", my_progname));
309
my_print_help(my_long_options);
310
print_defaults("my", load_default_groups);
311
my_print_variables(my_long_options);
314
#include <help_end.h>
317
get_one_option(int optid, const struct my_option *opt __attribute__((unused)),
325
setscreenmode(SCR_AUTOCLOSE_ON_EXIT);
330
tmpfile_createflag= O_RDWR | O_TRUNC;
333
write_loop= verbose= 0;
338
/* Avoid to reset 'verbose' if it was already set > 1. */
343
length= (uint) (strmov(tmp_dir, argument) - tmp_dir);
344
if (length != dirname_length(tmp_dir))
346
tmp_dir[length]=FN_LIBCHAR;
351
verbose++; /* Allow for selecting the level of verbosity. */
355
DBUG_PUSH(argument ? argument : "d:t:o");
369
/* Initiates DEBUG - but no debugging here ! */
371
static void get_options(int *argc,char ***argv)
375
my_progname= argv[0][0];
376
if (isatty(fileno(stdout)))
379
if ((ho_error=handle_options(argc, argv, my_long_options, get_one_option)))
389
backup=0; /* Not needed */
396
static MI_INFO *open_isam_file(char *name,int mode)
400
DBUG_ENTER("open_isam_file");
402
if (!(isam_file=mi_open(name,mode,
403
(opt_wait ? HA_OPEN_WAIT_IF_LOCKED :
404
HA_OPEN_ABORT_IF_LOCKED))))
406
VOID(fprintf(stderr, "%s gave error %d on open\n", name, my_errno));
410
if (share->options & HA_OPTION_COMPRESS_RECORD && !join_table)
414
VOID(fprintf(stderr, "%s is already compressed\n", name));
415
VOID(mi_close(isam_file));
419
puts("Recompressing already compressed table");
420
share->options&= ~HA_OPTION_READ_ONLY_DATA; /* We are modifing it */
422
if (! force_pack && share->state.state.records != 0 &&
423
(share->state.state.records <= 1 ||
424
share->state.state.data_file_length < 1024))
426
VOID(fprintf(stderr, "%s is too small to compress\n", name));
427
VOID(mi_close(isam_file));
430
VOID(mi_lock_database(isam_file,F_WRLCK));
431
DBUG_RETURN(isam_file);
435
static my_bool open_isam_files(PACK_MRG_INFO *mrg, char **names, uint count)
440
mrg->file=(MI_INFO**) my_malloc(sizeof(MI_INFO*)*count,MYF(MY_FAE));
442
mrg->src_file_has_indexes_disabled= 0;
443
for (i=0; i < count ; i++)
445
if (!(mrg->file[i]=open_isam_file(names[i],O_RDONLY)))
448
mrg->src_file_has_indexes_disabled|=
449
! mi_is_all_keys_active(mrg->file[i]->s->state.key_map,
450
mrg->file[i]->s->base.keys);
452
/* Check that files are identical */
453
for (j=0 ; j < count-1 ; j++)
455
MI_COLUMNDEF *m1,*m2,*end;
456
if (mrg->file[j]->s->base.reclength != mrg->file[j+1]->s->base.reclength ||
457
mrg->file[j]->s->base.fields != mrg->file[j+1]->s->base.fields)
459
m1=mrg->file[j]->s->rec;
460
end=m1+mrg->file[j]->s->base.fields;
461
m2=mrg->file[j+1]->s->rec;
462
for ( ; m1 != end ; m1++,m2++)
464
if (m1->type != m2->type || m1->length != m2->length)
472
VOID(fprintf(stderr, "%s: Tables '%s' and '%s' are not identical\n",
473
my_progname, names[j], names[j+1]));
476
mi_close(mrg->file[i]);
477
my_free((uchar*) mrg->file,MYF(0));
482
static int compress(PACK_MRG_INFO *mrg,char *result_table)
485
File new_file,join_isam_file;
488
char org_name[FN_REFLEN],new_name[FN_REFLEN],temp_name[FN_REFLEN];
489
uint i,header_length,fields,trees,used_trees;
490
my_off_t old_length,new_length,tot_elements;
491
HUFF_COUNTS *huff_counts;
492
HUFF_TREE *huff_trees;
493
DBUG_ENTER("compress");
495
isam_file=mrg->file[0]; /* Take this as an example */
497
new_file=join_isam_file= -1;
502
/* Create temporary or join file */
505
VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2));
507
VOID(fn_format(org_name,isam_file->filename,"",MI_NAME_DEXT,2+4+16));
508
if (!test_only && result_table)
510
/* Make a new indexfile based on first file in list */
513
strmov(org_name,result_table); /* Fix error messages */
514
VOID(fn_format(new_name,result_table,"",MI_NAME_IEXT,2));
515
if ((join_isam_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME)))
518
length=(uint) share->base.keystart;
519
if (!(buff= (uchar*) my_malloc(length,MYF(MY_WME))))
521
if (my_pread(share->kfile,buff,length,0L,MYF(MY_WME | MY_NABP)) ||
522
my_write(join_isam_file,buff,length,
523
MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
525
my_free(buff,MYF(0));
528
my_free(buff,MYF(0));
529
VOID(fn_format(new_name,result_table,"",MI_NAME_DEXT,2));
531
else if (!tmp_dir[0])
532
VOID(make_new_name(new_name,org_name));
534
VOID(fn_format(new_name,org_name,tmp_dir,DATA_TMP_EXT,1+2+4));
536
(new_file=my_create(new_name,0,tmpfile_createflag,MYF(MY_WME))) < 0)
539
/* Start calculating statistics */
542
for (i=0 ; i < mrg->count ; i++)
543
mrg->records+=mrg->file[i]->s->state.state.records;
545
DBUG_PRINT("info", ("Compressing %s: (%lu records)",
546
result_table ? new_name : org_name,
547
(ulong) mrg->records));
548
if (write_loop || verbose)
550
VOID(printf("Compressing %s: (%lu records)\n",
551
result_table ? new_name : org_name, (ulong) mrg->records));
553
trees=fields=share->base.fields;
554
huff_counts=init_huff_count(isam_file,mrg->records);
558
Read the whole data file(s) for statistics.
560
DBUG_PRINT("info", ("- Calculating statistics"));
561
if (write_loop || verbose)
562
VOID(printf("- Calculating statistics\n"));
563
if (get_statistic(mrg,huff_counts))
567
for (i=0; i < mrg->count ; i++)
568
old_length+= (mrg->file[i]->s->state.state.data_file_length -
569
mrg->file[i]->s->state.state.empty);
572
Create a global priority queue in preparation for making
573
temporary Huffman trees.
575
if (init_queue(&queue,256,0,0,compare_huff_elements,0))
579
Check each column if we should use pre-space-compress, end-space-
580
compress, empty-field-compress or zero-field-compress.
582
check_counts(huff_counts,fields,mrg->records);
585
Build a Huffman tree for each column.
587
huff_trees=make_huff_trees(huff_counts,trees);
590
If the packed lengths of combined columns is less then the sum of
591
the non-combined columns, then create common Huffman trees for them.
592
We do this only for byte compressed columns, not for distinct values
595
if ((int) (used_trees=join_same_trees(huff_counts,trees)) < 0)
599
Assign codes to all byte or column values.
601
if (make_huff_decode_table(huff_trees,fields))
604
/* Prepare a file buffer. */
605
init_file_buffer(new_file,0);
608
Reserve space in the target file for the fixed compressed file header.
610
file_buffer.pos_in_file=HEAD_LENGTH;
612
VOID(my_seek(new_file,file_buffer.pos_in_file,MY_SEEK_SET,MYF(0)));
615
Write field infos: field type, pack type, length bits, tree number.
617
write_field_info(huff_counts,fields,used_trees);
622
if (!(tot_elements=write_huff_tree(huff_trees,trees)))
626
Calculate the total length of the compression info header.
627
This includes the fixed compressed file header, the column compression
628
type descriptions, and the decode trees.
630
header_length=(uint) file_buffer.pos_in_file+
631
(uint) (file_buffer.pos-file_buffer.buffer);
634
Compress the source file into the target file.
636
DBUG_PRINT("info", ("- Compressing file"));
637
if (write_loop || verbose)
638
VOID(printf("- Compressing file\n"));
639
error=compress_isam_file(mrg,huff_counts);
640
new_length=file_buffer.pos_in_file;
641
if (!error && !test_only)
643
uchar buff[MEMMAP_EXTRA_MARGIN]; /* End marginal for memmap */
644
bzero(buff,sizeof(buff));
645
error=my_write(file_buffer.file,buff,sizeof(buff),
646
MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
650
Write the fixed compressed file header.
653
error=write_header(mrg,header_length,used_trees,tot_elements,
656
/* Flush the file buffer. */
659
/* Display statistics. */
660
DBUG_PRINT("info", ("Min record length: %6d Max length: %6d "
661
"Mean total length: %6ld\n",
662
mrg->min_pack_length, mrg->max_pack_length,
663
(ulong) (mrg->records ? (new_length/mrg->records) : 0)));
664
if (verbose && mrg->records)
665
VOID(printf("Min record length: %6d Max length: %6d "
666
"Mean total length: %6ld\n", mrg->min_pack_length,
667
mrg->max_pack_length, (ulong) (new_length/mrg->records)));
669
/* Close source and target file. */
672
error|=my_close(new_file,MYF(MY_WME));
675
error|=my_close(isam_file->dfile,MYF(MY_WME));
676
isam_file->dfile= -1; /* Tell mi_close file is closed */
681
free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
682
if (! test_only && ! error)
686
error=save_state_mrg(join_isam_file,mrg,new_length,glob_crc);
692
if (my_rename(org_name,make_old_name(temp_name,isam_file->filename),
698
error=my_copy(new_name,org_name,MYF(MY_WME));
700
error=my_rename(new_name,org_name,MYF(MY_WME));
703
VOID(my_copystat(temp_name,org_name,MYF(MY_COPYTIME)));
705
VOID(my_delete(new_name,MYF(MY_WME)));
713
error=my_copy(new_name,org_name,
714
MYF(MY_WME | MY_HOLD_ORIGINAL_MODES | MY_COPYTIME));
716
VOID(my_delete(new_name,MYF(MY_WME)));
719
error=my_redel(org_name,new_name,MYF(MY_WME | MY_COPYTIME));
722
error=save_state(isam_file,mrg,new_length,glob_crc);
725
error|=mrg_close(mrg);
726
if (join_isam_file >= 0)
727
error|=my_close(join_isam_file,MYF(MY_WME));
730
VOID(fprintf(stderr, "Aborting: %s is not compressed\n", org_name));
731
VOID(my_delete(new_name,MYF(MY_WME)));
734
if (write_loop || verbose)
737
VOID(printf("%.4g%% \n",
738
(((int64_t) (old_length - new_length)) * 100.0 /
739
(int64_t) old_length)));
741
puts("Empty file saved in compressed format");
746
free_counts_and_tree_and_queue(huff_trees,trees,huff_counts,fields);
748
VOID(my_close(new_file,MYF(0)));
749
if (join_isam_file >= 0)
750
VOID(my_close(join_isam_file,MYF(0)));
752
VOID(fprintf(stderr, "Aborted: %s is not compressed\n", org_name));
756
/* Init a huff_count-struct for each field and init it */
758
static HUFF_COUNTS *init_huff_count(MI_INFO *info,my_off_t records)
761
register HUFF_COUNTS *count;
762
if ((count = (HUFF_COUNTS*) my_malloc(info->s->base.fields*
764
MYF(MY_ZEROFILL | MY_WME))))
766
for (i=0 ; i < info->s->base.fields ; i++)
768
enum en_fieldtype type;
769
count[i].field_length=info->s->rec[i].length;
770
type= count[i].field_type= (enum en_fieldtype) info->s->rec[i].type;
771
if (type == FIELD_INTERVALL ||
772
type == FIELD_CONSTANT ||
775
if (count[i].field_length <= 8 &&
776
(type == FIELD_NORMAL ||
777
type == FIELD_SKIP_ZERO))
778
count[i].max_zero_fill= count[i].field_length;
780
For every column initialize a tree, which is used to detect distinct
781
column values. 'int_tree' works together with 'tree_buff' and
782
'tree_pos'. It's keys are implemented by pointers into 'tree_buff'.
783
This is accomplished by '-1' as the element size.
785
init_tree(&count[i].int_tree,0,0,-1,(qsort_cmp2) compare_tree,0, NULL,
787
if (records && type != FIELD_BLOB && type != FIELD_VARCHAR)
788
count[i].tree_pos=count[i].tree_buff =
789
my_malloc(count[i].field_length > 1 ? tree_buff_length : 2,
797
/* Free memory used by counts and trees */
799
static void free_counts_and_tree_and_queue(HUFF_TREE *huff_trees, uint trees,
800
HUFF_COUNTS *huff_counts,
807
for (i=0 ; i < trees ; i++)
809
if (huff_trees[i].element_buffer)
810
my_free((uchar*) huff_trees[i].element_buffer,MYF(0));
811
if (huff_trees[i].code)
812
my_free((uchar*) huff_trees[i].code,MYF(0));
814
my_free((uchar*) huff_trees,MYF(0));
818
for (i=0 ; i < fields ; i++)
820
if (huff_counts[i].tree_buff)
822
my_free((uchar*) huff_counts[i].tree_buff,MYF(0));
823
delete_tree(&huff_counts[i].int_tree);
826
my_free((uchar*) huff_counts,MYF(0));
828
delete_queue(&queue); /* This is safe to free */
832
/* Read through old file and gather some statistics */
834
static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
838
ulong reclength,max_blob_length;
839
uchar *record,*pos,*next_pos,*end_pos,*start_pos;
840
ha_rows record_count;
841
my_bool static_row_size;
842
HUFF_COUNTS *count,*end_count;
843
TREE_ELEMENT *element;
844
DBUG_ENTER("get_statistic");
846
reclength=mrg->file[0]->s->base.reclength;
847
record=(uchar*) my_alloca(reclength);
848
end_count=huff_counts+mrg->file[0]->s->base.fields;
849
record_count=0; glob_crc=0;
852
/* Check how to calculate checksum */
854
for (count=huff_counts ; count < end_count ; count++)
856
if (count->field_type == FIELD_BLOB ||
857
count->field_type == FIELD_VARCHAR)
865
while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
867
ulong tot_blob_length=0;
870
/* glob_crc is a checksum over all bytes of all records. */
872
glob_crc+=mi_static_checksum(mrg->file[0],record);
874
glob_crc+=mi_checksum(mrg->file[0],record);
876
/* Count the incidence of values separately for every column. */
877
for (pos=record,count=huff_counts ;
882
next_pos=end_pos=(start_pos=pos)+count->field_length;
885
Put the whole column value in a tree if there is room for it.
886
'int_tree' is used to quickly check for duplicate values.
887
'tree_buff' collects as many distinct column values as
888
possible. If the field length is > 1, it is tree_buff_length,
889
else 2 bytes. Each value is 'field_length' bytes big. If there
890
are more distinct column values than fit into the buffer, we
891
give up with this tree. BLOBs and VARCHARs do not have a
892
tree_buff as it can only be used with fixed length columns.
893
For the special case of field length == 1, we handle only the
894
case that there is only one distinct value in the table(s).
895
Otherwise, we can have a maximum of 256 distinct values. This
896
is then handled by the normal Huffman tree build.
898
Another limit for collecting distinct column values is the
899
number of values itself. Since we would need to build a
900
Huffman tree for the values, we are limited by the 'IS_OFFSET'
901
constant. This constant expresses a bit which is used to
902
determine if a tree element holds a final value or an offset
903
to a child element. Hence, all values and offsets need to be
904
smaller than 'IS_OFFSET'. A tree element is implemented with
905
two integer values, one for the left branch and one for the
906
right branch. For the extreme case that the first element
907
points to the last element, the number of integers in the tree
908
must be less or equal to IS_OFFSET. So the number of elements
909
must be less or equal to IS_OFFSET / 2.
911
WARNING: At first, we insert a pointer into the record buffer
912
as the key for the tree. If we got a new distinct value, which
913
is really inserted into the tree, instead of being counted
914
only, we will copy the column value from the record buffer to
915
'tree_buff' and adjust the key pointer of the tree accordingly.
917
if (count->tree_buff)
920
if (!(element=tree_insert(&count->int_tree,pos, 0,
921
count->int_tree.custom_arg)) ||
922
(element->count == 1 &&
923
(count->tree_buff + tree_buff_length <
924
count->tree_pos + count->field_length)) ||
925
(count->int_tree.elements_in_tree > IS_OFFSET / 2) ||
926
(count->field_length == 1 &&
927
count->int_tree.elements_in_tree > 1))
929
delete_tree(&count->int_tree);
930
my_free(count->tree_buff,MYF(0));
936
If tree_insert() succeeds, it either creates a new element
937
or increments the counter of an existing element.
939
if (element->count == 1)
941
/* Copy the new column value into 'tree_buff'. */
942
memcpy(count->tree_pos,pos,(size_t) count->field_length);
943
/* Adjust the key pointer in the tree. */
944
tree_set_pointer(element,count->tree_pos);
945
/* Point behind the last column value so far. */
946
count->tree_pos+=count->field_length;
951
/* Save character counters and space-counts and zero-field-counts */
952
if (count->field_type == FIELD_NORMAL ||
953
count->field_type == FIELD_SKIP_ENDSPACE)
955
/* Ignore trailing space. */
956
for ( ; end_pos > pos ; end_pos--)
957
if (end_pos[-1] != ' ')
959
/* Empty fields are just counted. Go to the next record. */
962
count->empty_fields++;
963
count->max_zero_fill=0;
967
Count the total of all trailing spaces and the number of
968
short trailing spaces. Remember the longest trailing space.
970
length= (uint) (next_pos-end_pos);
971
count->tot_end_space+=length;
973
count->end_space[length]++;
974
if (count->max_end_space < length)
975
count->max_end_space = length;
978
if (count->field_type == FIELD_NORMAL ||
979
count->field_type == FIELD_SKIP_PRESPACE)
981
/* Ignore leading space. */
982
for (pos=start_pos; pos < end_pos ; pos++)
985
/* Empty fields are just counted. Go to the next record. */
988
count->empty_fields++;
989
count->max_zero_fill=0;
993
Count the total of all leading spaces and the number of
994
short leading spaces. Remember the longest leading space.
996
length= (uint) (pos-start_pos);
997
count->tot_pre_space+=length;
999
count->pre_space[length]++;
1000
if (count->max_pre_space < length)
1001
count->max_pre_space = length;
1004
/* Calculate pos, end_pos, and max_length for variable length fields. */
1005
if (count->field_type == FIELD_BLOB)
1007
uint field_length=count->field_length -portable_sizeof_char_ptr;
1008
ulong blob_length= _mi_calc_blob_length(field_length, start_pos);
1009
memcpy_fixed((char*) &pos, start_pos+field_length,sizeof(char*));
1010
end_pos=pos+blob_length;
1011
tot_blob_length+=blob_length;
1012
set_if_bigger(count->max_length,blob_length);
1014
else if (count->field_type == FIELD_VARCHAR)
1016
uint pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
1017
length= (pack_length == 1 ? (uint) *(uchar*) start_pos :
1018
uint2korr(start_pos));
1019
pos= start_pos+pack_length;
1020
end_pos= pos+length;
1021
set_if_bigger(count->max_length,length);
1024
/* Evaluate 'max_zero_fill' for short fields. */
1025
if (count->field_length <= 8 &&
1026
(count->field_type == FIELD_NORMAL ||
1027
count->field_type == FIELD_SKIP_ZERO))
1030
/* Zero fields are just counted. Go to the next record. */
1031
if (!memcmp((uchar*) start_pos,zero_string,count->field_length))
1033
count->zero_fields++;
1037
max_zero_fill starts with field_length. It is decreased every
1038
time a shorter "zero trailer" is found. It is set to zero when
1039
an empty field is found (see above). This suggests that the
1040
variable should be called 'min_zero_fill'.
1042
for (i =0 ; i < count->max_zero_fill && ! end_pos[-1 - (int) i] ;
1044
if (i < count->max_zero_fill)
1045
count->max_zero_fill=i;
1048
/* Ignore zero fields and check fields. */
1049
if (count->field_type == FIELD_ZERO ||
1050
count->field_type == FIELD_CHECK)
1054
Count the incidence of every byte value in the
1055
significant field value.
1057
for ( ; pos < end_pos ; pos++)
1058
count->counts[(uchar) *pos]++;
1060
/* Step to next field. */
1063
if (tot_blob_length > max_blob_length)
1064
max_blob_length=tot_blob_length;
1066
if (write_loop && record_count % WRITE_COUNT == 0)
1068
VOID(printf("%lu\r", (ulong) record_count));
1069
VOID(fflush(stdout));
1072
else if (error != HA_ERR_RECORD_DELETED)
1074
VOID(fprintf(stderr, "Got error %d while reading rows", error));
1078
/* Step to next record. */
1082
VOID(printf(" \r"));
1083
VOID(fflush(stdout));
1087
If --debug=d,fakebigcodes is set, fake the counts to get big Huffman
1090
DBUG_EXECUTE_IF("fakebigcodes", fakebigcodes(huff_counts, end_count););
1092
DBUG_PRINT("info", ("Found the following number of incidents "
1093
"of the byte codes:"));
1095
VOID(printf("Found the following number of incidents "
1096
"of the byte codes:\n"));
1097
for (count= huff_counts ; count < end_count; count++)
1100
my_off_t total_count;
1103
DBUG_PRINT("info", ("column: %3u", (uint) (count - huff_counts + 1)));
1105
VOID(printf("column: %3u\n", (uint) (count - huff_counts + 1)));
1106
if (count->tree_buff)
1108
DBUG_PRINT("info", ("number of distinct values: %u",
1109
(uint) ((count->tree_pos - count->tree_buff) /
1110
count->field_length)));
1112
VOID(printf("number of distinct values: %u\n",
1113
(uint) ((count->tree_pos - count->tree_buff) /
1114
count->field_length)));
1117
for (idx= 0; idx < 256; idx++)
1119
if (count->counts[idx])
1121
total_count+= count->counts[idx];
1122
DBUG_PRINT("info", ("counts[0x%02x]: %12s", idx,
1123
llstr((int64_t) count->counts[idx], llbuf)));
1125
VOID(printf("counts[0x%02x]: %12s\n", idx,
1126
llstr((int64_t) count->counts[idx], llbuf)));
1129
DBUG_PRINT("info", ("total: %12s", llstr((int64_t) total_count,
1131
if ((verbose >= 2) && total_count)
1133
VOID(printf("total: %12s\n",
1134
llstr((int64_t) total_count, llbuf)));
1138
mrg->records=record_count;
1139
mrg->max_blob_length=max_blob_length;
1140
my_afree((uchar*) record);
1141
DBUG_RETURN(error != HA_ERR_END_OF_FILE);
1144
static int compare_huff_elements(void *not_used __attribute__((unused)),
1147
return *((my_off_t*) a) < *((my_off_t*) b) ? -1 :
1148
(*((my_off_t*) a) == *((my_off_t*) b) ? 0 : 1);
1151
/* Check each tree if we should use pre-space-compress, end-space-
1152
compress, empty-field-compress or zero-field-compress */
1154
static void check_counts(HUFF_COUNTS *huff_counts, uint trees,
1157
uint space_fields,fill_zero_fields,field_count[(int) FIELD_enum_val_count];
1158
my_off_t old_length,new_length,length;
1159
DBUG_ENTER("check_counts");
1161
bzero((uchar*) field_count,sizeof(field_count));
1162
space_fields=fill_zero_fields=0;
1164
for (; trees-- ; huff_counts++)
1166
if (huff_counts->field_type == FIELD_BLOB)
1168
huff_counts->length_bits=max_bit(huff_counts->max_length);
1171
else if (huff_counts->field_type == FIELD_VARCHAR)
1173
huff_counts->length_bits=max_bit(huff_counts->max_length);
1176
else if (huff_counts->field_type == FIELD_CHECK)
1178
huff_counts->bytes_packed=0;
1179
huff_counts->counts[0]=0;
1183
huff_counts->field_type=FIELD_NORMAL;
1184
huff_counts->pack_type=0;
1186
/* Check for zero-filled records (in this column), or zero records. */
1187
if (huff_counts->zero_fields || ! records)
1189
my_off_t old_space_count;
1191
If there are only zero filled records (in this column),
1192
or no records at all, we are done.
1194
if (huff_counts->zero_fields == records)
1196
huff_counts->field_type= FIELD_ZERO;
1197
huff_counts->bytes_packed=0;
1198
huff_counts->counts[0]=0;
1201
/* Remeber the number of significant spaces. */
1202
old_space_count=huff_counts->counts[' '];
1203
/* Add all leading and trailing spaces. */
1204
huff_counts->counts[' ']+= (huff_counts->tot_end_space +
1205
huff_counts->tot_pre_space +
1206
huff_counts->empty_fields *
1207
huff_counts->field_length);
1208
/* Check, what the compressed length of this would be. */
1209
old_length=calc_packed_length(huff_counts,0)+records/8;
1210
/* Get the number of zero bytes. */
1211
length=huff_counts->zero_fields*huff_counts->field_length;
1212
/* Add it to the counts. */
1213
huff_counts->counts[0]+=length;
1214
/* Check, what the compressed length of this would be. */
1215
new_length=calc_packed_length(huff_counts,0);
1216
/* If the compression without the zeroes would be shorter, we are done. */
1217
if (old_length < new_length && huff_counts->field_length > 1)
1219
huff_counts->field_type=FIELD_SKIP_ZERO;
1220
huff_counts->counts[0]-=length;
1221
huff_counts->bytes_packed=old_length- records/8;
1224
/* Remove the insignificant spaces, but keep the zeroes. */
1225
huff_counts->counts[' ']=old_space_count;
1227
/* Check, what the compressed length of this column would be. */
1228
huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
1231
If there are enough empty records (in this column),
1232
treating them specially may pay off.
1234
if (huff_counts->empty_fields)
1236
if (huff_counts->field_length > 2 &&
1237
huff_counts->empty_fields + (records - huff_counts->empty_fields)*
1238
(1+max_bit(max(huff_counts->max_pre_space,
1239
huff_counts->max_end_space))) <
1240
records * max_bit(huff_counts->field_length))
1242
huff_counts->pack_type |= PACK_TYPE_SPACE_FIELDS;
1246
length=huff_counts->empty_fields*huff_counts->field_length;
1247
if (huff_counts->tot_end_space || ! huff_counts->tot_pre_space)
1249
huff_counts->tot_end_space+=length;
1250
huff_counts->max_end_space=huff_counts->field_length;
1251
if (huff_counts->field_length < 8)
1252
huff_counts->end_space[huff_counts->field_length]+=
1253
huff_counts->empty_fields;
1255
if (huff_counts->tot_pre_space)
1257
huff_counts->tot_pre_space+=length;
1258
huff_counts->max_pre_space=huff_counts->field_length;
1259
if (huff_counts->field_length < 8)
1260
huff_counts->pre_space[huff_counts->field_length]+=
1261
huff_counts->empty_fields;
1267
If there are enough trailing spaces (in this column),
1268
treating them specially may pay off.
1270
if (huff_counts->tot_end_space)
1272
huff_counts->counts[' ']+=huff_counts->tot_pre_space;
1273
if (test_space_compress(huff_counts,records,huff_counts->max_end_space,
1274
huff_counts->end_space,
1275
huff_counts->tot_end_space,FIELD_SKIP_ENDSPACE))
1277
huff_counts->counts[' ']-=huff_counts->tot_pre_space;
1281
If there are enough leading spaces (in this column),
1282
treating them specially may pay off.
1284
if (huff_counts->tot_pre_space)
1286
if (test_space_compress(huff_counts,records,huff_counts->max_pre_space,
1287
huff_counts->pre_space,
1288
huff_counts->tot_pre_space,FIELD_SKIP_PRESPACE))
1292
found_pack: /* Found field-packing */
1294
/* Test if we can use zero-fill */
1296
if (huff_counts->max_zero_fill &&
1297
(huff_counts->field_type == FIELD_NORMAL ||
1298
huff_counts->field_type == FIELD_SKIP_ZERO))
1300
huff_counts->counts[0]-=huff_counts->max_zero_fill*
1301
(huff_counts->field_type == FIELD_SKIP_ZERO ?
1302
records - huff_counts->zero_fields : records);
1303
huff_counts->pack_type|=PACK_TYPE_ZERO_FILL;
1304
huff_counts->bytes_packed=calc_packed_length(huff_counts,0);
1307
/* Test if intervall-field is better */
1309
if (huff_counts->tree_buff)
1313
DBUG_EXECUTE_IF("forceintervall",
1314
huff_counts->bytes_packed= ~ (my_off_t) 0;);
1315
tree.element_buffer=0;
1316
if (!make_huff_tree(&tree,huff_counts) &&
1317
tree.bytes_packed+tree.tree_pack_length < huff_counts->bytes_packed)
1319
if (tree.elements == 1)
1320
huff_counts->field_type=FIELD_CONSTANT;
1322
huff_counts->field_type=FIELD_INTERVALL;
1323
huff_counts->pack_type=0;
1327
my_free((uchar*) huff_counts->tree_buff,MYF(0));
1328
delete_tree(&huff_counts->int_tree);
1329
huff_counts->tree_buff=0;
1331
if (tree.element_buffer)
1332
my_free((uchar*) tree.element_buffer,MYF(0));
1334
if (huff_counts->pack_type & PACK_TYPE_SPACE_FIELDS)
1336
if (huff_counts->pack_type & PACK_TYPE_ZERO_FILL)
1338
field_count[huff_counts->field_type]++;
1340
DBUG_PRINT("info", ("normal: %3d empty-space: %3d "
1341
"empty-zero: %3d empty-fill: %3d",
1342
field_count[FIELD_NORMAL],space_fields,
1343
field_count[FIELD_SKIP_ZERO],fill_zero_fields));
1344
DBUG_PRINT("info", ("pre-space: %3d end-space: %3d "
1345
"intervall-fields: %3d zero: %3d",
1346
field_count[FIELD_SKIP_PRESPACE],
1347
field_count[FIELD_SKIP_ENDSPACE],
1348
field_count[FIELD_INTERVALL],
1349
field_count[FIELD_ZERO]));
1351
VOID(printf("\nnormal: %3d empty-space: %3d "
1352
"empty-zero: %3d empty-fill: %3d\n"
1353
"pre-space: %3d end-space: %3d "
1354
"intervall-fields: %3d zero: %3d\n",
1355
field_count[FIELD_NORMAL],space_fields,
1356
field_count[FIELD_SKIP_ZERO],fill_zero_fields,
1357
field_count[FIELD_SKIP_PRESPACE],
1358
field_count[FIELD_SKIP_ENDSPACE],
1359
field_count[FIELD_INTERVALL],
1360
field_count[FIELD_ZERO]));
1364
/* Test if we can use space-compression and empty-field-compression */
1367
test_space_compress(HUFF_COUNTS *huff_counts, my_off_t records,
1368
uint max_space_length, my_off_t *space_counts,
1369
my_off_t tot_space_count, enum en_fieldtype field_type)
1373
my_off_t space_count,min_space_count,min_pack,new_length,skip;
1375
length_bits=max_bit(max_space_length);
1377
/* Default no end_space-packing */
1378
space_count=huff_counts->counts[(uint) ' '];
1379
min_space_count= (huff_counts->counts[(uint) ' ']+= tot_space_count);
1380
min_pack=calc_packed_length(huff_counts,0);
1382
huff_counts->counts[(uint) ' ']=space_count;
1384
/* Test with allways space-count */
1385
new_length=huff_counts->bytes_packed+length_bits*records/8;
1386
if (new_length+1 < min_pack)
1389
min_pack=new_length;
1390
min_space_count=space_count;
1392
/* Test with length-flag */
1393
for (skip=0L, i=0 ; i < 8 ; i++)
1395
if (space_counts[i])
1398
huff_counts->counts[(uint) ' ']+=space_counts[i];
1399
skip+=huff_counts->pre_space[i];
1400
new_length=calc_packed_length(huff_counts,0)+
1401
(records+(records-skip)*(1+length_bits))/8;
1402
if (new_length < min_pack)
1405
min_pack=new_length;
1406
min_space_count=huff_counts->counts[(uint) ' '];
1411
huff_counts->counts[(uint) ' ']=min_space_count;
1412
huff_counts->bytes_packed=min_pack;
1415
return(0); /* No space-compress */
1416
case -1: /* Always space-count */
1417
huff_counts->field_type=field_type;
1418
huff_counts->min_space=0;
1419
huff_counts->length_bits=max_bit(max_space_length);
1422
huff_counts->field_type=field_type;
1423
huff_counts->min_space=(uint) min_pos;
1424
huff_counts->pack_type|=PACK_TYPE_SELECTED;
1425
huff_counts->length_bits=max_bit(max_space_length);
1428
return(1); /* Using space-compress */
1432
/* Make a huff_tree of each huff_count */
1434
static HUFF_TREE* make_huff_trees(HUFF_COUNTS *huff_counts, uint trees)
1437
HUFF_TREE *huff_tree;
1438
DBUG_ENTER("make_huff_trees");
1440
if (!(huff_tree=(HUFF_TREE*) my_malloc(trees*sizeof(HUFF_TREE),
1441
MYF(MY_WME | MY_ZEROFILL))))
1444
for (tree=0 ; tree < trees ; tree++)
1446
if (make_huff_tree(huff_tree+tree,huff_counts+tree))
1449
my_free((uchar*) huff_tree[tree].element_buffer,MYF(0));
1450
my_free((uchar*) huff_tree,MYF(0));
1454
DBUG_RETURN(huff_tree);
1458
Build a Huffman tree.
1462
huff_tree The Huffman tree.
1463
huff_counts The counts.
1466
Build a Huffman tree according to huff_counts->counts or
1467
huff_counts->tree_buff. tree_buff, if non-NULL contains up to
1468
tree_buff_length of distinct column values. In that case, whole
1469
values can be Huffman encoded instead of single bytes.
1476
static int make_huff_tree(HUFF_TREE *huff_tree, HUFF_COUNTS *huff_counts)
1478
uint i,found,bits_packed,first,last;
1479
my_off_t bytes_packed;
1480
HUFF_ELEMENT *a,*b,*new_huff_el;
1483
if (huff_counts->tree_buff)
1485
/* Calculate the number of distinct values in tree_buff. */
1486
found= (uint) (huff_counts->tree_pos - huff_counts->tree_buff) /
1487
huff_counts->field_length;
1488
first=0; last=found-1;
1492
/* Count the number of byte codes found in the column. */
1493
for (i=found=0 ; i < 256 ; i++)
1495
if (huff_counts->counts[i])
1506
/* When using 'tree_buff' we can have more that 256 values. */
1507
if (queue.max_elements < found)
1509
delete_queue(&queue);
1510
if (init_queue(&queue,found,0,0,compare_huff_elements,0))
1514
/* Allocate or reallocate an element buffer for the Huffman tree. */
1515
if (!huff_tree->element_buffer)
1517
if (!(huff_tree->element_buffer=
1518
(HUFF_ELEMENT*) my_malloc(found*2*sizeof(HUFF_ELEMENT),MYF(MY_WME))))
1525
(HUFF_ELEMENT*) my_realloc((uchar*) huff_tree->element_buffer,
1526
found*2*sizeof(HUFF_ELEMENT),
1529
huff_tree->element_buffer=temp;
1532
huff_counts->tree=huff_tree;
1533
huff_tree->counts=huff_counts;
1534
huff_tree->min_chr=first;
1535
huff_tree->max_chr=last;
1536
huff_tree->char_bits=max_bit(last-first);
1537
huff_tree->offset_bits=max_bit(found-1)+1;
1539
if (huff_counts->tree_buff)
1541
huff_tree->elements=0;
1542
huff_tree->tree_pack_length=(1+15+16+5+5+
1543
(huff_tree->char_bits+1)*found+
1544
(huff_tree->offset_bits+1)*
1546
(uint) (huff_tree->counts->tree_pos-
1547
huff_tree->counts->tree_buff);
1549
Put a HUFF_ELEMENT into the queue for every distinct column value.
1551
tree_walk() calls save_counts_in_queue() for every element in
1552
'int_tree'. This takes elements from the target trees element
1553
buffer and places references to them into the buffer of the
1554
priority queue. We insert in column value order, but the order is
1555
in fact irrelevant here. We will establish the correct order
1558
tree_walk(&huff_counts->int_tree,
1559
(int (*)(void*, element_count,void*)) save_counts_in_queue,
1560
(uchar*) huff_tree, left_root_right);
1564
huff_tree->elements=found;
1565
huff_tree->tree_pack_length=(9+9+5+5+
1566
(huff_tree->char_bits+1)*found+
1567
(huff_tree->offset_bits+1)*
1570
Put a HUFF_ELEMENT into the queue for every byte code found in the column.
1572
The elements are taken from the target trees element buffer.
1573
Instead of using queue_insert(), we just place references to the
1574
elements into the buffer of the priority queue. We insert in byte
1575
value order, but the order is in fact irrelevant here. We will
1576
establish the correct order later.
1578
for (i=first, found=0 ; i <= last ; i++)
1580
if (huff_counts->counts[i])
1582
new_huff_el=huff_tree->element_buffer+(found++);
1583
new_huff_el->count=huff_counts->counts[i];
1584
new_huff_el->a.leaf.null=0;
1585
new_huff_el->a.leaf.element_nr=i;
1586
queue.root[found]=(uchar*) new_huff_el;
1590
If there is only a single byte value in this field in all records,
1591
add a second element with zero incidence. This is required to enter
1592
the loop, which builds the Huffman tree.
1596
new_huff_el=huff_tree->element_buffer+(found++);
1597
new_huff_el->count=0;
1598
new_huff_el->a.leaf.null=0;
1600
new_huff_el->a.leaf.element_nr=huff_tree->min_chr=last-1;
1602
new_huff_el->a.leaf.element_nr=huff_tree->max_chr=last+1;
1603
queue.root[found]=(uchar*) new_huff_el;
1607
/* Make a queue from the queue buffer. */
1608
queue.elements=found;
1611
Make a priority queue from the queue. Construct its index so that we
1612
have a partially ordered tree.
1614
for (i=found/2 ; i > 0 ; i--)
1615
_downheap(&queue,i);
1617
/* The Huffman algorithm. */
1618
bytes_packed=0; bits_packed=0;
1619
for (i=1 ; i < found ; i++)
1622
Pop the top element from the queue (the one with the least incidence).
1623
Popping from a priority queue includes a re-ordering of the queue,
1624
to get the next least incidence element to the top.
1626
a=(HUFF_ELEMENT*) queue_remove(&queue,0);
1628
Copy the next least incidence element. The queue implementation
1629
reserves root[0] for temporary purposes. root[1] is the top.
1631
b=(HUFF_ELEMENT*) queue.root[1];
1632
/* Get a new element from the element buffer. */
1633
new_huff_el=huff_tree->element_buffer+found+i;
1634
/* The new element gets the sum of the two least incidence elements. */
1635
new_huff_el->count=a->count+b->count;
1637
The Huffman algorithm assigns another bit to the code for a byte
1638
every time that bytes incidence is combined (directly or indirectly)
1639
to a new element as one of the two least incidence elements.
1640
This means that one more bit per incidence of that byte is required
1641
in the resulting file. So we add the new combined incidence as the
1642
number of bits by which the result grows.
1644
bits_packed+=(uint) (new_huff_el->count & 7);
1645
bytes_packed+=new_huff_el->count/8;
1646
/* The new element points to its children, lesser in left. */
1647
new_huff_el->a.nod.left=a;
1648
new_huff_el->a.nod.right=b;
1650
Replace the copied top element by the new element and re-order the
1653
queue.root[1]=(uchar*) new_huff_el;
1654
queue_replaced(&queue);
1656
huff_tree->root=(HUFF_ELEMENT*) queue.root[1];
1657
huff_tree->bytes_packed=bytes_packed+(bits_packed+7)/8;
1661
static int compare_tree(void* cmp_arg __attribute__((unused)),
1662
register const uchar *s, register const uchar *t)
1665
for (length=global_count->field_length; length-- ;)
1667
return (int) s[-1] - (int) t[-1];
1672
Organize distinct column values and their incidences into a priority queue.
1675
save_counts_in_queue()
1676
key The column value.
1677
count The incidence of this value.
1678
tree The Huffman tree to be built later.
1681
We use the element buffer of the targeted tree. The distinct column
1682
values are organized in a priority queue first. The Huffman
1683
algorithm will later organize the elements into a Huffman tree. For
1684
the time being, we just place references to the elements into the
1685
queue buffer. The buffer will later be organized into a priority
1692
static int save_counts_in_queue(uchar *key, element_count count,
1695
HUFF_ELEMENT *new_huff_el;
1697
new_huff_el=tree->element_buffer+(tree->elements++);
1698
new_huff_el->count=count;
1699
new_huff_el->a.leaf.null=0;
1700
new_huff_el->a.leaf.element_nr= (uint) (key- tree->counts->tree_buff) /
1701
tree->counts->field_length;
1702
queue.root[tree->elements]=(uchar*) new_huff_el;
1708
Calculate length of file if given counts should be used.
1711
calc_packed_length()
1712
huff_counts The counts for a column of the table(s).
1713
add_tree_lenght If the decode tree length should be added.
1716
We need to follow the Huffman algorithm until we know, how many bits
1717
are required for each byte code. But we do not need the resulting
1718
Huffman tree. Hence, we can leave out some steps which are essential
1719
in make_huff_tree().
1722
Number of bytes required to compress this table column.
1725
static my_off_t calc_packed_length(HUFF_COUNTS *huff_counts,
1726
uint add_tree_lenght)
1728
uint i,found,bits_packed,first,last;
1729
my_off_t bytes_packed;
1730
HUFF_ELEMENT element_buffer[256];
1731
DBUG_ENTER("calc_packed_length");
1734
WARNING: We use a small hack for efficiency: Instead of placing
1735
references to HUFF_ELEMENTs into the queue, we just insert
1736
references to the counts of the byte codes which appeared in this
1737
table column. During the Huffman algorithm they are successively
1738
replaced by references to HUFF_ELEMENTs. This works, because
1739
HUFF_ELEMENTs have the incidence count at their beginning.
1740
Regardless, wether the queue array contains references to counts of
1741
type my_off_t or references to HUFF_ELEMENTs which have the count of
1742
type my_off_t at their beginning, it always points to a count of the
1745
Instead of using queue_insert(), we just copy the references into
1746
the buffer of the priority queue. We insert in byte value order, but
1747
the order is in fact irrelevant here. We will establish the correct
1751
for (i=found=0 ; i < 256 ; i++)
1753
if (huff_counts->counts[i])
1758
/* We start with root[1], which is the queues top element. */
1759
queue.root[found]=(uchar*) &huff_counts->counts[i];
1763
DBUG_RETURN(0); /* Empty tree */
1765
If there is only a single byte value in this field in all records,
1766
add a second element with zero incidence. This is required to enter
1767
the loop, which follows the Huffman algorithm.
1770
queue.root[++found]=(uchar*) &huff_counts->counts[last ? 0 : 1];
1772
/* Make a queue from the queue buffer. */
1773
queue.elements=found;
1775
bytes_packed=0; bits_packed=0;
1776
/* Add the length of the coding table, which would become part of the file. */
1777
if (add_tree_lenght)
1778
bytes_packed=(8+9+5+5+(max_bit(last-first)+1)*found+
1779
(max_bit(found-1)+1+1)*(found-2) +7)/8;
1782
Make a priority queue from the queue. Construct its index so that we
1783
have a partially ordered tree.
1785
for (i=(found+1)/2 ; i > 0 ; i--)
1786
_downheap(&queue,i);
1788
/* The Huffman algorithm. */
1789
for (i=0 ; i < found-1 ; i++)
1793
HUFF_ELEMENT *new_huff_el;
1796
Pop the top element from the queue (the one with the least
1797
incidence). Popping from a priority queue includes a re-ordering
1798
of the queue, to get the next least incidence element to the top.
1800
a= (my_off_t*) queue_remove(&queue, 0);
1802
Copy the next least incidence element. The queue implementation
1803
reserves root[0] for temporary purposes. root[1] is the top.
1805
b= (my_off_t*) queue.root[1];
1806
/* Create a new element in a local (automatic) buffer. */
1807
new_huff_el= element_buffer + i;
1808
/* The new element gets the sum of the two least incidence elements. */
1809
new_huff_el->count= *a + *b;
1811
The Huffman algorithm assigns another bit to the code for a byte
1812
every time that bytes incidence is combined (directly or indirectly)
1813
to a new element as one of the two least incidence elements.
1814
This means that one more bit per incidence of that byte is required
1815
in the resulting file. So we add the new combined incidence as the
1816
number of bits by which the result grows.
1818
bits_packed+=(uint) (new_huff_el->count & 7);
1819
bytes_packed+=new_huff_el->count/8;
1821
Replace the copied top element by the new element and re-order the
1822
queue. This successively replaces the references to counts by
1823
references to HUFF_ELEMENTs.
1825
queue.root[1]=(uchar*) new_huff_el;
1826
queue_replaced(&queue);
1828
DBUG_RETURN(bytes_packed+(bits_packed+7)/8);
1832
/* Remove trees that don't give any compression */
1834
static uint join_same_trees(HUFF_COUNTS *huff_counts, uint trees)
1837
HUFF_COUNTS count,*i,*j,*last_count;
1839
last_count=huff_counts+trees;
1840
for (tree_number=0, i=huff_counts ; i < last_count ; i++)
1842
if (!i->tree->tree_number)
1844
i->tree->tree_number= ++tree_number;
1846
continue; /* Don't join intervall */
1847
for (j=i+1 ; j < last_count ; j++)
1849
if (! j->tree->tree_number && ! j->tree_buff)
1851
for (k=0 ; k < 256 ; k++)
1852
count.counts[k]=i->counts[k]+j->counts[k];
1853
if (calc_packed_length(&count,1) <=
1854
i->tree->bytes_packed + j->tree->bytes_packed+
1855
i->tree->tree_pack_length+j->tree->tree_pack_length+
1858
memcpy_fixed((uchar*) i->counts,(uchar*) count.counts,
1859
sizeof(count.counts[0])*256);
1860
my_free((uchar*) j->tree->element_buffer,MYF(0));
1861
j->tree->element_buffer=0;
1863
bmove((uchar*) i->counts,(uchar*) count.counts,
1864
sizeof(count.counts[0])*256);
1865
if (make_huff_tree(i->tree,i))
1872
DBUG_PRINT("info", ("Original trees: %d After join: %d",
1873
trees, tree_number));
1875
VOID(printf("Original trees: %d After join: %d\n", trees, tree_number));
1876
return tree_number; /* Return trees left */
1881
Fill in huff_tree encode tables.
1884
make_huff_decode_table()
1885
huff_tree An array of HUFF_TREE which are to be encoded.
1886
trees The number of HUFF_TREE in the array.
1893
static int make_huff_decode_table(HUFF_TREE *huff_tree, uint trees)
1896
for ( ; trees-- ; huff_tree++)
1898
if (huff_tree->tree_number > 0)
1900
elements=huff_tree->counts->tree_buff ? huff_tree->elements : 256;
1901
if (!(huff_tree->code =
1902
(uint64_t*) my_malloc(elements*
1903
(sizeof(uint64_t) + sizeof(uchar)),
1904
MYF(MY_WME | MY_ZEROFILL))))
1906
huff_tree->code_len=(uchar*) (huff_tree->code+elements);
1907
make_traverse_code_tree(huff_tree, huff_tree->root,
1908
8 * sizeof(uint64_t), 0LL);
1915
static void make_traverse_code_tree(HUFF_TREE *huff_tree,
1916
HUFF_ELEMENT *element,
1917
uint size, uint64_t code)
1920
if (!element->a.leaf.null)
1922
chr=element->a.leaf.element_nr;
1923
huff_tree->code_len[chr]= (uchar) (8 * sizeof(uint64_t) - size);
1924
huff_tree->code[chr]= (code >> size);
1925
if (huff_tree->height < 8 * sizeof(uint64_t) - size)
1926
huff_tree->height= 8 * sizeof(uint64_t) - size;
1931
make_traverse_code_tree(huff_tree,element->a.nod.left,size,code);
1932
make_traverse_code_tree(huff_tree, element->a.nod.right, size,
1933
code + (((uint64_t) 1) << size));
1940
Convert a value into binary digits.
1945
length The number of low order bits to convert.
1948
The result string is in static storage. It is reused on every call.
1949
So you cannot use it twice in one expression.
1952
A pointer to a static NUL-terminated string.
1955
static char *bindigits(uint64_t value, uint bits)
1957
static char digits[72];
1961
DBUG_ASSERT(idx < sizeof(digits));
1963
*(ptr++)= '0' + ((char) (value >> (--idx)) & (char) 1);
1970
Convert a value into hexadecimal digits.
1977
The result string is in static storage. It is reused on every call.
1978
So you cannot use it twice in one expression.
1981
A pointer to a static NUL-terminated string.
1984
static char *hexdigits(uint64_t value)
1986
static char digits[20];
1988
uint idx= 2 * sizeof(value); /* Two hex digits per byte. */
1990
DBUG_ASSERT(idx < sizeof(digits));
1993
if ((*(ptr++)= '0' + ((char) (value >> (4 * (--idx))) & (char) 0xf)) > '9')
1994
*(ptr - 1)+= 'a' - '9' - 1;
2001
/* Write header to new packed data file */
2003
static int write_header(PACK_MRG_INFO *mrg,uint head_length,uint trees,
2004
my_off_t tot_elements,my_off_t filelength)
2006
uchar *buff= (uchar*) file_buffer.pos;
2008
bzero(buff,HEAD_LENGTH);
2009
memcpy_fixed(buff,myisam_pack_file_magic,4);
2010
int4store(buff+4,head_length);
2011
int4store(buff+8, mrg->min_pack_length);
2012
int4store(buff+12,mrg->max_pack_length);
2013
int4store(buff+16,tot_elements);
2014
int4store(buff+20,intervall_length);
2015
int2store(buff+24,trees);
2016
buff[26]=(char) mrg->ref_length;
2017
/* Save record pointer length */
2018
buff[27]= (uchar) mi_get_pointer_length((uint64_t) filelength,2);
2021
VOID(my_seek(file_buffer.file,0L,MY_SEEK_SET,MYF(0)));
2022
return my_write(file_buffer.file,(const uchar *) file_buffer.pos,HEAD_LENGTH,
2023
MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)) != 0;
2026
/* Write fieldinfo to new packed file */
2028
static void write_field_info(HUFF_COUNTS *counts, uint fields, uint trees)
2031
uint huff_tree_bits;
2032
huff_tree_bits=max_bit(trees ? trees-1 : 0);
2034
DBUG_PRINT("info", (" "));
2035
DBUG_PRINT("info", ("column types:"));
2036
DBUG_PRINT("info", ("FIELD_NORMAL 0"));
2037
DBUG_PRINT("info", ("FIELD_SKIP_ENDSPACE 1"));
2038
DBUG_PRINT("info", ("FIELD_SKIP_PRESPACE 2"));
2039
DBUG_PRINT("info", ("FIELD_SKIP_ZERO 3"));
2040
DBUG_PRINT("info", ("FIELD_BLOB 4"));
2041
DBUG_PRINT("info", ("FIELD_CONSTANT 5"));
2042
DBUG_PRINT("info", ("FIELD_INTERVALL 6"));
2043
DBUG_PRINT("info", ("FIELD_ZERO 7"));
2044
DBUG_PRINT("info", ("FIELD_VARCHAR 8"));
2045
DBUG_PRINT("info", ("FIELD_CHECK 9"));
2046
DBUG_PRINT("info", (" "));
2047
DBUG_PRINT("info", ("pack type as a set of flags:"));
2048
DBUG_PRINT("info", ("PACK_TYPE_SELECTED 1"));
2049
DBUG_PRINT("info", ("PACK_TYPE_SPACE_FIELDS 2"));
2050
DBUG_PRINT("info", ("PACK_TYPE_ZERO_FILL 4"));
2051
DBUG_PRINT("info", (" "));
2055
VOID(printf("column types:\n"));
2056
VOID(printf("FIELD_NORMAL 0\n"));
2057
VOID(printf("FIELD_SKIP_ENDSPACE 1\n"));
2058
VOID(printf("FIELD_SKIP_PRESPACE 2\n"));
2059
VOID(printf("FIELD_SKIP_ZERO 3\n"));
2060
VOID(printf("FIELD_BLOB 4\n"));
2061
VOID(printf("FIELD_CONSTANT 5\n"));
2062
VOID(printf("FIELD_INTERVALL 6\n"));
2063
VOID(printf("FIELD_ZERO 7\n"));
2064
VOID(printf("FIELD_VARCHAR 8\n"));
2065
VOID(printf("FIELD_CHECK 9\n"));
2067
VOID(printf("pack type as a set of flags:\n"));
2068
VOID(printf("PACK_TYPE_SELECTED 1\n"));
2069
VOID(printf("PACK_TYPE_SPACE_FIELDS 2\n"));
2070
VOID(printf("PACK_TYPE_ZERO_FILL 4\n"));
2073
for (i=0 ; i++ < fields ; counts++)
2075
write_bits((uint64_t) (int) counts->field_type, 5);
2076
write_bits(counts->pack_type,6);
2077
if (counts->pack_type & PACK_TYPE_ZERO_FILL)
2078
write_bits(counts->max_zero_fill,5);
2080
write_bits(counts->length_bits,5);
2081
write_bits((uint64_t) counts->tree->tree_number - 1, huff_tree_bits);
2082
DBUG_PRINT("info", ("column: %3u type: %2u pack: %2u zero: %4u "
2083
"lbits: %2u tree: %2u length: %4u",
2084
i , counts->field_type, counts->pack_type,
2085
counts->max_zero_fill, counts->length_bits,
2086
counts->tree->tree_number, counts->field_length));
2088
VOID(printf("column: %3u type: %2u pack: %2u zero: %4u lbits: %2u "
2089
"tree: %2u length: %4u\n", i , counts->field_type,
2090
counts->pack_type, counts->max_zero_fill, counts->length_bits,
2091
counts->tree->tree_number, counts->field_length));
2097
/* Write all huff_trees to new datafile. Return tot count of
2098
elements in all trees
2099
Returns 0 on error */
2101
static my_off_t write_huff_tree(HUFF_TREE *huff_tree, uint trees)
2107
uint *packed_tree,*offset,length;
2110
/* Find the highest number of elements in the trees. */
2111
for (i=length=0 ; i < trees ; i++)
2112
if (huff_tree[i].tree_number > 0 && huff_tree[i].elements > length)
2113
length=huff_tree[i].elements;
2115
Allocate a buffer for packing a decode tree. Two numbers per element
2116
(left child and right child).
2118
if (!(packed_tree=(uint*) my_alloca(sizeof(uint)*length*2)))
2120
my_error(EE_OUTOFMEMORY,MYF(ME_BELL),sizeof(uint)*length*2);
2124
DBUG_PRINT("info", (" "));
2129
for (elements=0; trees-- ; huff_tree++)
2131
/* Skip columns that have been joined with other columns. */
2132
if (huff_tree->tree_number == 0)
2133
continue; /* Deleted tree */
2135
DBUG_PRINT("info", (" "));
2138
/* Count the total number of elements (byte codes or column values). */
2139
elements+=huff_tree->elements;
2140
huff_tree->max_offset=2;
2141
/* Build a tree of offsets and codes for decoding in 'packed_tree'. */
2142
if (huff_tree->elements <= 1)
2145
offset=make_offset_code_tree(huff_tree,huff_tree->root,packed_tree);
2147
/* This should be the same as 'length' above. */
2148
huff_tree->offset_bits=max_bit(huff_tree->max_offset);
2151
Since we check this during collecting the distinct column values,
2152
this should never happen.
2154
if (huff_tree->max_offset >= IS_OFFSET)
2155
{ /* This should be impossible */
2156
VOID(fprintf(stderr, "Tree offset got too big: %d, aborted\n",
2157
huff_tree->max_offset));
2158
my_afree((uchar*) packed_tree);
2162
DBUG_PRINT("info", ("pos: %lu elements: %u tree-elements: %lu "
2164
(ulong) (file_buffer.pos - file_buffer.buffer),
2165
huff_tree->elements, (ulong) (offset - packed_tree),
2166
huff_tree->char_bits));
2167
if (!huff_tree->counts->tree_buff)
2169
/* We do a byte compression on this column. Mark with bit 0. */
2171
write_bits(huff_tree->min_chr,8);
2172
write_bits(huff_tree->elements,9);
2173
write_bits(huff_tree->char_bits,5);
2174
write_bits(huff_tree->offset_bits,5);
2179
int_length=(uint) (huff_tree->counts->tree_pos -
2180
huff_tree->counts->tree_buff);
2181
/* We have distinct column values for this column. Mark with bit 1. */
2183
write_bits(huff_tree->elements,15);
2184
write_bits(int_length,16);
2185
write_bits(huff_tree->char_bits,5);
2186
write_bits(huff_tree->offset_bits,5);
2187
intervall_length+=int_length;
2189
DBUG_PRINT("info", ("tree: %2u elements: %4u char_bits: %2u "
2190
"offset_bits: %2u %s: %5u codelen: %2u",
2191
tree_no, huff_tree->elements, huff_tree->char_bits,
2192
huff_tree->offset_bits, huff_tree->counts->tree_buff ?
2193
"bufflen" : "min_chr", huff_tree->counts->tree_buff ?
2194
int_length : huff_tree->min_chr, huff_tree->height));
2196
VOID(printf("tree: %2u elements: %4u char_bits: %2u offset_bits: %2u "
2197
"%s: %5u codelen: %2u\n", tree_no, huff_tree->elements,
2198
huff_tree->char_bits, huff_tree->offset_bits,
2199
huff_tree->counts->tree_buff ? "bufflen" : "min_chr",
2200
huff_tree->counts->tree_buff ? int_length :
2201
huff_tree->min_chr, huff_tree->height));
2203
/* Check that the code tree length matches the element count. */
2204
length=(uint) (offset-packed_tree);
2205
if (length != huff_tree->elements*2-2)
2207
VOID(fprintf(stderr, "error: Huff-tree-length: %d != calc_length: %d\n",
2208
length, huff_tree->elements * 2 - 2));
2213
for (i=0 ; i < length ; i++)
2215
if (packed_tree[i] & IS_OFFSET)
2216
write_bits(packed_tree[i] - IS_OFFSET+ (1 << huff_tree->offset_bits),
2217
huff_tree->offset_bits+1);
2219
write_bits(packed_tree[i]-huff_tree->min_chr,huff_tree->char_bits+1);
2220
DBUG_PRINT("info", ("tree[0x%04x]: %s0x%04x",
2221
i, (packed_tree[i] & IS_OFFSET) ?
2222
" -> " : "", (packed_tree[i] & IS_OFFSET) ?
2223
packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
2225
VOID(printf("tree[0x%04x]: %s0x%04x\n",
2226
i, (packed_tree[i] & IS_OFFSET) ? " -> " : "",
2227
(packed_tree[i] & IS_OFFSET) ?
2228
packed_tree[i] - IS_OFFSET + i : packed_tree[i]));
2233
Display coding tables and check their correctness.
2235
codes= huff_tree->counts->tree_buff ? huff_tree->elements : 256;
2236
for (i= 0; i < codes; i++)
2243
if (! (len= huff_tree->code_len[i]))
2245
DBUG_PRINT("info", ("code[0x%04x]: 0x%s bits: %2u bin: %s", i,
2246
hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
2247
bindigits(huff_tree->code[i],
2248
huff_tree->code_len[i])));
2250
VOID(printf("code[0x%04x]: 0x%s bits: %2u bin: %s\n", i,
2251
hexdigits(huff_tree->code[i]), huff_tree->code_len[i],
2252
bindigits(huff_tree->code[i], huff_tree->code_len[i])));
2254
/* Check that the encode table decodes correctly. */
2258
DBUG_EXECUTE_IF("forcechkerr1", len--;);
2259
DBUG_EXECUTE_IF("forcechkerr2", bits= 8 * sizeof(code););
2260
DBUG_EXECUTE_IF("forcechkerr3", idx= length;);
2265
VOID(fflush(stdout));
2266
VOID(fprintf(stderr, "error: code 0x%s with %u bits not found\n",
2267
hexdigits(huff_tree->code[i]), huff_tree->code_len[i]));
2272
code|= (huff_tree->code[i] >> (--len)) & 1;
2274
if (bits > 8 * sizeof(code))
2276
VOID(fflush(stdout));
2277
VOID(fprintf(stderr, "error: Huffman code too long: %u/%u\n",
2278
bits, (uint) (8 * sizeof(code))));
2282
idx+= (uint) code & 1;
2285
VOID(fflush(stdout));
2286
VOID(fprintf(stderr, "error: illegal tree offset: %u/%u\n",
2291
if (packed_tree[idx] & IS_OFFSET)
2292
idx+= packed_tree[idx] & ~IS_OFFSET;
2294
break; /* Hit a leaf. This contains the result value. */
2299
DBUG_EXECUTE_IF("forcechkerr4", packed_tree[idx]++;);
2300
if (packed_tree[idx] != i)
2302
VOID(fflush(stdout));
2303
VOID(fprintf(stderr, "error: decoded value 0x%04x should be: 0x%04x\n",
2304
packed_tree[idx], i));
2308
} /*end for (codes)*/
2312
/* Write column values in case of distinct column value compression. */
2313
if (huff_tree->counts->tree_buff)
2315
for (i=0 ; i < int_length ; i++)
2317
write_bits((uint64_t) (uchar) huff_tree->counts->tree_buff[i], 8);
2318
DBUG_PRINT("info", ("column_values[0x%04x]: 0x%02x",
2319
i, (uchar) huff_tree->counts->tree_buff[i]));
2321
VOID(printf("column_values[0x%04x]: 0x%02x\n",
2322
i, (uchar) huff_tree->counts->tree_buff[i]));
2327
DBUG_PRINT("info", (" "));
2330
my_afree((uchar*) packed_tree);
2333
VOID(fprintf(stderr, "Error: Generated decode trees are corrupt. Stop.\n"));
2340
static uint *make_offset_code_tree(HUFF_TREE *huff_tree, HUFF_ELEMENT *element,
2345
prev_offset= offset;
2347
'a.leaf.null' takes the same place as 'a.nod.left'. If this is null,
2348
then there is no left child and, hence no right child either. This
2349
is a property of a binary tree. An element is either a node with two
2350
childs, or a leaf without childs.
2352
The current element is always a node with two childs. Go left first.
2354
if (!element->a.nod.left->a.leaf.null)
2356
/* Store the byte code or the index of the column value. */
2357
prev_offset[0] =(uint) element->a.nod.left->a.leaf.element_nr;
2363
Recursively traverse the tree to the left. Mark it as an offset to
2364
another tree node (in contrast to a byte code or column value index).
2366
prev_offset[0]= IS_OFFSET+2;
2367
offset=make_offset_code_tree(huff_tree,element->a.nod.left,offset+2);
2370
/* Now, check the right child. */
2371
if (!element->a.nod.right->a.leaf.null)
2373
/* Store the byte code or the index of the column value. */
2374
prev_offset[1]=element->a.nod.right->a.leaf.element_nr;
2380
Recursively traverse the tree to the right. Mark it as an offset to
2381
another tree node (in contrast to a byte code or column value index).
2383
uint temp=(uint) (offset-prev_offset-1);
2384
prev_offset[1]= IS_OFFSET+ temp;
2385
if (huff_tree->max_offset < temp)
2386
huff_tree->max_offset = temp;
2387
return make_offset_code_tree(huff_tree,element->a.nod.right,offset);
2391
/* Get number of bits neaded to represent value */
2393
static uint max_bit(register uint value)
2395
register uint power=1;
2403
static int compress_isam_file(PACK_MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
2406
uint i,max_calc_length,pack_ref_length,min_record_length,max_record_length,
2407
intervall,field_length,max_pack_length,pack_blob_length;
2408
my_off_t record_count;
2410
ulong length,pack_length;
2411
uchar *record,*pos,*end_pos,*record_pos,*start_pos;
2412
HUFF_COUNTS *count,*end_count;
2414
MI_INFO *isam_file=mrg->file[0];
2415
uint pack_version= (uint) isam_file->s->pack.version;
2416
DBUG_ENTER("compress_isam_file");
2418
/* Allocate a buffer for the records (excluding blobs). */
2419
if (!(record=(uchar*) my_alloca(isam_file->s->base.reclength)))
2422
end_count=huff_counts+isam_file->s->base.fields;
2423
min_record_length= (uint) ~0;
2424
max_record_length=0;
2427
Calculate the maximum number of bits required to pack the records.
2428
Remember to understand 'max_zero_fill' as 'min_zero_fill'.
2429
The tree height determines the maximum number of bits per value.
2430
Some fields skip leading or trailing spaces or zeroes. The skipped
2431
number of bytes is encoded by 'length_bits' bits.
2432
Empty blobs and varchar are encoded with a single 1 bit. Other blobs
2433
and varchar get a leading 0 bit.
2435
for (i=max_calc_length=0 ; i < isam_file->s->base.fields ; i++)
2437
if (!(huff_counts[i].pack_type & PACK_TYPE_ZERO_FILL))
2438
huff_counts[i].max_zero_fill=0;
2439
if (huff_counts[i].field_type == FIELD_CONSTANT ||
2440
huff_counts[i].field_type == FIELD_ZERO ||
2441
huff_counts[i].field_type == FIELD_CHECK)
2443
if (huff_counts[i].field_type == FIELD_INTERVALL)
2444
max_calc_length+=huff_counts[i].tree->height;
2445
else if (huff_counts[i].field_type == FIELD_BLOB ||
2446
huff_counts[i].field_type == FIELD_VARCHAR)
2447
max_calc_length+=huff_counts[i].tree->height*huff_counts[i].max_length + huff_counts[i].length_bits +1;
2450
(huff_counts[i].field_length - huff_counts[i].max_zero_fill)*
2451
huff_counts[i].tree->height+huff_counts[i].length_bits;
2453
max_calc_length= (max_calc_length + 7) / 8;
2454
pack_ref_length= calc_pack_length(pack_version, max_calc_length);
2456
/* 'max_blob_length' is the max length of all blobs of a record. */
2457
pack_blob_length= isam_file->s->base.blobs ?
2458
calc_pack_length(pack_version, mrg->max_blob_length) : 0;
2459
max_pack_length=pack_ref_length+pack_blob_length;
2461
DBUG_PRINT("fields", ("==="));
2463
while ((error=mrg_rrnd(mrg,record)) != HA_ERR_END_OF_FILE)
2465
ulong tot_blob_length=0;
2468
if (flush_buffer((ulong) max_calc_length + (ulong) max_pack_length))
2470
record_pos= (uchar*) file_buffer.pos;
2471
file_buffer.pos+=max_pack_length;
2472
for (start_pos=record, count= huff_counts; count < end_count ; count++)
2474
end_pos=start_pos+(field_length=count->field_length);
2477
DBUG_PRINT("fields", ("column: %3lu type: %2u pack: %2u zero: %4u "
2478
"lbits: %2u tree: %2u length: %4u",
2479
(ulong) (count - huff_counts + 1),
2481
count->pack_type, count->max_zero_fill,
2482
count->length_bits, count->tree->tree_number,
2483
count->field_length));
2485
/* Check if the column contains spaces only. */
2486
if (count->pack_type & PACK_TYPE_SPACE_FIELDS)
2488
for (pos=start_pos ; *pos == ' ' && pos < end_pos; pos++) ;
2491
DBUG_PRINT("fields",
2492
("PACK_TYPE_SPACE_FIELDS spaces only, bits: 1"));
2493
DBUG_PRINT("fields", ("---"));
2498
DBUG_PRINT("fields",
2499
("PACK_TYPE_SPACE_FIELDS not only spaces, bits: 1"));
2502
end_pos-=count->max_zero_fill;
2503
field_length-=count->max_zero_fill;
2505
switch (count->field_type) {
2506
case FIELD_SKIP_ZERO:
2507
if (!memcmp((uchar*) start_pos,zero_string,field_length))
2509
DBUG_PRINT("fields", ("FIELD_SKIP_ZERO zeroes only, bits: 1"));
2514
DBUG_PRINT("fields", ("FIELD_SKIP_ZERO not only zeroes, bits: 1"));
2518
DBUG_PRINT("fields", ("FIELD_NORMAL %lu bytes",
2519
(ulong) (end_pos - start_pos)));
2520
for ( ; start_pos < end_pos ; start_pos++)
2522
DBUG_PRINT("fields",
2523
("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2525
hexdigits(tree->code[(uchar) *start_pos]),
2526
(uint) tree->code_len[(uchar) *start_pos],
2527
bindigits(tree->code[(uchar) *start_pos],
2528
(uint) tree->code_len[(uchar) *start_pos])));
2529
write_bits(tree->code[(uchar) *start_pos],
2530
(uint) tree->code_len[(uchar) *start_pos]);
2533
case FIELD_SKIP_ENDSPACE:
2534
for (pos=end_pos ; pos > start_pos && pos[-1] == ' ' ; pos--) ;
2535
length= (ulong) (end_pos - pos);
2536
if (count->pack_type & PACK_TYPE_SELECTED)
2538
if (length > count->min_space)
2540
DBUG_PRINT("fields",
2541
("FIELD_SKIP_ENDSPACE more than min_space, bits: 1"));
2542
DBUG_PRINT("fields",
2543
("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
2544
length, field_length, count->length_bits));
2546
write_bits(length,count->length_bits);
2550
DBUG_PRINT("fields",
2551
("FIELD_SKIP_ENDSPACE not more than min_space, "
2559
DBUG_PRINT("fields",
2560
("FIELD_SKIP_ENDSPACE skip %lu/%u bytes, bits: %2u",
2561
length, field_length, count->length_bits));
2562
write_bits(length,count->length_bits);
2564
/* Encode all significant bytes. */
2565
DBUG_PRINT("fields", ("FIELD_SKIP_ENDSPACE %lu bytes",
2566
(ulong) (pos - start_pos)));
2567
for ( ; start_pos < pos ; start_pos++)
2569
DBUG_PRINT("fields",
2570
("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2572
hexdigits(tree->code[(uchar) *start_pos]),
2573
(uint) tree->code_len[(uchar) *start_pos],
2574
bindigits(tree->code[(uchar) *start_pos],
2575
(uint) tree->code_len[(uchar) *start_pos])));
2576
write_bits(tree->code[(uchar) *start_pos],
2577
(uint) tree->code_len[(uchar) *start_pos]);
2581
case FIELD_SKIP_PRESPACE:
2582
for (pos=start_pos ; pos < end_pos && pos[0] == ' ' ; pos++) ;
2583
length= (ulong) (pos - start_pos);
2584
if (count->pack_type & PACK_TYPE_SELECTED)
2586
if (length > count->min_space)
2588
DBUG_PRINT("fields",
2589
("FIELD_SKIP_PRESPACE more than min_space, bits: 1"));
2590
DBUG_PRINT("fields",
2591
("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
2592
length, field_length, count->length_bits));
2594
write_bits(length,count->length_bits);
2598
DBUG_PRINT("fields",
2599
("FIELD_SKIP_PRESPACE not more than min_space, "
2607
DBUG_PRINT("fields",
2608
("FIELD_SKIP_PRESPACE skip %lu/%u bytes, bits: %2u",
2609
length, field_length, count->length_bits));
2610
write_bits(length,count->length_bits);
2612
/* Encode all significant bytes. */
2613
DBUG_PRINT("fields", ("FIELD_SKIP_PRESPACE %lu bytes",
2614
(ulong) (end_pos - start_pos)));
2615
for (start_pos=pos ; start_pos < end_pos ; start_pos++)
2617
DBUG_PRINT("fields",
2618
("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2620
hexdigits(tree->code[(uchar) *start_pos]),
2621
(uint) tree->code_len[(uchar) *start_pos],
2622
bindigits(tree->code[(uchar) *start_pos],
2623
(uint) tree->code_len[(uchar) *start_pos])));
2624
write_bits(tree->code[(uchar) *start_pos],
2625
(uint) tree->code_len[(uchar) *start_pos]);
2628
case FIELD_CONSTANT:
2631
DBUG_PRINT("fields", ("FIELD_CONSTANT/ZERO/CHECK"));
2634
case FIELD_INTERVALL:
2636
pos=(uchar*) tree_search(&count->int_tree, start_pos,
2637
count->int_tree.custom_arg);
2638
intervall=(uint) (pos - count->tree_buff)/field_length;
2639
DBUG_PRINT("fields", ("FIELD_INTERVALL"));
2640
DBUG_PRINT("fields", ("index: %4u code: 0x%s bits: %2u",
2641
intervall, hexdigits(tree->code[intervall]),
2642
(uint) tree->code_len[intervall]));
2643
write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
2648
ulong blob_length=_mi_calc_blob_length(field_length-
2649
portable_sizeof_char_ptr,
2651
/* Empty blobs are encoded with a single 1 bit. */
2654
DBUG_PRINT("fields", ("FIELD_BLOB empty, bits: 1"));
2659
uchar *blob,*blob_end;
2660
DBUG_PRINT("fields", ("FIELD_BLOB not empty, bits: 1"));
2662
/* Write the blob length. */
2663
DBUG_PRINT("fields", ("FIELD_BLOB %lu bytes, bits: %2u",
2664
blob_length, count->length_bits));
2665
write_bits(blob_length,count->length_bits);
2666
memcpy_fixed(&blob,end_pos-portable_sizeof_char_ptr,
2668
blob_end=blob+blob_length;
2669
/* Encode the blob bytes. */
2670
for ( ; blob < blob_end ; blob++)
2672
DBUG_PRINT("fields",
2673
("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2674
(uchar) *blob, hexdigits(tree->code[(uchar) *blob]),
2675
(uint) tree->code_len[(uchar) *blob],
2676
bindigits(tree->code[(uchar) *start_pos],
2677
(uint)tree->code_len[(uchar) *start_pos])));
2678
write_bits(tree->code[(uchar) *blob],
2679
(uint) tree->code_len[(uchar) *blob]);
2681
tot_blob_length+=blob_length;
2688
uint var_pack_length= HA_VARCHAR_PACKLENGTH(count->field_length-1);
2689
ulong col_length= (var_pack_length == 1 ?
2690
(uint) *(uchar*) start_pos :
2691
uint2korr(start_pos));
2692
/* Empty varchar are encoded with a single 1 bit. */
2695
DBUG_PRINT("fields", ("FIELD_VARCHAR empty, bits: 1"));
2696
write_bits(1,1); /* Empty varchar */
2700
uchar *end= start_pos + var_pack_length + col_length;
2701
DBUG_PRINT("fields", ("FIELD_VARCHAR not empty, bits: 1"));
2703
/* Write the varchar length. */
2704
DBUG_PRINT("fields", ("FIELD_VARCHAR %lu bytes, bits: %2u",
2705
col_length, count->length_bits));
2706
write_bits(col_length,count->length_bits);
2707
/* Encode the varchar bytes. */
2708
for (start_pos+= var_pack_length ; start_pos < end ; start_pos++)
2710
DBUG_PRINT("fields",
2711
("value: 0x%02x code: 0x%s bits: %2u bin: %s",
2713
hexdigits(tree->code[(uchar) *start_pos]),
2714
(uint) tree->code_len[(uchar) *start_pos],
2715
bindigits(tree->code[(uchar) *start_pos],
2716
(uint)tree->code_len[(uchar) *start_pos])));
2717
write_bits(tree->code[(uchar) *start_pos],
2718
(uint) tree->code_len[(uchar) *start_pos]);
2725
case FIELD_enum_val_count:
2726
abort(); /* Impossible */
2728
start_pos+=count->max_zero_fill;
2729
DBUG_PRINT("fields", ("---"));
2732
length=(ulong) ((uchar*) file_buffer.pos - record_pos) - max_pack_length;
2733
pack_length= save_pack_length(pack_version, record_pos, length);
2734
if (pack_blob_length)
2735
pack_length+= save_pack_length(pack_version, record_pos + pack_length,
2737
DBUG_PRINT("fields", ("record: %lu length: %lu blob-length: %lu "
2738
"length-bytes: %lu", (ulong) record_count, length,
2739
tot_blob_length, pack_length));
2740
DBUG_PRINT("fields", ("==="));
2742
/* Correct file buffer if the header was smaller */
2743
if (pack_length != max_pack_length)
2745
bmove(record_pos+pack_length,record_pos+max_pack_length,length);
2746
file_buffer.pos-= (max_pack_length-pack_length);
2748
if (length < (ulong) min_record_length)
2749
min_record_length=(uint) length;
2750
if (length > (ulong) max_record_length)
2751
max_record_length=(uint) length;
2753
if (write_loop && record_count % WRITE_COUNT == 0)
2755
VOID(printf("%lu\r", (ulong) record_count));
2756
VOID(fflush(stdout));
2759
else if (error != HA_ERR_RECORD_DELETED)
2762
if (error == HA_ERR_END_OF_FILE)
2766
VOID(fprintf(stderr, "%s: Got error %d reading records\n",
2767
my_progname, error));
2770
VOID(printf("wrote %s records.\n", llstr((int64_t) record_count, llbuf)));
2772
my_afree((uchar*) record);
2773
mrg->ref_length=max_pack_length;
2774
mrg->min_pack_length=max_record_length ? min_record_length : 0;
2775
mrg->max_pack_length=max_record_length;
2776
DBUG_RETURN(error || error_on_write || flush_buffer(~(ulong) 0));
2780
static char *make_new_name(char *new_name, char *old_name)
2782
return fn_format(new_name,old_name,"",DATA_TMP_EXT,2+4);
2785
static char *make_old_name(char *new_name, char *old_name)
2787
return fn_format(new_name,old_name,"",OLD_EXT,2+4);
2790
/* rutines for bit writing buffer */
2792
static void init_file_buffer(File file, bool read_buffer)
2794
file_buffer.file=file;
2795
file_buffer.buffer= (uchar*) my_malloc(ALIGN_SIZE(RECORD_CACHE_SIZE),
2797
file_buffer.end=file_buffer.buffer+ALIGN_SIZE(RECORD_CACHE_SIZE)-8;
2798
file_buffer.pos_in_file=0;
2803
file_buffer.pos=file_buffer.end;
2808
file_buffer.pos=file_buffer.buffer;
2809
file_buffer.bits=BITS_SAVED;
2811
file_buffer.bitbucket= 0;
2815
static int flush_buffer(ulong neaded_length)
2820
file_buffer.end is 8 bytes lower than the real end of the buffer.
2821
This is done so that the end-of-buffer condition does not need to be
2822
checked for every byte (see write_bits()). Consequently,
2823
file_buffer.pos can become greater than file_buffer.end. The
2824
algorithms in the other functions ensure that there will never be
2825
more than 8 bytes written to the buffer without an end-of-buffer
2826
check. So the buffer cannot be overrun. But we need to check for the
2827
near-to-buffer-end condition to avoid a negative result, which is
2828
casted to unsigned and thus becomes giant.
2830
if ((file_buffer.pos < file_buffer.end) &&
2831
((ulong) (file_buffer.end - file_buffer.pos) > neaded_length))
2833
length=(ulong) (file_buffer.pos-file_buffer.buffer);
2834
file_buffer.pos=file_buffer.buffer;
2835
file_buffer.pos_in_file+=length;
2838
if (error_on_write|| my_write(file_buffer.file,
2839
(const uchar*) file_buffer.buffer,
2841
MYF(MY_WME | MY_NABP | MY_WAIT_IF_FULL)))
2847
if (neaded_length != ~(ulong) 0 &&
2848
(ulong) (file_buffer.end-file_buffer.buffer) < neaded_length)
2851
neaded_length+=256; /* some margin */
2852
tmp= my_realloc((char*) file_buffer.buffer, neaded_length,MYF(MY_WME));
2855
file_buffer.pos= ((uchar*) tmp +
2856
(ulong) (file_buffer.pos - file_buffer.buffer));
2857
file_buffer.buffer= (uchar*) tmp;
2858
file_buffer.end= (uchar*) (tmp+neaded_length-8);
2864
static void end_file_buffer(void)
2866
my_free((uchar*) file_buffer.buffer,MYF(0));
2869
/* output `bits` low bits of `value' */
2871
static void write_bits(register uint64_t value, register uint bits)
2873
DBUG_ASSERT(((bits < 8 * sizeof(value)) && ! (value >> bits)) ||
2874
(bits == 8 * sizeof(value)));
2876
if ((file_buffer.bits-= (int) bits) >= 0)
2878
file_buffer.bitbucket|= value << file_buffer.bits;
2882
register uint64_t bit_buffer;
2883
bits= (uint) -file_buffer.bits;
2884
bit_buffer= (file_buffer.bitbucket |
2885
((bits != 8 * sizeof(value)) ? (value >> bits) : 0));
2886
#if BITS_SAVED == 64
2887
*file_buffer.pos++= (uchar) (bit_buffer >> 56);
2888
*file_buffer.pos++= (uchar) (bit_buffer >> 48);
2889
*file_buffer.pos++= (uchar) (bit_buffer >> 40);
2890
*file_buffer.pos++= (uchar) (bit_buffer >> 32);
2892
*file_buffer.pos++= (uchar) (bit_buffer >> 24);
2893
*file_buffer.pos++= (uchar) (bit_buffer >> 16);
2894
*file_buffer.pos++= (uchar) (bit_buffer >> 8);
2895
*file_buffer.pos++= (uchar) (bit_buffer);
2897
if (bits != 8 * sizeof(value))
2898
value&= (((uint64_t) 1) << bits) - 1;
2899
if (file_buffer.pos >= file_buffer.end)
2900
VOID(flush_buffer(~ (ulong) 0));
2901
file_buffer.bits=(int) (BITS_SAVED - bits);
2902
file_buffer.bitbucket= value << (BITS_SAVED - bits);
2907
/* Flush bits in bit_buffer to buffer */
2909
static void flush_bits(void)
2912
uint64_t bit_buffer;
2914
bits= file_buffer.bits & ~7;
2915
bit_buffer= file_buffer.bitbucket >> bits;
2916
bits= BITS_SAVED - bits;
2920
*file_buffer.pos++= (uchar) (bit_buffer >> bits);
2922
if (file_buffer.pos >= file_buffer.end)
2923
VOID(flush_buffer(~ (ulong) 0));
2924
file_buffer.bits= BITS_SAVED;
2925
file_buffer.bitbucket= 0;
2929
/****************************************************************************
2930
** functions to handle the joined files
2931
****************************************************************************/
2933
static int save_state(MI_INFO *isam_file,PACK_MRG_INFO *mrg,my_off_t new_length,
2936
MYISAM_SHARE *share=isam_file->s;
2937
uint options=mi_uint2korr(share->state.header.options);
2939
DBUG_ENTER("save_state");
2941
options|= HA_OPTION_COMPRESS_RECORD | HA_OPTION_READ_ONLY_DATA;
2942
mi_int2store(share->state.header.options,options);
2944
share->state.state.data_file_length=new_length;
2945
share->state.state.del=0;
2946
share->state.state.empty=0;
2947
share->state.dellink= HA_OFFSET_ERROR;
2948
share->state.split=(ha_rows) mrg->records;
2949
share->state.version=(ulong) time((time_t*) 0);
2950
if (! mi_is_all_keys_active(share->state.key_map, share->base.keys))
2953
Some indexes are disabled, cannot use current key_file_length value
2954
as an estimate of upper bound of index file size. Use packed data file
2957
share->state.state.key_file_length= new_length;
2960
If there are no disabled indexes, keep key_file_length value from
2961
original file so "myisamchk -rq" can use this value (this is necessary
2962
because index size cannot be easily calculated for fulltext keys)
2964
mi_clear_all_keys_active(share->state.key_map);
2965
for (key=0 ; key < share->base.keys ; key++)
2966
share->state.key_root[key]= HA_OFFSET_ERROR;
2967
for (key=0 ; key < share->state.header.max_block_size_index ; key++)
2968
share->state.key_del[key]= HA_OFFSET_ERROR;
2969
isam_file->state->checksum=crc; /* Save crc here */
2970
share->changed=1; /* Force write of header */
2971
share->state.open_count=0;
2972
share->global_changed=0;
2973
(void)ftruncate(share->kfile, share->base.keystart);
2974
if (share->base.keys)
2976
DBUG_RETURN(mi_state_info_write(share->kfile,&share->state,1+2));
2980
static int save_state_mrg(File file,PACK_MRG_INFO *mrg,my_off_t new_length,
2983
MI_STATE_INFO state;
2984
MI_INFO *isam_file=mrg->file[0];
2986
DBUG_ENTER("save_state_mrg");
2988
state= isam_file->s->state;
2989
options= (mi_uint2korr(state.header.options) | HA_OPTION_COMPRESS_RECORD |
2990
HA_OPTION_READ_ONLY_DATA);
2991
mi_int2store(state.header.options,options);
2992
state.state.data_file_length=new_length;
2994
state.state.empty=0;
2995
state.state.records=state.split=(ha_rows) mrg->records;
2996
/* See comment above in save_state about key_file_length handling. */
2997
if (mrg->src_file_has_indexes_disabled)
2999
isam_file->s->state.state.key_file_length=
3000
max(isam_file->s->state.state.key_file_length, new_length);
3002
state.dellink= HA_OFFSET_ERROR;
3003
state.version=(ulong) time((time_t*) 0);
3004
mi_clear_all_keys_active(state.key_map);
3005
state.state.checksum=crc;
3006
if (isam_file->s->base.keys)
3008
state.changed=STATE_CHANGED | STATE_NOT_ANALYZED; /* Force check of table */
3009
DBUG_RETURN (mi_state_info_write(file,&state,1+2));
3013
/* reset for mrg_rrnd */
3015
static void mrg_reset(PACK_MRG_INFO *mrg)
3019
mi_extra(*mrg->current, HA_EXTRA_NO_CACHE, 0);
3024
static int mrg_rrnd(PACK_MRG_INFO *info,uchar *buf)
3032
isam_info= *(info->current=info->file);
3033
info->end=info->current+info->count;
3034
mi_reset(isam_info);
3035
mi_extra(isam_info, HA_EXTRA_CACHE, 0);
3036
filepos=isam_info->s->pack.header_length;
3040
isam_info= *info->current;
3041
filepos= isam_info->nextpos;
3046
isam_info->update&= HA_STATE_CHANGED;
3047
if (!(error=(*isam_info->s->read_rnd)(isam_info,(uchar*) buf,
3049
error != HA_ERR_END_OF_FILE)
3051
mi_extra(isam_info,HA_EXTRA_NO_CACHE, 0);
3052
if (info->current+1 == info->end)
3053
return(HA_ERR_END_OF_FILE);
3055
isam_info= *info->current;
3056
filepos=isam_info->s->pack.header_length;
3057
mi_reset(isam_info);
3058
mi_extra(isam_info,HA_EXTRA_CACHE, 0);
3063
static int mrg_close(PACK_MRG_INFO *mrg)
3067
for (i=0 ; i < mrg->count ; i++)
3068
error|=mi_close(mrg->file[i]);
3070
my_free((uchar*) mrg->file,MYF(0));
3075
#if !defined(DBUG_OFF)
3077
Fake the counts to get big Huffman codes.
3081
huff_counts A pointer to the counts array.
3082
end_count A pointer past the counts array.
3086
Huffman coding works by removing the two least frequent values from
3087
the list of values and add a new value with the sum of their
3088
incidences in a loop until only one value is left. Every time a
3089
value is reused for a new value, it gets one more bit for its
3090
encoding. Hence, the least frequent values get the longest codes.
3092
To get a maximum code length for a value, two of the values must
3093
have an incidence of 1. As their sum is 2, the next infrequent value
3094
must have at least an incidence of 2, then 4, 8, 16 and so on. This
3095
means that one needs 2**n bytes (values) for a code length of n
3096
bits. However, using more distinct values forces the use of longer
3097
codes, or reaching the code length with less total bytes (values).
3099
To get 64(32)-bit codes, I sort the counts by decreasing incidence.
3100
I assign counts of 1 to the two most frequent values, a count of 2
3101
for the next one, then 4, 8, and so on until 2**64-1(2**30-1). All
3102
the remaining values get 1. That way every possible byte has an
3103
assigned code, though not all codes are used if not all byte values
3104
are present in the column.
3106
This strategy would work with distinct column values too, but
3107
requires that at least 64(32) values are present. To make things
3108
easier here, I cancel all distinct column values and force byte
3109
compression for all columns.
3115
static void fakebigcodes(HUFF_COUNTS *huff_counts, HUFF_COUNTS *end_count)
3118
my_off_t *cur_count_p;
3119
my_off_t *end_count_p;
3120
my_off_t **cur_sort_p;
3121
my_off_t **end_sort_p;
3122
my_off_t *sort_counts[256];
3124
DBUG_ENTER("fakebigcodes");
3126
for (count= huff_counts; count < end_count; count++)
3129
Remove distinct column values.
3131
if (huff_counts->tree_buff)
3133
my_free((uchar*) huff_counts->tree_buff, MYF(0));
3134
delete_tree(&huff_counts->int_tree);
3135
huff_counts->tree_buff= NULL;
3136
DBUG_PRINT("fakebigcodes", ("freed distinct column values"));
3140
Sort counts by decreasing incidence.
3142
cur_count_p= count->counts;
3143
end_count_p= cur_count_p + 256;
3144
cur_sort_p= sort_counts;
3145
while (cur_count_p < end_count_p)
3146
*(cur_sort_p++)= cur_count_p++;
3147
(void) my_qsort(sort_counts, 256, sizeof(my_off_t*), (qsort_cmp) fakecmp);
3150
Assign faked counts.
3152
cur_sort_p= sort_counts;
3153
#if SIZEOF_LONG_LONG > 4
3154
end_sort_p= sort_counts + 8 * sizeof(uint64_t) - 1;
3156
end_sort_p= sort_counts + 8 * sizeof(uint64_t) - 2;
3158
/* Most frequent value gets a faked count of 1. */
3159
**(cur_sort_p++)= 1;
3161
while (cur_sort_p < end_sort_p)
3163
**(cur_sort_p++)= total;
3166
/* Set the last value. */
3167
**(cur_sort_p++)= --total;
3169
Set the remaining counts.
3171
end_sort_p= sort_counts + 256;
3172
while (cur_sort_p < end_sort_p)
3173
**(cur_sort_p++)= 1;
3180
Compare two counts for reverse sorting.
3185
count2 Another count.
3193
static int fakecmp(my_off_t **count1, my_off_t **count2)
3195
return ((**count1 < **count2) ? 1 :
3196
(**count1 > **count2) ? -1 : 0);
added
removed
storage/myisam/myisampack.c
