cde/programs/dtinfo/DtMmdb/hmphf/mphf_hash_table.C

   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  * $TOG: mphf_hash_table.C /main/4 1998/04/17 11:50:23 mgreess $
  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 #include "hmphf/mphf_hash_table.h"
  52
  53 #define FULL 1
  54
  55 mphf_hash_table::mphf_hash_table(params& params_ptr) :
  56 v_no_slots(params_ptr.v_n), v_num_filled_slots(0)
  57 {
  58    v_rep = new char[v_no_slots];
  59    v_random_table = new int[v_no_slots];
  60    v_map_table = new int[v_no_slots];
  61
  62    clear();
  63 }
  64
  65 mphf_hash_table::~mphf_hash_table()
  66 {
  67    delete v_rep ;
  68    delete v_random_table ;
  69    delete v_map_table ;
  70 }
  71
  72 void mphf_hash_table::clear()
  73 {
  74    int i;
  75    //, right;
  76
  77    pm_random pm(19);
  78
  79    for ( i=0; i<v_no_slots; i++ ) {
  80       v_rep[i] = 0;
  81    }
  82
  83    for ( i=0; i<v_no_slots; i++ ) {
  84       v_random_table[i] = i;
  85    }
  86
  87    for ( i = 0; i < v_no_slots; i++) {
  88       //right = pm.rand() % ( v_no_slots - i) + i;
  89       int_swap( v_random_table[pm.rand() % ( v_no_slots - i) + i],
  90                 v_random_table[i]
  91               );
  92    }
  93
  94    for ( i = 0; i < v_no_slots; i++)
  95        v_map_table[v_random_table[i]] = i;
  96
  97    v_num_filled_slots = 0;
  98 }
  99
 100
 101 int mphf_hash_table::fast_fit(int_pattern& pat)
 102 {
 103    int ok;
 104    int i, j, alignment, landing_slot;
 105    int right_rdm_tbl_index, left_rdm_tbl_cnt;
 106
 107    for ( i = v_num_filled_slots; i < v_no_slots; i++ ) {
 108       ok = 0;
 109
 110 /**************************/
 111 /* compute the alignment  */
 112 /**************************/
 113       alignment = (v_no_slots + v_random_table[i] - pat[0])
 114                     % v_no_slots;
 115
 116 /**************************/
 117 /* test fit the pattern   */
 118 /**************************/
 119       for ( j=1; j<pat.no_elmts(); j++ ) {
 120          landing_slot = (pat[j] + alignment) % v_no_slots;
 121          if ( v_rep[landing_slot] == FULL ) {
 122             ok = -1;
 123             break; // try another alignment
 124          }
 125       }
 126
 127 /**************************/
 128 /* really fit the pattern */
 129 /**************************/
 130       if ( ok == 0 ) {
 131          for ( j=0; j < pat.no_elmts(); j++ ) {
 132             landing_slot = (pat[j] + alignment) % v_no_slots;
 133             v_rep[landing_slot] = FULL ;
 134
 135             right_rdm_tbl_index = v_map_table[landing_slot];
 136             left_rdm_tbl_cnt = v_random_table[v_num_filled_slots + j];
 137
 138             v_random_table[right_rdm_tbl_index] = left_rdm_tbl_cnt;
 139             v_map_table[left_rdm_tbl_cnt] = right_rdm_tbl_index;
 140             v_random_table[v_num_filled_slots + j] = landing_slot;
 141
 142             v_map_table[landing_slot] = v_num_filled_slots + j;
 143          }
 144          v_num_filled_slots += pat.no_elmts();
 145          return alignment;
 146       }
 147    }
 148    return -1;
 149 }
 150
 151 int mphf_hash_table::fit_hash_table(int_pattern& pat)
 152 {
 153    int i, j;
 154    for ( i=0; i<pat.no_elmts(); i++ ) {
 155       if ( v_rep[int(pat[i])] != (int) 0 ) {
 156
 157          for ( j=0; j<=i; j++ )
 158            v_rep[int(pat[j])] = (int) 0;
 159
 160          v_num_filled_slots -= i+1;
 161          return -1;
 162       } else {
 163          v_rep[int(pat[i])] = FULL;
 164          v_num_filled_slots++;
 165       }
 166    }
 167    return 0;
 168 }