블럭 단위 더블 링크드 리스트

간단프로그래밍2011. 7. 31. 01:23

블럭 단위 더블 링크드 리스트

객체 지향적 인터프리터? 같은것을 만들어 보고 싶어서 리스트를 짜보았다.

블럭 단위로 메모리가 할당이 되고 이 블럭 안에서는 배열처럼 탐색하다가

꽉 차면 블럭을 새로 할당한다.

덱 구조 처럼 만들기 위해서 앞에서 push, pop 이 되도록 (이름을 eat, overeat 으로..)

뒤에서도 push pop 되도록 하였다.

헤더

소스

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

block_t* create_block(block_t* prv, block_t* nxt ){

block_t* ret;

ret = (block_t*)malloc(sizeof(block_t));
	ret->prv = prv;
	ret->nxt = nxt;

return ret;
}

void delete_block(block_t* blk){
	free(blk);
}

list_t* create_list(){

list_t* ret;
	block_t* blk;

ret = (list_t*)malloc(sizeof(list_t));

blk = create_block(NULL, NULL);

ret->first = blk;
	ret->last = blk;
	ret->first_idx=0;
	ret->size=0;
	ret->blk_num = 1;

return ret;
}

int get_memsize_list(list_t* list){
	return sizeof(list_t) + (sizeof(block_t) * list->blk_num);
}

int get_list_size(list_t* list){
	return list->size;
}

obj_t* get_in_list(list_t* list, int index){

block_t* tmp;

if(-1* list->size <= index && index < list->size){
		if(index < 0){
			index += list->size;
		}
		index += list->first_idx;

for(tmp = list->first; tmp != NULL; tmp = tmp->nxt){
			if(index < BLOCK_SIZE){
				break;
			}
			index -= BLOCK_SIZE;
		}
		return tmp->blk[index];
	}
	return NULL;
}

obj_t* set_in_list(list_t* list, int index, obj_t* item){

block_t* tmp;

if(-1* list->size <= index && index < list->size){
		if(index < 0){
			index += list->size;
		}
		index += list->first_idx;

for(tmp = list->first; tmp != NULL; tmp = tmp->nxt){
			if(index < BLOCK_SIZE){
				break;
			}
			index -= BLOCK_SIZE;
		}
		tmp->blk[index] = item; // set 
		return tmp->blk[index];

}else{
		int new_size;
		int new_blk_num;

if(index < 0){
			new_size = -1 * index;
		}else{
			new_size = index + 1;
		}

list->size = new_size;
		index = new_size-1;

index += list->first_idx;

tmp = list->first;
		while(index > BLOCK_SIZE){
			if(tmp->nxt == NULL){
				tmp->nxt = create_block(tmp,NULL);
				list->blk_num++;
			}
			index -= BLOCK_SIZE;
			tmp = tmp->nxt;
		}

list->last = tmp;

tmp->blk[index] = item;
		return tmp->blk[index];
	}
}

obj_t* eat_list(list_t* list, obj_t* item){

block_t* tmp;

if(list->first_idx > 0){
		list->first_idx--;
	}else{
		tmp = create_block(NULL, list->first);
		list->blk_num++;
		list->first->prv = tmp;

list->first = tmp;
		list->first_idx = BLOCK_SIZE - 1;
	}
	list->first->blk[list->first_idx] = item;
	list->size++;
	return list->first->blk[list->first_idx];
}

obj_t* overeat_list(list_t* list){

block_t* tmp;
	obj_t* ret;

if(list->size == 0)
		return NULL;

ret = list->first->blk[list->first_idx];

if(list->first_idx < BLOCK_SIZE -1){
		list->first_idx++;
	}else{
		tmp = list->first;
		list->first =  tmp->nxt;
		list->first->prv = NULL;
		delete_block(tmp);
		list->blk_num--;
		list->first_idx = 0;
	}
	list->size--;
	return ret;
}

obj_t* push_list(list_t* list, obj_t* item){

block_t* tmp;
	int last_index = 
		list->first_idx + list->size;

int chk = list->blk_num * BLOCK_SIZE;

if(last_index < chk){
	}else{
		tmp = create_block(list->last, NULL);
		list->blk_num++;
		list->last->nxt = tmp;

list->last = tmp;
	}

list->last->blk[last_index%BLOCK_SIZE] = item;
	list->size++;

return list->last->blk[last_index%BLOCK_SIZE] ;
}

obj_t* pop_list(list_t* list){

block_t* tmp;
	obj_t* ret;

int last_index = 
		list->first_idx + list->size - 1;

if(list->size == 0)
		return NULL;

ret = list->last->blk[last_index%BLOCK_SIZE];

if(last_index%BLOCK_SIZE > 0){
	}else{
		tmp = list->last;
		list->last = tmp->prv;
		list->last->nxt = NULL;
		delete_block(tmp);
		list->blk_num--;
	}

list->size--;
	return ret;
}

void _chk_list(list_t* list){

int i,index;
	block_t* tmp;

index = list->first_idx;
	tmp = list->first;

printf("[ ");

for( i = 0; i < list->size; i++){

if(index < BLOCK_SIZE){
			//pass
		}else{
			tmp = tmp->nxt;
			index = 0;
		}

if(tmp->blk[index]){
			printf("exist, ");
		}else{
			printf("None , ");
		}
		index++;
	}
	printf("]\n");

}

void _chk_list_info(list_t* list){

printf("{== info ==}\n");

printf("first blk id: %p\n", list->first);
	printf("las t blk id: %p\n", list->last);
	printf("first_idx: %d\n", list->first_idx);
	printf("list_size: %d\n", list->size);

printf("list_block_num: %d\n", list->blk_num);
	printf("{== ====  ==}\n");
}

set 이 구린거 같다.

저작자표시

'간단프로그래밍' 카테고리의 다른 글

python 간단한 lexer 만들기 (0)	2011.08.06
PyQt , 간단 예제, calculator (0)	2011.08.05
블럭 단위 더블 링크드 리스트 (0)	2011.07.31
opengl 확장 기능 알아보기 (0)	2011.06.28
우분투에 opengl 설치 (0)	2011.06.24
3D 렌더러 학교 플젝 소, opengl 점 찍는 함수만 사용 (0)	2011.06.19

Posted by 멍충한아싸

Trackback 0 Comment 0

댓글을 달아 주세요

«이전 1 ··· 66 67 68 69 70 71 72 73 74 ··· 240 다음»

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

성대아싸의 멍충한 프로그래밍