cde/programs/dtinfo/DtMmdb/storage/chunks_index.C

   1 /*
   2  * $XConsortium: chunks_index.cc /main/4 1996/07/18 14:52:47 drk $
   3  *
   4  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
   5  * All rights reserved.  Unpublished -- rights reserved under
   6  * the Copyright Laws of the United States.  USE OF A COPYRIGHT
   7  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
   8  * OR DISCLOSURE.
   9  *
  10  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  11  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  12  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  13  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  14  * INTERNATIONAL, LTD.
  15  *
  16  *                         RESTRICTED RIGHTS LEGEND
  17  * Use, duplication, or disclosure by the Government is subject
  18  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  19  * of the Rights in Technical Data and Computer Software clause
  20  * at DFARS 252.227-7013.
  21  *
  22  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  23  *                  1315 Dell Avenue
  24  *                  Campbell, CA  95008
  25  *
  26  */
  27
  28
  29
  30 #include "storage/chunks_index.h"
  31
  32 /****************************************************/
  33 // record and comparison functions for string index
  34 /****************************************************/
  35
  36 Boolean str_index_record_ls(const void* o1, const void* o2)
  37 {
  38    const str_index_record_t* x = (str_index_record_t*)o1;
  39    const str_index_record_t* y = (str_index_record_t*)o2;
  40
  41 /*
  42 MESSAGE(cerr, "LS");
  43 debug(cerr, x -> str_offset);
  44 debug(cerr, x -> loc);
  45 debug(cerr, y -> str_offset);
  46 debug(cerr, y -> loc);
  47 MESSAGE(cerr, "");
  48 */
  49
  50    return ( x -> str_offset < y -> str_offset ) ? true : false;
  51 }
  52
  53 Boolean str_index_record_eq(const void* o1, const void* o2)
  54 {
  55    const str_index_record_t* x = (str_index_record_t*)o1;
  56    const str_index_record_t* y = (str_index_record_t*)o2;
  57
  58 /*
  59 MESSAGE(cerr, "EQ");
  60 debug(cerr, x -> str_offset);
  61 debug(cerr, x -> loc);
  62 debug(cerr, y -> str_offset);
  63 debug(cerr, y -> loc);
  64 MESSAGE(cerr, "");
  65 */
  66
  67    return ( x -> str_offset == y -> str_offset ) ? true : false;
  68 }
  69
  70 ///////////////////////////////////////////////////////
  71 //
  72 ///////////////////////////////////////////////////////
  73
  74 chunks_index::chunks_index(abs_storage* store,
  75                            mmdb_pos_t loc) :
  76 v_index_imp(str_index_record_eq, str_index_record_ls),
  77 v_storage_ptr(store), v_initial_loc(loc)
  78 {
  79    str_index_record_tPtr* vector = 0;
  80    int vector_sz = 0;
  81
  82    if ( v_storage_ptr == 0 || v_initial_loc == 0 )
  83       return ;
  84
  85    ((page_storage*)v_storage_ptr) -> get_str_locs(loc, vector, vector_sz);
  86
  87 /*
  88 MESSAGE(cerr, "vector:");
  89 debug(cerr, vector_sz);
  90 for ( int i=0; i<vector_sz; i++ ) {
  91 debug(cerr, i);
  92 debug(cerr, vector[i] -> loc);
  93 debug(cerr, vector[i] -> str_offset);
  94 }
  95 */
  96
  97
  98    binary_insert(vector, 0, vector_sz-1);
  99    delete vector;
 100 }
 101
 102 chunks_index::~chunks_index()
 103 {
 104     v_index_imp.del_elements(delete_str_index_record);
 105 }
 106
 107 /***************************************************/
 108 // Note: given that the keys in vector are non-
 109 //       decreasing, it is optimal to binarilly
 110 //       insert keys to obtained a
 111 //       balanced binary search tree.
 112 //
 113 //       get_str_locs() returns a non-decreasing
 114 //       key vector
 115 /***************************************************/
 116
 117 Boolean
 118 chunks_index::binary_insert(str_index_record_tPtr* vector,
 119                             int left, int right)
 120 {
 121    if ( left > right )
 122      return true;
 123
 124    int middle = (right + 1 - left) / 2 + left;
 125 //debug(cerr, middle);
 126    v_index_imp.insert(vector[middle]);
 127
 128    Boolean ok1 = binary_insert(vector, left, middle-1);
 129    Boolean ok2 = binary_insert(vector, middle+1, right);
 130
 131    return  ( ok1 == true && ok2 == true ) ? true : false;
 132 }
 133
 134
 135 str_index_record_t*
 136 chunks_index::chunk_location( int offset )
 137 {
 138    str_index_record_t key(offset);
 139
 140    str_index_record_t* anchor = (str_index_record_t*)
 141         v_index_imp.smaller_member((root*)&key);
 142
 143    if ( anchor == 0 ) {
 144       throw(stringException("chunk_location(): no smaller member"));
 145    }
 146
 147    return anchor;
 148 }
 149