What does the author of the bowels mean "in place"?

Question

I just implemented a kind of bitwise trie (based on subsoil), but my code has a lot of memory allocation (for each node). Contrary to my implementation, the bowels are said to be fast, among all things, due to their small amount of memory allocation (if any). The author claims that its implementation is “in place,” but what does this really mean in this context? And how do non-conductors achieve such a small number of dynamic memory allocations?

Ps: I know that sources are available, but the code is pretty hard to follow, and I can't figure out how this works.

Answer 1

I took a look at the source code of nedtrie.h. It seems that the reason "in place" is that you have to add three bookkeeping to the items you want to keep.

You use the NEDTRIE_ENTRY macro to add parent / child / previous / previous links to your data structure, and then you can pass this data structure to various trie routines that will retrieve and use these added elements.

Thus, it is “in place” in the sense that you are expanding your existing data structures and trie code connectors on this.

At least that's what it looks like. There are many macros in this code, so I might be confused (:

Answer 2

I am an author, so this is useful for many, according to Google, who also have difficulty using non-wired ones. I would like to thank people here for the stack flow for not making unpleasant comments about me personally, about any other discussions about the bowels.

• I'm afraid I don’t understand the difficulties, knowing how to use it. Usage is exceptionally simple - just copy the example in the Readme.html file:

typedef struct foo_s foo_t; struct foo_s { NEDTRIE_ENTRY(foo_t) link; size_t key; }; typedef struct foo_tree_s foo_tree_t; NEDTRIE_HEAD(foo_tree_s, foo_t); static foo_tree_t footree; 

static size_t fookeyfunct(const foo_t *RESTRICT r) { return r->key; }

NEDTRIE_GENERATE(static, foo_tree_s, foo_s, link, fookeyfunct, NEDTRIE_NOBBLEZEROS(foo_tree_s));

int main(void) { foo_t a, b, c, *r; NEDTRIE_INIT(&footree); a.key=2; NEDTRIE_INSERT(foo_tree_s, &footree, &a); b.key=6; NEDTRIE_INSERT(foo_tree_s, &footree, &b); r=NEDTRIE_FIND(foo_tree_s, &footree, &b); assert(r==&b); c.key=5; r=NEDTRIE_NFIND(foo_tree_s, &footree, &c); assert(r==&b); /* NFIND finds next largest. Invert the key function to invert this */ NEDTRIE_REMOVE(foo_tree_s, &footree, &a); NEDTRIE_FOREACH(r, foo_tree_s, &footree) { printf("%p, %u\n", r, r->key); } NEDTRIE_PREV(foo_tree_s, &footree, &a); return 0; }

You declare your element type - here it is struct foo_s. You need NEDTRIE_ENTRY () inside it, otherwise it may contain anything you like. You also need a key generation function. Other than that, it's pretty boilerplate.

I would not choose this macro-based initialization system! But this is for compatibility with rbtree.h BSD, so nedtries are very easy to swap for anything using rbtree.h BSD.

• As for my on-site use, algorithms, well, I think my lack of a computer science show here. What I would call "in place" when you use only memory is transferred to a piece of code, so if you transfer 64 bytes to a place, the algorithm will only touch 64 bytes, that is, it will not use additional metadata or allocate some additional memory or really write a global state. A good example is an in-place implementation where only the sorting of the collection (and I suppose the thread stack) is touched.

  Consequently, no, nedtries do not need a memory allocator. It stores all the data required by NEDTRIE_ENTRY and NEDTRIE_HEAD. In other words, when you allocate your foo_s structure, you do all the memory allocation for the subsoil.

• Regarding understanding the good macro, it’s much easier to understand the logic if you compile it as C ++ and then debug it :). The C ++ assembly uses templates and the debugger will clearly show you the state at any point in time. In fact, all debugging with my end happens in C ++ build and I meticulously convert C ++ changes to macrolized C.

• Finally, before the new version, I search Google for people having problems with my software to find out, I can fix things, and I am usually struck by what people say to me and my free software. First of all, why aren't those people who are asking me the difficulties directly? Help? If I know that there is something wrong with the documents, then I can fix them - the same way, asking stackoverflow does not let me know immediately that there are documents, the problem bur relies more on me to find it in the next release. So all that I would like to say is that if someone finds problems with my documents, please do write me and say so, even if there is a discussion like here on stackflow.

Niall

Answer 3

In place, it means that you are working with the source (input) data, so the input data becomes the output. Off-site means that you have separate input and output, and the input is not changed. On-site operations have several advantages: less cache / memory, less memory bandwidth, therefore, as a rule, higher performance, etc., but they have the disadvantage that they are destructive, that is, you lose the original input data ( which may or may not matter, depending on the use case).

Answer 4

In place, it means working with the input and (possibly) updating it. It is understood that there is no copying / moving of the input data. This can lead to the loss of the original input values, which you will need to consider if this applies to your specific case.