Ask HN: Favorite pointer tricks in C?

https://news.ycombinator.com/item?id=1925399

by cjtenny • 16 years ago

62 78 16 years ago

news.ycombinator.com

Hey HN,

I'm teaching a class to a bunch of high school and middle school students tomorrow who've all had moderate experience with programming. I'm covering pointer basics in C as a light intro or refresher, then focusing on cool (but relatively simple / not too crazy) tricks/tips/etc (e.g. stack walking, function pointer arrays). Care to share any of your favorite small pointer tricks with me for the class?

Thanks :)

-Cam

cperciva• 16 years ago

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

Anilm32• 16 years ago

Could you put an example?

okmjuhb• 16 years ago

http://en.wikipedia.org/wiki/XOR_linked_list

jhrobert• 16 years ago

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.

jallmann6• 16 years ago

I've recently started using offsetof in my own code, it's a pretty neat operator. Useful for nested structs, where you have a child but need to reference the parent.

jonsen• 16 years ago

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

cjtenny• 16 years ago

I'm teaching the class as a part of ESP's Splash @ MIT, a two-day educational outreach program. Thousands of middle and high school students swarm our campus just for this weekend, and MIT students/community/other teach whatever they want. I'm teaching this as a one-hour class, with two sections (that is, two times), for a bit of entertainment and to make this world a minimally more bug-free place... or something along those lines.

dkarl• 16 years ago

Pointer tricks are dirty and scare the elders. cjtenny is playing the childless uncle who talks about things no parent would. Kids that age will eat it up :-)

jallmann6• 16 years ago

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.

dgallagher• 16 years ago

The same as above, only using Pointer Arithmetic instead of Array Subscripting:

    *(array + index) == *(index + array)

Further broken down:

    *(&array[0] + index) == *(index + &array[0])

jallmann6• 16 years ago

Yep. And if teaching that to a bunch of middle or high schoolers, I would add that pointer arith works in increments of sizeof(array[0]) bytes. If you're not careful about operator precedence in moderately complicated expressions, that could come back to bite you.

brl2• 16 years ago

You didn't really spell out why this trick works:

    array[index] == *(array + index) == *(index + array) == index[array]

alan-crowe• 16 years ago

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

philwelch• 16 years ago

This is a fantastic way to show younger or beginning programmers to think beyond what the code is supposed to denote and consider how it works in reality--in other words, the hacker's perspective. A naive programmer takes array[index] at face value. The hacker gets the idea that array[index] is just *(array + index) deeply enough to make a perverse joke out of it.

jswinghammer• 16 years ago

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.

Good luck!

dtf2• 16 years ago

char buf[1024]; /* should be enough */

I actually write this a lot in my code. Not code that I intend to share with others, of course. But I do find it amusing about the value I put in brackets. I find it amusing that I have an OCD-like predisposition to make it a power of two. And I find it amusing how the number between the brackets has increased over the last ten years, from a frugal 64 to an opulent 1024. This, to me, is progress.

jallmann6• 16 years ago

In fact, a lot of code does this to avoid mallocs. Just be sure to check the length before you put anything into the buffer.

Also, making it a power of 2 is a good idea if you are concerned about alignment.

bbulkow2• 16 years ago

This avoids allocation and is safe (the cost of two extra compares is low because they'll branch the same way all the time, so you'll get branch prediction power)

  char *bufp;
  uint8_t buf[1024];
  if (need_sz >= 1024)
    bufp = malloc(need_sz);
  else
    bufp = buf;
  ....
  if (bufp != buf) free(bufp);

Jach3• 16 years ago

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 allocated structure.

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

bbulkow2• 16 years ago

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 getting a structure with only one memory allocation:

http://stackoverflow.com/questions/688471/variable-sized-str...

Jach3• 16 years ago

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 */

Someone• 16 years ago

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

xtacy• 16 years ago

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

benreesman• 16 years ago

this is how v8 does tagged pointers.

mansr5• 16 years ago

This trick is often seen in language interpreters. Two widely used examples are Emacs Lisp and Mozilla Spidermonkey Javascript.

bnastic• 16 years ago

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

dlsspy2• 16 years ago

It's kind of an anti-pattern, but I've found this to actually enhance clarity in a few places:

    int moved = (is_reading ? read : write)(fd, buf, len);

Dav3xor2• 16 years ago

pointers to structs for things like network protocols...

struct packet_header { uint from_addr; uint to_addr; ushort flags; ... }

packet *p;

read(socket, somebuf, sizeof(packet));

p = &somebuf;

printf("from = %u to = %u flags = %u\n",p->from_addr, p->to_addr, p->flags);

dspeyer• 16 years ago

Won't this leave all multi-byte values in network endianness?

tptacek3• 16 years ago

Yes, but so do the OS socket data structures, which is why htons() and htonl() are in the first chapter of any book on network programming.

The bigger problem with this scheme is alignment, although we appear to have outgrown architectures that will blow up when you get this wrong.

jmkeyes• 16 years ago

Don't use structures as lenses over unchecked input data.

makmanalp• 16 years ago

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.

_delirium• 16 years ago

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.

cma• 16 years ago

Also useful for storing parse results:

    "<a href='blah'>"

gets modified during parsing to become:

    "<a\0href\0'blah\0>"

Your parse tree result result can then just contain pointers to "a\0", "href\0", and "blah\0" rather than doing any copying.

deutronium• 16 years ago

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.

