グローバル関数 ローカル関数
RBUQprintTree
mssFreeUnqDat
mssInitUnqDat
mssPreUnq
mssReadWriteUnq
RBUQaddExternalNodes
RBUQcpKey
RBUQcpKeyMemCnt
RBUQdeleteNode
RBUQdetermineAB
RBUQdouble_rotate
RBUQfindMax
RBUQfind_brother
RBUQfree
RBUQfreeAllNode
RBUQfreeKey
RBUQfreeNode
RBUQhasLeftNode
RBUQinit
RBUQinsert
RBUQisExternalNode
RBUQisLeftNode
RBUQisRedNode
RBUQisTopNode
RBUQmakeNode
RBUQmember
RBUQpop
RBUQptree
RBUQrebalanceOnDelete
RBUQrebalanceOnInsert
RBUQsingleRotate
RBUQupdate
RBUQwriteAllNode
RBUQwriteNode
getFname
keyCmp
mergeRBUQ
readRBUQkey
setFirstLineRBUQ
sortUQ
0001: /**
0002: * # CHAPTER #
0003: * ============================================================================
0004: * MUSASHIで用いられる集計関連の関数
0005: * ============================================================================
0006: */
0007:
0008: #include <mssBase.h>
0009: #include <mssUniq.h>
0010: #include <mssHeader.h>
0011:
0012: #include <stdio.h>
0013: #include <stdlib.h>
0014: #include <string.h>
0015: #include <unistd.h>
0016: #include <signal.h>
0017:
0018: /**
0019: * グローバル変数
0020: */
0021: extern struct mssGlobalVariables mssGV;
0022:
0023: static MssOptKEY *OptKey; /*-kパラメータ*/
0024: static int FldCnt; /*集計する項目数*/
0025: static char readEnd[2]={0xff,0}; /*番兵*/
0026: static char fname[MssFileNameMaxLen]; /*一時ファイル名*/
0027:
0028: /**
0029: * # SECTION #
0030: * ----------------------------------------------------------------------------
0031: * 赤黒木(Red Black Tree)
0032: * ----------------------------------------------------------------------------
0033: * 参考文献: 渡部敏正『データ構造とアルゴリズム』共立出版,2000,6章4節.
0034: * p.224 下から9行目は誤り!!
0035: * 誤) if (v == NULL ) return(1) -> 正) if (v == NULL ) return(0)
0036: */
0037:
0038: /**
0039: * # FUNCTION #
0040: */
0041: static int RBUQhasLeftNode(struct RBUQnode *v)
0042: {
0043: if(v->left->rank !=0){
0044: return(1);
0045: }
0046: return(0);
0047: }
0048:
0049: /**
0050: * # FUNCTION #
0051: */
0052: static int RBUQisExternalNode(struct RBUQnode *v)
0053: {
0054: if(v->rank==0)
0055: return(1);
0056: return(0);
0057: }
0058:
0059: /**
0060: * # FUNCTION #
0061: */
0062: static int RBUQisTopNode(struct RBUQnode *v)
0063: {
0064: if(v->parent->rank==0){
0065: return(1);
0066: }
0067: return(0);
0068: }
0069:
0070: /**
0071: * # FUNCTION #
0072: */
0073: static int RBUQisLeftNode(struct RBUQnode *v)
0074: {
0075: if(v==v->parent->left)
0076: return(1);
0077: return(0);
0078: }
0079:
0080: /**
0081: * # FUNCTION #
0082: */
0083: static int RBUQisRedNode(struct RBUQnode *v)
0084: {
0085: if(v==NULL) return(0);
0086: if(v->rank == v->parent->rank)
0087: return(1);
0088: return(0);
0089: }
0090:
0091: /**
0092: * # FUNCTION #
0093: */
0094: static struct RBUQnode *RBUQfindMax(struct RBUQnode *v)
0095: {
0096: while(!RBUQisExternalNode(v->right))
0097: v=v->right;
0098: return(v);
0099: }
0100:
0101: /**
0102: * # FUNCTION #
0103: */
0104: static struct RBUQnode *RBUQfind_brother(struct RBUQnode *v)
0105: {
0106: if(RBUQisLeftNode(v))
0107: return(v->parent->right);
0108: return(v->parent->left);
0109: }
0110:
0111: /**
0112: * # FUNCTION #
0113: */
0114: static struct RBUQnode *RBUQmakeNode(void)
0115: {
0116: struct RBUQnode *new;
0117: struct RBUQkey *key;
0118: new=(struct RBUQnode *)mssMalloc(sizeof(struct RBUQnode),"RBUQmkNode");
0119: key=(struct RBUQkey *)mssMalloc(sizeof(struct RBUQkey ),"RBUQmkNode");
0120: new->key=key;
0121: /*new->key.str[0]='\0';*/
0122: new->key->str=NULL;
0123: new->rank = 0;
0124: new->left=new->right=NULL;
0125: return new;
0126: }
0127:
0128: /**
0129: * # FUNCTION #
0130: */
0131: static void RBUQfreeKey(struct RBUQkey *key)
0132: {
0133: mssFree(key->str);
0134: mssFree(key->fld);
0135: mssFree(key->bkt);
0136: mssFree(key);
0137: }
0138:
0139: /**
0140: * # FUNCTION #
0141: */
0142: static void RBUQfreeNode(struct RBUQnode *v)
0143: {
0144: if(RBUQisExternalNode(v)){
0145: mssFree(v->key);
0146: mssFree(v);
0147: return;
0148: }else{
0149: RBUQfreeKey(v->key);
0150: mssFree(v);
0151: return;
0152: }
0153: }
0154:
0155: /**
0156: * # FUNCTION #
0157: */
0158: static void RBUQfreeAllNode(struct RBUQnode *v)
0159: {
0160: if(RBUQisExternalNode(v)){
0161: mssFree(v->key);
0162: mssFree(v);
0163: return;
0164: }else{
0165: RBUQfreeAllNode(v->left);
0166: RBUQfreeAllNode(v->right);
0167: RBUQfreeNode(v);
0168: return;
0169: }
0170: }
0171:
0172: /**
0173: * # FUNCTION #
0174: */
0175: static int keyCmp(struct mssFldRec *fr, struct RBUQnode *v)
0176: {
0177: int i;
0178: int cmp;
0179:
0180: for(i=0; i<OptKey->flds->cnt; i++){
0181: if( 0 != ( cmp=strcmp( *(fr->pnt+MssFlds2num(OptKey->flds,i)),
0182: *(v->key->fld+MssFlds2num(OptKey->flds,i)) )) ){
0183: return(cmp);
0184: }
0185: }
0186: return(0); /*同じキー!!*/
0187: }
0188:
0189: /**
0190: * # FUNCTION #
0191: */
0192: static struct RBUQnode *RBUQmember(struct mssFldRec *fr, struct RBUQnode *v)
0193: {
0194: struct RBUQnode *vv;
0195:
0196: if(RBUQisExternalNode(v)) return(v);
0197:
0198: if( 0 > keyCmp(fr, v) ){
0199: vv=RBUQmember(fr,v->left);
0200: }else if( 0 < keyCmp(fr, v) ){
0201: vv=RBUQmember(fr,v->right);
0202: }else{
0203: return(v);
0204: }
0205: return(vv);
0206: }
0207:
0208: /**
0209: * # FUNCTION #
0210: */
0211: static void RBUQaddExternalNodes(struct RBUQnode *n)
0212: {
0213: n->left = RBUQmakeNode();
0214: n->right= RBUQmakeNode();
0215: n->left->parent =n;
0216: n->right->parent=n;
0217: }
0218:
0219: /**
0220: * # FUNCTION #
0221: */
0222: static void RBUQsingleRotate(struct RBUQnode *v)
0223: {
0224: struct RBUQnode *p, *pp,*ppp;
0225:
0226: p =v->parent;
0227: pp =p->parent;
0228: ppp=pp->parent;
0229:
0230: if(RBUQisLeftNode(pp)){
0231: ppp->left=p;
0232: }else{
0233: ppp->right=p;
0234: }
0235: if(RBUQisLeftNode(v)){
0236: pp->left=p->right;
0237: pp->left->parent=pp;
0238: p->right=pp;
0239: pp->parent=p;
0240: }else{
0241: pp->right = p->left;
0242: pp->right->parent = pp;
0243: p->left = pp;
0244: pp->parent = p;
0245: }
0246: p->parent=ppp;
0247: }
0248:
0249: /**
0250: * # FUNCTION #
0251: */
0252: static void RBUQdouble_rotate(struct RBUQnode *v)
0253: {
0254: struct RBUQnode *p;
0255: p=v->parent;
0256: if(RBUQisLeftNode(v)){
0257: RBUQsingleRotate(v->left);
0258: RBUQsingleRotate(p);
0259: }else{
0260: RBUQsingleRotate(v->right);
0261: RBUQsingleRotate(p);
0262: }
0263: }
0264:
0265: /**
0266: * # FUNCTION #
0267: */
0268: static void RBUQrebalanceOnInsert(struct RBUQnode *v)
0269: {
0270: struct RBUQnode *w, *p, *pp;
0271: int p_is_left;
0272:
0273: p=v->parent;
0274: pp=p->parent;
0275: if(RBUQisTopNode(p)){
0276: return;
0277: }
0278: if(RBUQisRedNode(p)){
0279: p_is_left=0;
0280: if((p_is_left=RBUQisLeftNode(p))){
0281: w=pp->right;
0282: }else{
0283: w=pp->left;
0284: }
0285: if(RBUQisRedNode(w)){
0286: (pp->rank)++;
0287: if(!RBUQisTopNode(pp) && RBUQisRedNode(pp->parent)){
0288: RBUQrebalanceOnInsert(pp);
0289: }
0290: }else{
0291: if(RBUQisLeftNode(v)){
0292: if(p_is_left){
0293: RBUQsingleRotate(v);
0294: }else{
0295: RBUQdouble_rotate(v);
0296: }
0297: }else{
0298: if(p_is_left){
0299: RBUQdouble_rotate(v);
0300: }else{
0301: RBUQsingleRotate(v);
0302: }
0303: }
0304: }
0305: }
0306: }
0307:
0308: /**
0309: * # FUNCTION #
0310: */
0311: static void RBUQdetermineAB(struct RBUQnode **a, struct RBUQnode **b, struct RBUQnode *v, struct RBUQnode *u)
0312: {
0313: if(RBUQisLeftNode(v)){
0314: *a=u->right;
0315: *b=u->left;
0316: }else{
0317: *a=u->left;
0318: *b=u->right;
0319: }
0320: }
0321:
0322: /**
0323: * # FUNCTION #
0324: */
0325: static void RBUQrebalanceOnDelete(struct RBUQnode *v)
0326: {
0327: struct RBUQnode *p,*u,*a,*b;
0328: int v_is_left, p_was_red;
0329:
0330: p=v->parent;
0331: if(v->rank+1 >= p->rank)
0332: return;
0333: u=RBUQfind_brother(v);
0334: RBUQdetermineAB(&a,&b,v,u);
0335: v_is_left=RBUQisLeftNode(v);
0336: p_was_red=RBUQisRedNode(p);
0337: if(RBUQisRedNode(u)){
0338: if(RBUQisRedNode(a) || RBUQisRedNode(b))
0339: return;
0340: RBUQsingleRotate(a);
0341: RBUQrebalanceOnDelete(v);
0342: }else{
0343: if(!RBUQisRedNode(a)){
0344: if(!RBUQisRedNode(b)){
0345: (p->rank)--;
0346: if(!p_was_red)
0347: RBUQrebalanceOnDelete(p);
0348: }else{
0349: RBUQdouble_rotate(b);
0350: (b->rank)++;
0351: (p->rank)--;
0352: }
0353: }else{
0354: RBUQsingleRotate(a);
0355: (u->rank)++;
0356: (u->rank)--;
0357: }
0358: }
0359: }
0360:
0361: /**
0362: * # FUNCTION #
0363: */
0364: static void RBUQptree(struct RBUQnode *p,int h)
0365: {
0366: int i,j;
0367:
0368: if(!RBUQisExternalNode(p)){
0369: RBUQptree(p->left, h+1);
0370: if(0 == strcmp(p->key->str,readEnd) ){
0371: for(i=1; i<=h; i++) fprintf(stderr," ");
0372: printf("key='EOF' ");
0373: /*printf(" bktCnt=%d bkt=",p->key->bktCnt);*/
0374: for(j=0; j<PWayU; j++){
0375: if(*(p->key->bkt+j) == 1)
0376: printf("%d ",j);
0377: }
0378: printf("\n");
0379: }else{
0380: for(i=1; i<=h; i++) fprintf(stderr," ");
0381: printf("key='");
0382: for(j=0; j<OptKey->flds->cnt; j++){
0383: printf("%s ",*(p->key->fld+MssFlds2num(OptKey->flds,j)+1));
0384: }
0385:
0386: /*printf(" bktCnt=%d bkt=",p->key->bktCnt);*/
0387: for(j=0; j<PWayU; j++){
0388: if(*(p->key->bkt+j) == 1)
0389: printf("%d ",j);
0390: }
0391: /*for(j=0; j<p->key->bktCnt; j++){*/
0392: /* printf("%d ",*(p->key->bkt+j));*/
0393: /*}*/
0394: printf("\n");
0395: }
0396: RBUQptree(p->right,h+1);
0397: }
0398: }
0399:
0400: /**
0401: * # FUNCTION #
0402: * RBUQcpKeyの関数で確保されたメモリ量の計算
0403: */
0404: static int RBUQcpKeyMemCnt( struct mssFldRec *fr)
0405: {
0406:
0407: int memCnt=0;
0408:
0409: if(fr->eof==1){ /*EOF*/
0410: /*文字列として番兵を入れておく*/
0411: memCnt+=2*sizeof(char);
0412:
0413: /*キー項目のアドレスを全て番兵に設定する*/
0414: memCnt+=FldCnt*sizeof(char *);
0415:
0416: /*sortUQでは以下のbkt変数は利用していない。mergeRBUQで利用。*/
0417: memCnt+=(sizeof(int)*PWayU);
0418:
0419: }else{
0420:
0421: /*frの全項目をまるごとコピー*/
0422: memCnt+=fr->chrCnt*sizeof(char);
0423:
0424: /*キー項目のアドレスを計算によりセット*/
0425: memCnt+=FldCnt*sizeof(char *);
0426:
0427: /*sortUQでは以下のbkt変数は利用していない。mergeRBUQで利用。*/
0428: memCnt+=(sizeof(int)*PWayU);
0429: }
0430: return(memCnt);
0431: }
0432:
0433: /**
0434: * # FUNCTION #
0435: */
0436: static void RBUQcpKey( struct RBUQnode *v, struct mssFldRec *fr, int bkt)
0437: {
0438: int i;
0439:
0440: if(fr->eof==1){ /*EOF*/
0441: /*文字列として番兵を入れておく*/
0442: v->key->str = mssMalloc(2*sizeof(char),"RBUQUQtree1");
0443: memcpy(v->key->str, readEnd, 2);
0444:
0445: /*キー項目のアドレスを全て番兵に設定する*/
0446: v->key->fld = mssMalloc(FldCnt*sizeof(char *),"RBUQUQtree2");
0447: for(i=0; i<FldCnt; i++){
0448: *(v->key->fld+i) = v->key->str;
0449: }
0450:
0451: /*sortUQでは以下のbkt変数は利用していない。mergeRBUQで利用。*/
0452: v->key->bkt = mssCalloc(sizeof(int)*PWayU, "RBUQtree");
0453: *(v->key->bkt+bkt) = 1;
0454: /**v->key->bkt = bkt;*/
0455: /*v->key->bktCnt = 1;*/
0456:
0457: }else{
0458:
0459: /*frの全項目をまるごとコピー*/
0460: v->key->str = mssMalloc(fr->chrCnt*sizeof(char),"RBUQUQtree4");
0461: memcpy(v->key->str, *fr->pnt, fr->chrCnt);
0462:
0463: /*キー項目のアドレスを計算によりセット*/
0464: v->key->fld = mssMalloc(FldCnt*sizeof(char *),"RBUQUQtree5");
0465: for(i=0; i<FldCnt; i++){
0466: *(v->key->fld+i) = v->key->str + (*(fr->pnt+i) - *fr->pnt);
0467: }
0468:
0469: /*sortUQでは以下のbkt変数は利用していない。mergeRBUQで利用。*/
0470: v->key->bkt = mssCalloc(sizeof(int)*PWayU, "RBUQtree");
0471: *(v->key->bkt+bkt) = 1;
0472: }
0473: }
0474:
0475: /**
0476: * # FUNCTION #
0477: *指定のノードをFldRec構造体のデータで更新
0478: */
0479: static void RBUQupdate( struct RBUQnode *v, int bkt)
0480: {
0481: /*更新したバケット番号をバケットフラグに更新する*/
0482: *(v->key->bkt+bkt) = 1;
0483: }
0484:
0485: /**
0486: * # FUNCTION #
0487: * RBtreeにFldRec構造体のデータを追加
0488: * 既にキーが存在すればRBUQupdateで値を更新
0489: */
0490: static int RBUQinsert( struct RBUQnode *v, struct mssFldRec *fr, int bkt)
0491: {
0492: int memCnt=0;
0493:
0494: v = RBUQmember(fr, v);
0495:
0496: /*キーが存在しなければ追加*/
0497: if(RBUQisExternalNode(v)){
0498: RBUQcpKey(v, fr, bkt);
0499: memCnt=RBUQcpKeyMemCnt(fr);
0500: v->rank=1;
0501: RBUQaddExternalNodes(v);
0502: RBUQrebalanceOnInsert(v);
0503: memCnt+=sizeof(struct RBUQnode)*2;
0504: memCnt+=sizeof(struct RBUQkey )*2;
0505:
0506: /*キーが存在すれば、読み込みフラグをON*/
0507: }else{
0508: RBUQupdate(v, bkt);
0509: }
0510:
0511: return(memCnt);
0512: }
0513:
0514: /**
0515: * # FUNCTION #
0516: *指定のノードを削除
0517: */
0518: static void RBUQdeleteNode(struct RBUQnode *v)
0519: {
0520: struct RBUQnode *w,*x;
0521:
0522: if(RBUQisExternalNode(v)){
0523: fprintf(stderr,"Not found such node\n");
0524: return;
0525: }
0526: if(RBUQhasLeftNode(v)){
0527: w=RBUQfindMax(v->left);
0528: if(w->parent != v){
0529: w->parent->right = w->left;
0530: w->left->parent = w->parent;
0531: }
0532: x=w->left;
0533: RBUQfreeNode(w->right);
0534: /*free(w->right->key);*/
0535: /*free(w->right);*/
0536:
0537: if(RBUQisLeftNode(v)){
0538: v->parent->left=w;
0539: }else{
0540: v->parent->right=w;
0541: }
0542: if(w->parent != v){
0543: w->left = v->left;
0544: w->left->parent = w;
0545: }
0546: w->rank = v->rank;
0547: w->parent = v->parent;
0548: w->right = v->right;
0549: w->right->parent=w;
0550: RBUQfreeNode(v);
0551: /*free(v->key);*/
0552: /*free(v);*/
0553: }else{
0554: w=v->right;
0555: if(RBUQisLeftNode(v)){
0556: v->parent->left=w;
0557: }else{
0558: v->parent->right=w;
0559: }
0560: w->parent=v->parent;
0561: RBUQfreeNode(v->left);
0562: RBUQfreeNode(v);
0563: /*free(v->left->key);*/
0564: /*free(v->left);*/
0565: /*free(v->key);*/
0566: /*free(v);*/
0567: x=w;
0568: }
0569:
0570: RBUQrebalanceOnDelete(x);
0571: }
0572:
0573: /**
0574: * # FUNCTION #
0575: *指定のノードを削除
0576: *RBtreeから優先行のノードアドレスを返す
0577: *この処理でノードを削除はしない。呼び出す本体側でRBUQdeleteNode(node)を実行
0578: */
0579: static struct RBUQnode *RBUQpop(struct RBUQnode *v)
0580: {
0581: struct RBUQnode *vv;
0582:
0583: if(RBUQisExternalNode(v)){
0584: return(NULL);
0585: }else{
0586: vv=v;
0587: while(!RBUQisExternalNode(vv)){
0588: vv=vv->left; /*rightを辿れば最大、leftは最小*/
0589: }
0590: return(vv->parent);
0591: }
0592: }
0593:
0594: /**
0595: * # FUNCTION #
0596: * RBtreeをツリーとして書き出す(デバッグ用)
0597: */
0598: void RBUQprintTree(char *s,struct RBUQnode *pp)
0599: {
0600: fprintf(stderr,"%s\n",s);
0601: RBUQptree(pp,0);
0602: }
0603:
0604: /**
0605: * # FUNCTION #
0606: * 指定のノードを行として書き出す
0607: */
0608: static void RBUQwriteNode( struct RBUQnode *p, struct mssFPW *fpw)
0609: {
0610: int i;
0611:
0612: /*データテキストの出力*/
0613: for(i=0; i<FldCnt-1; i++){
0614: mssWriteStr(*(p->key->fld+i),fpw); mssWriteDlm(fpw);
0615: }
0616: mssWriteStr(*(p->key->fld+i),fpw); mssWriteRet(fpw);
0617: }
0618:
0619: /**
0620: * # FUNCTION #
0621: * RBtreeを全て行として書き出す(デバッグ用)
0622: */
0623: static void RBUQwriteAllNode(struct RBUQnode *p, struct mssFPW *fpw)
0624: {
0625: if(!RBUQisExternalNode(p)){
0626: RBUQwriteAllNode(p->left,fpw);
0627: RBUQwriteNode(p,fpw);
0628: RBUQwriteAllNode(p->right,fpw);
0629: }
0630: }
0631:
0632: /**
0633: * # FUNCTION #
0634: * RBtreeのメモリ領域解放
0635: */
0636: static void RBUQfree(struct RBUQnode *v)
0637: {
0638: RBUQfreeAllNode(v->left);
0639: mssFree(v->key);
0640: mssFree(v);
0641: }
0642:
0643: /**
0644: * # FUNCTION #
0645: * RBnodeの初期化(ノード作成)
0646: */
0647: static struct RBUQnode *RBUQinit(struct RBUQnode *rb)
0648: {
0649: /*赤黒木の初期化*/
0650: rb = RBUQmakeNode();
0651: rb->parent = rb;
0652: rb->right = NULL;
0653: rb->rank = 0;
0654: rb->left = RBUQmakeNode();
0655: rb->left->parent = rb;
0656: return(rb);
0657: }
0658:
0659: /**
0660: * # SECTION #
0661: * ----------------------------------------------------------------------------
0662: * 集計関連関数
0663: * ----------------------------------------------------------------------------
0664: */
0665:
0666: /**
0667: * # FUNCTION #
0668: * 一時ファイル名の取得
0669: */
0670: static char *getFname(char *prefix, int number)
0671: {
0672: /*fnameはグローバル変数*/
0673: sprintf(fname,"%s%d",prefix,number);
0674: return(fname);
0675: }
0676:
0677: /**
0678: * # FUNCTION #
0679: * mssFldRec構造体に一行読み込む(番兵処理)
0680: */
0681: static void readRBUQkey( struct mssFPR *fp, struct mssFldRec *fr)
0682: {
0683: int i;
0684:
0685: if(EOF==mssReadFldRec(fp,fr)){
0686: for(i=0; i<fr->fldCnt; i++)
0687: *(fr->pnt+i)=readEnd; /*EOFの時は番兵を入れる*/
0688: }
0689: }
0690:
0691: /**
0692: * # FUNCTION #
0693: *各バケットの最初の行をRBキューに読み込み
0694: *mergeRB,preSortから呼び出される
0695: *iFromからiToまでのファイルの先頭行をRBキューに入れる
0696: * ud : iFile,rbをセットする
0697: * iFrom: 開始ファイル番号
0698: * iTo : 終了ファイル番号
0699: */
0700: static void setFirstLineRBUQ( struct mssUnqDat *ud, int iFrom, int iTo)
0701: {
0702: int bkt; /*現在処理中のバケット番号(0から始まる)*/
0703: int i;
0704:
0705: /*プライオリティキューの初期化*/
0706: ud->rb=RBUQinit(ud->rb);
0707: bkt=0;
0708: for(i=iFrom; i<=iTo; i++){
0709: ud->fr[bkt]=mssInitFldRec(FldCnt);
0710:
0711: ud->iFile[bkt]=mssOpenFPR(getFname(ud->prefixTxt,i),4);
0712:
0713: /*一行(先頭行)読み込み*/
0714: readRBUQkey(ud->iFile[bkt],ud->fr[bkt]);
0715:
0716: /*赤黒木に挿入(物理的にコピー)*/
0717: RBUQinsert(ud->rb->left,ud->fr[bkt],bkt);
0718: bkt++;
0719: }
0720: }
0721:
0722: /**
0723: * # FUNCTION #
0724: * RBキューを用いたPWayマージ
0725: * 既に並べ変わっているバケット(iCnt個)を併合していく
0726: * 最後の一つになるまで併合はしない
0727: * PWayU個より少なくなったときに併合を止める
0728: */
0729: static void mergeRBUQ(struct mssUnqDat *ud)
0730: {
0731: int bkt[PWayU]; /*Pway併合時にRBtreeからpopしたデータのバケットNo*/
0732: int bktCnt; /*そのバケット数*/
0733: struct RBUQnode *node; /*popにて取りだしたノードを格納*/
0734:
0735: struct mssFPW *oFile; /*出力ワークファイルポインタ*/
0736:
0737: int iStart; /*入力ワークファイルの開始番号(ファイル名の一部)*/
0738: int iEnd; /*入力ワークファイルの終了番号(ファイル名の一部)*/
0739: int oStart; /*出力ワークファイルの開始番号(ファイル名の一部)*/
0740: int oEnd; /*出力ワークファイルの終了番号(ファイル名の一部)*/
0741: int iFrom,iTo; /*併合する時のファイル番号*/
0742: int k;
0743: int i;
0744:
0745: /*次のループでin,outをswapするので、ここでは逆に定義*/
0746: iStart=ud->iEnd+1;
0747: iEnd =ud->iEnd+1;
0748: oStart=ud->iStart;
0749: oEnd =ud->iEnd;
0750:
0751: /*ファイルを併合するループ iCntがPWayU個より大きい場合まわり続ける*/
0752: while(1){
0753: mssSwapInt(&iStart,&oStart);
0754: mssSwapInt(&iEnd ,&oEnd );
0755: oEnd=oStart;
0756:
0757: /*入力ファイル数がPWayU以下ならば終了*/
0758: if(iEnd-iStart+1 <= PWayU){
0759: ud->iStart = iStart;
0760: ud->iEnd = iEnd;
0761: break;
0762: }
0763:
0764: /*Pway個のiFileを一つのoFileに書き出す"を繰り返すループ*/
0765: k=0;
0766: while(1){
0767: /*各バケットの最初行をキューに入れる*/
0768: iFrom= k *PWayU+iStart; /* PWayU=3で一時ファイルが
0769: 0,1,2,3,4,5,6の時*/
0770: iTo =(k+1)*PWayU+iStart-1; /* iFrom: 0 3 6*/
0771: if(iTo>iEnd) iTo=iEnd; /* iTo : 2 5 6*/
0772:
0773: setFirstLineRBUQ(ud, iFrom,iTo);
0774:
0775: /*出力ファイルオープン*/
0776: oFile=mssOpenFPW(getFname(ud->prefixTxt,oEnd),0,0);
0777:
0778: /*各バケットから一行づつ読み込み書き出すループ*/
0779: while(1) {
0780: node=RBUQpop(ud->rb->left); /*キューから一行取り出し*/
0781: if(strcmp(node->key->str,readEnd)==0)/*readEnd(番兵)を取り出したら終了*/
0782: break;
0783: RBUQwriteNode(node,oFile); /*一行書き出し*/
0784: bktCnt=0; /*popで取り出したkey値のバケット数*/
0785: for(i=0; i<PWayU; i++){
0786: if(*(node->key->bkt+i) == 1)
0787: bkt[bktCnt++]=i; /*バケット番号をセット*/
0788: }
0789: RBUQdeleteNode(node); /*取り出したノードの削除*/
0790:
0791: /*popしたバケットから新に読みこんでRBtreeに挿入する*/
0792: for(i=0; i<bktCnt; i++){
0793: readRBUQkey(ud->iFile[bkt[i]],ud->fr[bkt[i]]);
0794: RBUQinsert(ud->rb->left,ud->fr[bkt[i]],bkt[i]);
0795: }
0796: }
0797:
0798: RBUQfree(ud->rb); /*キューの開放*/
0799: for(i=0; i<=iTo-iFrom; i++){ /*入力ファイルのクローズ*/
0800: mssCloseFPR(ud->iFile[i]);
0801: mssFreeFldRec(ud->fr[i]);
0802: }
0803: mssCloseFPW(oFile); /*出力ファイルのクローズ*/
0804: if(iTo==iEnd)break; /*最後のバケットまでいけば終了*/
0805: oEnd++; /*出力ファイル番号カウントアップ*/
0806: k++; /*併合回数カウントアップ*/
0807: }
0808: for(i=iStart; i<=iEnd; i++){
0809: unlink(getFname(ud->prefixTxt,i)); /*入力ワークファイルの削除*/
0810: }
0811: }
0812: }
0813:
0814: /**
0815: * # FUNCTION #
0816: * 集計しながらsortする関数
0817: * 集計しながら赤黒木を作成
0818: * メモリ消費がMAXを越えたら一時ファイルに書き出し
0819: */
0820: static void sortUQ( struct mssUnqDat *ud, struct mssFPR *fpr)
0821: {
0822:
0823: struct mssFldRec *fr; /*入力ファイルをキー順に並べ換えるためのバッファ*/
0824: int pid; /*プロセスID(ファイル名の一部)*/
0825: int oNum; /*ワークファイル番号のカウントアップ変数*/
0826: int memCnt; /*メモリ消費量*/
0827:
0828: struct RBUQnode *rb=NULL; /*赤黒木*/
0829: struct mssFPW *fpw; /*出力一時ファイル*/
0830:
0831: fr=mssInitFldRec(FldCnt);/*FldRecの初期化*/
0832: rb=RBUQinit(rb); /*RBUQtreeの初期化*/
0833:
0834: /*ファイル名のプレフィックスの設定*/
0835: pid=getpid();
0836: if(strlen(ud->tmpDir) > MssFileNameMaxLen - 50 ) {
0837: mssShowErrMsg("length of path name must be less than %d",MssFileNameMaxLen-50);
0838: exit(mssErrorNoDefault);
0839: }
0840: sprintf(ud->prefixTxt,"%s/xt##%d-PreUnqTxt-",ud->tmpDir,pid);
0841:
0842: memCnt=0; /*消費メモリカウンタのクリア*/
0843: oNum=0; /*出力ファイル番号*/
0844: while(1){
0845: /*データの読み込み*/
0846: mssReadFldRec(fpr,fr);
0847: (*ud->inCnt)++;
0848:
0849: /*赤黒木のサイズがMaxを越えたら もしくは 最終行を検出したら*/
0850: /*ワークファイルへ書き出す*/
0851: if( memCnt >= MaxMemU || fr->eof==1){
0852: fpw=mssOpenFPW(getFname(ud->prefixTxt,oNum),0,0);/*出力ファイルオープン*/
0853: RBUQwriteAllNode(rb->left, fpw); /*RBtree全て出力*/
0854: mssCloseFPW(fpw); /*出力ファイルのクローズ*/
0855: oNum++; /*出力ファイル数countUp*/
0856: RBUQfree(rb); /*RBUQtreeの領域解放*/
0857: if(fr->eof==1){ /*最終行で終了*/
0858: (*ud->inCnt)--;
0859: break;
0860: }
0861: rb=RBUQinit(rb); /*RBUQtreeの初期化*/
0862: memCnt=0; /*消費メモリカウンタのクリア*/
0863: }
0864:
0865: /*赤黒木に挿入して(物理的にコピー)、メモリ消費をカウントアップ*/
0866: memCnt += RBUQinsert(rb->left,fr,1);
0867: }
0868: mssFreeFldRec(fr);/*FldRecの初期化*/
0869:
0870: ud->iStart = 0;
0871: ud->iEnd = oNum-1;
0872: }
0873:
0874: /**
0875: * # FUNCTION #
0876: *必用となる項目関係のグローバル変数の設定
0877: *preUnqとrbTreeUQとのつなぎのための変数は全てここで
0878: */
0879: struct mssUnqDat *mssInitUnqDat(int fldCnt, MssOptKEY *optKey, char *tmpDir, int *inCnt)
0880: {
0881: struct mssUnqDat *unqDat;
0882: unqDat=mssMalloc(sizeof(struct mssUnqDat),"initUnqDat");
0883:
0884: unqDat->fldCnt = fldCnt;
0885: unqDat->optKey = optKey;
0886: unqDat->tmpDir = tmpDir;
0887: unqDat->inCnt = inCnt;
0888:
0889: /*グローバル変数*/
0890: FldCnt = unqDat->fldCnt;
0891: OptKey = unqDat->optKey;
0892:
0893: return(unqDat);
0894: }
0895:
0896: /**
0897: * # FUNCTION #
0898: * RBキューを用いた項目切り分け型行読み込み
0899: * 既に並べ変わっているバケット(ud->iStartからud->iEnd)を
0900: * 集計しながら併合していく
0901: * ファイルの個数は既にPWayU以下になっていることが前提
0902: */
0903: int mssReadWriteUnq(struct mssUnqDat *ud, struct mssFPW *oFile)
0904: {
0905: struct RBUQnode *node; /*popにて取りだしたノードを格納*/
0906: int bkt[PWayU];/*Pway併合時にRBtreeからpopしたデータのバケットNo*/
0907: int bktCnt; /*そのバケット数*/
0908: int i;
0909:
0910: node=RBUQpop(ud->rb->left); /*キューから一行取り出し*/
0911: if(strcmp(node->key->str,readEnd)==0) /*readEnd(番兵)を取り出したら終了*/
0912: return(EOF);
0913:
0914: /*一行書き出し*/
0915: mssWriteFld(node->key->fld,FldCnt,"\n",oFile);
0916:
0917: bktCnt=0; /*popで取り出したkey値のバケット数*/
0918: for(i=0; i<PWayU; i++){
0919: if(*(node->key->bkt+i) == 1)
0920: bkt[bktCnt++]=i; /*バケットフラグをセット*/
0921: }
0922: RBUQdeleteNode(node); /*取り出したノードの削除*/
0923:
0924: /*popしたバケットから新に読みこんでRBtreeに挿入する*/
0925: for(i=0; i<bktCnt; i++){
0926: readRBUQkey(ud->iFile[bkt[i]],ud->fr[bkt[i]]);
0927: RBUQinsert(ud->rb->left,ud->fr[bkt[i]],bkt[i]);
0928: }
0929: return(1); /*とりあえず*/
0930: }
0931:
0932: /**
0933: * # FUNCTION #
0934: * mssUnqDat構造体の開放。
0935: */
0936: void mssFreeUnqDat(struct mssUnqDat *ud)
0937: {
0938: int i;
0939:
0940: if(ud->procType==1){
0941: /*バッファ管理のために、入力ファイルはここで初めてクローズする*/
0942: for(i=0; i<=ud->iEnd-ud->iStart; i++){
0943: mssCloseFPR(ud->iFile[i]);
0944: mssFreeFldRec(ud->fr[i]);
0945: }
0946:
0947: /*ファイルの削除*/
0948: for(i=ud->iStart; i<=ud->iEnd; i++){
0949: unlink(getFname(ud->prefixTxt,i));
0950: }
0951:
0952: /*領域開放*/
0953: RBUQfree(ud->rb);
0954: }
0955: mssFree(ud);
0956: }
0957:
0958: /**
0959: * # FUNCTION #
0960: * 赤黒木を作りながら集計＋集計しながらPWayマージソート
0961: */
0962: void mssPreUnq( struct mssUnqDat *ud, struct mssFPR *iFile)
0963: {
0964: /*シグナルハンドラの設定*/
0965: mssGV.usedTempFileFlg=1;
0966: mssSetSignalHandler();
0967:
0968: sortUQ(ud,iFile);
0969: mergeRBUQ(ud);
0970: setFirstLineRBUQ(ud, ud->iStart,ud->iEnd);
0971: }