MUSASHI C source: mssHash.c

グローバル関数
mssFreeHash mssFreeHashFld mssHashInsert mssHashInsertAdd mssHashInsertAddNull mssHashInsertFld mssHashMember mssHashMemberAdd mssHashMemberFld mssHashMemberVal mssInitHash mssInitHashFld mssShowHash mssShowHashFld

ローカル関数
getHashVal getHashValFld keyCmp

0001: /** 
0002:  * # CHAPTER # 
0003:  * ============================================================================ 
0004:  * MUSASHIで用いられるハッシュ関連の関数 
0005:  * ============================================================================ 
0006:  */ 
0007:  
0008: #include <mssHash.h> 
0009: #include <mssValue.h> 
0010: #include <mssHeader.h> 
0011:  
0012: #include <string.h> 
0013:  
0014: /** 
0015:  * # SECTION # 
0016:  * ---------------------------------------------------------------------------- 
0017:  * 行-項目を扱うハッシュ 
0018:  * ---------------------------------------------------------------------------- 
0019:  */ 
0020:  
0021: /** 
0022:  * # FUNCTION # 
0023:  * 行-項目Hash関数：複数項目文字列からのHash値の計算 
0024:  */ 
0025: static int getHashValFld(char **str, struct mssFields *flds, int hv) 
0026: { 
0027:   int i,h=0; 
0028:   char *v; 
0029:  
0030:   for(i=0; i<flds->cnt; i++){ 
0031:     v=*(str+MssFlds2num(flds,i)); 
0032:     while(*v != '\0'){ 
0033:       h=(64*h + (unsigned char)*v) % hv; 
0034:       v++; 
0035:     } 
0036:   } 
0037:   return h; 
0038: } 
0039:  
0040: /** 
0041:  * # FUNCTION # 
0042:  * 二つの行(s1,s2)の指定項目(flds1,flds2)によるの比較 
0043:  * strcmp()関数と同様の値を返す。 
0044:  */ 
0045: static int keyCmp(char **s1,struct mssFields *flds1,char **s2,struct mssFields *flds2) 
0046: { 
0047:   int i; 
0048:   int cmp; 
0049:  
0050:   if( flds1->cnt != flds2->cnt ){ 
0051:     mssShowErrMsg("internal error : mismatch of the number of key fields"); 
0052:     exit(mssErrorNoDefault); 
0053:   } 
0054:  
0055:   for(i=0; i<flds1->cnt; i++){ 
0056:     if( 0 != (cmp=strcmp(*(s1+MssFlds2num(flds1,i)), 
0057:                          *(s2+MssFlds2num(flds2,i)))) ){ 
0058:       return(cmp); 
0059:     } 
0060:   } 
0061:   return(0); 
0062: } 
0063:  
0064: /** 
0065:  * # FUNCTION # 
0066:  * 行-項目ハッシュ構造体(HashFld)を初期化し、そのポインタを返す。 
0067:  * sizeには、ハッシュ表のサイズ(スロットの数)を指定する。 
0068:  * fldsは、ハッシュ値を計算する元になる項目を示したmssFields構造体。 
0069:  * この値は、２の巾乗に近くない素数を選ぶべきである。 
0070:  * チェイン法を用いている。 
0071:  * ハッシュ関数には除算法を用いている。 
0072:  */ 
0073: struct mssHashFld *mssInitHashFld( int size, struct mssFields *flds) 
0074: { 
0075:  
0076:   struct mssHashFld *hash; 
0077:  
0078:   hash=mssMalloc(sizeof(struct mssHashFld),"initHashFld"); 
0079:   hash->hashVal = size; 
0080:   hash->flds    = flds; 
0081:   hash->keyCnt  = 0; 
0082:   hash->endCnt  = 0; 
0083:   hash->node=mssCalloc(sizeof(struct mssHashNodeFld *)*hash->hashVal,"initHashFld"); 
0084:   return(hash); 
0085: } 
0086:  
0087: /** 
0088:  * # FUNCTION # 
0089:  * 行-項目ハッシュ構造体(HashFld)領域の開放。 
0090:  */ 
0091: void mssFreeHashFld(struct mssHashFld *hash){ 
0092:   int i; 
0093:   struct mssHashNodeFld *node; 
0094:   struct mssHashNodeFld *tmp; 
0095:  
0096:   if(hash==NULL) return; 
0097:   for(i=0; i<hash->hashVal; i++){ 
0098:     if( NULL != (node=*(hash->node+i)) ){ 
0099:       while(node!=NULL){ 
0100:         tmp=node; 
0101:         mssFree(node->rec); 
0102:         node=node->next; 
0103:         mssFree(tmp); 
0104:       } 
0105:     } 
0106:   } 
0107:   mssFree(hash->node); 
0108:   mssFree(hash); 
0109: } 
0110:  
0111: /** 
0112:  * # FUNCTION # 
0113:  * 行-項目ハッシュテーブルに、新しいデータを追加する。 
0114:  */ 
0115: void mssHashInsertFld(struct mssHashFld *hash, char **str) 
0116: { 
0117:   int hv; 
0118:  
0119:   struct mssHashNodeFld *newNode; 
0120:   struct mssHashNodeFld *node; 
0121:   struct mssHashNodeFld *last; 
0122:  
0123:   hv=getHashValFld(str,hash->flds,hash->hashVal); 
0124:   node=*(hash->node+hv); 
0125:  
0126:   newNode=mssCalloc(sizeof(struct mssHashNodeFld),"hashInsertFld"); 
0127:  
0128:   if(node==NULL){ 
0129:     *(hash->node+hv)=newNode; 
0130:   }else{ 
0131:     while(node!=NULL){ 
0132:       if(0==keyCmp(*node->rec,hash->flds,str,hash->flds)){ 
0133:         node->rec=mssRealloc(node->rec, 
0134:                           sizeof(char **)*(node->recCnt+1),"hashInsertFld"); 
0135:         *(node->rec+node->recCnt)=str; 
0136:         node->recCnt++; 
0137:         mssFree(newNode); 
0138:         return; 
0139:       }else{ 
0140:         last=node; 
0141:         node=node->next; 
0142:       } 
0143:     } 
0144:     last->next=newNode; 
0145:   } 
0146:   newNode->rec=mssMalloc(sizeof(char **),"hashInsertFld"); 
0147:   *newNode->rec=str; 
0148:   newNode->recCnt++; 
0149:   newNode->next=NULL;  
0150:   hash->keyCnt++; /*キーの種類をカウントアップ*/ 
0151: } 
0152:  
0153: /** 
0154:  * # FUNCTION # 
0155:  * 行-項目ハッシュテーブルから指定の項目値を持った値を検索しする。 
0156:  * 見つかれば、そのHashNodeFldへのポインタを返す。なければNULLを返す。 
0157:  * 項目値はstrとfldsによって指定する。 
0158:  */ 
0159: struct mssHashNodeFld *mssHashMemberFld( struct mssHashFld *hash, char **str, struct mssFields *flds) 
0160: { 
0161:   int hv; 
0162:   struct mssHashNodeFld *node; 
0163:  
0164:   hv=getHashValFld(str,flds,hash->hashVal); 
0165:   node=*(hash->node+hv); 
0166:  
0167:   while(node!=NULL){ 
0168:     if(0==keyCmp(*node->rec,hash->flds,str,flds)){ 
0169:       node->endFlg=1; 
0170:       hash->endCnt++; 
0171:       return(node); 
0172:     }else{ 
0173:       node=node->next; 
0174:     } 
0175:   } 
0176:   return(NULL); 
0177: } 
0178:  
0179: /** 
0180:  * # FUNCTION # 
0181:  * 行-項目ハッシュテーブルの出力(デバッグ用)。 
0182:  */ 
0183: void mssShowHashFld(struct mssHashFld *hash, int fldCnt) 
0184: { 
0185:   int i,j,k; 
0186:   struct mssHashNodeFld *node; 
0187:  
0188:   printf("Key    :"); 
0189:   for(i=0; i<hash->flds->cnt; i++){ 
0190:     printf("%d ", (*(hash->flds->fi+i))->num); 
0191:   } 
0192:   printf("\n"); 
0193:   printf("keyCnt :%d\n",hash->keyCnt); 
0194:   printf("endCnt :%d\n",hash->endCnt); 
0195:   printf("fldCnt :%d\n",hash->fldCnt); 
0196:   printf("hashVal:%d\n",hash->hashVal); 
0197:   for(i=0; i<hash->hashVal; i++){ 
0198:     if( NULL!=(node=*(hash->node+i)) ){ 
0199:       while(node!=NULL){ 
0200:         printf("========== HashNo: [%d]\n",i); 
0201:         for(j=0; j<node->recCnt; j++){ 
0202:           for(k=0; k<fldCnt; k++){ 
0203:             printf("|%s |",*(*(node->rec+j)+k)); 
0204:           } 
0205:           printf("\n"); 
0206:         } 
0207:         node=node->next; 
0208:       } 
0209:     } 
0210:   } 
0211: } 
0212:  
0213: /** 
0214:  * # SECTION # 
0215:  * ---------------------------------------------------------------------------- 
0216:  * MssValueを扱うハッシュ 
0217:  * ---------------------------------------------------------------------------- 
0218:  */ 
0219:  
0220: /** 
0221:  * # FUNCTION # 
0222:  * MssValue Hash関数：複数項目文字列からのHash値の計算 
0223:  */ 
0224: static int getHashVal(char *str,int hv){ 
0225:   int v=0; 
0226:  
0227:   while(*str != '\0') v+=(unsigned char)*str++; 
0228:   return(v % hv); 
0229: } 
0230:    
0231: /** 
0232:  * # FUNCTION # 
0233:  * MssValueハッシュ構造体(Hash)を初期化し、そのポインタを返す。 
0234:  * sizeには、ハッシュ表のサイズ(スロットの数)を指定する。 
0235:  * fldsは、ハッシュ値を計算する元になる項目を示したmssFields構造体。 
0236:  * この値は、２の巾乗に近くない素数を選ぶべきである。 
0237:  * チェイン法を用いている。 
0238:  * ハッシュ関数には除算法を用いている。 
0239:  */ 
0240: struct mssHash *mssInitHash(int size) 
0241: { 
0242:  
0243:   struct mssHash *hash; 
0244:  
0245:   hash=mssMalloc(sizeof(struct mssHash),"initHash"); 
0246:   hash->hashVal = size; 
0247:   hash->cnt = 0; 
0248:   hash->node=mssCalloc(sizeof(struct mssHashNode *)*hash->hashVal,"initHash"); 
0249:   return(hash); 
0250: } 
0251:  
0252: /** 
0253:  * # FUNCTION # 
0254:  * MssValueハッシュ構造体(HashFld)領域の開放。 
0255:  */ 
0256: void mssFreeHash(struct mssHash *hash) 
0257: { 
0258:   int i; 
0259:   struct mssHashNode *node; 
0260:   struct mssHashNode *tmp; 
0261:  
0262:   if(hash==NULL) return; 
0263:   for(i=0; i<hash->hashVal; i++){ 
0264:     if( NULL != (node=*(hash->node+i)) ){ 
0265:       while(node!=NULL){ 
0266:         tmp=node; 
0267:         mssFree(node->str); 
0268:         node=node->next; 
0269:         mssFree(tmp); 
0270:       } 
0271:     } 
0272:   } 
0273:   mssFree(hash->node); 
0274:   mssFree(hash); 
0275: } 
0276:  
0277: /** 
0278:  * # FUNCTION # 
0279:  * MssValueハッシュテーブルに、新しいデータ(val)を追加する。 
0280:  * 新しい値としてinsertできれば1を返す.既に値が存在すれば0を返す。 
0281:  */ 
0282: int mssHashInsert( struct mssHash *hash, char *str, MssValue val) 
0283: { 
0284:   int hv; 
0285:   struct mssHashNode *newNode; 
0286:   struct mssHashNode *node; 
0287:   struct mssHashNode *last; 
0288:  
0289:   hv=getHashVal(str,hash->hashVal); 
0290:   node=*(hash->node+hv); 
0291:  
0292:   newNode=mssMalloc(sizeof(struct mssHashNode),"hashInsert"); 
0293:  
0294:   if(node==NULL){ 
0295:    *(hash->node+hv)=newNode; 
0296:   }else{ 
0297:     while(node!=NULL){ 
0298:       if( 0==strcmp(node->str,str) ){ 
0299:         mssFree(newNode); 
0300:         return(0); 
0301:       }else{ 
0302:         last=node; 
0303:         node=node->next; 
0304:       } 
0305:     } 
0306:     last->next=newNode; 
0307:   } 
0308:   newNode->str=mssStrdup(str); 
0309:   newNode->val=val; 
0310:   newNode->next=NULL; 
0311:   hash->cnt++; 
0312:   return(1); 
0313: } 
0314:  
0315: /** 
0316:  * # FUNCTION # 
0317:  * MssValueハッシュテーブルに、新しいデータ(val)を追加する。 
0318:  * 新しい値としてinsertできればノードのアドレスを返す。 
0319:  * 既に値が存在すれば、そのノードのアドレスを返す。 
0320:  */ 
0321: struct mssHashNode *mssHashInsertAdd(struct mssHash *hash, char *str, MssValue val) 
0322: { 
0323:   int hv; 
0324:   struct mssHashNode *newNode; 
0325:   struct mssHashNode *node; 
0326:   struct mssHashNode *last; 
0327:  
0328:   hv=getHashVal(str,hash->hashVal); 
0329:   node=*(hash->node+hv); 
0330:  
0331:   newNode=mssMalloc(sizeof(struct mssHashNode),"hashInsertAdd"); 
0332:  
0333:   if(node==NULL){ 
0334:    *(hash->node+hv)=newNode; 
0335:   }else{ 
0336:     while(node!=NULL){ 
0337:       if( 0==strcmp(node->str,str) ){ 
0338:         mssFree(newNode); 
0339:         return(node); 
0340:       }else{ 
0341:         last=node; 
0342:         node=node->next; 
0343:       } 
0344:     } 
0345:     last->next=newNode; 
0346:   } 
0347:   newNode->str=mssStrdup(str); 
0348:   newNode->val=val; 
0349:   newNode->next=NULL; 
0350:   hash->cnt++; 
0351:   return(newNode); 
0352: } 
0353:  
0354: /** 
0355:  * # FUNCTION # 
0356:  * MssValueハッシュテーブルに、新しいデータ(val)を追加する。 
0357:  * 新しい値としてinsertできればノードのアドレスを返す。 
0358:  * 既に値が存在すれば、NULLを返す。 
0359:  */ 
0360: struct mssHashNode *mssHashInsertAddNull(struct mssHash *hash, char *str, MssValue val) 
0361: { 
0362:   int hv; 
0363:   struct mssHashNode *newNode; 
0364:   struct mssHashNode *node; 
0365:   struct mssHashNode *last; 
0366:  
0367:   hv=getHashVal(str,hash->hashVal); 
0368:   node=*(hash->node+hv); 
0369:  
0370:   newNode=mssMalloc(sizeof(struct mssHashNode),"hashInsertAdd"); 
0371:  
0372:   if(node==NULL){ 
0373:    *(hash->node+hv)=newNode; 
0374:   }else{ 
0375:     while(node!=NULL){ 
0376:       if( 0==strcmp(node->str,str) ){ 
0377:         mssFree(newNode); 
0378:         return(NULL); 
0379:       }else{ 
0380:         last=node; 
0381:         node=node->next; 
0382:       } 
0383:     } 
0384:     last->next=newNode; 
0385:   } 
0386:   newNode->str=mssStrdup(str); 
0387:   newNode->val=val; 
0388:   newNode->next=NULL; 
0389:   hash->cnt++; 
0390:   return(newNode); 
0391: } 
0392:  
0393: /** 
0394:  * # FUNCTION # 
0395:  * MssValueハッシュテーブルに、メンバー(str)があるか検索する。 
0396:  * あればばそのノードへのポインタを返し、なければNULLを返す。 
0397:  */ 
0398: struct mssHashNode *mssHashMember(struct mssHash *hash, char *str) 
0399: { 
0400:   int hv; 
0401:   struct mssHashNode *node; 
0402:  
0403:   hv=getHashVal(str,hash->hashVal); 
0404:   node=*(hash->node+hv); 
0405:   while(node!=NULL){ 
0406:     if( 0==strcmp(node->str,str) ){ 
0407:       return(node); 
0408:     }else{ 
0409:       node=node->next; 
0410:     } 
0411:   } 
0412:   return(NULL); 
0413: } 
0414:  
0415: /** 
0416:  * # FUNCTION # 
0417:  * MssValueハッシュテーブルに、メンバー(str)があるか検索する。 
0418:  * あればそのメンバーの文字列(node->str)へのポインタを返し、なければNULLを返す。 
0419:  */ 
0420: char *mssHashMemberAdd(struct mssHash *hash, char *str) 
0421: { 
0422:   int hv; 
0423:   struct mssHashNode *node; 
0424:  
0425:   hv=getHashVal(str,hash->hashVal); 
0426:   node=*(hash->node+hv); 
0427:   while(node!=NULL){ 
0428:     if( 0==strcmp(node->str,str) ){ 
0429:       return(node->str); 
0430:     }else{ 
0431:       node=node->next; 
0432:     } 
0433:   } 
0434:   return(NULL); 
0435: } 
0436:  
0437: /** 
0438:  * # FUNCTION # 
0439:  * MssValueハッシュテーブルに、メンバー(str)があるか検索する。 
0440:  * あればそのメンバーのMssValue(node->value)を返し、なければNULLのMssValueを返す。 
0441:  */ 
0442: MssValue mssHashMemberVal(struct mssHash *hash, char *str) 
0443: { 
0444:   int hv; 
0445:   struct mssHashNode *node; 
0446:   MssValue v; 
0447:  
0448:   hv=getHashVal(str,hash->hashVal); 
0449:   node=*(hash->node+hv); 
0450:   while(node!=NULL){ 
0451:     if( 0==strcmp(node->str,str) ){ 
0452:       return(node->val); 
0453:     }else{ 
0454:       node=node->next; 
0455:     } 
0456:   } 
0457:   v.nul=1; 
0458:   return(v); 
0459: } 
0460:  
0461: /** 
0462:  * # FUNCTION # 
0463:  * MssValueハッシュテーブルの出力(デバッグ用)。 
0464:  */ 
0465: void mssShowHash(struct mssHash *hash) 
0466: { 
0467:   int i; 
0468:   struct mssHashNode *node; 
0469:  
0470:   for(i=0; i<hash->hashVal; i++){ 
0471:     if( NULL != (node=*(hash->node+i)) ){ 
0472:       while(node!=NULL){ 
0473:         printf("hashVal=%d str=%s ",i,node->str); 
0474:         switch(node->val.vType){ 
0475:         case INT : /* int    */ 
0476:           printf("val=%d\n",node->val.v.i); 
0477:           break; 
0478:         case DBL : /* double */ 
0479:           printf("val=%g\n",node->val.v.d); 
0480:           break; 
0481:         case STR : /* char * */ 
0482:           printf("val=%s\n",node->val.v.s); 
0483:           break; 
0484:         case ADD : /* void * */ 
0485:           printf("val=%x\n",(int)node->val.v.a); 
0486:           break; 
0487:         case USI : /* unsigned short int */ 
0488:           printf("val=%d\n",(int)node->val.v.usi); 
0489:           break; 
0490:         } 
0491:         node=node->next; 
0492:       } 
0493:     } 
0494:   } 
0495: } 
0496: