cde/programs/dtinfo/DtMmdb/hmphf/sorter.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 libraries 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: sorter.cc /main/3 1996/06/11 17:20:47 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
  53 #include "hmphf/sorter.h"
  54
  55 /*#define NUM_BUCKETS 10 */
  56 #define NUM_BUCKETS 5000
  57
  58 sorter::sorter(char* key_file) :
  59    v_max_bucket_sz(0),
  60    v_no_unique_keys(0),
  61    v_unique_keys(0),
  62    b_convertor(NUM_BUCKETS, 128)
  63 {
  64    fstream in(key_file, ios::in);
  65    _init(in);
  66 }
  67
  68 sorter::sorter(istream& in) :
  69    v_max_bucket_sz(0),
  70    v_no_unique_keys(0),
  71    v_unique_keys(0),
  72    b_convertor(NUM_BUCKETS, 128)
  73 {
  74    _init(in);
  75 }
  76
  77 void sorter::_init(istream& in)
  78 {
  79    v_bucket_array = new bucketPtr[NUM_BUCKETS];
  80
  81    int i;
  82    for ( i=0; i<NUM_BUCKETS; v_bucket_array[i++] = 0);
  83
  84    char key_buf[LBUFSIZ];
  85
  86    int k;
  87    while ( in.getline(key_buf, LBUFSIZ) ) {
  88       i = b_convertor.atoi(key_buf, strlen(key_buf), 0, NUM_BUCKETS);
  89
  90       if ( v_bucket_array[i] == 0 ) {
  91          v_bucket_array[i] = new bucket(key_buf, i, true);
  92          k = 1;
  93       } else {
  94          k = v_bucket_array[i] -> add_key(key_buf, true);
  95       }
  96
  97       v_max_bucket_sz = MAX(v_max_bucket_sz, k);
  98
  99       in.getline(key_buf, LBUFSIZ); // skip the next info field
 100    }
 101
 102    filter_by_hash();
 103
 104    assemble_unique_keys();
 105 }
 106
 107 sorter::~sorter()
 108 {
 109    int i;
 110    for ( i=0; i<NUM_BUCKETS; delete v_bucket_array[i++] );
 111    delete [] v_bucket_array;
 112
 113    for ( i=0; i<v_no_unique_keys; delete v_unique_keys[i++] );
 114    delete [] v_unique_keys;
 115 }
 116
 117 void sorter::filter_by_hash()
 118 {
 119 // a small hash table for keys to map to
 120    v_map_table = new charPtr[2*v_max_bucket_sz];
 121
 122    int i;
 123    for ( i=0; i<2*v_max_bucket_sz; v_map_table[i++] = 0 );
 124
 125 // an int table remembering slots in the v_map_table
 126 // that have been mapped.
 127    v_index_table =  new int[v_max_bucket_sz];
 128
 129 // a charPtr table remembering possibly duplicated keys
 130    v_check_table = new charPtr[v_max_bucket_sz];
 131
 132 // a charPtr table remembering dupcated keys
 133    v_dup_table = new charPtr[v_max_bucket_sz];
 134
 135    for ( i=0; i<NUM_BUCKETS; i++ ) {
 136       if ( v_bucket_array[i] )
 137          filter_a_bucket(v_bucket_array[i]);
 138    }
 139
 140    delete [] v_map_table;
 141    delete [] v_check_table;
 142    delete [] v_index_table;
 143    delete [] v_dup_table;
 144 }
 145
 146 void sorter::filter_a_bucket(bucketPtr bkt)
 147 {
 148    slist_void_ptr_cell *lp = bkt -> key_ptr;
 149
 150    while ( lp ) {
 151       remove_keys(bkt, (char*)(lp -> void_ptr()), lp);
 152       lp = (slist_void_ptr_cell*)(lp -> v_succ);
 153    }
 154 }
 155
 156 void sorter::remove_keys(bucketPtr bkt, char* key, slist_void_ptr_cell* lp)
 157 {
 158 //debug(cerr, key);
 159
 160    slist_void_ptr_cell *llp = lp;
 161
 162    while ( llp && llp -> v_succ ) {
 163
 164       slist_void_ptr_cell *next_lp =
 165           (slist_void_ptr_cell*)llp -> v_succ;
 166 //debug(cerr, (char*)(next_lp -> void_ptr()));
 167
 168       if ( strcmp( key, (char*)(next_lp -> void_ptr()) ) == 0 ) {
 169 //MESSAGE(cerr, "rmove key:");
 170 //cerr <<  (char*)(next_lp -> void_ptr()) << "\n";
 171          llp -> v_succ = next_lp -> v_succ;
 172
 173          delete (char*)(next_lp -> void_ptr());
 174          delete next_lp;
 175
 176          bkt -> v_no_keys --;
 177       } else
 178          llp = (slist_void_ptr_cell*)(llp -> v_succ);
 179
 180    }
 181 }
 182
 183
 184 //
 185 //
 186 //   int n_chk = 0;
 187 //   int n_idx = 0;
 188 //
 189 //   slist_void_ptr_cell *lp = bkt -> key_ptr;
 190 //
 191 //   while ( lp ) {
 192 //
 193 //// maintaint the order of key chains in v_check_table[]!!!
 194 //
 195 //      char* key2 = ((char*)(lp -> void_ptr()));
 196 //
 197 //      int hash = b_convertor.atoi(
 198 //                    key2, strlen(key2),
 199 //                    1, 2*v_max_bucket_sz
 200 //                                 );
 201 //
 202 //      if ( v_map_table[hash] != 0 ) {
 203 //
 204 //         if ( v_map_table[hash] != (charPtr)1 ) {
 205 //            v_check_table[n_chk++] = v_map_table[hash];
 206 //            v_map_table[hash] = (charPtr)1;
 207 //                                 // set to occupied. so that the same
 208 //                                 // key will be in the v_check_table once.
 209 //                                 // assume 1 will never be the address
 210 //                                 // of any keys.
 211 //         }
 212 //
 213 //         v_check_table[n_chk++] = key2;
 214 //
 215 //      } else {
 216 //         //v_map_table[hash] = ((Ostring*)(lp -> void_ptr())) -> get();
 217 //         v_map_table[hash] = ((char*)(lp -> void_ptr()));
 218 //      }
 219 //
 220 //      v_index_table[n_idx++] = hash; // remember the slot being set
 221 //
 222 //      lp = (slist_void_ptr_cell*)(lp -> succ);
 223 //   }
 224 ////debug(cerr, n_chk);
 225 //
 226 //// double check possiblly collided keys
 227 //   int n_dup = 0;
 228 //   for ( int u=0; u<n_chk-1; u++ ) {
 229 //      for (int v=u+1; v<n_chk; v++ ) {
 230 //         if ( v_check_table[u] && v_check_table[v] &&
 231 //              strcmp(v_check_table[u], v_check_table[v]) == 0 )
 232 //         {
 233 //// mark v as a duplicated key
 234 //            v_dup_table[n_dup++] = v_check_table[v];
 235 //            v_check_table[v] = 0;
 236 //         }
 237 //
 238 //      }
 239 //   }
 240 //
 241 ////debug(cerr, n_dup);
 242 //
 243 //// remove the duplicates
 244 //   if ( n_dup > 0 ) {
 245 //      slist_void_ptr_cell *lp = bkt -> key_ptr;
 246 //      slist_void_ptr_cell *prev_lp = lp;
 247 //
 248 //      int u = 0;
 249 //      lp = (slist_void_ptr_cell*)(lp -> succ);
 250 //
 251 //      while ( lp && u<n_dup ) {
 252 //
 253 //
 254 ///*
 255 //debug(cerr, v_dup_table[u]);
 256 //debug(cerr, int(v_dup_table[u]));
 257 //debug(cerr, (char*)(lp -> void_ptr()));
 258 //debug(cerr, int((char*)(lp -> void_ptr())));
 259 //*/
 260 //
 261 //
 262 //         if ( v_dup_table[u] == ((char*)(lp -> void_ptr())) )
 263 //         {
 264 //
 265 //MESSAGE(cerr, "key removed:");
 266 //debug(cerr, v_dup_table[u]);
 267 //
 268 //             prev_lp -> succ = lp -> succ;
 269 //             bkt -> v_no_keys --;
 270 //             u++;
 271 //         } else
 272 //             prev_lp = lp;
 273 //
 274 //         lp = (slist_void_ptr_cell*)(lp -> succ);
 275 //
 276 //      }
 277 //   }
 278 //
 279 //// clean v_map_table
 280 //   for ( int k=0; k<n_idx; k++ ) {
 281 //      v_map_table[v_index_table[k]] = 0;
 282 //   }
 283 //
 284 ////MESSAGE(cerr, "SOS0");
 285 //}
 286
 287 void sorter::assemble_unique_keys()
 288 {
 289    int i;
 290    for ( i=0; i<NUM_BUCKETS; i++ ) {
 291       if ( v_bucket_array[i] ) {
 292          v_no_unique_keys += v_bucket_array[i] -> v_no_keys;
 293       }
 294    }
 295
 296    v_unique_keys = new charPtr[v_no_unique_keys];
 297
 298    int j = 0;
 299    slist_void_ptr_cell *lp = 0;
 300
 301    for ( i=0; i<NUM_BUCKETS; i++ ) {
 302
 303       if ( v_bucket_array[i] == 0 ) continue;
 304
 305       lp = v_bucket_array[i] -> key_ptr;
 306
 307       while ( lp ) {
 308
 309          v_unique_keys[j++] = ((char*)(lp -> void_ptr()));
 310          lp -> set_vptr(0);
 311
 312          lp = (slist_void_ptr_cell*)(lp -> v_succ);
 313       }
 314    }
 315 }
 316
 317 ostream& operator<< (ostream& out, sorter& st)
 318 {
 319    debug(out, st.v_no_unique_keys);
 320
 321    for ( int i=0; i<st.v_no_unique_keys; i++ ) {
 322       out << st.v_unique_keys[i] << "\n";
 323    }
 324
 325    return out;
 326 }