What is Relative Pointers?

[@wojwesoly]

Why did it take me almost a year to understand where there channel name came from? (coding -> цoding (ц is pronounced as /ts/) -> tsoding)

[@IntoTheTerminal]

Tsoding! I am actually glad you see you alive and kicking! I missed your streams on Twitch lately (can very well be due to my presence, lately, too), so I am happy to see you being active here. Keep it up and stay save, man. ;-)

[@martinkopta2161]

Brilliant explanation! Thank you for making this. I enjoyed it very much 👍

[@pitri_hub]

[edit] never mind, I wrote this a few minutes before you mentioned it at 1:47:45 I've noticed that this system could really nicely be encapsulated in a C++ class: template class relative_ptr { public: // constructor(s) // operator= // operator* // operator-> // operator bool (for easy null checks) // operator++, --, +=, -= private: offset_type m_offset{}; }; if all of these are implemented correctly, they'd just be used like regular pointers. And due to the second (defaulted) template parameter, we could easily inject our preferred (signed) offset-type on declaration.

[@a5daw218d]

"You nver have to call free, if you never called malloc" Thats how this guy managed to forgot memory leaks and truly live his life.

[@lolcat69]

4:36 but, because of how structs works it would still allocate 16 bytes of memory insteaf of 12 bytes, because if you don't change it with a preprocessor thingy, it will always allocate like a multiple of sizeof(uintptr_t)

[@lolcat69]

Oh wait no it uses less because you had 2 pointers, but if it was only 1 it would not be worth it

[@archavez100]

36:48 I actually did end up saving the structure to the filesystem, loaded it back up, and everything works. I'm unable to to get a segmentation fault like he does in his video... I also noticed that I'm getting the same memory address for the root node both when writing to fruits.bin, and when loading everything back into memory. Here's the source code for anyone that wants it: #include #include #include #include #include #include #include #include "fruits.h" #define UNIMPLEMENTED \ do { \ fprintf(stderr, "%s:%d UNIMPLEMENTED ", __FILE__, __LINE__);\ exit(1); \ } while(0) #define UNUSED(x) (void)(x) typedef struct Node Node; struct Node { char text[32]; Node *left; Node *right; }; #define NODE_POOL_CAP 1024 typedef struct { size_t size; Node nodes[NODE_POOL_CAP]; } Node_Pool; static Node_Pool global_node = {0}; Node *node_pool_alloc(Node_Pool *np) { assert(np->size < NODE_POOL_CAP); Node *result = &np->nodes[np->size]; memset(result, 0, sizeof(Node)); np->size += 1; return result; } void node_set_text(Node *node, const char *text_cstr) { size_t n = strlen(text_cstr); if (n > sizeof(node->text) - 1) n = sizeof(node->text) - 1; memset(node->text, 0, sizeof(node->text)); memcpy(node->text, text_cstr, n); } Node *node_pool_alloc_with_text(Node_Pool *np, const char *text_cstr) { Node *result = node_pool_alloc(np); node_set_text(result, text_cstr); return result; } void print_tree(FILE *stream, Node *node, size_t level) { for (size_t i = 0; i < level; ++i) fputs(" ", stream); fputs((const char*)node->text, stream); fputc(' ', stream); if (node->left) print_tree(stream, node->left, level+1); if (node->right) print_tree(stream, node->right, level+1); } Node* random_tree(Node_Pool *np, size_t level) { if (level == 0) return NULL; Node *root = node_pool_alloc_with_text(np, fruits[rand()%fruits_count]); root->left = random_tree(np, level - 1); root->right = random_tree(np, level - 1); return root; } void save_node_pool_to_file(Node_Pool *np, const char *file_path) { FILE *out = fopen(file_path, "wb"); if (out == NULL) { fprintf(stderr, "ERROR: could not write to file %s: %s %s%d", file_path, strerror(errno), __FILE__, __LINE__); exit(1); } size_t n = fwrite(np->nodes, sizeof(Node), np->size, out); assert(n == np->size); if (ferror(out)) { fprintf(stderr, "ERROR: could not write to file %s: %s %s%d", file_path, strerror(errno), __FILE__, __LINE__); exit(1); } fclose(out); } void load_node_pool_from_file(Node_Pool *np, const char *file_path) { FILE *out = fopen(file_path, "rb"); if (out == NULL) { fprintf(stderr, "ERROR: could not read from file %s: %s %s%d", file_path, strerror(errno), __FILE__, __LINE__); exit(1); } fseek(out, 0, SEEK_END); long m = ftell(out); fseek(out, 0, SEEK_SET); assert(m % sizeof(Node) == 0); np->size = m / sizeof(Node); assert(np->size nodes, sizeof(Node), np->size, out); assert(n == np->size); if (ferror(out)) { fprintf(stderr, "ERROR: could not read from file %s: %s %s%d", file_path, strerror(errno), __FILE__, __LINE__); exit(1); } fclose(out); } #define FRUITS_BIN_PATH "fruits.bin" // loading tree into memory from fs int main(void) { printf("Loading from file... "); load_node_pool_from_file(&global_node, FRUITS_BIN_PATH); Node *root = &global_node.nodes[0]; printf("root: %p ", root); print_tree(stdout, root, 0); return 0; } // saving random tree to fs /* int main(void) */ /* { */ /* srand(time(0)); */ /* printf("Writing to file... "); */ /* Node* root = random_tree(&global_node, 3); */ /* printf("root: %p ", root); */ /* print_tree(stdout, root, 0); */ /* save_node_pool_to_file(&global_node, FRUITS_BIN_PATH); */ /* } */

