Iterating through structs: a programming exercise

[MrAureliusR]

Hey everyone. This whole topic came about because of a piece of software I was writing to bit-bang the Dallas One-Wire protocol with a standard DS18B20 temperature sensor. Because of the project, it made sense to store all the data around the sensor in a struct, so in the code we start with something like this:

Code: [Select]

...
typedef struct sensor {
     int regA;
     int regB;
     int regC;
     int regD;
} sensor_t;
...

I like organizing things like this into structs. It (usually) makes sense to declare it as a type, especially if you have multiple sensors that are the same. The problem I ran into is that in C there is no way to iterate through a struct. That is, there is no way to 'move' through the members of a struct the same way you can iterate through members of an array.
There are two different solutions for this. The first is a bit of a 'hack', and the second is a bit more elegant. They will both work, but the choice is up to you. I post this here because this problem nagged at me for a while until I finally figured out a good way to do it

So, here's the sort of 'hacked together' method:

Code: [Select]

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

typedef struct test { // this method would work for non-type structs as well
int a;
int b;
int c;
int d;
int e;
int f;
} test_t;

test_t iter, *pIter = &iter;
int *temp; // this is used to iterate through the struct
int main(void) {
pIter->a = 15; // set all the members to some value
pIter->b = 16;
pIter->c = 17;
pIter->d = 18;
pIter->e = 19;
pIter->f = 20;
printf("Testing, \n %d \n %d \n %d \n %d \n %d \n %d \n", pIter->a, pIter->b, pIter->c, pIter->d, pIter->e, pIter->f);
int j;
temp = &iter.a; // point the int pointer to the first int inside the struct
for(j=0; j < 6; j++) {
*temp = j; // set the new values of the struct (this can be done many ways)
temp++; // increase the address to the next value ** see below comments
}
printf("Second go, \n %d \n %d \n %d \n %d \n %d \n %d \n", pIter->a, pIter->b, pIter->c, pIter->d, pIter->e, pIter->f);

return 0;
}

/*
 * ** the temp++ line works because C pointer math will automatically increment the pointer
 *    by the correct size to move it to the next item. This is a function typically used
 *    for iterating through arrays, but it works here ONLY if your struct members are all
 *    the same size.
 *    Interestingly, setting a variable to sizeof(int) and adding this to the j variable
 *    results in a bizarre, different result. This is probably because of the way the C
 *    compiler is placing things in memory?
 */
