C 구조체에서 가변길이 문자열 처리.

splendor의 이미지

C로 url 주소의 리스트를 구조체로 만들려고 하는데요,
url주소의 길이도 제각각이고 몇개가 될지도 모릅니다.

아래와 같이 단순 무식하게 만들었는데,

#define URL_MAX_COUNT 255
#define URL_MAX_LENGTH 255

typedef struct _URL_LIST {
int url_count;
char urls[URL_MAX_COUNT][URL_MAX_LENGTH];
} URL_LIST;

위 구조체는 항상 MAX data 크기를 가지게 되서 memory 낭비가 되는데,
보다 최적화된 구조체는 없을까요?

익명 사용자의 이미지

cinsk의 이미지


struct url {
size_t size;
char body[0];
};

익명 사용자의 이미지

제가 몇자 덧붙이자면...

http://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html

gcc의 zero-length array하고 ISO C99의 flexible array member하고는 약간 차이가 있으니 유의하세요. 권장하는 쪽은 후자입니다.

해당 링크에서 ISO C90부터 flexible array member가 있다고 하는데, 제가 알기로 이건 C99에서부터 생긴걸로 알고 있습니다. 확인은 못하겠군요.

익명 사용자의 이미지

메모리 낭비를 없게 하려면 문자열마다 그 크기만큼 동적으로 할당하고
그걸 링크드리스트로 쭈욱 연결해서 관리하면 메모리 낭비는 없죠.

대신 느려집니다.

HDNua의 이미지

리스트의 내용이 변경되거나 삭제되지 않는다면, 이런 꼴도 재밌을 것 같네요.

hdslist.h

#ifndef __HDSTR_H__
#define __HDSTR_H__
 
void            hds_init(unsigned int align);
const char *    hds_push(const char *str);
const char *    hds_first();
const char *    hds_next(const char *pos);
void            hds_clear();
 
unsigned int    hds_count();
 
#endif

hdslist.c

#include "hdslist.h"
 
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <memory.h>
 
static struct
{
    unsigned int len;
    unsigned int max;
    unsigned int count;
    unsigned int align;
    char *buf;
    char *pos;
} global;
 
static void extend()
{
    char *buf = (char *)realloc(global.buf, global.max + global.align);
    global.max += global.align;
    if (buf != global.buf)
    {
        memcpy(buf, global.buf, sizeof(char)*global.max);
        global.buf = buf;
    }
}
 
void hds_init(unsigned int align)
{
    global.align = align;
    global.buf = (char *)calloc(align, sizeof(char));
    global.pos = global.buf;
    global.max = align;
    global.len = 0;
    global.count = 0;
}
const char *hds_push(const char *str)
{
    const char *hds;
    const size_t len = strlen(str);
 
    while (global.max - global.len < len)
        extend();
 
    strcpy(global.pos, str);
    hds = global.pos;
 
    global.pos += len + 1;
    global.len += len + 1;
    ++global.count;
 
    return hds;
}
const char *hds_first()
{
    return global.buf;
}
const char *hds_next(const char *pos)
{
    while (*pos++)
        ;
    return pos;
}
void hds_clear()
{
    if (global.buf)
        free(global.buf);
    hds_init(global.max);
}
 
unsigned int hds_count()
{
    return global.count;
}

main.c

#include <stdio.h>
#include "hdslist.h"
 
void show_list();
 
int main(void)
{
    const char *arr[10];
    int ac = 0;
 
    hds_init(10);
 
    hds_push("Hello, world!");
    hds_push("My name is DoYeong Han!");
    hds_push("See ya!");
    show_list();
 
    hds_push("Hello again, friend!");
    show_list();
 
    hds_clear();
    show_list();
 
    hds_push("string 1");
    hds_push("string 2");
    show_list();
 
    return 0;
}
 
void show_list()
{
    unsigned int i;
    const char *pos;
    unsigned int count;
 
    count = hds_count();
    for (i=0, pos=hds_first(); i<count; ++i, pos=hds_next(pos))
        printf("%d: %s\n", i, pos);
    puts("");
}

각각의 노드에 대해 동적할당을 하는 방식이 아닌,
문자열을 연속적으로 저장하는 배열을 만들고
이에 대해서만 길이를 조정하자는 거지요.
문자열이 여러 번 추가되어야 한다면 초기 align 값을 크게 주어
realloc 호출 횟수를 줄일 수 있습니다.

저는 이렇게 생각했습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.