Ask HN: Favorite pointer tricks in C?

What I think takes the cake is this:<p><pre><code> array[index] == index[array] </code></pre> Not that you would actually use this, but it gave me a lot of insight into how addressing and stuff works inside the compiler. Also from this example, there's the implicit suggestion that an array can be treated as a pointer. So that leads into pointer arithmetic which can be very useful.

The canonical evil pointer trick is using prev_xor_next to construct a doubly linked list.

Regarding function pointer arrays, I'm doing something in labrea (<a href="http://github.com/dustin/labrea" rel="nofollow">http://github.com/dustin/labrea</a>) where I need to make what is effectively an FFI call from C to C where I know the number of arguments, and their types, but I have them in the form of an array of unions.<p>For example, if I need to call read, it's basically an invocation of a function with a 4 byte, 8 byte, and then 4 byte argument (on a 64-bit system). I have a union argument type that represents 32-bit and 64-bit parameter types at the same time. I make a call like this:<p><pre><code> rv = abstractInvoke(&#38;fun, args); </code></pre> which, depending on arity of fun, invokes something like this (auto-generated):<p><pre><code> rv = abstractInvoke(fun, args[0], args[1], args[2]); </code></pre> That three-arg function looks roughly like this (calling my argument type ``a_t'' to abbreviate):<p><pre><code> a_t abstractInvoke(struct ftype *fun, a_t a0, a_t a1, a_t a2) { static a_t (*allfuns[])(const void*, a_t a0, a_t a1, a_t a2) = { invoke_3_4_444, // 0 invoke_3_8_444, // 1 invoke_3_4_448, // 2 invoke_3_8_448, // 3 invoke_3_4_484, // 4 invoke_3_8_484, // 5 // [...] invoke_3_8_888, // 15 }; return allfuns[fun-&#62;offset](fun-&#62;orig, a0, a1, a2); } </code></pre> I generate all of the functions by arity and types and then compute an array offset of them ahead of time (so read has an offset of 5 since it returns an 8 byte value and its arguments take a 4 byte, 8 byte, and then 4 byte value).<p>Without this trick, I'd have to use very non-portable assembler to do the same invocation (OK, I'd use libffi or dyncall's already prepackaged very non-portable assembler, which I may end up with anyway) to make this function call.

Copy-free contiguous subsets of arrays are fairly simple but often convenient. If you want elements 5 through 33 of big_array, you just get a pointer to element 5, and keep track separately of the length. A common case is where you split an array into two non-overlapping subparts, in which case, if you no longer need the original, you can treat each subpart as if it were a separate array. Saves the work of allocating two new arrays for the split parts, which is necessary in many other languages. Useful for efficiently implementing things like decision-tree learners.

I like the trick of using the last few bits of aligned pointers to store something useful. It's tricky and has to be done correctly. A class wrapper around the pointer would be better.<p>For e.g., a constraint in an AVL tree requires that the difference in sizes of left and right subtrees be -1, 0 or 1 (just 3 values, which requires 2 bits). A 4-byte aligned pointer would be enough. =)

You can demonstrate pointer arithmetic by showing how you would work with the strstr function. It's the clearest and most understandable reason for someone to see why you'd even discuss this topic I think. I talk to some people without C experience and they hear that idea and get scared. I usually explain how strstr works and that seems to always make sense to them.<p>Good luck!

It's kind of an anti-pattern, but I've found this to actually enhance clarity in a few places:<p><pre><code> int moved = (is_reading ? read : write)(fd, buf, len);</code></pre>

Compare pointers rather than compare strings: convert all words in a dictionary to a trie structure. Then, each leaf of the tree (a word) is a pointer. A phrase or sentance can be a list of pointers. Pointer compares are mondo-faster when comparing two pointers than walking down two strings.

One that comes to mind:<p><pre><code> struct name { int namelen; char namestr[1]; }; struct name *makename(char *newname) { struct name *ret = malloc(sizeof(struct name)-1 + strlen(newname)+1); /* -1 for initial [1]; +1 for \0 */ if(ret != NULL) { ret-&#62;namelen = strlen(newname); strcpy(ret-&#62;namestr, newname); } return ret; } </code></pre> (From <a href="http://c-faq.com/struct/structhack.html" rel="nofollow">http://c-faq.com/struct/structhack.html</a> ) Simple way of storing a string's name and length in one allocated structure.<p>Others: virtual function tables, function pointers inside of structs that take a "this" argument effectively giving you OOP, opaque pointers to give compile- and run-time private encapsulation...

* Using pointer offsets to get to the stack frame pointer, and then walking the frame pointer backwards to get the call stack.<p>* Using &#38;&#38; to take the address of a jump label.<p>* Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.

I remembered another one, the teleporting turtle algorithm. <a href="http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html" rel="nofollow">http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html</a> It's a neat way to determine if there are loops in a linked list (among many other uses).<p><i>We start with the turtle and rabbit pointing to the head, and then on each clock tick we advance the rabbit by one step. After a while, assuming we've neither found the end of the list nor caught the turtle, we teleport the turtle to the rabbit's position, double the length of time we're willing to wait, then go again.</i>

implementing linked lists the way the linux kernel does, that is: each node contains one pointer for each list it can be part of, that pointer's position is determined using some offset_of( field, name) macro.

Now I won't spell out actual "pointer tricks" but try to give some context in which these tricks might naturally be used:<p>I think that data structures like trees are a nice thing to continue once the fundamental properties of pointers have been discussed. (pointer to left, right and data...).<p>Then sketch out the operations necessary to insert elements, and then explain how pivoting the tree makes it stay performant. This gives you a lot of opportunity to use pointers-to-pointers and so on.<p>It's a thing that can be nicely visualized on a whiteboard, and it has relevance for students to understand things like databases or filesystems.<p>If you care to elaborate, you could continue explaining the pitfalls of multithreading, or locking all or parts of the tree during updates, making updates visible in a atomic way... but that gets's out of your "not too simple/crazy" limit pretty fast.<p>You could also make up a nice producer/consumer example where parts of data that has to be processed is passed around by pointers, stored in linked lists, sliced up/combined. Processing images (rotating tiles), or drawing fractals in parts of memory pointed to by some variable comes to mind.

Would you care to share the learning objectives you are fulfilling with pointer tricks in C? Or if it's just some extracurricular entertainment?

Instead of using a while loop to iterate through a linked list, consider using a for loop.<p><pre><code> Node * iter; for (iter=root; iter != NULL; iter=iter-&#62;next) { /* iter-&#62;object; */ } </code></pre> A concise implementation of strlen<p><pre><code> size_t strlen(char * str) { char * cur; for(cur=str; *cur; ++cur); return (cur-str); } </code></pre> Reverse a string in-place.<p><pre><code> void reverse(char * str) { char *i,*j, tmp; for (i=str, j=(str+strlen(str)-1); i &#60; j; ++i,++j) { tmp = *i; *i = *j; *j = tmp; }</code></pre>

A trick to save memory:<p>If you have a struct/class with a lot of members that are usually set to zero or some other initial value, you can store them in a "lookaside" structure that is hung off a global hash table with the pointer of the original object as the hashtable key. You can then use a bitfield to keep track of which members actually have interesting data.<p>So -- accessing the member would look something like this:<p><pre><code> int MyClass::get_foo() { if (foo_set_) return global_lookaside[this].foo; return 0; }</code></pre>

My favorite pointer trick is a simple one. I learned it when I had to implement it (in 64-bit) in a C compiler.<p>Simply, you can subtract pointers. Let's say you're walking a string from the front and from the back at the same time, and want to find the length of the substring. Well, you don't have to use indeces, just do this:<p><pre><code> int len = back_ptr - front_ptr; </code></pre> You'd be surprised how often this crops up when you're using lots of pointer tricks.

I am not zure whether it fits what you call 'relatively simple', but Knuth's "Dancing links" (<a href="http://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow">http://en.wikipedia.org/wiki/Dancing_Links</a>) would make my list.

pointers to structs for things like network protocols...<p>struct packet_header { uint from_addr; uint to_addr; ushort flags; ... }<p>packet *p;<p>read(socket, somebuf, sizeof(packet));<p>p = &#38;somebuf;<p>printf("from = %u to = %u flags = %u\n",p-&#62;from_addr, p-&#62;to_addr, p-&#62;flags);

You may want to show them how you can <i>generate</i> code by emitting assembly hex-codes into a block of memory and then _call_ the block of code after casting it into a function pointer.

Copy a string in one line:<p><pre><code> while (*dst++ = *src++);</code></pre>

I wish an HNer had taught <i>me</i> C in high school.

String literals are implicitly pointers and pointers are mostly equivalent to arrays.<p>char digitAsChar = "0123456789"[digitAsInt%10];

<p><pre><code> void strcpy(char *s, char *d) { while(*d++ = *s++); }</code></pre>

foo[5] is the same thing as * (foo + 5) (since "foo" is the address of the first element), which is equivalent to * (5 + foo) which is equivalent to 5[foo]! EDIT: hn ate up my * s.