Four is the number of letters in the ...: Difference between revisions
Content added Content deleted
(Performance improvement) |
(C - reduce memory usage) |
||
Line 136: | Line 136: | ||
} |
} |
||
⚫ | |||
#define SHORT_STRING_MAX 16 |
|||
⚫ | |||
size_t size; |
size_t size; |
||
size_t capacity; |
size_t capacity; |
||
char* string; |
|||
} string_buffer; |
|||
char buffer[SHORT_STRING_MAX]; |
|||
char* ptr; |
|||
⚫ | |||
} string_t; |
|||
void |
void string_buffer_create(string_buffer* buffer, size_t capacity) { |
||
buffer->size = 0; |
|||
buffer->capacity = capacity; |
|||
buffer->string = xmalloc(capacity); |
|||
s->str.ptr = xmalloc(capacity); |
|||
⚫ | |||
memcpy(s->str.ptr, str, len + 1); |
|||
} else { |
|||
s->capacity = SHORT_STRING_MAX; |
|||
⚫ | |||
} |
|||
⚫ | |||
} |
} |
||
void |
void string_buffer_destroy(string_buffer* buffer) { |
||
⚫ | |||
if (s->capacity > SHORT_STRING_MAX) |
|||
buffer->string = NULL; |
|||
⚫ | |||
buffer->size = 0; |
|||
buffer->capacity = 0; |
|||
} |
} |
||
void string_buffer_clear(string_buffer* buffer) { |
|||
⚫ | |||
buffer->size = 0; |
|||
⚫ | |||
⚫ | |||
if (s->capacity < min_capacity) { |
|||
void string_buffer_append(string_buffer* buffer, const char* str, size_t len) { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
if (new_capacity < min_capacity) |
if (new_capacity < min_capacity) |
||
new_capacity = min_capacity; |
new_capacity = min_capacity; |
||
buffer->string = xrealloc(buffer->string, new_capacity); |
|||
buffer->capacity = new_capacity; |
|||
memcpy(ptr, s->str.buffer, s->size); |
|||
s->str.ptr = ptr; |
|||
} |
|||
else |
|||
s->str.ptr = xrealloc(s->str.ptr, new_capacity); |
|||
s->capacity = new_capacity; |
|||
} |
} |
||
⚫ | |||
char* dst = s->capacity > SHORT_STRING_MAX ? s->str.ptr : s->str.buffer; |
|||
buffer->size += len; |
|||
⚫ | |||
} |
} |
||
typedef struct word_tag { |
|||
const char* string_cstr(const string_t* s) { |
|||
size_t offset; |
|||
return s->capacity > SHORT_STRING_MAX ? s->str.ptr : s->str.buffer; |
|||
⚫ | |||
⚫ | |||
} word; |
|||
size_t string_length(const string_t* s) { |
|||
return s->size; |
|||
⚫ | |||
typedef struct word_list_tag { |
typedef struct word_list_tag { |
||
size_t size; |
size_t size; |
||
size_t capacity; |
size_t capacity; |
||
word* words; |
|||
⚫ | |||
} word_list; |
} word_list; |
||
Line 206: | Line 187: | ||
words->size = 0; |
words->size = 0; |
||
words->capacity = capacity; |
words->capacity = capacity; |
||
words->words = xmalloc(capacity * sizeof( |
words->words = xmalloc(capacity * sizeof(word)); |
||
string_buffer_create(&words->str, capacity*8); |
|||
} |
} |
||
void word_list_destroy(word_list* words) { |
void word_list_destroy(word_list* words) { |
||
string_buffer_destroy(&words->str); |
|||
⚫ | |||
free(words->words); |
free(words->words); |
||
words->words = NULL; |
words->words = NULL; |
||
Line 219: | Line 200: | ||
void word_list_clear(word_list* words) { |
void word_list_clear(word_list* words) { |
||
string_buffer_clear(&words->str); |
|||
string_destroy(&words->words[i]); |
|||
words->size = 0; |
words->size = 0; |
||
} |
} |
||
void word_list_append(word_list* words, const char* str) { |
|||
size_t offset = words->str.size; |
|||
size_t len = strlen(str); |
|||
string_buffer_append(&words->str, str, len); |
|||
size_t min_capacity = words->size + 1; |
size_t min_capacity = words->size + 1; |
||
if (words->capacity < min_capacity) { |
if (words->capacity < min_capacity) { |
||
size_t new_capacity = (words->capacity * |
size_t new_capacity = (words->capacity * 5)/4; |
||
if (new_capacity < min_capacity) |
if (new_capacity < min_capacity) |
||
new_capacity = min_capacity; |
new_capacity = min_capacity; |
||
words->words = xrealloc(words->words, new_capacity * sizeof( |
words->words = xrealloc(words->words, new_capacity * sizeof(word)); |
||
words->capacity = new_capacity; |
words->capacity = new_capacity; |
||
} |
} |
||
word* w = &words->words[words->size++]; |
|||
⚫ | |||
string_create(s, str); |
|||
w->length = len; |
|||
⚫ | |||
⚫ | |||
word* w = &words->words[words->size - 1]; |
|||
size_t len = strlen(str); |
|||
⚫ | |||
string_buffer_append(&words->str, str, len); |
|||
} |
} |
||
Line 247: | Line 237: | ||
word_list_append(words, get_small_name(&tens[n/10 - 2], ordinal)); |
word_list_append(words, get_small_name(&tens[n/10 - 2], ordinal)); |
||
} else { |
} else { |
||
word_list_append(words, get_small_name(&tens[n/10 - 2], false)); |
|||
word_list_extend(words, "-"); |
|||
word_list_extend(words, get_small_name(&small[n % 10], ordinal)); |
|||
} |
} |
||
count = 1; |
count = 1; |
||
Line 268: | Line 258: | ||
} |
} |
||
size_t count_letters(const |
size_t count_letters(const word_list* words, size_t index) { |
||
⚫ | |||
size_t letters = 0; |
size_t letters = 0; |
||
const char* s = |
const char* s = words->str.string + w->offset; |
||
for (size_t i = 0, n = |
for (size_t i = 0, n = w->length; i < n; ++i) { |
||
if (isalpha((unsigned char)s[i])) |
if (isalpha((unsigned char)s[i])) |
||
++letters; |
++letters; |
||
Line 288: | Line 279: | ||
word_list_append(result, words[i]); |
word_list_append(result, words[i]); |
||
for (size_t i = 1; count > n; ++i) { |
for (size_t i = 1; count > n; ++i) { |
||
n += append_number_name(result, count_letters( |
n += append_number_name(result, count_letters(result, i), false); |
||
word_list_append(result, "in"); |
word_list_append(result, "in"); |
||
word_list_append(result, "the"); |
word_list_append(result, "the"); |
||
Line 294: | Line 285: | ||
n += append_number_name(result, i + 1, true); |
n += append_number_name(result, i + 1, true); |
||
// Append a comma to the final word |
// Append a comma to the final word |
||
word_list_extend(result, ","); |
|||
} |
} |
||
} |
} |
||
Line 302: | Line 293: | ||
if (n == 0) |
if (n == 0) |
||
return 0; |
return 0; |
||
return words->str.size + n - 1; |
|||
for (size_t i = 0; i < n; ++i) |
|||
length += string_length(&words->words[i]); |
|||
⚫ | |||
} |
} |
||
Line 318: | Line 306: | ||
if (i != 0) |
if (i != 0) |
||
printf("%c", i % 25 == 0 ? '\n' : ' '); |
printf("%c", i % 25 == 0 ? '\n' : ' '); |
||
printf("%'2lu", count_letters(&result |
printf("%'2lu", count_letters(&result, i)); |
||
} |
} |
||
printf("\nSentence length: %'lu\n", sentence_length(&result)); |
printf("\nSentence length: %'lu\n", sentence_length(&result)); |
||
for (n = 1000; n <= 10000000; n *= 10) { |
for (n = 1000; n <= 10000000; n *= 10) { |
||
sentence(&result, n); |
sentence(&result, n); |
||
const |
const word* w = &result.words[n - 1]; |
||
const char* s = result.str.string + w->offset; |
|||
printf("The %'luth word is '%s' and has %lu letters. ", n, |
printf("The %'luth word is '%.*s' and has %lu letters. ", n, (int)w->length, s, |
||
count_letters( |
count_letters(&result, n - 1)); |
||
printf("Sentence length: %'lu\n" , sentence_length(&result)); |
printf("Sentence length: %'lu\n" , sentence_length(&result)); |
||
} |
} |