tree나 trie 데이터 구조를 만들 때, 유용한 가변배열.
저장할 때, 엔디언 정리 필요함.
난 오로지 i586 리눅스/유닉스!! ㅋ
"sambuf.h"파일
저장할 때, 엔디언 정리 필요함.
난 오로지 i586 리눅스/유닉스!! ㅋ
"sambuf.h"파일
#define DATA_IS_NULL -1
#define INVALID_DATA_SIZE -2
#define MEMORY_FULL -3
#define FILE_OPEN_ERROR -4
#define NOT_FOUND -5
#define POSITION_ERROR -6
#define UNKNOWN_ERROR -99
#define SMDK_NO_ERROR 1
#define DEF_INC_SIZE 100
#define DEL_LIST_INC_SIZE 100
#define DEL_LIST_DATA_SIZE 4
#define SORT_SIZE 100
#define OPT_USED 1
#define OPT_MAX 2
#define OPT_REFINE 3
#define LS 4
typedef struct sambuf
{
void *data ;
int used ;
int max ;
int inc_size ;
int data_size ;
}sambuf_t ;
typedef struct dynamic_array
{
sambuf_t *lists_real ;
sambuf_t *lists_deleted ;
} dynamic_array_t;
#define INVALID_DATA_SIZE -2
#define MEMORY_FULL -3
#define FILE_OPEN_ERROR -4
#define NOT_FOUND -5
#define POSITION_ERROR -6
#define UNKNOWN_ERROR -99
#define SMDK_NO_ERROR 1
#define DEF_INC_SIZE 100
#define DEL_LIST_INC_SIZE 100
#define DEL_LIST_DATA_SIZE 4
#define SORT_SIZE 100
#define OPT_USED 1
#define OPT_MAX 2
#define OPT_REFINE 3
#define LS 4
typedef struct sambuf
{
void *data ;
int used ;
int max ;
int inc_size ;
int data_size ;
}sambuf_t ;
typedef struct dynamic_array
{
sambuf_t *lists_real ;
sambuf_t *lists_deleted ;
} dynamic_array_t;
#include <stdio.h>
#include "sambuf.h"
/////////////////////////////////////////////////////
// 동적 ARRAY를 위한 버퍼 함수들.
/////////////////////////////////////////////////////
sambuf_t *alloc_buf(int inc_size, int data_size)
{
sambuf_t *buf ;
buf = (sambuf_t *)malloc(sizeof(sambuf_t));
buf->data = (void *)malloc( inc_size * data_size );
buf->used = 0;
buf->max = inc_size;
buf->inc_size = inc_size;
buf->data_size = data_size;
return buf ;
}
void free_buf(sambuf_t *buf)
{
if(buf->used>0) free(buf->data);
buf->used = 0;
buf->max = 0;
buf->inc_size = 0;
buf->data_size = 0;
}
int buf_clear(sambuf_t *buf)
{
if( buf->max > buf->inc_size )
{
if( buf->data ) free(buf->data);
buf->data = (void *)malloc(buf->inc_size * buf->data_size);
}
buf->used = 0;
return 1;
}
int buf_resize(sambuf_t *buf, int resize)
{
char *data ;
int size, cp_size ;
size = resize * buf->inc_size * buf->data_size ;
data = (char *)malloc(size) ;
if( size < (buf->used * buf->data_size) )
cp_size = size ;
else
cp_size = buf->used * buf->data_size ;
memcpy(data, buf->data, cp_size);
free(buf->data);
buf->data = data ;
buf->max = buf->inc_size * resize ;
return SMDK_NO_ERROR ;
}
int buf_increase(sambuf_t *buf)
{
int resize ;
resize = buf->max / buf->inc_size + 1 ;
return buf_resize(buf,resize);
}
int buf_delete(sambuf_t *buf, long data_pos)
{
if( buf->used == buf->max )
if( buf_increase(buf) < 0 ) return MEMORY_FULL ;
memcpy((char *)buf->data + buf->used * buf->data_size, &data_pos, LS);
buf->used++;
return SMDK_NO_ERROR ;
}
int buf_check(sambuf_t *buf, long data_pos)
{
int i ;
for( i=0; i<buf->used; i++ )
{
if( data_pos == *((long *)((char *)buf->data+buf->data_size * i)) )
return data_pos ;
}
return -1;
}
long buf_delpos(sambuf_t *buf)
{
if( buf->used==0 ) return -1;
return *(long*)((char *)buf->data+(--(buf->used)) * buf->data_size) ;
}
int buf_sort(sambuf_t *buf, int (*comp)(const void *, const void *))
{
qsort(buf->data, buf->used, buf->data_size, comp);
return SMDK_NO_ERROR ;
}
//////////////////////////////////////////
// 동적 ARRAY 함수.
//////////////////////////////////////////
dynamic_array_t *alloc_dy_array(int inc_size, int data_size)
{
dynamic_array_t *dy_array ;
dy_array = (dynamic_array_t *)malloc(sizeof(dynamic_array_t)) ;
dy_array->lists_real = alloc_buf(inc_size,data_size);
dy_array->lists_deleted = alloc_buf(DEL_LIST_INC_SIZE,DEL_LIST_DATA_SIZE);
return dy_array ;
}
int free_dy_array( dynamic_array_t *array )
{
if( array->lists_real ) free_buf(array->lists_real);
if( array->lists_deleted ) free_buf(array->lists_deleted);
free(array);
return 0;
}
int dy_clear(dynamic_array_t *dy_arr)
{
buf_clear(dy_arr->lists_real) ;
buf_clear(dy_arr->lists_deleted) ;
return 0;
}
int dy_append_item(dynamic_array_t *dy_arr, void *data)
{
if( dy_arr->lists_real->used == dy_arr->lists_real->max )
if( buf_increase(dy_arr->lists_real) < 0 )
return MEMORY_FULL ;
memcpy
(
(char *)dy_arr->lists_real->data + dy_arr->lists_real->used * dy_arr->lists_real->data_size,
data,
dy_arr->lists_real->data_size
);
return dy_arr->lists_real->used - 1 ;
}
int dy_append_block(dynamic_array_t *dy_arr, void *data, int size)
{
int resize ;
if( size+dy_arr->lists_real->used > dy_arr->lists_real->max )
{
resize = (size+dy_arr->lists_real->used) / dy_arr->lists_real->inc_size +1 ;
if( buf_resize(dy_arr->lists_real,resize) < 0 )
return MEMORY_FULL ;
}
memcpy(
(char *)dy_arr->lists_real->data + dy_arr->lists_real->used,
data,
dy_arr->lists_real->data_size * size
);
return dy_arr->lists_real->used - size;
}
int dy_add_item(dynamic_array_t *dy, void *data)
{
long pos ;
if( (pos=buf_delpos(dy->lists_deleted)) < 0 )
{
if( dy->lists_real->used==dy->lists_real->max )
if( buf_increase(dy->lists_real) < 0 )
return MEMORY_FULL ;
pos = dy->lists_real->used++;
}
memcpy
(
(char *)dy->lists_real->data + dy->lists_real->data_size * pos,
data,
dy->lists_real->data_size
);
return pos ;
}
int dy_refine(dynamic_array_t *dy)
{
int del, i, j ;
sambuf_t *al, *dl ;
long vi, vj ;
if( dy->lists_deleted->used==0 ) return SMDK_NO_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
for(i=0; i<dl->used-1; i++)
{
vi = *((long *)((char *)dl->data + dl->data_size * i));
for(j=i; j<dl->used; j++)
{
vj = *((long *)((char *)dl->data + dl->data_size * j));
if( vi > vj )
{
*((long *)((char *)dl->data+dl->data_size * i)) = vj ;
*((long *)((char *)dl->data+dl->data_size * j)) = vi ;
}
}
}
while( dl->used > 0 )
{
del = *((long *)((char *)dl->data + (dl->used-1)*dl->data_size)) ;
if((al->used-1) < del) break;
else if((al->used-1) > del)
{
memcpy (
(char *)al->data + al->data_size * del,
(char *)al->data + al->data_size * (al->used-1),
al->data_size);
}
al->used--;
dl->used--;
}
buf_resize(al,al->used/al->inc_size +1);
buf_resize(dl,1);
return SMDK_NO_ERROR ;
}
int dy_get_itemnum(dynamic_array_t *dy)
{
return (dy->lists_real->used - dy->lists_deleted->used) ;
}
int dy_get_usednum(dynamic_array_t *dy)
{
return dy->lists_deleted->used ;
}
int dy_get_maxitemnum(dynamic_array_t *dy)
{
return dy->lists_real->max ;
}
void *dy_get_item(dynamic_array_t *dy, long data_pos)
{
if( data_pos < 0 || data_pos >= dy->lists_real->used ) return NULL;
//deleted에 있으면 데이터는 삭제되었으므로
if( buf_check(dy->lists_deleted,data_pos)==data_pos ) return NULL;
return (char *)dy->lists_real->data + dy->lists_real->data_size * data_pos ;
}
void *dy_get_dataptr(dynamic_array_t *dy)
{
return dy->lists_real->data ;
}
int dy_load(dynamic_array_t *dy, char *filename, int opt)
{
FILE *fp ;
sambuf_t *al, *dl ;
if( strlen(filename) < 1 ) return DATA_IS_NULL;
if((fp=fopen(filename,"r"))==NULL) return FILE_OPEN_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
if( al==NULL || dl==NULL ) return MEMORY_FULL ;
fread(al, sizeof(sambuf_t), 1, fp);
fread(dl, sizeof(sambuf_t), 1, fp);
// 엔디언 정리.
if( (al->data=(void *)malloc(al->max * al->data_size))==NULL ) return MEMORY_FULL;
if( (dl->data=(void *)malloc(dl->max * dl->data_size))==NULL )
{
free(al->data);
return MEMORY_FULL ;
}
switch(opt)
{
case OPT_MAX:
fread(al->data, al->max * al->data_size, 1, fp);
fread(dl->data, dl->max * dl->data_size, 1, fp);
break ;
case OPT_REFINE:
fread(al->data, al->max * al->data_size, 1, fp);
break;
case OPT_USED:
default:
fread(al->data, al->used * al->data_size, 1, fp);
fread(dl->data, dl->used * dl->data_size, 1, fp);
break ;
}
dy->lists_real = al ;
dy->lists_deleted = dl ;
fclose(fp);
return SMDK_NO_ERROR ;
}
int dy_save(dynamic_array_t *dy, char *filename, int opt)
{
FILE *fp ;
sambuf_t *al, *dl ;
if( strlen(filename) < 1 ) return DATA_IS_NULL;
if( (fp=fopen(filename,"w"))==NULL ) return FILE_OPEN_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
//빅엔디언과 리틀엔디언변환
fwrite(al, sizeof(sambuf_t), 1, fp);
fwrite(dl, sizeof(sambuf_t), 1, fp);
switch(opt)
{
case OPT_MAX :
fwrite(al->data, al->max * al->data_size, 1, fp);
fwrite(dl->data, dl->max * dl->data_size, 1, fp);
break;
case OPT_REFINE:
dy_refine(dy);
fwrite(al->data, al->used * al->data_size, 1, fp);
break;
case OPT_USED:
default:
fwrite(al->data, al->used * al->data_size, 1, fp);
fwrite(dl->data, dl->used * dl->data_size, 1, fp);
break;
}
fclose(fp);
//빅엔디언과 리틀엔디언 복구.
}
int dy_search(dynamic_array_t *dy,void *data, int (*comp)(const void *,const void *), long start_pos)
{
sambuf_t *al, *dl ;
long i ;
void *p ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
for(i=start_pos; i < al->used; i++)
{
p = dy_get_item(dy,i);
if( !p ) continue ;
if( comp(p,data)== 0 ) return i;
}
return NOT_FOUND ;
}
int dy_sort(dynamic_array_t *dy,int (*comp)(const void *,const void *))
{
if(dy_refine(dy) < 0) return MEMORY_FULL ;
return buf_sort(dy->lists_real,comp);
}
#include "sambuf.h"
/////////////////////////////////////////////////////
// 동적 ARRAY를 위한 버퍼 함수들.
/////////////////////////////////////////////////////
sambuf_t *alloc_buf(int inc_size, int data_size)
{
sambuf_t *buf ;
buf = (sambuf_t *)malloc(sizeof(sambuf_t));
buf->data = (void *)malloc( inc_size * data_size );
buf->used = 0;
buf->max = inc_size;
buf->inc_size = inc_size;
buf->data_size = data_size;
return buf ;
}
void free_buf(sambuf_t *buf)
{
if(buf->used>0) free(buf->data);
buf->used = 0;
buf->max = 0;
buf->inc_size = 0;
buf->data_size = 0;
}
int buf_clear(sambuf_t *buf)
{
if( buf->max > buf->inc_size )
{
if( buf->data ) free(buf->data);
buf->data = (void *)malloc(buf->inc_size * buf->data_size);
}
buf->used = 0;
return 1;
}
int buf_resize(sambuf_t *buf, int resize)
{
char *data ;
int size, cp_size ;
size = resize * buf->inc_size * buf->data_size ;
data = (char *)malloc(size) ;
if( size < (buf->used * buf->data_size) )
cp_size = size ;
else
cp_size = buf->used * buf->data_size ;
memcpy(data, buf->data, cp_size);
free(buf->data);
buf->data = data ;
buf->max = buf->inc_size * resize ;
return SMDK_NO_ERROR ;
}
int buf_increase(sambuf_t *buf)
{
int resize ;
resize = buf->max / buf->inc_size + 1 ;
return buf_resize(buf,resize);
}
int buf_delete(sambuf_t *buf, long data_pos)
{
if( buf->used == buf->max )
if( buf_increase(buf) < 0 ) return MEMORY_FULL ;
memcpy((char *)buf->data + buf->used * buf->data_size, &data_pos, LS);
buf->used++;
return SMDK_NO_ERROR ;
}
int buf_check(sambuf_t *buf, long data_pos)
{
int i ;
for( i=0; i<buf->used; i++ )
{
if( data_pos == *((long *)((char *)buf->data+buf->data_size * i)) )
return data_pos ;
}
return -1;
}
long buf_delpos(sambuf_t *buf)
{
if( buf->used==0 ) return -1;
return *(long*)((char *)buf->data+(--(buf->used)) * buf->data_size) ;
}
int buf_sort(sambuf_t *buf, int (*comp)(const void *, const void *))
{
qsort(buf->data, buf->used, buf->data_size, comp);
return SMDK_NO_ERROR ;
}
//////////////////////////////////////////
// 동적 ARRAY 함수.
//////////////////////////////////////////
dynamic_array_t *alloc_dy_array(int inc_size, int data_size)
{
dynamic_array_t *dy_array ;
dy_array = (dynamic_array_t *)malloc(sizeof(dynamic_array_t)) ;
dy_array->lists_real = alloc_buf(inc_size,data_size);
dy_array->lists_deleted = alloc_buf(DEL_LIST_INC_SIZE,DEL_LIST_DATA_SIZE);
return dy_array ;
}
int free_dy_array( dynamic_array_t *array )
{
if( array->lists_real ) free_buf(array->lists_real);
if( array->lists_deleted ) free_buf(array->lists_deleted);
free(array);
return 0;
}
int dy_clear(dynamic_array_t *dy_arr)
{
buf_clear(dy_arr->lists_real) ;
buf_clear(dy_arr->lists_deleted) ;
return 0;
}
int dy_append_item(dynamic_array_t *dy_arr, void *data)
{
if( dy_arr->lists_real->used == dy_arr->lists_real->max )
if( buf_increase(dy_arr->lists_real) < 0 )
return MEMORY_FULL ;
memcpy
(
(char *)dy_arr->lists_real->data + dy_arr->lists_real->used * dy_arr->lists_real->data_size,
data,
dy_arr->lists_real->data_size
);
return dy_arr->lists_real->used - 1 ;
}
int dy_append_block(dynamic_array_t *dy_arr, void *data, int size)
{
int resize ;
if( size+dy_arr->lists_real->used > dy_arr->lists_real->max )
{
resize = (size+dy_arr->lists_real->used) / dy_arr->lists_real->inc_size +1 ;
if( buf_resize(dy_arr->lists_real,resize) < 0 )
return MEMORY_FULL ;
}
memcpy(
(char *)dy_arr->lists_real->data + dy_arr->lists_real->used,
data,
dy_arr->lists_real->data_size * size
);
return dy_arr->lists_real->used - size;
}
int dy_add_item(dynamic_array_t *dy, void *data)
{
long pos ;
if( (pos=buf_delpos(dy->lists_deleted)) < 0 )
{
if( dy->lists_real->used==dy->lists_real->max )
if( buf_increase(dy->lists_real) < 0 )
return MEMORY_FULL ;
pos = dy->lists_real->used++;
}
memcpy
(
(char *)dy->lists_real->data + dy->lists_real->data_size * pos,
data,
dy->lists_real->data_size
);
return pos ;
}
int dy_refine(dynamic_array_t *dy)
{
int del, i, j ;
sambuf_t *al, *dl ;
long vi, vj ;
if( dy->lists_deleted->used==0 ) return SMDK_NO_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
for(i=0; i<dl->used-1; i++)
{
vi = *((long *)((char *)dl->data + dl->data_size * i));
for(j=i; j<dl->used; j++)
{
vj = *((long *)((char *)dl->data + dl->data_size * j));
if( vi > vj )
{
*((long *)((char *)dl->data+dl->data_size * i)) = vj ;
*((long *)((char *)dl->data+dl->data_size * j)) = vi ;
}
}
}
while( dl->used > 0 )
{
del = *((long *)((char *)dl->data + (dl->used-1)*dl->data_size)) ;
if((al->used-1) < del) break;
else if((al->used-1) > del)
{
memcpy (
(char *)al->data + al->data_size * del,
(char *)al->data + al->data_size * (al->used-1),
al->data_size);
}
al->used--;
dl->used--;
}
buf_resize(al,al->used/al->inc_size +1);
buf_resize(dl,1);
return SMDK_NO_ERROR ;
}
int dy_get_itemnum(dynamic_array_t *dy)
{
return (dy->lists_real->used - dy->lists_deleted->used) ;
}
int dy_get_usednum(dynamic_array_t *dy)
{
return dy->lists_deleted->used ;
}
int dy_get_maxitemnum(dynamic_array_t *dy)
{
return dy->lists_real->max ;
}
void *dy_get_item(dynamic_array_t *dy, long data_pos)
{
if( data_pos < 0 || data_pos >= dy->lists_real->used ) return NULL;
//deleted에 있으면 데이터는 삭제되었으므로
if( buf_check(dy->lists_deleted,data_pos)==data_pos ) return NULL;
return (char *)dy->lists_real->data + dy->lists_real->data_size * data_pos ;
}
void *dy_get_dataptr(dynamic_array_t *dy)
{
return dy->lists_real->data ;
}
int dy_load(dynamic_array_t *dy, char *filename, int opt)
{
FILE *fp ;
sambuf_t *al, *dl ;
if( strlen(filename) < 1 ) return DATA_IS_NULL;
if((fp=fopen(filename,"r"))==NULL) return FILE_OPEN_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
if( al==NULL || dl==NULL ) return MEMORY_FULL ;
fread(al, sizeof(sambuf_t), 1, fp);
fread(dl, sizeof(sambuf_t), 1, fp);
// 엔디언 정리.
if( (al->data=(void *)malloc(al->max * al->data_size))==NULL ) return MEMORY_FULL;
if( (dl->data=(void *)malloc(dl->max * dl->data_size))==NULL )
{
free(al->data);
return MEMORY_FULL ;
}
switch(opt)
{
case OPT_MAX:
fread(al->data, al->max * al->data_size, 1, fp);
fread(dl->data, dl->max * dl->data_size, 1, fp);
break ;
case OPT_REFINE:
fread(al->data, al->max * al->data_size, 1, fp);
break;
case OPT_USED:
default:
fread(al->data, al->used * al->data_size, 1, fp);
fread(dl->data, dl->used * dl->data_size, 1, fp);
break ;
}
dy->lists_real = al ;
dy->lists_deleted = dl ;
fclose(fp);
return SMDK_NO_ERROR ;
}
int dy_save(dynamic_array_t *dy, char *filename, int opt)
{
FILE *fp ;
sambuf_t *al, *dl ;
if( strlen(filename) < 1 ) return DATA_IS_NULL;
if( (fp=fopen(filename,"w"))==NULL ) return FILE_OPEN_ERROR ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
//빅엔디언과 리틀엔디언변환
fwrite(al, sizeof(sambuf_t), 1, fp);
fwrite(dl, sizeof(sambuf_t), 1, fp);
switch(opt)
{
case OPT_MAX :
fwrite(al->data, al->max * al->data_size, 1, fp);
fwrite(dl->data, dl->max * dl->data_size, 1, fp);
break;
case OPT_REFINE:
dy_refine(dy);
fwrite(al->data, al->used * al->data_size, 1, fp);
break;
case OPT_USED:
default:
fwrite(al->data, al->used * al->data_size, 1, fp);
fwrite(dl->data, dl->used * dl->data_size, 1, fp);
break;
}
fclose(fp);
//빅엔디언과 리틀엔디언 복구.
}
int dy_search(dynamic_array_t *dy,void *data, int (*comp)(const void *,const void *), long start_pos)
{
sambuf_t *al, *dl ;
long i ;
void *p ;
al = dy->lists_real ;
dl = dy->lists_deleted ;
for(i=start_pos; i < al->used; i++)
{
p = dy_get_item(dy,i);
if( !p ) continue ;
if( comp(p,data)== 0 ) return i;
}
return NOT_FOUND ;
}
int dy_sort(dynamic_array_t *dy,int (*comp)(const void *,const void *))
{
if(dy_refine(dy) < 0) return MEMORY_FULL ;
return buf_sort(dy->lists_real,comp);
}
Posted by 백구씨쥔장