publib.c

求2个或多个文本间的公共子串

#include "publib.h"

ssize_t readblock(int fd, void * buf, size_t size)
{
	
	char * bufp = buf;
	size_t bytestoread = size;
	ssize_t bytesread = 0;
	size_t totalbytes = 0;

	if( (NULL == buf) && (0 != size) )
		return -1;

	for(; 0 < bytestoread; bufp += bytesread, bytestoread -= bytesread){
		bytesread = read(fd, bufp, bytestoread);
		
		if(0 == bytesread){
			if(0 == totalbytes){
				return 0;
			}else{
				errno = EINVAL;
				return -1;
			}
		}

		
		if(-1 == bytesread){
			if(EINTR == errno){
				bytesread = 0;
			}else{
				return -1;
			}
		}
		
		totalbytes += bytesread;
	}
	
	return totalbytes;
}


int GetFileInfo(char * pPath, Fileinfo * pInfo)
{
	struct stat statbuf;
	int retval = -1;	
	int filefd = -1;
	
	if((NULL == pPath) || (NULL == pInfo)){
		return -1;
	}

	if(-1 == stat(pPath, &statbuf)){
		perror("Failed to get file status");
		return -1;
	}
	
	
	pInfo->nLen = statbuf.st_size;
	strncpy( pInfo->pPath, pPath, sizeof(pInfo->pPath));
	
	pInfo->pStr = (char *)malloc(statbuf.st_size);
	if(NULL == pInfo->pStr){
		perror("Failed to allocate memory");
		return -1;
	}
	
	
	while( (-1 == (filefd = open(pPath, O_RDONLY))) && (EINTR == errno));
	if(-1 == filefd){
		perror("Filed to open the file");
		free(pInfo->pStr);
		return -1;
	}
	
	if(readblock(filefd, pInfo->pStr, pInfo->nLen) != pInfo->nLen){
		perror("Failed to read file content");
		free(pInfo->pStr);
		return -1;
	}

	while( retval = close(filefd), (-1 == retval) && (EINTR == errno));
	if(-1 == retval){
		perror("Failed to close the file");
	}
	
	return 0;
}





