C pointer is the most powerful and nasty concept. Whether marstering C points or not separate intermediate C programers from the elementary ones. Want to know whether you have mastered C pointers? Have a look at this program. If the basic idea is clear to you, you are qualified to be an intermediate programmer. If you have difficulty, you should learn hard from other programmers. It is unwise to study this program as a beginner. The catch in the program is too complicated.
This program is adapted from an example in the C bible “The C Programming Language” written by Kernighan & Ritchie. I commented it and extended its function a bit. This allocator is usually not as efficient as malloc family that comes with the system, but it is good enough for a lot of practical applications. Also, this allocator is simple and clear. You can largely predict its behaviour. In comparison, it is not always easy to understand malloc is doing.
I came to know this allocator from Phil Green’s Phrap assembler. I then found the book and reimplemented in my way.
I wouldn’t say that it’s true that you have to be able to write, or even understand your own custom general purpose allocator in order to say you have a firm grasp of pointers in C.
For most everyday purposes, malloc and free are good enough, and for those times when they aren’t (say, not fast enough, or not deterministic in time usage, etc.) there is more often than not some special attribute of the allocator that you do need which you can take advantage of (e.g. it’s often the case that you might only need to allocate chunks of a single, fixed size) which means you don’t need a general purpose allocator, and can do some other kinds of tricks (e.g. use a bit map for marking those fixed size chunks as free or used, and possibly some fast assembly to manipulate and search those bit maps if your need for speed is extreme).
Knowing how a general purpose allocator works is a different thing than knowing how pointers work, how they relate to arrays and can be treated in many ways as arrays, how pointer arithmetic works, and just generally how to use them in the language.
BTW, there are some neat pointer tricks in the linux kernel linked list implementation. I think that sort of thing is more related to “understanding how pointers work in C” than knowing how to write your own general purpose allocator is.
Thanks for the comments. I totally agree that in most practical cases, we do not need a general purpose allocator. I just think a general allocator itself is interesting, especially when I know the core functionality can be done in a few tens of lines. In addition, although I use malloc all the time, I can see a hand-made allocator may be potentially useful as it improves the error checking (just a bit), provide a way to know whether there is a memory leak (although no way to know the code that causes the leak), and give a stable performance on memory allocation in all systems.
undeniably…..