#Linked list and trie issues

28 messages · Page 1 of 1 (latest)

quaint relic
#

Hi all. I'm trying to build up a linked list from strings that are stored in nodes from a trie here: https://github.com/Ttibsi/autosuggest/blob/main/main.c#L46-L72. I'm running into a problem where after running for a bit, the code is hanging on this function that checks the length of the linked list: https://github.com/Ttibsi/autosuggest/blob/main/dll.h#L39-L47, although I can't really tell what is causing it. Going through GDB, I can see that at some point, there's a node that still has a next set, but no word stored in it. I'm not sure why this is happening, and I've tried changing dll.h:41 to looking for if n->word != NULL instead of how it currently is (checking for a not null next pointer).

(gdb) p *n
$2 = {next = 0x7fea51a750, prev = 0x0, word = 0x6c8beed8 "placability", word_len = 0, selected = false}
(gdb) p *n->next
$3 = {next = 0x7fea51a7b0, prev = 0x53298ad0, word = 0x0, word_len = 0, selected = false}

It looks like this gets set potentially at a previous point, although I don't know where a string copy into the linked list node wouldn't work properly (I'm assuming the pointer just isn't passed over?)

If anyone's able to take a look through and see if they can spot anything wrong here? I'm pretty new to C specifically, so if there's anything that could be done better, I'm up for any feedback. Thank you

restive plinthBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

jade ember
#

2 things immediately pops to mind:

        n.word = (char*)arena_alloc(..., sizeof(char) * strlen(word));
        n.word = strcpy(n.word, word);

is highly suspicious. a kind reminder that strlen returns the length of a c string excluding the null terminator

quaint relic
#

kind reminder that strlen returns the length of a c string excluding the null terminator
I hadn't taken that into consideration, thank you. I'm just adjusting now

#

lifetime ends as soon as the function returns
I thought this didn't happen in C becuase there's nothing to cleanup after n here? If there is, that's going to be what the problem is. My assumption is that the best approach here would be to malloc it and set the bytes? (If so, I'll probably use the arena allocator I'm using around this codebase)

restive plinthBOT
#

@quaint relic Has your question been resolved? If so, type !solved :)

jade ember
#

hence n gets cleaned up when the function returns and the pointer simply dangle

quaint relic
#

Yea, that would be the problem here then, I think. What would you suggest?

jade ember
#

either roll out your own vector instead and copy the node over
or
allocate the thing on the heap

quaint relic
#

On the heap usually means allocating memory (malloc and family), right?

jade ember
#

generally speaking - yes

quaint relic
#

Perfect, thank you. I'll make these changes tomorrow and probably ask more questions here/in the general help chat

wanton mountain
#

That is some of the most horrid C I've seen in a while. The parts which can be called C, some isn't even actual standard C at all.

#

Shit. The more I look, the more annoyed I am getting. I'll try to come back and give some proper feedback once my eyeballs start burning.

quaint relic
#

Well that’s constructive

jade ember
#

some notes i took you might be interested in:

  • headers only library are convenient, however if some source file included the same header twice - you're in for some compilation errors (2 separate header relay on the lib, the source file include these 2 headers).
    i'd stay away from those unless you know what you're doing.
  • having your allocator as a static var, declared in a header is a code smell. for one, globals are discouraged as they're hard to reason about (which part of the code alters the global state?)
    and second - you'll run into the same issue explained in the above bulletin. global vars declared in headers should be declared as extern, though, again - i'd stay away from those unless you know what you're doing.
  • any function returning a void * need not to be casted. e.g. https://github.com/Ttibsi/autosuggest/blob/b076ed07e32cf0b8562302116818440dfa4e7bb7/trie.h#L35 the cast is redundant
  • "\0" should be written as ""
  • any identifier which starts with a _ followed by a capital letter in the file scope is reserved by the standard https://github.com/Ttibsi/autosuggest/blob/b076ed07e32cf0b8562302116818440dfa4e7bb7/dll.h#L8, i'd change that struct name
quaint relic
#

Thank you for the feedback. Do you need to extern a static global even if it’s going to only exist inside that header? I’ll look into splitting some of these into header and impl files instead, I guess.

restive plinthBOT
#

@quaint relic Has your question been resolved? If so, type !solved :)

jade ember
quaint relic
#

I’ve split my own files up, but the arena.h (which isn’t mine) — I’m only defining the implementation in my main.c, but including the header in multiple files for the Arena declaration. However it thinks there’s multiple declarations for every function.

How should I work around this? I assumed that multiple includes shouldn’t be a problem as it should be the same as any other header?

Just pushing a new commit with these changes now.

jade ember
#

what exactly gives you errors? what does the errors looks like?

quaint relic
#

This error is repeated for every function in the file:

arena.h:431:6: error: redefinition of ‘arena_trim’
  431 | void arena_trim(Arena *a){
      |      ^~~~~~~~~~
arena.h:431:6: note: previous definition of ‘arena_trim’ with type ‘void(Arena *)’
  431 | void arena_trim(Arena *a){
      |      ^~~~~~~~~~
jade ember
#

try and define ARENA_IMPLEMENTATION in this manner instead.

#include "dll.h"
#include "trie.h"

#define ARENA_IMPLEMENTATION
#include "arena.h"
quaint relic
#

Yep, that was it. Thank you!

#

Is it generally advised to avoid STB headers, then?

jade ember
#

thats not what i said. if you know what you're doing - go for it. otherwise - well, they have their quirks as you saw