【CS 107】Assignment 3 C言語におけるvectorとhashsetの実現

実装部分(vector.c)と(hashset.c)、windowsオペレーティングシステム、minGW用makeをインストールしてリンクをコンパイルし、vector-test、hashset-test、thesaurus-lookのテストを通過することができます:

#include "vector.h"  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <assert.h>  
  
static void VectorGrow(vector *v)  
{  
    if(v->length==v->loglength)  
    {  
        v->loglength*=2;  
        v->base=realloc(v->base,v->elemSize*v->loglength);        
    }  
}  
  
void VectorNew(vector *v, int elemSize, VectorFreeFunction freeFn, int initialAllocation)  
{  
    assert(initialAllocation>=0);  
    if(initialAllocation==0)  
        v->loglength=4;  
    else  
        v->loglength=initialAllocation;  
    v->base=malloc(elemSize*v->loglength);  
    v->elemSize=elemSize;  
    v->length=0;  
    v->freeFunc=freeFn;  
}  
  
void VectorDispose(vector *v)  
{  
    if(v->freeFunc!=NULL)  
    {  
        for(int i=0;i<v->length;i++)  
         {  
             v->freeFunc( (char*)v->base+i*v->elemSize);  
         }  
    }  
    free(v->base);  
}  
  
int VectorLength(const vector *v)  
{  
    return v->length;   
}  
  
void *VectorNth(const vector *v, int position)  
{    
    assert(position>=0);  
    assert( position <v->loglength);  
    return (char*)v->base+position*v->elemSize;   
}  
  
void VectorReplace(vector *v, const void *elemAddr, int position)  
{  
    assert(position>=0);  
    assert( position <(v->loglength));  
    memcpy( (char*)v->base+position*v->elemSize, elemAddr, v->elemSize);  
}  
  
void VectorInsert(vector *v, const void *elemAddr, int position)  
{  
    assert(position>=0);  
    assert( position <v->loglength);  
    VectorGrow(v);  
    memmove( (char*)v->base+(position+1)*v->elemSize, (char*)v->base+position*v->elemSize, v->elemSize*(v->length-position));  
    VectorReplace(v, elemAddr, position);  
    v->length++;  
}  
  
void VectorAppend(vector *v, const void *elemAddr)  
{  
    VectorGrow(v);  
    VectorReplace(v, elemAddr, v->length);  
    v->length++;  
}  
  
void VectorDelete(vector *v, int position)  
{  
    assert(position>=0);  
    assert( position <v->loglength);  
    memmove( (char*)v->base+(position)*v->elemSize, (char*)v->base+(position+1)*v->elemSize, v->elemSize*(v->length-position-1) );  
    v->length--;  
}  
  
void VectorSort(vector *v, VectorCompareFunction compare)  
{  
    assert(compare!=NULL);  
    qsort(v->base,v->length,v->elemSize,compare);  
}  
  
void VectorMap(vector *v, VectorMapFunction mapFn, void *auxData)  
{  
    assert(mapFn!=NULL);  
    for(int i=0; i<v->length; i++)  
    {  
        mapFn( (char*)v->base+i*v->elemSize, auxData);      
    }  
}  
  
static const int kNotFound = -1;  
int VectorSearch(const vector *v, const void *key, VectorCompareFunction searchFn, int startIndex, bool isSorted)  
{   
    assert(startIndex>=0);  
    assert( startIndex <v->length);  
    assert(searchFn!=NULL);  
    assert( key!=NULL);  
    if(isSorted)  
    {    
        char* temp=bsearch(key, (char*)v->base+startIndex*v->elemSize, v->length-startIndex, v->elemSize, searchFn);  
        if (temp!=NULL)  
         return (int)( temp-(char*)v->base )/v->elemSize;  
    }  
    else  
    {  
        for(int i=0; i<v->length; i++)  
        {  
            if(memcmp(key, (char*)v->base+i*v->elemSize, v->elemSize)==0)  
             return i;  
        }  
    }  
    return -1;   
}

#include "hashset.h"  
#include <assert.h>  
#include <stdlib.h>  
#include <string.h>  
  
static int GetHashIndex(const hashset *h, const void *elemAddr)  
{  
    assert(elemAddr!=NULL);  
    int index=h->hashFunc(elemAddr, h->bucketSize);  
    assert(index>=0 && index<h->bucketSize);  
    return index;  
}  
  
void HashSetNew(hashset *h, int elemSize, int numBuckets,  
        HashSetHashFunction hashfn, HashSetCompareFunction comparefn, HashSetFreeFunction freefn)  
{  
    assert(elemSize>0 && numBuckets>0 && hashfn!=NULL && comparefn!=NULL);  
    h->bucketSize=numBuckets;  
    h->elemSize=elemSize;  
    h->count=0;  
    h->base=malloc(elemSize*numBuckets);  
    h->hashFunc=hashfn;  
    h->compFunc=comparefn;  
    h->freeFunc=freefn;  
    char zero=0;  
    for(int i=0; i<numBuckets*elemSize; i++)  
    {  
        memcpy((char*)h->base+i, &zero, sizeof(char));  
  
    }  
}  
  
void HashSetDispose(hashset *h)  
{  
    if(h->freeFunc!=NULL)  
    {  
        for(int i=0;i<h->bucketSize;i++)  
        {   
            h->freeFunc( (char*)h->base+i*h->elemSize);  
        }  
    }  
    free(h->base);  
}  
  
int HashSetCount(const hashset *h)  
{   
    return h->count;  
}  
  
void HashSetMap(hashset *h, HashSetMapFunction mapfn, void *auxData)  
{   
    assert(mapfn!=NULL);  
    for(int i=0; i<h->bucketSize; i++)  
    {  
        if( (char*)h->base+i*h->elemSize!=NULL)  
            mapfn( (char*)h->base+i*h->elemSize, auxData);  
    }  
}  
  
void HashSetEnter(hashset *h, const void *elemAddr)  
{    
    memcpy( (char*)h->base+GetHashIndex(h,elemAddr)*h->elemSize, elemAddr, h->elemSize);  
    h->count++;  
}  
  
void *HashSetLookup(const hashset *h, const void *elemAddr)  
{   
    int index=GetHashIndex(h,elemAddr);  
    char zero=0;  
    if(memcmp( (char*)h->base+index*h->elemSize, &zero, sizeof(char))==NULL)  
        return NULL;  
    return (char*)h->base+index*h->elemSize;  
} 

=======================================================
転載は出典を明記してください.http://blog.csdn.net/utimes/article/details/8743303
=======================================================