Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Self-referential structure in C

A `Group` structure links to subgroups of its own type. A depth-first search checks local values first and can report which group contains the first match.

Version: ISO C23; implementation support may vary

Syntax

typedef struct Group {
    const char *name;
    const int *values;
    size_t value_count;
    struct Group **subs;
} Group;

static int find_value(Group *group, int wanted, Group **out_group);

A self-referential structure uses a pointer to refer to an object of its own type. In typedef struct Group { ... } Group;, the tag Group is already visible after struct, but the type is incomplete until the closing }. A member struct Group child; is therefore invalid, while struct Group **subs; is valid. The tag and the typedef name occupy different namespaces; the alias introduced by this declaration is not yet available inside the braces.

subs is a pointer to a pointer, not an embedded array. In the example it points to the first element of a separate array of Group * pointers. The NULL macro is available from <stddef.h>: subs == NULL means there is no subgroup array, while the first NULL element in an existing array marks its end. A missing sentinel can lead to an out-of-bounds read. Local values, by contrast, are scanned using value_count. If value_count is nonzero, values must point to a sequence of at least value_count readable elements.

find_value performs depth-first search (DFS): it checks the current group's values first, then recursively searches subgroups in array order. It short-circuits at the first match and returns 1; a null group pointer or no match yields 0. Pass &found, where found has type Group *, to receive the matching group pointer via *out_group on success. Pass NULL if you only want the status. On a miss, the output variable is unchanged.

The groups and arrays are not copied and must stay alive for as long as they are used through pointers. This function assumes there are no cycles; track visited groups if cycles are possible. For very deep hierarchies, consider an explicit stack instead of recursion. The pattern needs no features introduced in C23; support for C23 mode depends on the implementation.

Examples

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

typedef struct Group {
    const char *name;
    const int *values;
    size_t value_count;
    struct Group **subs;
} Group;

static int find_value(Group *group, int wanted, Group **out_group)
{
    if (group == NULL)
        return 0;

    for (size_t i = 0; i < group->value_count; ++i) {
        if (group->values[i] == wanted) {
            if (out_group != NULL)
                *out_group = group;
            return 1;
        }
    }

    if (group->subs != NULL) {
        for (size_t i = 0; group->subs[i] != NULL; ++i) {
            if (find_value(group->subs[i], wanted, out_group))
                return 1;
        }
    }
    return 0;
}

int main(void)
{
    const int root_values[] = {7, 9};
    const int deep_values[] = {7, 42};
    const int right_values[] = {42};

    Group deep = {"deep", deep_values, 2, NULL};
    Group right = {"right", right_values, 1, NULL};
    Group *left_subs[] = {&deep, NULL};
    Group left = {"left", NULL, 0, left_subs};
    Group *root_subs[] = {&left, &right, NULL};
    Group root = {"root", root_values, 2, root_subs};
    Group *found = NULL;

    if (find_value(&root, 7, &found))
        printf("7: %s\n", found->name);
    if (find_value(&root, 42, &found))
        printf("42: %s\n", found->name);
    if (find_value(&root, 9, NULL))
        puts("9: found without output parameter");
    if (!find_value(&root, 99, &found))
        printf("99: not found; previous result: %s\n", found->name);

    return 0;
}

Result

7: root
42: deep
9: found without output parameter
99: not found; previous result: deep

`7` matches in `root` before any subgroup is searched. For `42`, the search descends through `left` to `deep` and stops at the match there, so `right`, the next subgroup of `root`, is never checked. The search for `9` requests no output pointer, and the miss for `99` leaves `found` pointing to `deep`.

Related lessons

  • C · Lesson 79 · Advanced · Version: 3

Sources