[@i007c]

the talk about mozilla is actually accurate 😂😂

[@desertfish74]

How about that!

[@rewixx69420]

69 comets

[@FelipeBalbi]

for print_tree(), you can use %*s and pass level as an extra argument: fprintf(stream, "%*s-%s ", level, " ", node->text); or something like that

[@BradenBest]

The syntax of a printf format is percent width [dot precision] type. For string (s), printing a subtring involves manipulating its precision. manipulating the width just makes it left/right justify to a "block" of W width depending on whether W is positive or negative. So to print 3 characters of a string, the format specifier is %.3s, and to print N characters of a string, it's %.*s, with N appearing as an argument before S, hence `printf("Your name is %.*s ", name->len, name->chardata);` This also goes a long way in explaining stuff like the float specifier. %.2f or %0.2f will print the float argument to a minimum width of 0 and a precision of 2 decimal places, whereas %6.3f will print to 3 decimal places but ensure that the string is padded to be at _least_ 6 characters long (somewhat counterintuitively including the decimal point), so numbers like 34.141 and 2.98 will align nicely, but something like 102.1 will break alignment because it's going to come out to 7 characters. Of course you can do something like %15f, which will justify to 15 characters but use the default precision, which is several decimal places. The precision behaves in different ways depending on the type, I don't think it does anything for integers (d/i/u) or hex/pointers (x/p). But the width always tells an exact number of characters to be the minimum width. Oh yeah, and another aspect of the width is that it can have prefixes, namely - and 0. Minus just reverses the padding direction, but if you prefix it with 0, the padding will be done with zeros instead of spaces, so %02u will print an unsigned number like 4 as 04, and I'm pretty sure %06.2f will print a number like 1.2 as 001.20. Hope that helps.

[@fumanchu332]

Thank you so much for finishing the stream here, after it went off-line.

[@Artentus]

Can confirm, am a Rustaceon and almost had a heart attack when I heard null pointer.

[@Heater-v1.0.0]

Think of it as "Option" where "T" is a reference to "Some" thing. When the value is zero it's "None" :)

[@TheQwertyiui]

At 1:44:34 you can see that the first `to_string` in line 10 uses c_style_strlen itself, so you could probably just write `s := to_string(text.data)`

[@Czeckie]

not important, but maybe someone is confused: 1 + 2 + 4 + 8 + 16 = 31, the number of elements in a (full) tree with L levels is 2^L - 1

[@puncherinokripperino2500]

*full binary tree

[@TfhvjvHvg]

nice to see you again

[@otesunki]

12:33 the pointer in the linked list doesn't point to itself, but to the beginning of the struct. it is not zero, but negative.

[@lhpl]

