Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Favorite pointer tricks in C?

news.ycombinator.com

Post reply on HN
Print view View original

71–80 of 81 posts

Re: Ask HN: Favorite pointer tricks in C?

#71

Post by alan-crowe »

brl wrote: post #34
jallmann wrote: post #5

What I think takes the cake is this: array[index] == index[array] 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.

You didn't really spell out why this trick works: array[index] == *(array + index) == *(index + array) == index[array]

array + index == index + array needs justification

One expects the generic + in a+i to get expanded to raw addition .+. and raw multiplication .x. with s the size of elements of the array

    a .+. s .x. i
One expects index + array to throw a type error because index is just a number and doesn't have an element size.

So I'm guessing that the real reason that the trick works is that generic + has three methods with signatures

    int + int
    array + int
    int + array

Re: Ask HN: Favorite pointer tricks in C?

#72

Post by cnvogel »

Now I won't spell out actual "pointer tricks" but try to give some context in which these tricks might naturally be used:

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...).

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.

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.

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.

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.

Re: Ask HN: Favorite pointer tricks in C?

#74

Post by Jach »

bbulkow wrote: post #31
Jach wrote: post #9

One that comes to mind: 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->namelen = strlen(newname); strcpy(ret->namestr, newname); } return ret; } (From http://c-faq.com/struct/structhack.html ) Simple way of storing a string's name and length in one all…

The correct way to write this is to not use /1/ in the size of namestr, it's to use a simple []. This tells subsequent programmers that you are using variable length structures. In older compilers, the metaphor was to use '0', but C99 (maybe even earlier) got everyone using []. Here's a nice discussion in StackOverflow, including a bunch of C++ guys saying to just use Vectors, which ignores the entire point of gettin…

From GCC: ISO C90 does not support flexible array members. and: ISO C forbids zero-size array 'namestr'

Therefore I contest that your way is the "correct" way, especially since most C code is not C99 code. Also I'd probably never use this in C++. If you want to let subsequent programmers know you're using the variable length structure, add the comment: /* unwarranted chumminess with the compiler */

Re: Ask HN: Favorite pointer tricks in C?

#75

Post by deutronium »

cma wrote: post #55
_delirium wrote: post #20

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…

Also useful for storing parse results: " " gets modified during parsing to become: " " Your parse tree result result can then just contain pointers to "a\0", "href\0", and "blah\0" rather than doing any copying.

This is how strtok returns tokens too.

Incidentally I only found this after trying:

    char tmp[] = "cat,mat,sat";
    char *t;

    t = strtok(tmp,",");
    while(t != NULL){
      printf("%s\n",t);
      t = strtok(NULL,",");
    }
And getting a segfault, as 'tmp' is not writeable memory.

Re: Ask HN: Favorite pointer tricks in C?

#76

Post by jaen »

mansr wrote: post #68
thedigitalengel wrote: post #60

You may want to show them how you can generate 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.

Modern hardware and operating systems require special care when doing this. Firstly, the D-cache must be cleaned and the I-cache invalidated for the relevant memory addresses. This is because the CPU does not in general maintain coherency between these caches for performance reasons (writing instructions is rare). Secondly, memory protection must be set to allow execution of the generated code. Some systems even forb…

By modern hardware I assume you do not mean x86? Self-modifying code (without flushing the I-cache) is still allowed even on the latest processors. Modern OSes indeed do not mark all pages read/execute by default, but that takes a 1-line mprotect() or VirtualProtect() to change. Also, on RISC architectures, D-caches are generally not cleared as part of that process. After all, you are writing instructions, not data.

Re: Ask HN: Favorite pointer tricks in C?

#77

Post by mansr »

jaen wrote: post #76
mansr wrote: post #68

Earlier quoted context omitted.

Modern hardware and operating systems require special care when doing this. Firstly, the D-cache must be cleaned and the I-cache invalidated for the relevant memory addresses. This is because the CPU does not in general maintain coherency between these caches for performance reasons (writing instructions is rare). Secondly, memory protection must be set to allow execution of the generated code. Some systems even forb…

By modern hardware I assume you do not mean x86? Self-modifying code (without flushing the I-cache) is still allowed even on the latest processors. Modern OSes indeed do not mark all pages read/execute by default, but that takes a 1-line mprotect() or VirtualProtect() to change. Also, on RISC architectures, D-caches are generally not cleared as part of that process. After all, you are writing instructions, not data.

To the store instruction everything is data, even if it happens to be instructions. Stores initially go the L1 D-cache, and unless the I and D caches are coherent, explicit cleaning (D) and invalidating (I) is required. Maybe they are coherent on x86, but I know with certainty that they are not on for example ARM.

Re: Ask HN: Favorite pointer tricks in C?

#78

Post by bnastic »

xtacy wrote: post #13

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. 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. =)

This trick has been around for a very long time. I remember Tempus Editor on Atari ST (remember those?) using 8 bits of address registers for additional storage (as only 24 bits out of 32 were used for addressing).

Re: Ask HN: Favorite pointer tricks in C?

#80

Post by visualphoenix »

Locke1689 wrote: post #62
visualphoenix wrote: post #61

Earlier quoted context omitted.

Shouldn't that be --j in your reverse function? Anyhow, when asked to write those on a blackboard, I typically do this: size_t strlen(char* start) { char* end=start; while(*end) ++end; return (end-start); } and void reverse(char* i) { char* j=(i+strlen(i)-1); for (; i

Yup, --j. Also, the XOR version probably isn't worth the complexity.

True in practice, but on a blackboard during an interview, it obviates the need to recode for the follow-up "now reverse the string in place" request.
Post reply on HN