cde/programs/dtinfo/DtMmdb/dynhash/bucket.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: bucket.h /main/3 1996/06/11 17:19:00 cde-hal $
  25  *
  26  * Copyright (c) 1992 HaL Computer Systems, Inc.  All rights reserved.
  27  * UNPUBLISHED -- rights reserved under the Copyright Laws of the United
  28  * States.  Use of a copyright notice is precautionary only and does not
  29  * imply publication or disclosure.
  30  *
  31  * This software contains confidential information and trade secrets of HaL
  32  * Computer Systems, Inc.  Use, disclosure, or reproduction is prohibited
  33  * without the prior express written permission of HaL Computer Systems, Inc.
  34  *
  35  *                         RESTRICTED RIGHTS LEGEND
  36  * Use, duplication, or disclosure by the Government is subject to
  37  * restrictions as set forth in subparagraph (c)(l)(ii) of the Rights in
  38  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  39  *                        HaL Computer Systems, Inc.
  40  *                  1315 Dell Avenue, Campbell, CA  95008
  41  *
  42  */
  43
  44
  45 /***************************************************************/
  46 //
  47 //Implementation of the dynamic perfect hashing algorithm, based on:
  48 //
  49 //         "Dynamic Perfect Hashing: Upper and Lower Bounds"
  50 //
  51 //                                By
  52 //
  53 //        M. Dietzfelbinger, A. Karlin, K. Mehlhorn,
  54 //        F. Meyer auf der Heider, H.  Rohnert and
  55 //        R. E. Tarjan
  56 //                            appearing in
  57 //
  58 //                             1988 FOCS.
  59 //
  60 /***************************************************************/
  61
  62
  63 /***************************************************************/
  64 // Programmer: QiFan Chen
  65 // Date: June 14, 1992
  66 // Language: C++ (2.0)
  67 // Machine: SUN SPARCstation IPC
  68 /***************************************************************/
  69
  70 #ifndef _bucket_h
  71 #define _bucket_h
  72
  73 #include "utility/funcs.h"
  74 #include "utility/prandom.h"
  75 #include "dynhash/data.h"
  76
  77
  78 /**************************************************************/
  79 // define a data object that is shared by the first
  80 // and the second level hash functions
  81 /**************************************************************/
  82
  83 struct shared_t {
  84    prandom rand_generator;  // rand generator
  85    int p;                   // prime number p
  86    int sum;                 // the value of the lhs of condition 4
  87    int limit;               // the value of the rhs of condition 4
  88    data_t* internal_L;      // the list representation
  89 };
  90
  91 /****************************/
  92 // A bucket object forms a
  93 // second level hash function
  94 /****************************/
  95 class bucket {
  96
  97 protected:
  98    static int upper_limit; // set to 2*Mj*Mj by first()
  99                            // for fast iteration
 100
 101    int k;                 // valye k used in H_{{2M_j}^2}()
 102    int Mj;                // size window
 103    int wj;                // keys in the bucket
 104    int old_wj;            // value of wj after a memory allocation
 105    data_tPtr data_array;  // key array
 106
 107    void rehash_all(data_t& dt, shared_t&); // rehash all keys
 108    void select_h_params(shared_t&);        // select the parameter k
 109
 110 public:
 111    bucket(int new_Mj, int old_wj);
 112    virtual ~bucket();
 113
 114    int h(int key, shared_t&);    //  hash function H_{{2M_j}^2}()
 115    int M_size() { return Mj; };  //  the value of Mj
 116    int wj_size() { return wj; }; //  the value of wj
 117
 118    Boolean insert(data_t& dt, shared_t&);  // insert a key
 119    Boolean remove(data_t& dt, shared_t&);  // remove a key
 120    Boolean member(data_t& dt, shared_t&);  // member test
 121
 122    int first();                 // iterate over all keys in
 123    data_t& operator()(int ind); // the bucket
 124    void next(int& ind);         // terminate condition: -1
 125
 126    friend ostream& operator<<(ostream&, bucket&);
 127 };
 128
 129 typedef bucket* bucketPtr;
 130
 131 #endif