19.컨테이너 APIs
19.1 동적 배열
c언어에서 일반적인 컨테이너 타입은 배열의 형태를 띄고 있다. 그러나 배열의 크기는 보통 고정 크기이지만 libapr은 동적배열을 제공한다. apr_tables.h에 보면 API들 정의가 있는데 컨테이너 타입의 동적 배열로써 특정을 보면
| append | efficient(API support) |
| insert/prepend | inefficient(no API support) |
| delete | inefficient(no API support) |
| delete(only the first element) | efficient(API support) |
| search(lookup) | inefficient, but depends(no API support) |
| iteration | efficient(no API support) |
'API에서 지원하지 않는다'의 의미는 apr_array_header_t::elts를 직접 건드려야 한다는 것을 의미한다. 이것은 프로그래머에게 좋은 태도는 아니다. 그러나 실용적인 프로그래머로써 수용할 수는 있다. 동적 배열형은 apr_array_header_t 타입이다. 오브젝트는 apr_arrary_make()함수에 의해 생성된다.
/* excerpted from array-sample.c */
apr_array_header_t *arr;
arr = apr_array_make(mp, ARRAY_INIT_SZ, sizeof(const char*));
첫번째 아규먼트는 사용할 메모리플이다. 사용할 배열과 엘리먼트는 메모리플에서 할당한다.
두번째 아규먼트는 배열의 초기값이다.
세번째 아규먼트는 엘리먼트의 크기이다. 세번째 아규먼트는 코드를 읽는 사람에게는 중요하다. 왜냐하면 컨테이너 타입오브젝트가 무엇인지를 알수 있기 때문이다. STL과는 다르게 apr_array_header_t는 type-save하지 않다. 그러므로 타입을 명시적으로 선언하는건 중요한다. 다음에 있는 것으로써 문자열 포인터의 배열로써 배열을 사용될것임을 알수 있다.
주의 : 다른 libapr API에 친숙하다면 조금 이상한 생각이 들것이다. 새로 만들어진 오브젝트는 결과 아규먼트로 사용되지 않기 때문에. 신경쓰지 마라
배열에 새로운 값을 추가히기 위해 apr_array_push()를 호출한다.
/* excerpted from array-sample.c */
*(const char**)apr_array_push(arr) = "123";
배열에서 반복은 중요한 작업이다. 아래를 보면
int i;
apr_array_header_t *arr;
for (i = 0; i < arr->nelts; i++)
{
const char *s = ((const char**)arr->elts)[i];
printf("%d: %s\n", i, s);
}
API들이 직관적이지는 않다. 그러나 운좋게도 api들은 매우 간단한 인터페이스이고, 바로 적응하게 될것이다. 배열에서 일반적인 API 특징을 보면
/* generic form of apr_array_header_t usages. 'T' is a type name. */
apr_array_header_t *arr = apr_array_make(mp, ARRAY_INIT_SZ, sizeof(T));/* array of T objects */
/* add an element */
T elem;
*(T*)apr_array_push(arr) = elem;
/* iteration */
for (i = 0; i < arr->nelts; i++)
T elem = ((T*)arr->elts)[i];
array-sample.c를 보면 배열은 포인터의 배열이다. 배열의 요소는 apr_array_make()에 의해 메모리 플에 할당된다. 포인터의 메모리만 할당되기 때문에 포인터가 가르키고 있
는 오브젝트에 대한 것은 할당하지 않는다. 그래서 아래 샘플 코드에는 버그가 있는데 배열안에 있는 문자열은 영구적이지 않다.
/* BUGGY sample of apr_array_header_t usage */
void func(apr_array_header_t *str_arr)
{
char str[32];
strcpy(str, "foobar");
*(const char**)apr_array_push(str_arr) = str;/* BUG, if function caller uses this array */
return;
}
대부분의 경우에, 배열과 엘리먼트는 lifetime이 같다. 그래서 아래 처리 메모리플에 오브젝트도 같이 할당하는 것이 좋다.
/* fix example of above bug */
void func(apr_array_header_t *str_arr)
{
const char *str = apr_pstrdup(str_arr->pool, "foobar");
*(const char**)apr_array_push(str_arr) = str;
}
보시다시피 apr_array_header_t는 arbitary type으로 작동한다. 분명한건, 문자열 배열은 다른 것보다는 보다 파워풀하다. apr_array_pstrcat() 때문에, 일반적으로 문자열 배열과 같이 동작한다. T는 char*이거나 const char *이다.
apr_array_pstrcat()는 배열에 모든것을 연결시킨다. 그리고 새로운 문자열을 만든다. 문자열 청크로부터 하나의 문자열을 어떻게 만드는지 예를 봐라
/* pseudo code to make one string from string chunks */
apr_array_header_t *html_arr = apr_array_make(mp, ARRAY_INIT_SZ, sizeof(const char*));
*(const char**)apr_array_push(html_arr) = "<html>";
*(const char**)apr_array_push(html_arr) = "<head><title>foo</title></head>";
*(const char**)apr_array_push(html_arr) = "<body><ul>";
for (i = 0; i < NUM_LIST; i++)
*(const char**)apr_array_push(html_arr) = apr_psprintf(mp, "<li>%d</li>", i);
*(const char**)apr_array_push(html_arr) = "</ul></body>";
*(const char**)apr_array_push(html_arr) = "</html>";
const char *html_str = apr_array_pstrcat(mp, html_arr, '\0');
배열안에서 엘리먼트를 정렬하기를 원한다고 할때, 배열에서 검색은 효율적이지 않다. 그러나 bsearch(3)로 효율적으로 할수도 있다. 아래 qsort()를 사용할 array를 보면
/* qsort(3) sample with array */
/* we assume arr is an array of string */
qsort(arr->elts, arr->nelts, arr->elt_size, cmp_string);
/* compare function for qsort(3) */
static int cmp_string(const void *v1, const void *v2)
{
const char *s1 = *(const char**)v1;
const char *s2 = *(const char**)v2;
return strcmp(s1, s2);
}
apr_array_pop()를 언급해야 할것 같다. apr_array_pop()함수는 (first in- last-out 컨테이너)스택을 사용한다.
19.2 테이블
테이블은 키-값의 컨테이너이다. 키는 문자열이고, 값은 어떤것이든 상관없다. 보통은 문자열이다. 아래 설명을 보면 키-값 모두 문자열이라고 가정하고, 컨테이너로서 테이블을
특징을 보면
| append | efficient(API support) |
| insert/prepend | inefficient(API support) |
| delete | inefficient(API support) |
| search(lookup) | almost efficient(API support) |
| iteration | efficient(API support) |
보시다시피, 속성은 거의 문자열과 같다. 이것이 당연한것은 테이블은 배열에 기초하고 있다. 테이블은 속성을 추가할때 좋다. 두번째는 테이블을 검색할때 좋고, 검색효율을 위해
내부에 체크섬을 사용한다. 비록 뒤에 설명한 해쉬테이블만큼 효과적이지는 않지만 충분히 쓸만하다.
테이블 타입은 apr_table_t이다. apr_table_make()함수를 통해 새로운 오브젝트를 얻는다.
/* excerpted from table-sample.c */
apr_table_t *tab;
tab = apr_table_make(mp, TABLE_INIT_SZ);
첫번째 아규멘트는 메모리플이다. apr_array_header_t와 비슷하게, 테이블과 엘리먼트는 메모리플에서 할당된다. 두번째 이규멘트는 테이블의 초기 크기
동적 배열과 같이 테이블 크기는 동적으로 잡힌다. 그래서 초기크기는 단지 힌트이다.
테이블에 엘러먼트를 추가하는 4개의 API는 다음과 같다.
void apr_table_set(apr_table_t *t, const char *key, const char *val);
void apr_table_setn(apr_table_t *t, const char *key, const char *val);
void apr_table_add(apr_table_t *t, const char *key, const char *val);
void apr_table_addn(apr_table_t *t, const char *key, const char *val);
set과 add 사이의 차이는 같은 키로 여러개의 값을 사용할지 말지에 있다. set은 여러개의 값을 허용하지 않는다. 만약 같은 키가 이미 존재한다면 apr_table_setn()함수로 덥어쓰기를 할수 있다. 반대로 apr_table_add()와 apr_table_addn()함수는 같은 키로 중복 값을 허용한다. 그렇기 때문에 이전에 있는 값들은 계속해서 유지된다.
마지막에 n이 붙는 함수와 그렇지 않은 함수는 키와 값이 메모리상에서 복사되느냐 그렇지 않느냐 차이다. n이 없이 호출하면 API는 키와 값 문자열을 복하하고 n을 같이 호출하면
API는 그들을 복사하지 않는다. 그래서 n을 붙여서 호출하는 것이 보다 효율적이다. 그래서 불필요하게 문자열을 복사하는것을 막으로면 apr_table_setn()또는 apr_table_addn()을 호출하면 된다. 예를 보면
/* examples we can call apr_table_setn() or apr_table_addn() */
apr_table_setn(tab, "foo", "bar"); /* string literals don't require duplication */
apr_table_setn(tab, apr_pstrdup(mp, "foo"), apr_pstrdup(mp, "bar")); /* since the strings are already allocated in the same memory pool, we don't need
double duplications */
키값을 찾기 위해서는 apr_table_get()을 호출하고, 프로토 타입은 const char * apr_table_get(const apr_table_t *t, const char *key);
테이블에 키가 있다면 그 키와 관련된 값이 리턴될 것이고 반면에 없다면 NULL값이 리턴된다. 앞에서 언급했듯이 add API는 하나의 키에 복수의 값을 허용지만 apr_table_get()은 복수의 값을 리턴하지는 못한다. 단지 첫번째 값만을 리턴한다. 테이블을 순회하면서 복수의 값을 가져와야 한다. 이후에 간단히 설명하겠다.
주의 : 테이블키는 대소문자구별이 없습니다. 역사적으로 테이블은 HTTP헤더에서 발전했다.
apr_table_get()의 리턴값은 포인터이다. 이것은 값을 복사하지 않는다는 것을 의미한다. 따라서 아래와 같은 코드에는 버그가 존재한다.
/* BUGGY sample */
apr_table_setn(tab, "mykey", strdup("myval"));/* apr_table_setn() doesn't duplicate the strings */
const char *v = apr_table_get(tab, "mykey");
assert(strcmp(v, "myval") == 0); /* v's value should be "myval" */
/* v is a string allocated by strdup(3), so calling free(v) is a proper operation.
* However, since the element still exists in the table, free(v) leaves an invalid memory in the table */
free(v);
간단한 해법은 메모리플을 사용하는 것이다. 모든 키와 모든 값 문자열을 테이블과 같은 메모리 플에서 할당받는다면, apr_pool_destroy()함수 호출로 해결할수 있다.
테이블 순회를 하는 두가지 방법. 첫번째는 callback함수를 사용하는 것이고 다른 하나는 apr_array_header_t를 직접 사용하는 것이다.
callback함수를 사용하는 순회 방법은 apr_table_do()를 호출한다. 이 함수의 프로토타입은
int apr_table_do(apr_table_do_callback_fn_t *comp, void *rec, const apr_table_t *t, ...);
apr_table_do(tab_cb, "label1", tab, NULL);
apr_table_do(tab_cb, "label2", tab, "key1", "key2", NULL);/* iteration with filters */
/* table iteration callback */
static int tab_cb(void *data, const char *key, const char *value)
{
const char *label = data;
printf("callback[%s]: %s %s\n", label, key, value);
return TRUE;/* TRUE:continue iteration. FALSE:stop iteration */
apr_table_do()함수의 첫번째 아규먼트는 callback함수이다. 두번째 아규먼트는 callback함수에서 context object passwd이고, 세번째 아규멘트는 테이블 오브젝트이다. 남
겨진 아규멘트는 키값을 필터링 할때 사용한다.
다른 키 순회는 apr_array_header_t를 직접 사용하는 것이다. 이것은 안좋은 방법인데, 왜냐하면 내부 구현에 의존적이기 대문에 실용적 프로그램 입장에서 안좋은 방법이다.
내부적으로 테이블은 apr_table_entry_t오브젝트이다. libapr의 동적 배열을 이해하고 있다면, 아래예제도 이해할수 있을 것이다.
const apr_array_header_t *tarr = apr_table_elts(tab);
const apr_table_entry_t *telts = (const apr_table_entry_t*)tarr->elts;
int i;
for (i = 0; i < tarr->nelts; i++)
printf("key = %s, val = %s\n", telts[i].key, telts[i].val);
19.3 해쉬
해쉬 테이블은 키와 값을 가지는 또 다른 저장 구조이다. 컨테이너 타입으로 해쉬 테이블은 아래와 같은 특징이 있다.
| append/insert/prepend | almost efficient(API support) |
| delete | almost inefficient(API support) |
| search(lookup) | efficient(API support) |
| iteration | almost inefficient(API support) |
검색은 효과적이고 확장가능하고, 다른 기능도 나쁘진 않다. 결과적으로 검색이 많고 쓰기 기능이 적은 컨테이너가 필요할 경우, 해쉬 테이블은 최고의 선택이다.
apr_hash_t * apr_hash_make(apr_pool_t *pool);
해쉬 테이블은 두가지 기본적인 동작이 있다. set과 get이다. 그들의 프로토 타입을 보면
void apr_hash_set(apr_hash_t *ht, const void *key, apr_ssize_t klen, const void *val);
void * apr_hash_get(apr_hash_t *ht, const void *key, apr_ssize_t klen);
키는 일반적으로 문자열이고,다른 타입도 상관은 없다. apr_ssize_t klen은 키의 길이, 보통은 문자열인 val은 값( 다른타입도 허용 ). 키와 값은 모두 포인터형이다. 이후에 메모리 관리와 관련된 것들을 이야기할것이다.
키가 문자열이라면 klen은 내부적으로 APR_HASH_KEY_STRING을 설정할수 있다.
키를 비교하기 위해 해쉬 테이블은 키의 값을 비교하기 보다는 키의 주소를 비교한다. 보다 정확하게 klen으로 키를 memcmp()한다. 키가 문자열이라면 모든것이 제대로 처리 된다.
아래 코드를 보면
/* works as you expect */
apr_hash_t *ht = apr_hash_make(mp);
const char *k1 = apr_pstrdup(mp, "foo");
const char *v1 = apr_pstrdup(mp, "bar");
apr_hash_set(ht, k1, APR_HASH_KEY_STRING, v1); /* "foo"=>"bar" */
const char *k2 = apr_pstrdup(mp, "foo");
assert(k1 != k2); /* key pointers are different */
assert(strcmp(k1, k2) == 0); /* key strings are same. hash table does the almost same comparison */
const char *v2 = apr_hash_get(ht, k2, APR_HASH_KEY_STRING);
assert(v1 == v2); /* hash table keeps the pointers. This equation is true */
assert(strcmp(v1, v2) == 0); /* needless to say, this is also true */
}
키가 문자열이 아니라면, 기대처럼 동작하지 않는다. 아래 예를 보면
/* Bit weird code. This doesn't work as you expect */
typedef struct _key_t {
int ki;
const char *ks;
} key_t;
key_t k1 = { 0, apr_pstrdup(mp, "foo") };
key_t k2 = { 0, apr_pstrdup(mp, "foo") };
const char *v = apr_pstrdup(mp, "bar");
apr_hash_set(ht, &k1, sizeof(key_t), v);/* this is legal */
const char *v1 = apr_hash_get(ht, &k1, sizeof(key_t));
assert(v1 == v); /* works as you expect */
const char *v2 = apr_hash_get(ht, &k2, sizeof(key_t));
/* Do you think v2 equals to v ? */
/* No. hash table calls memcmp(&k1, &k2, sizeof(key_t) internally.
By this comparison, k1::ks doesn't equal to k2:ks, so that v2 doesn't equal to v1. */
내 경험으로 문자열과 다른 타입을 드물게 사용했는데 신경쓸 필요는 없다.
아래예를 보면 apr_pstrdup()로 키와 값을 받는다. 해쉬 테이블은 오직 포인터를 사용해서 문자열 메모리를 주의 깁게 관리해야 한다. 아래는 버그가 있는 코드이다.
/* BUGGY code: an invalid entry exists in hash table */
void func(apr_hash_t *ht)
{
char key[32];
strcpy(key, "foo");
apr_hash_set(ht, key, APR_HASH_KEY_STRING, "bar");/* key is going to be invalid out of this function */
return;
}
엔트리를 삭제할때, val은 널이라서 지나간다.
apr_hash_set(ht, "to-del", APR_HASH_KEY_STRING, NULL);
이런 경우에 키문자열과 값 오브젝트는 메모리플에 할당되지 않았다. 그래서 메모리 관리를 주의깊게 해야한다. 해쉬테이블을 삭제한후에 그들의 메모리를 주의 깊게 관리해야 한
다.
/* A case value objects require own memory management */
typedef struct _ht_obj_t { /* value object type */
const char *key;
int val;
} ht_obj_t;
/* create an object value */
ht_obj_t *obj = malloc(sizeof(ht_obj_t));
obj->key = strdup("foo");
obj->val = 0;
apr_hash_set(ht, obj->key, APR_HASH_KEY_STRING, obj);
/* [1] typical memory leak bug in deleting entry */
{
apr_hash_set(ht, "foo", APR_HASH_KEY_STRING, NULL);
/* if we forget to free @obj related to "foo", we have memory leak bug */
}
/* [2] workaround of memory leak */
{
ht_obj_t *obj = apr_hash_get(ht, "foo", APR_HASH_KEY_STRING);
apr_hash_set(ht, "foo", APR_HASH_KEY_STRING, NULL);
destroy_obj(obj);/* assuming this takes care of free(obj->key) and free(obj) */
}
새로운 엔트리를 해쉬테이블에 추가할때, 키가 이미 존재할때는 어떻일이 벌어지나? 그 답은 이미 있던 값은 덥어쓰여진다. 그러나 덥어쓰여지지 않을 경우에 버그가 발생한다. 아
래 예를 보면
/* BUGGY code (very confusable) */
const char *old_key = strdup("foo");
const char *old_val = strdup("bar");
apr_hash_set(ht, old_key, APR_HASH_KEY_STRING, old_val);
/* overwrite with a new key, but the same key */
const char *new_key = apr_pstrdup(mp, "foo");
const char *new_val = apr_pstrdup(mp, "BAR");
apr_hash_set(ht, new_key, APR_HASH_KEY_STRING, new_val);/* this overwrites old entry as you expect except that @old_key is still alive... */
const char *v = apr_hash_get(ht, "foo", APR_HASH_KEY_STRING);
assert(v == new_val && v != old_val); /* We find the new value in hash table */
/* We would think both old key and old val have no reference... */
free(key); /* BUGGY... */
free(val);
해쉬 테이블 순회 코드
apr_hash_index_t *hi;
for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {
const char *k;
const char *v;
apr_hash_this(hi, (const void**)&k, NULL, (void**)&v);
printf("ht iteration: key=%s, val=%s\n", k, v);
}
주의 : 최신의 libapr은 해제할 테이블 리스트를 가지고 있다. 그러나 예전 버전에는 그런것이 없다. 이것은 유일한 키값으로 다양한 엔트리를 추가 삭제할때 메모리 릭을 야기시켰다. 예전 libapr 버전을 사용하고 있다면 새로운 버전으로 업그레이드를 추천한다.업그레이드가 어렵다면 apr_hash.c만이라도 업데이트를 하는게 좋다.
주의 : apr_hash_set()함수는 동일한 키값이 있을 경우 overwrite 된다. 따라서 먼저 입력된 값을 유지하고 싶으면 apr_hash_get()으로 존재 유무를 체크한후에 apr_hash_set()을 호출해야 한다.
19.4 링( 순환 이중 연결 리스트 )
링은 순환 이중 연결 리스트이다. 컨테이너 타입으로 아래와 같은 특징이 있다.
| append/insert/prepend | almost efficient(API support) |
| delete | almost efficient(API support) |
| search(lookup) | depends(API support) |
| iteration | almost efficient(API support) |
링크드 리스트는 추가, 입력, 앞에 붙이기, 삭제 같은 기능을 수정하기에 좋다.이런 기능들은 보통 다른 컨테이너보다 좋다. 게다가, 검색이나 순회같은 다른 기능들도 대체로 효율적이다. 쉽게 정렬된 연결 리스트를 만들수 있기 때문에 검색 기능을 보다 빠르게 할수 있다. 리스트는 당신에게 좋은 종종 좋은 선택이 될것이다.
apr_ring은 앞에서 언급한 컨테이너와는 조금 다르다. apr_ring은 컨테이너 타입은 아니다. 데이터 구조를 링크드 리스트로 만드는 것을 돕는다.
첫째로, 사용자 타입( 엘리먼트 타입, 컨테이너 타입)을 정의해야 한다. 예를 보면 my_elem_t는 엘리먼트 타입의 이름이고 my_ring_t은 컨테이너 타입의 이름이다. APR_RING_ENTRY()로 거대한 구조체타입을 넣는 것은 링 커네티어의 엘리먼트가됨을 의미한다. APR_RING_HEAD()는 사용자 링 컨테이너 타입을 정의한다.
/* type definitions sample of ring */
typedef struct _my_elem_t {
APR_RING_ENTRY(_my_elem_t) link;
int num;
const char *str;
} my_elem_t;
typedef struct _my_ring_t my_ring_t;
APR_RING_HEAD(_my_ring_t, _my_elem_t);
다음에, 링 컨테이너 오브젝트를 생선한다. 타입이 완료되면 명시적으로 오브젝트를 생성한다. my_ring_t의 내부에 의존하지 않는다는 것을 숙지해라. 그리고 그것을 사용하기 위해서 API를 호출한다. 링 컨테이너 오브젝트를 만든후에 APR_RING_INIT()로 초기화 한다. APR_RING_INIT()는 세개의 아규멘트를 필요로 한다. 링 컨테이너 오브젝트, 엘리먼트명, APR_RING_ENTRY()의 이름
my_ring_t *ring;
ring = apr_palloc(mp, sizeof(my_ring_t));
APR_RING_INIT(ring, _my_elem_t, link);
ring을 사용할 준비가 끝났다. 링에 엘리먼트는 추가하기 위해 APR_RING_INSERT_TAIL()을 호출한다. 앞쪽에 추가 하기 위해서 APR_RING_INSERT_HEAD()를 호출한다. 추가는 APR_RING_INSERT_BEFORE()또는 APR_RING_INSERT_AFTER()을 호출한다. ring-sample.c를 살펴봐라
동시에 엘리먼트 셋을 다를수 있다. 링에 엘리먼트를 추가하기 위해서 APR_RING_SPLICE_AFTER()또는 APR_RING_SPLICE_BEFORE()을 호출한다. 두개의 링을 하나의 링으로 쉽게 합칠수 있다. APR_RING_CONCAT()를 호출함으로써
링에서 엘리먼트를 제거아히 위해서 APR_RING_UNSPLICE()를 호출한다.
링을 순회하기 위해서 샘플 코드를 보면 기본적인 순회방법이 나와있다.
const my_elem_t *ep;
for (ep = APR_RING_FIRST(ring); ep != APR_RING_SENTINEL(ring, _my_elem_t, link); ep = APR_RING_NEXT(ep, link))
printf("elem: num=%d, str=%s\n", ep->num, ep->str);
링이 더블 링크드 리스트라서 역방향 순회도 가능하다. 게다가 링은 순환 링크드 리스트라서 우리는 리스트의 마지막을 계속 해서 순회한다. ring-sasmple.c를 살펴보면 사용법이 나와 있다.
주의 : 보시다시피 ring API는 매크로로써 구현되었다.
주의: 링 오브젝트의 lifetime은 길고, 메모리플에 엘리먼트를 할당받을수 있는데 이것은 freelist를 사용하기 위한 좋은 방법이다. 당신은 링으로 freelist를 쉽게 구현할수 있다. 이 방법으로 메모리 릭을줄일수 있고,게다가 새로운 엘리먼트를 빠르게 추가할수도 있다.
'C언어' 카테고리의 다른 글
| [APR] file lock (0) | 2009.01.30 |
|---|---|
| warning assignment makes pointer from integer without a cast (0) | 2009.01.30 |
| [APR] file handling (0) | 2009.01.23 |
| [APR] memory pool (0) | 2009.01.22 |
| apache 코어 설정 (0) | 2009.01.22 |