I was hoping this video would explore some advanced pointer tricks, such as implementing doubly linked lists with just one "uintptr_t other" field for both the prev and next pointers, by using the xor identities: (x xor y) xor y = x, (x xor y) xor x = y. Like: struct Node { uintptr_t other; ... }; struct List {struct Node *head, *tailtip;}; struct Cursor {struct Node *prev, *curr, *next; }; Cursor first(struct List a) { if(a->head) return { 0, a->head, (struct Node *)(((uintptr_t)0)^(a->head->other))}; else return {0, 0, 0}; } such that for any struct Node *x, with previous node p and next node n (p==0 for the first node, n==0 for the last, or p == n if used for a circular list) x->other == (uintptr_t)p ^ (uintptr_t)n, so that by just keeping track of the current Node and its immediate neighbors in a cursor, you can move the cursor in both directions. (Yes, I *know* this most likely may cause problems with some GC library or debugger, and may not be worth the trouble in most situations.) I noticed the great confusion caused by mixing Node pointers, char pointers, and array element pointers. It would have been far easier to represent "small/relative" pointers as the direct nonnegative integer indexes into the node pool (ie relative to node_pool[0]), or to the signed integer offsets (ie if np[i] has a left child np[j], then np[i].left == j-i.) By making the offsets not byte-based (of course requiring all nodes being the same size) the bit width can be even smaller. I kind of had the impression that this was done to make C look a lot worse than it is...

[@bothieGMX]

He started out with this idea, but explicitly wanted to showcase relative pointers, so simply indexing was not an option. But yea, I guess, in most cases, a simple index would be better.

[@MrRyanroberson1]

could you re-explain that XOR deal a little better? i don't understand from your explanation

[@bothieGMX]

@@MrRyanroberson1 The pointer other stores prev XOR next. Now, if you know, what prev was, then you can get next = other XOR prev. If you know what next was, you get prev = other XOR next. Since you use double linked lists to iterate forward or backward, you always know at least one of those two values.

[@lhpl]

@@bothieGMX thank you for explaining my comment. Yes, it is a way to implement doubly linked lists with just one more pointer in the "descriptor" than a singly linked list, instead of having a next and prev pointer in each node. I don't know if it has ever been used "in anger", as it is a bit more complicated, but for doubly linked lists where the node data is tiny (

[@bothieGMX]

@@lhpl yea, no problem I had to think about that storage method myself for a few minutes so I can imagine, how Ryan felt. Also: Having someone else explain it means getting a different explanation.

[@alexfrozen]

Why not just strncpy at 17:50? This truncation problem already solved for so populat case.

[@danielschmitt5750]

Nice video as always. I learned a lot. Thank you.

[@FiReLScar]

I managed to accidentally find your old KZbin channel while watching an old serenityos video

[@juanmacias5922]

Awesome pointer vid, just started learning C, and could understand like 25% of what you were doing haha

[@bothieGMX]

So, basicly, you understood everything but the interesting things ;) Keep it up, you're gonna learn it if you want it.

[@juanmacias5922]

@@bothieGMX Thanks man! I want it! :D

[@konstantinrebrov675]

That's good. 25% for just starting is not bad at all. How much do you understand now?

[@juanmacias5922]

​@@konstantinrebrov675I'm saddened to report I stopped using C months after... But I'm pretty comfortable using Dart, Python, and TypeScript, so I think getting the basics of C helped a lot, the reason I even picked it up was because I was trying to figure out the reason Golang worked the way it did lol

[@birdbeakbeardneck3617]

nice topic and explanation, thank u very much.. btw in my country, until recently we used pascal during high school until last year they introduced python, so ur not the only one using pascal

[@anon_y_mousse]

It's interesting that they chose to do relative pointers in Jai. I personally avoid bit tricks with pointers and instead implement a flat index into arrays when I need a stable reference to data. Makes it far easier to serialize. Every time I have to implement a custom hash table for a project, I use indices for the chain data. It makes reallocations much faster and if I need to rebuild the table data it's a simple one pass operation anyhow.

[@ManuelPietschmann]

I'm in the same boat, +1 for indices. They can be handed over as handles to other parts of the code. While relative pointers are interesting you need to know the base address from which they do offset.

[@rallolollo9309]

i agree i don't see the advantages of this roundabout way to do things

[@lhpl]

@@rallolollo9309 Indeed. The "fixation" on pointers probably stems from a time where compilers didn't optimize that well, and even integer multiplications were costly in cpu time (some architectures didn't even have mul instructions.) Hence zero-based array indexing and pointer incrementing for traversing an array. Per Brinch-Hansen designed a Pascal-inspired language, Edison, without pointers, only fixed size (!) (also enum-indexable!) arrays, and wrote an OS in it. So it can be done that way. ( _Programming a Personal Computer_ , Prentice-Hall, 1982.) With 64-bit architectures being common now, I wonder how much memory and time is wasted dealing with full 64-bit pointers instead of using integer indexes with sizes fitting the problem. Back when I used a Pentium M with 2GB RAM and 32-bit architecture, I could have about the same number of windows and tabs open in Firefox as I can now with 64 bits and 16 GB RAM.