dlsspy2• 16 years ago

Regarding function pointer arrays, I'm doing something in labrea (http://github.com/dustin/labrea) 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.

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:

    rv = abstractInvoke(&fun, args);

which, depending on arity of fun, invokes something like this (auto-generated):

    rv = abstractInvoke(fun, args[0], args[1], args[2]);

That three-arg function looks roughly like this (calling my argument type ``a_t'' to abbreviate):

    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->offset](fun->orig, a0, a1, a2);
    }

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

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.

aliguori• 16 years ago

This isn't terribly portable FWIW. Not all calling conventions massage data into either a 32-bit or 64-bit argument. In particular, passing structs by value has some interesting rules even in the common calling conventions.

It will certainly work for 90% of the common function types out there and is a pretty common trick.

Jach3• 16 years ago

I remembered another one, the teleporting turtle algorithm. http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html It's a neat way to determine if there are loops in a linked list (among many other uses).

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.

tptacek3• 16 years ago

* Using pointer offsets to get to the stack frame pointer, and then walking the frame pointer backwards to get the call stack.

* Using && to take the address of a jump label.

* Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.

brl2• 16 years ago

> Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.

This is awesome beyond words. If I stumbled across this in the wild I would flip flop between awe and disgust until my head exploded.

Let me guess, "SMTP verb" is not a hypothetical example?

jallmann6• 16 years ago

This is also the basis for the fourcc's used in multimedia. Checking them only requires an integer compare.

defen2• 16 years ago

Nginx does this too under certain circumstances...check out the ngx_strN_cmp macros in ngx_http_parse.c. (where N is an integer from 3..9)

mansr5• 16 years ago

There are at least three common mistakes involving tricks like this:

1. Alignment. Many CPUs will trap (or worse) if accessing a 32-bit quantity at a non-aligned address.

2. Endianness. Needless to say, the 32-bit value read for a given string depends on the machine endianness.

3. Aliasing. Casting between different pointer types can result in a violation of the C aliasing rules and, with a little bad luck, incorrect results.

defen2• 16 years ago

* Using && to take the address of a jump label.

Had to look that one up...turns out it's a GCC trick that allows you store the address of a jump label into a pointer to void. Later on, you can do "goto *ptr" to jump back to that address. Neat. See http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

(You obviously already know this...just putting it here in case anyone else hasn't heard of it and is curious)

mansr5• 16 years ago

Being a gcc extension to the C language, I recommend this construct never be used and certainly not taught.

ay• 16 years ago

> Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.

How do you ensure your code is portable between the architectures with different endianness ? One trick may be using htonl on the u_int32_t to get it to a canonical format, but probably there would be better approaches ?

scumola• 16 years ago

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.

corysama• 16 years ago

String literals are implicitly pointers and pointers are mostly equivalent to arrays.

char digitAsChar = "0123456789"[digitAsInt%10];

Locke16896• 16 years ago

Instead of using a while loop to iterate through a linked list, consider using a for loop.

  Node * iter;
  for (iter=root; iter != NULL; iter=iter->next) {
       /* iter->object; */
  }

A concise implementation of strlen

  size_t strlen(char * str) {
     char * cur;
     for(cur=str; *cur; ++cur);
     return (cur-str);
  }

Reverse a string in-place.

  void reverse(char * str) {
    char *i,*j, tmp;
    for (i=str, j=(str+strlen(str)-1); i < j; ++i,++j) {
      tmp = *i;
      *i = *j;
      *j = tmp;
    }

mrb• 16 years ago

You have a bug in strlen:

     for(cur=str; cur; ++cur);

should be:

     for(cur=str; *cur; ++cur);

Locke16896• 16 years ago

Right you are. Wrote all those in the comment block. Fixed in an edit.

phsoftnet• 16 years ago

   size_t strlen(char *s)
   {
     size_t i = 0;
     while(*s++) i++;
     return i;
   }

visualphoenix2• 16 years ago

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 < j; ++i,--j) {
      *i ^= *j;
      *j ^= *i;
      *i ^= *j;
    }

Locke16896• 16 years ago

Yup, --j.

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

sfgfdhgfdshdhhd• 16 years ago

void strcpy(char s1, char s2) { while((s1++) = (s2++)); }

CountHackulus• 16 years ago

My favorite pointer trick is a simple one. I learned it when I had to implement it (in 64-bit) in a C compiler.

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:

   int len = back_ptr - front_ptr;

You'd be surprised how often this crops up when you're using lots of pointer tricks.

zam• 16 years ago

  void strcpy(char *s, char *d) {
    while(*d++ = *s++);
  }

tedunangst2• 16 years ago

your arguments are backwards and you didn't return dst.

juanufrj• 16 years ago

Bit off-topic, are you ted unangst from openbsd?

zeraholladay• 16 years ago

Copy a string in one line:

   while (*dst++ = *src++);

spacemanaki• 16 years ago

I wish an HNer had taught me C in high school.

jbeda• 16 years ago

A trick to save memory:

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.

So -- accessing the member would look something like this:

  int MyClass::get_foo() {
    if (foo_set_)
      return global_lookaside[this].foo;
    return 0;
  }

thedigitalengel2• 16 years ago

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.

mansr5• 16 years ago

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 forbid pages being writeable and executable at the same time in order to make code injection attacks that little bit harder.

jaen• 16 years ago

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.

cnvogel• 16 years ago

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.

Ask HN: Favorite pointer tricks in C?

Related Stories