Posts Tagged ‘c’

Array map in C

October 16, 2010 4 comments

Last year, I got “The Ruby Way” (link) as a gift to myself. I’m not a major Ruby freak, but there are some cool things about it and I really enjoy Ruby in general.

As I read my way through the book, I remember reading about array map. Array map is cool, it let’s you do things like {|s| s.strip! }

Which is roughly equivalent to

new_arr = []
my_strings.each {|s| new_arr.append(s.strip) }

Of course, this is kindof a stupid example and you can do MUCH more interesting things with Array#select or Array#reject – like write a one-liner to find all the phone numbers in an array that start with 351 or don’t hash to the same bucket, whatever. Anyway, I remember being really excited about array#map for some reason when I read that chapter. And whenever I get excited about something… weird things tend to happen. 🙂

See, I spend a lot of time writing programs in C. It’s a great language, and pretty much the only option in the kernel/filesystem/embedded world. So when I see a cool feature in another language (like Array map), I think “gee, wouldn’t it be awesome to have that in C.”

Being a frequent C coder, I do a lot of things with/to/because of arrays – and the two most common things I do with arrays are indexing and looping. Indexing is cool because it’s an O(1) operation, and that’s great for writing fast code that uses a lot of RAM. Looping, on the other hand… well, it’s usefulness depends on the problem at hand, but this is pretty common:

for(i = 0; i < count; i--);

Ten bonus points if you can spot the subtle bugs I put into this trivial for loop. Hint #1: there are three of them. Hint #2: the program (or kernel/firmware/driver) will not do anything useful. Beyond the obvious problems with this code (and how easy it is to accidentally slip in the extra semicolon), writing for loops gets really tedious and old sometimes.

So I keep thinking that it’d be neat to write a C library to implement Array map, select, reject. But then I start thinking about the code. To do this properly, you could use macros, something like

#define ARRAY_MAP(arr, size, func)                       \
        for(int i=0; i<(size); i++) (func)(arr[i]);
my_arr = malloc(sizeof(u32)*10);
memcpy(my_arr, arr1, sizeof(u32)*10);
ARRAY_MAP(my_arr, 10, do_stuff);

Well, that looks like junk and doesn’t really do much. You could implement it with callbacks to avoid the evils of macros, but that doesn’t help you much either. You still have to handle memory allocation, deallocation, type safety, and in the end the code doesn’t look any simpler.

Not to mention, for anything really high performance (filesystems, OSes, etc) you generally want to avoid looping over arrays in general – the Linux kernel now has a native hash table and circular buffer (among other fun data types). If performance is critical, use a better/faster/cooler algorithm and a more appropriate data type.

So I’m back to square one, array map in C is pointless. If you don’t care about runtime, just use arrays and loops, or use Python or Ruby.

But array map/select/reject is so cool… wouldn’t it be neat in C?

   printk(KERN_ERR "/me wants array_map in C");
   goto infinite_loop;



Categories: Uncategorized Tags: , , , ,

Three Things I Love About C

May 12, 2010 20 comments

Like many other coders out there, I am multilingual.

Well, I’m not really multilingual per se… I can speak English passably and I know enough Spanish to make a fool of myself. Obviously, I’m talking about programming languages.

In no particular order, I have (at one time or another) dabbled in Scheme, Pascal, QBasic,, C#, Prolog, Python, PHP, pl/SQL, Perl, Ruby, x86 Assembly, machine code, bash/shell, Java, GLSL, and C++, and C. And probably some others I’ve forgotten.

I like Ruby and Python a good deal but don’t spend much time using them, most of the code I write goes into filesystems or drivers – so not suprisingly, I’m a big fan of C.

Here are three of my favorite things about C, things that absolutely tickle me pink and make me love coding in C.

Inline Assembly

What other language lets you do this:

asm("int $3");

Or better yet,

asm("leal -4(%esp), %ecx");

Inline assembly into C programs gives incredible flexibility and power to the system designer. Of course, in the wrong hands, inline assembly can hose up the system and make software suck. But you can’t deny the raw awesome computing power afforded by being able to inject assembly directly.

The Preprocessor

From macros to textual replacement to conditional compilation, the C preprocessor let’s you do some neat things which I find both frustrating and amazing.

A few stupid examples:

#ifdef __KERNEL__
#define READ_REGISTER(addr) ioread32(addr)
#define READ_REGISTER(addr) call_other_func(addr)

This can be used to support multiple OSes and/or environments without incurring runtime penalties in a common, shared codebase.

#define MAGIC_NUMBER 5
#ifdef __KERNEL__
#define printf(...)   printk(KERN_ERR, __VA_ARGS__)
printf("%d", MAGIC_NUMBER);

Now to be fair, you can accomplish the same thing in other languages – you can define constants in place of magic numbers, and define your own debug printf which detects the environment and does something different based on OS or other factors. But typically other languages push this decision making process into runtime, impacting performance.

When it comes to macros, sure, you can do all kinds of stupid things – for example,

#define MIN(a, b) ((a) < (b) ? (a) : (b))
foo = MIN(var1, func1(args));

If the return value of func1 can vary between function invocations, for example it accesses a shared data structure – you just set yourself up for a big fat race condition that could take you days to hunt down. Good luck with that.

All things considered, the preprocessor provides power and flexibility I’ve often found missing in other languages.


Ok, obviously all the other languages out there have some concept of references or pointers… but C thrives in weird pointer math and pointer calculations. What other language lets you get away with code like

((unsigned char*)dword_pointer)[byte_offset] = byte;

Now at this point purists will usually be panicking and hyperventilating at the sheer craziness of such an attempt – why would ANYONE EVER want to commit such an act of sedition?!! Well, because sometimes you do. Maybe you have code that needs to iterate through an array a dword at a time, but this one function needs to change a specific byte. Heck if I know, point is this kind of flexibility rocks.

Another way this is manifest is in C’s handling of multi-dimensional arrays – or rather, C’s lack of handling multi-dimensional arrays.

int foo_array[5][10]
int bar_array[50];

foo_array[43] = 10;
bar_array[43] = 10;

Both statements above set element 43 (byte offset 172) to 10. C doesn’t complain, because all arrays are really just pointers to virtually contiguous blocks of memory.

For that matter, you can even do the following:

struct foo bar;
unsigned char * wacky_ptr = (unsigned char*)&bar;
*(wacky_ptr + 10) = 5;

Holy crap batman, what kind of blasphemy is going on here? I’m taking a pointer to a struct, typecasting it to a byte pointer, and setting byte 10 of the structure to 5. Why would anyone ever want to do that?!!

Who cares?

Point is, you can. And there are legitimate, actually useful reasons for wanting to do this. Sure, you can abuse this flexibility and write completely useless and unmaintainable code… but in the right hands, this type of flexibility works wonders.

And that really is the crux of the issue for me. C affords you all kinds of power and flexibility not present or possible in other languages. You want to inline assembly and muck around with processor registers? Sure, go ahead, whatever. You want to #define printf to be an infinite loop and confuse the heck out of your coworkers? Why the heck not, it’s your choice Mr. Programmer. You want to do crazy weird things with pointers? Be my guest!

The reality is, C seperates the men from the mice. Coders from posers. The flexibility C provides can be just enough rope to hang yourself – or in the right hands, it can be a powerful tool that creates amazing and beautiful software.

And that is what I love about C.

Next time tune in for what I hate about C 🙂



Categories: Uncategorized Tags: , ,