構造体、共用体、列挙体 DEFINE,マクロ
struct TTnode
struct mssFPR
struct mssFileInfo
struct mssFldRec
struct mssFldRecDbl
struct mssFldRecKey
struct mssFldRecMax
struct mssRec
struct mssSortDat
MaxLineS
MaxMemS
MaxPntSize
PWayS
PipeSize
ReadCnt
0001: /**
0002: * # CHAPTER #
0003: * ============================================================================
0004: * MUSASHIで用いられるXMLtableデータの入力関連のヘッダーファイル
0005: * ============================================================================
0006: */
0007:
0008: #include <stdio.h>
0009: #include <zlib.h>
0010:
0011: #include <mssHeader.h>
0012: #include <mssConfig.h>
0013: #include <mssOutput.h>
0014: #include <mssOption.h>
0015:
0016:
0017: #ifndef __MSSINPUT_H
0018: #define __MSSINPUT_H 1
0019:
0020: /**
0021: * # DEFINE #
0022: * マージソートを行う際に、何個までのファイルを同時に併合させるか
0023: */
0024: #define PWayS 25
0025:
0026: /**
0027: * # DEFINE #
0028: * 分割ソートでのデータ読み込みバッファサイズの上限値
0029: * この値、もしくはMssMaxLineSortのいずれかが上限値に達したときのデータが
0030: * 分割ソートにおける一つのバケットとなる。
0031: */
0032: #define MaxMemS 2048000
0033:
0034: /**
0035: * # DEFINE #
0036: * 分割ソートでのデータ読み込み行数の上限値
0037: * この値、もしくはMssMaxMemSortのいずれかが上限値に達したときのデータが
0038: * 分割ソートにおける一つのバケットとなる。
0039: */
0040: #define MaxLineS 50000
0041:
0042: /**
0043: * # DEFINE #
0044: * パイプのバッファサイズ
0045: */
0046: #define PipeSize 4096
0047:
0048: /**
0049: * # DEFINE #
0050: * リングバッファの一つのキューのブロック数
0051: */
0052: #define ReadCnt 4
0053:
0054: /**
0055: * # DEFINE #
0056: * FRM構造体におけるポインタバッファのメモリ量上限値
0057: */
0058: #define MaxPntSize 2048000
0059:
0060: /**
0061: * # STRUCT #
0062: * トーナメントツリーのデータ構造
0063: *
0064: * (1)
0065: * +-------+--------+
0066: * | |
0067: * (2) (3)
0068: * +-----+------+ +---+--+
0069: * | | | |
0070: * (4) (5) (6) (7)
0071: * +--+--+ +--+--+
0072: * | | | |
0073: * (8) (9) (10) (11)
0074: * 各ノード毎にTTnode構造体が張りつけられる
0075: * ノード番号(4)についてみると、
0076: * node->parent は (2)
0077: * node->brother は (5)となる。
0078: * node->key はTTkey構造体へのポインタで実際の文字列を示すと考えればよい。
0079: * node->key->strが実際の文字列へのポインタを示し
0080: * node->key->bktはそのstr文字列がPwayマージソートで分割されたバケット番号
0081: * (ファイル番号)
0082: */
0083: struct TTnode {
0084: int num; /*ノード番号*/
0085: struct TTkey {
0086: char *str; /*キーの文字列*/
0087: int bkt; /*分割ソートにおけるバケット番号*/
0088: } *key;
0089: struct TTnode *parent; /*親ノード*/
0090: struct TTnode *brother; /*兄弟ノード*/
0091: };
0092:
0093: /**
0094: * # STRUCT #
0095: * ソート用のデータ構造
0096: * ソートのアルゴリズムは、実装において非常に複雑になっている。
0097: * 複雑さの原因は、数値や逆順ソートと通常の文字ソートを同一プログラムで
0098: * 扱っているところになる。
0099: * 数値逆順ソートでは全ての処理において、キーの比較を項目単位で行っているため
0100: * 読み込みおよびTNtreeでは項目を区切って処理している。
0101: * 一方で、通常の文字ソートの場合は、最初にデータを読み込む際に、項目をキー順
0102: * に並べ換える。そうすることによって、後の処理では項目を区切ることなく処理
0103: * できる。比較は、一行単位で先頭から文字比較をすればよい。
0104: * このアルゴリズムの違いによって、通常の文字ソートはかなり高速になる。
0105: * 500万件のベンチマークにおいて、約1.3倍の高速化が実現できている。
0106: * 両者のソートを数値逆順ソートにあわせることもできるが、そうすると、
0107: * プログラムが非常にシンプルになる代わりに、処理が遅くなる。
0108: * 通常の利用においては、単純な文字ソートの方が利用率が圧倒的に多いと予測される
0109: * ので、プログラムのシンプルさより、高速性を選んだ。
0110: */
0111: struct mssSortDat {
0112: struct TTnode *tt; /*トーナメントツリー(プライオリティキュー)*/
0113: struct mssFPR *iFile[PWayS]; /*入力ワークファイルポインタ*/
0114: struct mssRec *rec[PWayS]; /*入力ワークファイル読み込みバッファ*/
0115: struct mssFldRec *fr[PWayS]; /*数値や逆順ソートでの読み込みバッファ*/
0116: char prefix[MssFileNameMaxLen]; /*ワークファイル名のprefix*/
0117: int iStart; /*開始入力ファイル番号*/
0118: int iEnd; /*終了入力ファイル番号*/
0119: int bktCnt; /*バケットの数(iEnd-iStart+1)*/
0120: struct mssFields *flds; /*ソート項目*/
0121: int fldCnt; /*データの全項目数*/
0122: int recCnt; /*データのレコード数*/
0123: int conv[MssFieldMaxCnt];/*要素:ソート項目順番 値:infileの項目番号*/
0124: };
0125:
0126: /**
0127: * # STRUCT #
0128: * 入力バッファの構造体(リングバッファ)
0129: *
0130: * バッファの全体像 １つのキューの内容(読み込み単位)
0131: * fp->que -----+---------------+
0132: * |MssRecordMaxLen| / +------------+
0133: * +---------------+ / |PipeSize |0
0134: * 0|fp->queSize | / +------------+
0135: * | | / | |1
0136: * +---------------+/ +------------+
0137: * 1| | | : |
0138: * | | | : |
0139: * +---------------+\ | : |
0140: * | : | \ | : |
0141: * | : | \ +------------+
0142: * | : | \ | |ReadCnt
0143: * +---------------+ \ +------------+
0144: * | |
0145: * fp->queCnt| |
0146: * +---------------+
0147: */
0148: struct mssFPR {
0149: char *fName; /*ファイル名へのポインタ(NULL:標準入力)*/
0150: char *curPnt; /*現在の読み込みポインタ*/
0151: char *buf; /*リングバッファデータ本体*/
0152: int queCnt; /*queueの数 2の階乗でなければならない*/
0153: int queSize;/*queのサイズ=queCnt*PipeSize(毎回計算で求めるのが遅いので)*/
0154: int enq; /*次に読みこむバッファ番号*/
0155: int deq; /*有効なバッファの開始番号*/
0156: int full; /*バッファfullフラグ*/
0157: int last; /*eofを含む読み込みを行ったフラグ*/
0158: int recCnt; /*これまでに読み込んだレコードのカウント*/
0159: int chrCnt; /*これまでに読み込んだ文字のカウント*/
0160:
0161: int zflg; /*圧縮ファイル(1)か、通常ファイル(0)か?*/
0162: gzFile zfd; /*圧縮ファイル*/
0163: FILE *fp; /*通常ファイル*/
0164:
0165: int sort; /*通常ファイル(0)かソートファイル(1)か? reopenFPRsortでセット*/
0166: struct mssSortDat *sd; /*ソートファイルオブジェクト*/
0167: char *readPnt; /*データの読み込みポイント*/
0168: };
0169:
0170: /**
0171: * # STRUCT #
0172: * 一行読み込み構造体
0173: * 項目による分割はおこなわない。
0174: */
0175: struct mssRec {
0176: char *pnt; /*行の先頭へのポインタ*/
0177: int chrCnt; /*読みこんだ文字数*/
0178: int eof; /*ファイルを読み切った時にセットされる*/
0179: };
0180:
0181: /**
0182: * # STRUCT #
0183: * 項目によるトークン分割をともなった一行単位読み込み構造体
0184: */
0185: struct mssFldRec {
0186: char **pnt; /*各項目へのポインタ*/
0187: int fldCnt; /*項目数(初期化initFldRec時にセットされる)*/
0188: int chrCnt; /*読みこんだ文字数*/
0189: int eof;
0190: };
0191:
0192: /**
0193: * # STRUCT #
0194: * 項目によるトークン分割をともなった二行単位読み込み構造体
0195: * キーブレーク処理を行うときに利用する。
0196: */
0197: struct mssFldRecDbl {
0198: char **pnt[2]; /*各行各項目へのポインタ*/
0199: int new; /*0 or 1: pnt[new]で現在行の項目をさす*/
0200: int old; /*0 or 1: pnt[old]で前行の項目をさす*/
0201: int firstRead; /*最初の一行のキーブレーク時にのみ例外処理するためのフラグ*/
0202: int eof; /*ファイルを読み切った時にセットされる*/
0203: int newChrCnt; /*読みこんだ文字数(new)*/
0204: int oldChrCnt; /*読みこんだ文字数(old)*/
0205: int fldCnt; /*項目数(初期化initFRD時にセットされる)*/
0206: };
0207:
0208: /**
0209: * # STRUCT #
0210: * 項目によるトークン分割をともなったn行単位読み込み構造体
0211: * nの値はFPRのバッファの大きさ、もしくはMaxPntSizeで決まる。
0212: */
0213: struct mssFldRecMax {
0214: char **pnt; /*各行各項目へのポインタ
0215: (*(pnt+fldCnt*行番号)+項目番号)で行番号の項目番号をさす*/
0216: int fldCnt; /*項目数(初期化initFldRec時にセットされる)*/
0217: int chrCnt; /*読みこんだ文字数*/
0218: int eof; /*ファイルを読み切った時にセットされる*/
0219: int recCnt; /*読み込んだ行数*/
0220: int recMax; /*MaxPntSizeから計算される、読み込み行数の上限値*/
0221: };
0222:
0223: /**
0224: * # STRUCT #
0225: * 項目によるトークン分割をともなったキー単位読み込み構造体
0226: */
0227: struct mssFldRecKey {
0228: char **pnt; /*一行単位の項目ポインタ*/
0229: int fldCnt; /*項目数(初期化initFRK時にセットされる)*/
0230: int chrCnt; /*読みこんだ文字数*/
0231: int eof; /*ファイルを読み切った時にセットされる*/
0232: int keyRecCnt; /*現在のキーに含まれる行数*/
0233: int keyNo; /*現在の通しキー番号*/
0234:
0235: char **frPnt; /*項目行を格納するポインタ*/
0236: int firstRead; /*最初の一行のキーブレーク時にのみ例外処理するためのフラグ*/
0237: int alcRecCnt; /*pntに領域確保された行数*/
0238: int recPnt; /*pntに読み込む位置(行番号)*/
0239: MssOptKEY *optKey; /*キー*/
0240: int byFile; /*一時ファイルに出力されたかどうかのフラグ*/
0241: char fName[MssFileNameMaxLen]; /*一時ファイル名*/
0242: struct mssFPW *fpw; /*内部で利用するワークファイル用*/
0243: struct mssFPR *fpr;/*内部で利用するワークファイル用*/
0244: struct mssFldRec *fr;/*ワークファイルから行単位で読み込むため*/
0245: int curRecNo; /*現在処理中の行番号*/
0246: };
0247:
0248: /**
0249: * # STRUCT #
0250: * ファイルステータスの構造体
0251: */
0252: struct mssFileInfo {
0253: int maxCnt; /* 0:データ部を完全に読み込む n:n行まで*/
0254: char *fName; /*ファイル名*/
0255: int totalSize; /*-tの時はtotalSize==bodySize*/
0256: int readEnd; /*最終行まで読み込んだかどうか*/
0257: int bodySize; /*データ本体*/
0258: int fldCnt; /*項目数*/
0259: int recCnt; /*レコード数*/
0260: };
0261:
0262: /**
0263: * # PROTOTYPE #
0264: */
0265: struct mssFileInfo * mssGetFileInfo(char *fName, int recMax);
0266: struct mssRec * mssInitRec(void);
0267: void mssFreeRec(struct mssRec *rec);
0268: int mssReadRec(struct mssFPR *fp, struct mssRec *rec);
0269: struct mssFldRec * mssInitFldRec(int fldCnt);
0270: void mssFreeFldRec(struct mssFldRec* fr);
0271: int mssReadFldRec(struct mssFPR *fp, struct mssFldRec *fr);
0272: int mssReadRandFldRec(struct mssFPR *fp, struct mssFldRec *fr, int recNo, int datTop, int recLen);
0273: struct mssFldRecDbl * mssInitFRD(int fldCnt);
0274: void mssFreeFRD(struct mssFldRecDbl *frd);
0275: int mssReadFRD(struct mssFPR *fp, struct mssFldRecDbl *frd);
0276: int mssKeyBreak(struct mssFldRecDbl *frd, MssOptKEY *optKey);
0277: struct mssFldRecMax * mssInitFRM(int fldCnt);
0278: void mssFreeFRM(struct mssFldRecMax *frm);
0279: int mssReadFRM(struct mssFPR *fp, struct mssFldRecMax *frm);
0280: struct mssFldRecKey * mssInitFRK(int fldCnt,MssOptKEY *optKey,char *path);
0281: void mssFreeFRK(struct mssFldRecKey *frk);
0282: int mssReadFRK(struct mssFPR *fp, struct mssFldRecKey *frk);
0283: int mssReadFldRecFRK(struct mssFldRecKey *frk);
0284: void mssSeekTopFRK(struct mssFldRecKey *frk);
0285: int mssGetFldCntOnData(struct mssFPR *fp);
0286: void mssSeekTopFPR(struct mssFPR *fp);
0287: struct mssFPR * mssOpenFPR(char *fileName, int bufCnt);
0288: struct mssFPR * mssReopenFPRsort(struct mssFPR *inFile, int queCnt, struct mssFields *flds, int fldCnt, char *tmpPath);
0289: void mssCloseFPR(struct mssFPR *fp);
0290: struct mssFPR * mssOpenFPU(char *fileName, int queCnt);
0291: void mssCloseFPU(struct mssFPR *fp);
0292:
0293: #endif /* _INPUT_H */