[@mvladic]

In this video all we have is array of Nodes and allocator for that specific use case. So, you could just easy use indexes to the array instead of pointers. But, with pointers you can support structures of different sizes with more general allocator.

[@anon_y_mousse]

@@mvladic I don't know if you're aware, but in C array indexing is handled mostly by the compiler. You give an index and it multiplies that by the size of the individual cells. So any size structure you want will work and indices will work perfectly fine. 0 1 2 3 and the compiler knows it's x*sizeof(a[0]) and inserts the code for that.

[@clinteastwood-e6s]

Remember, don't make memory safe code because you want your program to be secure and stable, make memory safe code so a rust dev doesn't have a heart attack.

[@lrdass]

A thing that I don’t get it is that when you desserialize it , how come the relative pointer isn’t filled with garbage or you get a piece of memory that is being used 🤔🤔🤔

[@Lutz64]

@TsodingDaily could you push the finished code to github to make it easier to follow?

[@rafagd]

Ah yes, C++ creator Bjarne Soursop

[@homelessrobot]

Bjarnana Soursop

[@nmmm2000]

Very nice explanation! However I don't get what is the benefit of this kind of pointers? Why are they better than "normal" relative pointers that counts from the beginning from the arena?

[@errelin1326]

Well we don’t know either. But most of the time it’s just fun

[@JustSomeAussie1]

Does anyone know what font is being used in tsoding's emacs?

[@hmmm-interesting]

Probably Iosevka

[@JustSomeAussie1]

@@hmmm-interesting That looks like it. Thanks

[@alexfrozen]

It reminds me doom's wad files) Since I've seen it, I always use these technics. Only few real pointers for memory allocation.

[@DragonKidPlaysMC]

Does anyone have a link for the discord?

[@akshitsingh6429]

just search it up online

[@MehdiZeinaliZ]

alternative for node_set_text: void node_set_text(Node* node, const char* text_cstr) { snprintf(node->text, sizeof(node->text), "%s", text_cstr); }

[@14n73x]

Much better is to use strncpy(node->text, text_cstr, sizeof(node->text)/sizeof(char) - 1); Also to be completly secure you might want to explicitly set the last character of node->text to '\0' (in case the Node wasn't zeroed before).

[@danielschmitt5750]

Can someone explain to me why he implemented UNIMPLEMENTED as a do-while-loop?

[@dooptydoo90x]

It allows a macro to expand to a block of code that will only execute once

[@dwasd]

what is "Relative Pointers" concept?

[@flleaf]

27:01 "Why I switched to GitLab" comment section flashbacks

[@linesuid]

is there a use case where i must use malloc at all?

[@TsodingDaily]

When you need to allocate some memory on the heap?

[@linesuid]

@@TsodingDaily so when is that?

[@linesuid]

I'm just a noob asking btw

[@DalenPS]

@@linesuid when you need to allocate large blocks of memory, like say 1gb (the stack has limited space), and when you need an amount of memory that is only known at runtime. For example, consider a compiler. It needs to read in the program as text. The program may be 100 characters, it could be millions of lines

[@blackbeard3449]

@@linesuid the simplest example would be when you need an array of arbitrary size length that is only known at runtime

[@Shan224]

Well done🎉

[@arno.claude]

Hey Tsoding! Have you ever used fp-ts? It allows a Haskell-esque coding style in TypeScript. Would love to know your opinion on it :) Have a great day!

[@juan-tj1xf]

Ma fav Netflix series :)

[@zeeara1500]

3 times did not start, but then it worked

[@Mozartenhimer]

Relative pointers... So offsets?

[@Dzatoah]

yes

[@JATmatic]

I don't know why but every time dare to hit "play" on your video you consume +1h of my time.

[@AMith-lv2cv]

31:07 fruits(zozi's humor) and it on line... nice try randomness

[@antonw8134]

Turbo pascal was the best pascal. ;^}

[@cleciojung4645]

I'd like to see tsoding implement relative pointers in c++ using template class and operator overloading. It would be a very interesting video / live

[@i007c]

why make a unimplemented macro wtf just implement the damn code

[@aftalavera]

Is?

[@elotfreelancing1791]

do kernel development videos. do os development if possible

[@unsafecast3636]

28:18

[@omegafala720]

I did not understand nothing

[@aka_berkay]

so you understood everything