int TransferString(char * pOrgStr, const size_t orgLen, smch_t ** ppTranStr, size_t * pTranLen)
{
	size_t turn = 0;
	size_t inturn = 0;
	char * pChar = pOrgStr;
	char * pTranChar = NULL;
	
		
	/* for tranStr and pTranLen
	**********/
	size_t alloMemSize = 0;
	volatile size_t useMemSize = 0;
	const size_t eleSize = sizeof(smch_t);
	const size_t increSize = 10 * eleSize;
	
	/* bulk copy interval
	**********/
	volatile int nBegPos = -1;
	volatile int nEndPos = -1;

	char str[3];
	str[2] = 0;

	if( (NULL == pOrgStr) && (0 != orgLen))
		return -1;
	if( (NULL == pTranLen) || (NULL == ppTranStr))
		return -1;
	

	useMemSize = 0;
	alloMemSize = orgLen + increSize;
	*pTranLen = 0;
        *ppTranStr = (smch_t *)malloc(alloMemSize);
	pTranChar = (char *) *ppTranStr;
	if(NULL == *ppTranStr){
		perror("Failed to allocate memory when transfering string");
		return -1;
	}

	
	for(turn = 0; turn < orgLen;){
		
		/*******
		str[0] = *pChar;
		str[1] = *(pChar + 1);
		printf(" %u => %s\n", turn, str);
		********/
		
		if(643 == turn){
			printf("we got it!");
		}
				
		if(*pChar < 0){  /* simple chinese character */

			if(0 > nBegPos){
				nBegPos = turn;				
			}

			turn += eleSize; /* eleSize is 2 in 2006 */
			pChar += eleSize; 

		}else{           /* European  character */
			if(0 <= nBegPos){
				nEndPos = turn;
				if( (nEndPos - nBegPos) >= (alloMemSize - useMemSize)){  /* no enough memory */
                                        alloMemSize = (nEndPos - nBegPos) - (alloMemSize - useMemSize) \
                                         + alloMemSize + (orgLen - turn) + increSize;
					if(NULL == (*ppTranStr = realloc(*ppTranStr, alloMemSize))){
						perror("Failed to realloc");
						return -1;
					}
					pTranChar = (char *) *ppTranStr + useMemSize;
				}
				
				/* bulk copy
				********/
				strncpy(pTranChar, (char *)pOrgStr + nBegPos, nEndPos - nBegPos);
				useMemSize += (nEndPos - nBegPos);
				pTranChar += (nEndPos - nBegPos);
							

				nBegPos = -1;
				nEndPos = -1;
				
			}

			/* character copy
                        ********/
			if( (alloMemSize - useMemSize) <= (orgLen - turn) ){
				alloMemSize = alloMemSize + (orgLen - turn) - (alloMemSize - useMemSize) + increSize;
				if(NULL == (*ppTranStr = realloc(*ppTranStr, alloMemSize))){
                                	perror("Failed to realloc");
                                        return -1;
                             	}
                                pTranChar = (char *) *ppTranStr + useMemSize;
			}

                        for(inturn = 1; inturn < eleSize; ++inturn)
                        	*pTranChar++ = ' ';
                        *pTranChar++ = *pChar;
			useMemSize += eleSize;

			++turn;  /* only skip one character */
			++pChar;
		}
	}

	
	if(0 <= nBegPos){
		nEndPos = orgLen;
		if( (nEndPos - orgLen) % 2 != 0 ){
			--nEndPos;
			if(nEndPos <= nBegPos)
				return 0;
		}
			
		if( (nEndPos - nBegPos) >= (alloMemSize - useMemSize)){  /* no enough memory */
			alloMemSize = (nEndPos - nBegPos) - (alloMemSize - useMemSize) + alloMemSize;
			if(NULL == (*ppTranStr = realloc(*ppTranStr, alloMemSize))){
				perror("Failed to realloc");
				return -1;
			}
			pTranChar = (char *) *ppTranStr + useMemSize;
		}
		
		/* bulk copy
		 *********/ 
		strncpy(pTranChar, (char *)pOrgStr + nBegPos, nEndPos - nBegPos);
		useMemSize += (nEndPos - nBegPos);
	}
	
	
	*pTranLen = useMemSize;
	
	return 0;	

}

unsigned int SmchGB_Hash(const unsigned short smch)
{
	unsigned char * pChar = (unsigned char *)&smch;
	return ((*pChar - 176) * 94 + *(pChar + 1) - 161);
	
}

unsigned int SmchGBKHash(const unsigned short smch)
{
	unsigned char * pChar = (unsigned char *)&smch;
	return ((*pChar - 129) * 190 + ( *(pChar + 1) - 64) - *(pChar + 1)/128);
}



