src/slm/sim_fmerge.h

   1 // -*- mode: c++ -*-
   2 /*
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   4  *
   5  * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
   6  *
   7  * The contents of this file are subject to the terms of either the GNU Lesser
   8  * General Public License Version 2.1 only ("LGPL") or the Common Development and
   9  * Distribution License ("CDDL")(collectively, the "License"). You may not use this
  10  * file except in compliance with the License. You can obtain a copy of the CDDL at
  11  * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
  12  * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
  13  * specific language governing permissions and limitations under the License. When
  14  * distributing the software, include this License Header Notice in each file and
  15  * include the full text of the License in the License file as well as the
  16  * following notice:
  17  *
  18  * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
  19  * (CDDL)
  20  * For Covered Software in this distribution, this License shall be governed by the
  21  * laws of the State of California (excluding conflict-of-law provisions).
  22  * Any litigation relating to this License shall be subject to the jurisdiction of
  23  * the Federal Courts of the Northern District of California and the state courts
  24  * of the State of California, with venue lying in Santa Clara County, California.
  25  *
  26  * Contributor(s):
  27  *
  28  * If you wish your version of this file to be governed by only the CDDL or only
  29  * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
  30  * include this software in this distribution under the [CDDL or LGPL Version 2.1]
  31  * license." If you don't indicate a single choice of license, a recipient has the
  32  * option to distribute your version of this file under either the CDDL or the LGPL
  33  * Version 2.1, or to extend the choice of license to its licensees as provided
  34  * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
  35  * Version 2 license, then the option applies only if the new code is made subject
  36  * to such option by the copyright holder.
  37  */
  38
  39 #ifndef _SIM_FILE_MERGE_H
  40 #define _SIM_FILE_MERGE_H
  41
  42 #include "../portability.h"
  43
  44 #include <stdio.h>
  45 #include <deque>
  46 #include <vector>
  47 #include <algorithm>
  48
  49 template<class unit_type>
  50 class TUnitAndParaInfo {
  51 public:
  52     typedef unit_type TUnit;
  53     TUnitAndParaInfo() : unit(), runOut(false) {}
  54 public:
  55     TUnit unit;
  56     bool runOut;
  57 };
  58
  59 template<class unit_type>
  60 class file_para
  61 {
  62 public:
  63     typedef unit_type TUnit;
  64     typedef TUnitAndParaInfo<TUnit> UnitAndParaInfo;
  65     typedef std::deque<UnitAndParaInfo> TItemBuf;
  66     typedef typename TItemBuf::iterator TIBIterator;
  67     typedef typename TItemBuf::const_iterator TIBConstIterator;
  68
  69     file_para(FILE* p_file, size_t start, size_t end)
  70         : fp(p_file), runOut(false), cur_offset(start), last_offset(end),
  71           buf() {}
  72
  73     UnitAndParaInfo& operator*(){
  74         if (buf.size() == 0) {
  75             for (int i = 0; i < BUF_SIZE; ++i) {
  76                 buf.push_back(UnitAndParaInfo());
  77                 UnitAndParaInfo& e = buf.back();
  78                 e.runOut = runOut = !(e.unit.read(fp, cur_offset, last_offset));
  79                 if (runOut) break;
  80             }
  81         }
  82         return buf.front();
  83     }
  84
  85     file_para& operator++(){
  86         if (buf.size() == 0)
  87             this->operator*();
  88         buf.pop_front();
  89         return *this;
  90     }
  91
  92     bool operator<(file_para& another){
  93         const UnitAndParaInfo& me = this->operator*();
  94         const UnitAndParaInfo& you = *another;
  95         if (me.runOut) {
  96             if (you.runOut)
  97                 return((char *) &me < (char *) &you);
  98             else
  99                 return true;
 100         } else {
 101             if (you.runOut)
 102                 return false;
 103             else {
 104                 if (me.unit > you.unit) return true;
 105                 if (me.unit == you.unit) return((char *) &me < (char *) &you);
 106                 return false;
 107             }
 108         }
 109     }
 110
 111 private:
 112     static const int BUF_SIZE = 1024;
 113     FILE * fp;
 114     bool runOut;
 115     size_t cur_offset, last_offset;
 116     TItemBuf buf;
 117 };
 118
 119 template <class PPara>
 120 class PtrCompare {
 121 public:
 122     bool operator()(const PPara& p1, const PPara& p2)
 123     { return(*p1 < *p2); }
 124 };
 125
 126 template<class unit_type>
 127 class CMultiWayFileMerger
 128 {
 129 public:
 130     typedef file_para<unit_type> TPara;
 131     typedef std::vector<TPara*> TParaVec;
 132
 133     void addPara(FILE *fp, size_t first_offset, size_t last_offset) {
 134         paras.push_back(new TPara(fp, first_offset, last_offset));
 135     }
 136
 137     void start() {
 138         std::make_heap(paras.begin(), paras.end(), PtrCompare<TPara*>());
 139     }
 140     TPara* getBest(){ //You then have to deal same items form different part
 141         std::pop_heap(paras.begin(), paras.end(), PtrCompare<TPara*>());
 142         return paras.back();
 143     }
 144     void next(){
 145         ++(*(paras.back()));
 146         std::push_heap(paras.begin(), paras.end(), PtrCompare<TPara*>());
 147     }
 148     ~CMultiWayFileMerger() {
 149         for (size_t i = 0; i < paras.size(); i++) {
 150             delete paras[i];
 151         }
 152     }
 153 private:
 154     TParaVec paras;
 155 };
 156
 157 #endif