This does work, but is not particularly good use of pointers and pointer arithmetic. The above example shows why C is not a particularly 'type-safe' and memory safe language -- it certainly does give you power though!! GCC does not complain about the above code, though. (Maybe it would with -Wall, I didn't try that with this example though.)

Here is the more elegant method, which has the advantage of being able to iterate through the registers, but also call them by name when needed (the advantage of a struct!).

Code: [Select]

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

#define REGS 10

typedef struct test {
int a[REGS];
int other_data;
int more_stuff;
} test_t;

enum {
registerA = 0x00,
registerB = 0x01,
registerC = 0x02,
registerD = 0x03,
registerE = 0x04
//etc
};

test_t iter, *pIter = &iter;

int main(void) {
int i, j;
pIter->a[registerA] = 15; // set all the members to some value
pIter->a[registerB] = 16;
pIter->a[registerC] = 17;
pIter->a[registerD] = 18;
pIter->a[registerE] = 19;

printf("Testing, \n");
for(i = 0; i < 5; i++) {
printf("%d \n", pIter->a[i]); // now we can iterate to print their values, as well!
}

for(j=0; j < 5; j++) {
pIter->a[j] = j; // set the new values of the struct (this can be done many ways)
}

printf("Second go, \n");
for(i = 0; i < 5; i++) {
printf("%d \n", pIter->a[i]); // now we can iterate to print their values, as well!
}
return 0;
}

Up to the first time I wrote this, I hadn't used enums much. I used to use #define for constants -- but I've heard from many sources (and it makes sense) to either use const int or an enum, as this enables the compiler to check what you're doing and look for type errors, etc, whereas #defines (which are part of the preprocessor) simply replaces verbatim whatever value you define.

In this second version, if the other chip's registers aren't in a nice linear order, you can simply create a second array with the register addresses for each register in the appropriate place (which pertains to the correct register name in the enum). This way you can iterate through the register data in the struct while also iterating through all the addresses of each register (useful if you're sending the register address before reading/writing the remote register).

I was pretty proud of this nifty little solution! The reason I posted this today is I just ran into the same problem using the Bosch BMP180 pressure sensor. In order to calculate the pressure you have to read a whole bunch of calibration constants and then use them in a bunch of equations. I wanted to put all the calibration registers into a struct, but then when I got to the part where I read them I realized it would be so much easier if I could just iterate through them in a for loop -- and then I remembered I'd solved this problem before!

There's a good chance that there is someone else out there who did a similar version before, so I'm not by any means claiming I invented this technique -- I just wanted to share it with everyone!

Hope it helps you out! If you have other methods or other interesting coding techniques, please share them as well!

[hamster_nz]

Hi MrAureliusR,

Although it is a perfectly workable solution, somehow using the value of the enum sits oddly with me. I tend to treat them as being valueless. Just my hangup I guess

Here's how I would do it - I would use a union:

Code: [Select]

typedef union {
   struct { // this method would work for non-type structs as well
        int a;
        int b;
        int c;
        int d;
        int e;
        int f;
   } item;
   int items[1];  // Size of this array doesn't matter.
} test_t;

test_t iter;
int main(void) {
        test_t *pIter = &iter;
        int j;
        pIter->item.a = 15; // set all the members to some value
        pIter->item.b = 16;
        pIter->item.c = 17;
        pIter->item.d = 18;
        pIter->item.e = 19;
        pIter->item.f = 20;
        printf("Testing, \n %d \n %d \n %d \n %d \n %d \n %d \n",
              pIter->item.a, pIter->item.b, pIter->item.c, pIter->item.d, pIter->item.e, pIter->item.f);

        for(j=0; j < sizeof(test_t)/sizeof(int); j++) {
              pIter->items[j] = j;
        }
        printf("Second go, \n %d \n %d \n %d \n %d \n %d \n %d \n",
        pIter->item.a, pIter->item.b, pIter->item.c, pIter->item.d, pIter->item.e, pIter->item.f);

        return 0;
}

However, if it was a once-off for initialization of the structure and memset() wasn't able to cut it,  I just go with something like this:

Code: [Select]

        for(j=0; j < sizeof(test_t)/sizeof(int); j++) {
              ((int *)pIter)[j] = j;
        }


[FreddyVictor]

a tweak to your (MrAureliusR's) code:

Code: [Select]

tyepdef enum {
registerA = 0x00,
registerB = 0x01,
registerC = 0x02,
registerD = 0x03,
registerE = 0x04,
//etc
Register_COUNT
} Sensor_Register_t;

typedef struct test {
int a[Register_COUNT];
int other_data;
int more_stuff;
} test_t;

// then you can do things like:

void SensorRegGet( Sensor_Register_t reg );

for(i = 0; i < Register_COUNT; i++) {
printf("%d \n", pIter->a[i]); // now we can iterate to print their values, as well!
}


[Howardlong]

I may have misunderstood, but for this I'd do a union of a struct and array.

I would define the struct outside of the union, but that's my style, and then include it with the array in a union...

typedef struct
{
  int n1;
  int n2;
  ...
  int n6;
} MYSTRUCT;

typedef union
{
  MYSTRUCT ms;
  int an[6];
} MYUNION;

[MrAureliusR]

Why would you use a union? To my understanding a union can only hold one of the values at a time. If you wanted to hold all those values simultaneously I don't think that would work... or would it, because the struct is a member of the union? I don't see the advantage there at all. Correct me if I'm wrong?

a tweak to your (MrAureliusR's) code:

Code: [Select]

tyepdef enum {
registerA = 0x00,
registerB = 0x01,
registerC = 0x02,
registerD = 0x03,
registerE = 0x04,
//etc
Register_COUNT
} Sensor_Register_t;

typedef struct test {
int a[Register_COUNT];
int other_data;
int more_stuff;
} test_t;

// then you can do things like:

void SensorRegGet( Sensor_Register_t reg );

for(i = 0; i < Register_COUNT; i++) {
printf("%d \n", pIter->a[i]); // now we can iterate to print their values, as well!
}


Nice, if I understand that correctly, by adding the final value to the enum, it gets assigned the total number of members of the enum? Is that a compiler feature or a C language feature? I hadn't seen that before.
What's the advantage to typedef'ing the enum? Using a 'nameless' enum was, I read, a better way to declare constants than using #defines.

[IanB]

A union would generally be the first way that comes to mind. A union in C overlays two different data structures on the same memory. So you can refer to the same memory contents in different ways according to need.

In this particular case you would declare the named registers as you did and then overlay an array on top of them. When you want to iterate you use the array and when you want named access you use the named registers.

As for adding one more item to the list of enums this is part of the C language too. The next enum will be assigned the value of the previous enum plus one.

[Howardlong]

As I say, I may have misunderstood, but taking the middle code version out of the OP, a union of a struct and array would achieve exactly what was being shown, so you can reference either as individual struct elements or as an indexed item in an array, or indeed, by setting a pointer to the first element of the array, use pointer arithmetic to address the elements.

So in my example, ms.n1 is an alias of an[0], ms.n2 is an alias of an[1] etc.

Do you know how hard it is to write C code on an iPad!?!? Grrr.

[hamster_nz]

Why would you use a union?

I think of unions as indicating "this data structure can be viewed in multiple ways, and here are different viewpoints" - in this case either a strcture containing a set of named integers or an array of integers.

Using a 'nameless' enum was, I read, a better way to declare constants than using #defines.

Possibly yes, as you can leverage the compiler type-checking to help check your code's logic.

I tend to use enums only when the value assigned does not really matter - if you have to explicitly the values then I feel you are 'taking advantage' of the enum to hold actual data, rather then it just being a set of named values.

So I tend to only use enums when data involved has no persistence outside of current instance of the program. If the value assigned to the enum variable ends up stored on disk, or passed to another program over a network then using an integer data type and #defines is the better way.

The difference in key strokes required to code either way is actually minimal...

[IanB]

I tend to use enums only when the value assigned does not really matter - if you have to explicitly the values then I feel you are 'taking advantage' of the enum to hold actual data, rather then it just being a set of named values.

Enumerations are a very acceptable way to define named integer constants in C, for array offsets and other purposes.

[Maxlor]

Using unions in the way described is a good solution. Be careful with structs though, the memory layout doesn't have to be exactly what you wrote, the compiler is given some leeway to insert padding as it sees fit to preserve alignment. Also, the way padding is added changes between platforms, so code might turn out to be nonportable.

Example:

Code: [Select]

#include <stdlib.h>
#include <stdio.h>

struct test {
        char a;
        short b;
        short c;
        int d;
};

int main() {
        struct test t;
        printf("offset of a: %ld\n", (long)&t.a - (long)&t);
        printf("offset of b: %ld\n", (long)&t.b - (long)&t);
        printf("offset of c: %ld\n", (long)&t.c - (long)&t);
        printf("offset of d: %ld\n", (long)&t.d - (long)&t);
        return 0;
}Will print:
offset of a: 0
offset of b: 2
offset of c: 4
offset of d: 8

So the memory layout looks like this, with the _ characters showing padding bytes inserted by the compiler to keep variables aligned: |a _ b b | c c _ _ | d d d d | . If you overlay this struct onto raw memory or try to use pointer arithmetic, you might get unexpected results because of those padding bytes.

The way around this is to use #pragma pack(push, 1) before the struct definition and #pragma pack(pop) after it, which sets the alignment size to 1 thus disabling padding. After adding those two lines to the code, the output is:
offset of a: 0
offset of b: 1
offset of c: 3
offset of d: 5

My recommendation: when using unions to overlay structs and raw memory (e.g. a char array), always set alignment to 1 using #pragma pack and handle any padding you need yourself by explicitly adding padding struct members.

[rs20]

Some platforms can't handle misaligned ints, for example AVR32. Using #pragma pack 1 would make that field unuseable in your example on that platform.

[dannyf]

the memory layout doesn't have to be exactly what you wrote

Absolutely true and incredibly dangerous on those platforms, like many 32-bit chips.

[nctnico]

I agree. Don't overlay structs onto data in memory like packets received from some interface. As a rule of thumb: if you need a pragma to make your code work then your code is mediocre.

Besides that: iterating through structs is much easier with the storage containers like vector, list, etc from the STL library which comes with C++.

[Jeroen3]

If you insist in iterating through the elements, you can create an address reference table.
const unsigned type_x_iterator[] = { offsetoff(type_x.elementA), offsetoff(type_x.elementB).... };

Iterating will be done by:
void *p = &struct_x + type_x_iterator[j];

You'll need to find some way to know the type you are pointing to, and you should be very cautious of alignment limitations. Or only use the same type width.
This might be one of those times when it is safer to unroll your loop.

[Mechatrommer]

Code: [Select]

...
typedef struct test { // this method would work for non-type structs as well
int a;
int b;
int c;
int d;
int e;
int f;
} test_t;
...
[bold]
temp = &iter.a; // point the int pointer to the first int inside the struct
[/bold]
for(j=0; j < 6; j++) {
*temp = j; // set the new values of the struct (this can be done many ways)
temp++; // increase the address to the next value ** see below comments
}
}


dont make it the habit the bolded one. next month or next year you decide to move member "a" precedence to the bottom of the other members, you'll have buffer overrun problem. its not so obvious in the above very simple code since they fit in a window... suggestion if you have to use pointer is temp = (int*)(&iter) ... i know type casting is not safe, so... ymmv.

[Howardlong]

To be fair, it depends on the context. You could go to nth degree of anality if you wanted, but IMHO of you're not careful, you're likely to make your code less readable and obfuscate what you're doing.

If ints are the struct elements and the array elements, as in this example, then it's a pretty safe assumption that a union will work perfectly well.

Agreed regarding the caution of using of #pragma pack() at times, both in that you threaten portability and need an understanding of both the compiler and the target processor, but sometimes there is a reality check that needs to be made. After all, it might make a significant difference to your BOM cost. Equally on some architectures it results in a bus exception when accessing non-word aligned bytes. And any programmer worth his or her salt should be comfortable with that.

The exact same applies to splitting out packed byte items from int16_t or int32_t in that you need to be aware of endianness.

What I don't agree with is to sit in an ivory tower and discount options because you have some kind of religious fervour about something: sometimes you need to compromise, there are almost certainly some other rather more fundamental battles that deserve your attention.

[westfw]

All things considered, I'd go the other way and use macros when I wasn't iterating:

Code: [Select]

typedef struct test {
int a[Register_COUNT];
int other_data;
int more_stuff;
} test_t;
#define rega (test.a[0])
#define regb (test.a[1])
;; etc
This does require its own areas of care, of course.