Here's the data structure:
struct node {
unsigned char end;
unsigned char letter;
unsigned char nchild;
struct node **child;
};
struct tree {
struct node *root;
};
And the code:
int
load(struct tree *tree, FILE *fp)
{
char *line, *word;
const char ws[] = " \t";
while ((line = fparseln(fp, NULL, NULL, NULL, 0))) {
while ((word = strsep(&line, ws)))
if (*word)
load_word(tree, word);
free(line);
}
return (ferror(fp)) ? 0 : 1;
}
int
load_word(struct tree *tree, char *word)
{
struct node *node, *child, **newp;
unsigned char c, i, j;
const char *errstr;
if (*word == '\0') {
errstr = "empty word";
goto fail;
}
node = tree->root;
while ((c = *word++) != '\0') {
if (c >= 'A' && c <= 'Z')
c = c - 'A' + 'a';
if (!(c >= 'a' && c <= 'z'))
continue;
for (i = 0; i < node->nchild; i++)
if (c <= node->child[i]->letter)
break;
if (i < node->nchild && c == node->child[i]->letter) {
node = node->child[i];
continue;
}
if ((child = new(c)) == NULL) {
errstr = "new error";
goto fail;
}
/*
if ((newp = reallocarray(node->child, node->nchild+1,
sizeof(*node->child))) == NULL)
goto fail;
node->child = newp;
node->nchild++;
for (j = node->nchild; j > i; j--)
node->child[j] = node->child[j-1];
node->child[j] = child;
*/
if ((newp = calloc(node->nchild+1, sizeof(*node->child))) ==
NULL)
goto fail;
for (j = 0; j < i; j++)
newp[j] = node->child[j];
newp[j] = child;
for (j = i+1; j < node->nchild+1; i++, j++)
newp[j] = node->child[i];
node->child = newp;
node->nchild++;
node = child;
}
node->end = 1;
return 1;
fail:
if (errstr)
warnx("load: %s", errstr);
else
warn("load");
return 0;
}
On 8/24/16, Theo de Raadt <[email protected]> wrote:
> No way.
>
> the bug is in your own code, which you didn't show.
>
>> Hi everyone,
>>
>> Sorry to trouble the list if this issue turns out to be spurious. I am
>> a relatively novice C programmer so it may just be my error. However,
>> I have implemented a program two ways: one using reallocarray() and
>> the other using calloc().
>>
>> When I use reallocarray() I get the error "in realloc(): error: use
>> after free 0x..." So I recompiled with -g and ran gdb:
>>
>> Program terminated with signal 6, Aborted.
>> Loaded symbols for /home/pmaddams/<REDACTED>
>> Reading symbols from /usr/lib/libutil.so.12.1...done.
>> Loaded symbols for /usr/lib/libutil.so.12.1
>> Reading symbols from /usr/lib/libc.so.84.2...done.
>> Loaded symbols for /usr/lib/libc.so.84.2
>> Reading symbols from /usr/libexec/ld.so...done.
>> Loaded symbols for /usr/libexec/ld.so
>> #0 0x00000c01badbc87a in thrkill () at <stdin>:2
>> 2 <stdin>: No such file or directory.
>> in <stdin>
>>
>> The situation is, I have a sorted array of at most 26 elements
>> representing the child nodes of a trie. Instead of using a linked list
>> I have opted to reallocate the array as a new pointer, shift the top
>> elements away from the insertion index, copy the new element into the
>> proper location, and assign the new pointer to the old variable.
>>
>> Using small files this seems to work just fine. However, my goal is to
>> read in the entire file from /usr/share/dict/words, 2.4M of text. It
>> chokes and dies with the above error. But when I reimplement the
>> allocation routine with calloc() it seems to work fine.
>>
>> What information can I provide to help confirm whether this is a bug
>> in the system, or in my own code?
>>
>> Thanks.
>>
>
>
