cde/programs/dtinfo/DtMmdb/index/fast_mphf.h

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: fast_mphf.h /main/5 1996/07/18 14:36:28 drk $
  25  *
  26  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
  27  * All rights reserved.  Unpublished -- rights reserved under
  28  * the Copyright Laws of the United States.  USE OF A COPYRIGHT
  29  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
  30  * OR DISCLOSURE.
  31  *
  32  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  33  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  34  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  35  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  36  * INTERNATIONAL, LTD.
  37  *
  38  *                         RESTRICTED RIGHTS LEGEND
  39  * Use, duplication, or disclosure by the Government is subject
  40  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  41  * of the Rights in Technical Data and Computer Software clause
  42  * at DFARS 252.227-7013.
  43  *
  44  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  45  *                  1315 Dell Avenue
  46  *                  Campbell, CA  95008
  47  *
  48  */
  49
  50
  51 #ifndef _fast_mphf_h
  52 #define _fast_mphf_h 1
  53
  54 #include <sys/wait.h>
  55 #include "index/hash.h"
  56 #include "utility/atoi_pearson.h"
  57 #include "object/long_pstring.h"
  58 #include "utility/xtime.h"
  59 #include "hmphf/mphf_funcs.h"
  60 #include "hmphf/sorter.h"
  61
  62
  63 ///////////////////////////////////////////////////////////////
  64 // A fast MPHF contruct method proposed by Chen Qi Fan in 4/91.
  65 // Usually it will compute MPHFs using 2-3 bits/key.
  66 // Random number table size is reduced to 128 chars.
  67 // Computation is fast due to the pattern matching
  68 // used in the searching stage.
  69 //
  70 // Reference: VaTech Technical Report TR92-2, SIGIR92 paper.
  71 //
  72 // Modification:
  73 //              convert to mmdb version (task started on 9-15-92)
  74 ///////////////////////////////////////////////////////////////
  75
  76 class tbl_record
  77 {
  78
  79 public:
  80    int v_seed;
  81    atoi_pearson* v_tbl0;
  82    atoi_pearson* v_tbl1;
  83
  84 public:
  85    tbl_record(int sd = 0, atoi_pearson* t1 =0, atoi_pearson* t2 =0) :
  86         v_seed(sd), v_tbl0(t1), v_tbl1(t2) {};
  87    ~tbl_record();
  88 };
  89
  90 class tbl_cache
  91 {
  92 protected:
  93     void_ptr_array f_array;
  94
  95 public:
  96
  97    tbl_cache();
  98    ~tbl_cache();
  99
 100    void init_table(int hash_table_sz, int seed, atoi_pearson*&, atoi_pearson*&);
 101
 102    friend class fast_mphf;
 103 };
 104
 105 class fast_mphf : public long_pstring, public hash
 106 {
 107
 108 public:
 109
 110    fast_mphf(c_code_t = FAST_MPHF_CODE);
 111    virtual ~fast_mphf();
 112
 113    MMDB_SIGNATURES(fast_mphf);
 114
 115    void init_persistent_info(persistent_info*);
 116
 117
 118 // init the two ascii->integer map tables
 119    Boolean init_map_tbls();
 120
 121 // load the MPHF from files
 122    virtual io_status asciiIn(istream&);
 123
 124 // compute a hash value for a key.
 125    virtual int hashTo(const key_type&);
 126
 127 // compute a MPHF
 128    virtual Boolean build(const char* data_path);
 129    virtual Boolean build(istream& data_stream);
 130
 131 // show the mapping from keys to hash values and verify the mphf.
 132 // option = 0: no print, only check;
 133 // option = 1: print and check.
 134    void print_mapping( const char*key_file, int option = 0) ;
 135
 136    void print_gvalues(ostream&out = cerr) ;
 137
 138    virtual int cdr_sizeof();
 139    virtual io_status cdrOut(buffer&);
 140    virtual io_status cdrIn(buffer&);
 141
 142 protected:
 143
 144 // return the ith g value from the g array (in packed form)
 145    int gValue(int, int& gvalue, int& ctl_bit) ;
 146
 147    void print_tbls(ostream&out = cerr) ;
 148    int print_bits(unsigned, ostream& = cout);
 149
 150 protected:
 151
 152 #ifdef C_API
 153    static tbl_cache *v_tbl_cache_ptr;
 154 #else
 155    static tbl_cache v_tbl_cache;
 156 #endif
 157
 158    atoi_pearson *v_tbl0 ,  // table1
 159                 *v_tbl1 ;  // table2
 160
 161    Boolean v_long_string_core_indexed;
 162
 163    unsigned int v_no_ps,  // number of partitions (buckets)
 164                 v_p1, v_p2, // parameters p1 and p2.
 165                 r,
 166                 v_seed,
 167                 t;
 168
 169 };
 170
 171 HANDLER_SIGNATURES(fast_mphf)
 172
 173 #endif