int IndexCharForStr(smch_t * pConStr, const size_t nStrLen, CharIndex ** ppIndexArray, const size_t nIdxLen)
{
	smch_t * pSmch = NULL;
	size_t turn = 0;
	size_t uiHashPos = 0;
	smch_t smch = 0;
	CharIndex * pIndex = NULL;
	CharIndex * pIdxCur = NULL;
	
	
	if(NULL == pConStr)	
		return -1;
	if((0 != nStrLen) && ( (NULL == ppIndexArray) || (0 == nIdxLen)))
		return -1;
	if(0 == nStrLen) 
		return 0;

	
	for(turn = 0; turn < nIdxLen; ++turn){
		ppIndexArray[turn] = NULL;
	}	
	
	

	for(pSmch = pConStr, turn = 0; turn < nStrLen; ++turn, ++pSmch){
		smch = *pSmch;
		uiHashPos = (size_t)(SmchGBKHash(smch)) % nIdxLen;
		

		pIdxCur = ppIndexArray[uiHashPos];

		/********
		if(137 == turn){
			printf("we got it! index => %u hash => %u\n", (int)pIdxCur, uiHashPos);
		}
		************/
		
				
		if(NULL == pIdxCur){
			
			if(NULL == (pIndex = (CharIndex *)malloc(sizeof(CharIndex)))){
				perror("Failed to malloc");
				return -1;
			}
			pIndex->smch = smch;
			pIndex->pNext = NULL;
			pIndex->memLen = 5;
			pIndex->memUse = 0;
			pIndex->location = (size_t *)malloc(pIndex->memLen * sizeof(size_t));
			if(NULL == pIndex->location){
				perror("Failed to allocate memory");
				return -1;
			}
			pIndex->location[pIndex->memUse] = turn;
			pIndex->memUse = 1;
			
			
			ppIndexArray[uiHashPos] = pIndex;
		}else{
			
			while( (pIdxCur->smch != smch) && (NULL != pIdxCur->pNext)){
				pIdxCur = pIdxCur->pNext;
			}
			
			if(pIdxCur->smch != smch){  /*pIdxCur is the last node */
				
				if(NULL == (pIndex = (CharIndex *)malloc(sizeof(CharIndex)))){
					perror("Failed to malloc");
					return -1;
				}
				pIndex->smch = smch;
				pIndex->pNext = NULL;
				pIndex->memLen = 5;
				pIndex->memUse = 0;
				pIndex->location = (size_t *)malloc(pIndex->memLen * sizeof(size_t));
				
				if(NULL == pIndex->location){
					perror("Failed to allocate memory");
					return -1;
				}
				pIndex->location[pIndex->memUse] = turn;
				pIndex->memUse = 1;

				pIdxCur->pNext = pIndex;				
			}else{
				if((pIdxCur->memLen - pIdxCur->memUse) <= 1){
					pIdxCur->memLen *= 2;
					pIdxCur->location = realloc(pIdxCur->location, pIdxCur->memLen * sizeof(size_t));
					if(NULL == pIdxCur->location){
						perror("Faile to realloc");
						return -1;
					}				
				}
				pIdxCur->location[pIdxCur->memUse] = turn;
				pIdxCur->memUse += 1;	
			
				/**************	
				if(50 < pIdxCur->memUse){
					printf("warning!\n");
				}	
				***************/		
			}
		
		}
		
		/*************
			if((NULL != (pIndex = ppIndexArray[376])) && (3 <= pIndex->memUse)){
				char str[3];
				*((smch_t *)str) = pIndex->smch;
				str[2] = '\0';
				printf("turn => %u <376> => %s, len => %u\n", turn, str, pIndex->memUse);
			}
		************/
		
	}

	
	/* for 376 *******************
	if(NULL != (pIndex = ppIndexArray[376])){
		char str[3];
		*((smch_t *)str) = pIndex->smch;
		str[2] = '\0';
		printf("<376> => %s, len => %u", str, pIndex->memUse);		
	}
	*************/
	


	return 0;	
}

int GetCharPosList(const smch_t smch, CharIndex ** ppIndexArray, const size_t nIdxLen, size_t ** ppListPos, size_t * pListLen)
{
	size_t uiHashPos = 0;
	CharIndex * pIndex = NULL;

	if((NULL == ppIndexArray) || (0 == nIdxLen))
		return -1;
	if((NULL == ppListPos) || (NULL == pListLen))
		return -1;
	
	uiHashPos = (size_t)(SmchGBKHash(smch)) % nIdxLen;
	for(pIndex = ppIndexArray[uiHashPos]; (NULL != pIndex) && (smch != pIndex->smch); pIndex = pIndex->pNext); 
	
	if(NULL == pIndex)  /* no such character */
		return -1;	
	
	*ppListPos = pIndex->location;
	*pListLen = pIndex->memUse;
	
	return 0;	
}