Saturday, April 10, 2010

A horrible exercise in implementation hiding

The following is pretty straightforward C99 code. Try to guess what it does.


#include "list.h"
#include <stdio.h>

int main(int argc, char* argv[]) {
struct list *l = list_new();
*(void**) list_append(l)= (void*) 0x00;
*(void**) list_append(l)= (void*) 0x01;
*(void**) list_append(l)= (void*) 0x02;
*(void**) list_append(l)= (void*) 0x03;
*(void**) list_append(l)= (void*) 0x04;

for(struct list_iterator* it = l->first;
it != l->last; it = (struct list_iterator *) it->next) {
printf("%p\n", *(void**) it);
}

return 0;
}


Looks and feels like a linked list being created and then iterated, right? Wrong. It is so much worse than that. As a horrible exercise in implementation hiding, this is an array list, and the iteration is done in a very devious way.

The list header looks like the following:


#ifndef LIST_H
#define LIST_H

struct list_iterator {
void *data;
void *next[];
};

struct list {
struct list_iterator *first;
struct list_iterator *last;
int allocated;
};

struct list *list_new();
struct list_iterator *list_append(struct list* list);

#endif


It still kinda looks linked-list-ish at a glance, but something is off about it.

A rough sketch of the implementation would look like this:


#include "list.h"
#include <stdlib.h>

struct list *list_new() {
struct list *l = malloc(sizeof(*l));
l->allocated = 2;
l->first = malloc(l->allocated * sizeof(struct list_iterator));
l->last = l->first;

return l;
}

struct list_iterator *list_append(struct list* list) {
if(list->last == list->first + list->allocated) {
list->allocated *= 2;
list->first = realloc(list->first, list->allocated * sizeof(void *));
list->last = list->first + list->allocated / 2;
}
return list->last++;
}


That was no linked list.

It's decidedly sneaky: struct list_iterator.next overlaps with the next element in the array through use of C99's flexible array members, giving the list a free next pointer without any extra memory usage at all.

This is proof of concept, and I don't suggest this should ever be used for anything other than scaring the elderly and small children.

Well, it isn't strictly speaking true implementation hiding, as you can see what's going on from the public interface in the header. But in lack of a better term...

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete