cde/programs/dtinfo/DtMmdb/dynhash/imp_die.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: imp_die.h /main/3 1996/06/11 17:19:33 cde-hal $
  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
  52 #ifndef _imp_die_h
  53 #define _imp_die_h
  54
  55 #include "dstr/index_agent.h"
  56 #include "dynhash/imp_bucket.h"
  57
  58 /***************************************************************/
  59 //
  60 // An improved version of Dietzfelbinger etc.'s algorithm.
  61 //
  62 //             Goal: reducing the space consumption.
  63 //
  64 //                            By
  65 //
  66 //                  QiFan Chen  (June 24, 1992)
  67 //
  68 /***************************************************************/
  69
  70
  71 #define COLLISION_BIT 0x2
  72
  73 extern int steps[];
  74 extern int no_steps;
  75
  76 class bucket_holder {
  77
  78 public:
  79    data_t* data_ptr;
  80    bucket_holder *next;
  81
  82    bucket_holder() : data_ptr(0), next(0) {};
  83    virtual ~bucket_holder() {};
  84 };
  85
  86 //extern data_t bad_record;
  87
  88 class imp_die : public index_agent
  89 {
  90
  91 protected:
  92
  93    int k;        // parameter used in the 1st level hash function
  94    int p;        // prime number p
  95
  96    int H;        // current hash table size
  97    int B;        // current bucket table size
  98    int n;        // current key set size
  99
 100    imp_bucketPtr* bucket_array;    // bucket array
 101    data_tPtr* hash_table;   // the hash table
 102
 103    bucket_holder* free_list_head ;   // free bucket holder list head
 104    bucket_holder* collected_records; // collected bucket list head
 105
 106    pm_random rand_generator;         // rand generator
 107
 108    int h(int key) const;                 // h_{sM}() function
 109    void alloc_table(int new_M); // expand the hash tabel and bucket array
 110    void init_table();           // init hash table and bucket array
 111    void collect_all_keys();     // collect all keys into bcuket_list_head
 112    Boolean rehash();            // rehash all keys
 113
 114    Boolean bucket_insert(int bucket_num, data_t&);
 115    Boolean bucket_remove(int bucket_num, data_t&);
 116    Boolean bucket_member(int bucket_num, data_t&) const;
 117    Boolean bucket_rehash(int bucket_num) ;
 118
 119    Boolean bucket_fix_k(int bucket_num);
 120    Boolean bucket_rotate(int bucket_num);
 121    Boolean test_injective(imp_bucket& x);
 122
 123 public:
 124    imp_die(int prime = 32801, int expected_n = 100);
 125                                // prime and expected
 126                                // key set size
 127    virtual ~imp_die();
 128
 129    void clean() ; // remove all keys
 130
 131    Boolean insert(data_t& v);  // insert a key
 132    Boolean remove(data_t& v);  // remove a key
 133    Boolean member(data_t& v) {
 134       return bucket_member(v.bucket_num(k, p, B), v);
 135    }; // member test
 136
 137
 138    int no_keys() const { return n; }; // return key set size
 139
 140 // WARNING:  -1 is the terminate condition!!!
 141    int first_bucket();
 142    imp_bucket* get_bucket(int&);
 143    void next_bucket(int&);
 144
 145 // output this with print_f handling the printing of whole data_t.
 146 // pointer to data_t as voidd* is passed to print_f
 147    ostream& asciiOut(ostream& out, print_func_ptr_t print_f);
 148
 149    ostream& asciiOut(ostream& out);
 150    istream& asciiIn(istream& in);
 151 };
 152
 153 #endif
 154