uintptr_t and intptr_t in C language

Question

while I was studying XOR linked list I run into a type called intptr_t/uintptr_t, I know that we can cast a pointer to this type and manipulate it as an integer with no problems, but what if we do have a variable int a (let's say hypothetically that its address is 100), does this line (int* x=(intptr_t)100) mean that x points on a? if not what does it do then ?

Thanks in advance.

Answer 1

The XOR linked list method is a hack to construct a linked list that can be navigated in both directions using the space for a single pointer. The trick is to store the XOR of addresses of the next and previous items in the link member, converting these addresses as uintptr_t (or intptr_t) values, to perform bitwise exclusive or on integers of the appropriate size and store this info as an integer:

struct item {
    uintptr_t link;
    int data; // item payload. Can be any number of members of any type
};

The list can be traversed in both directions, provided you know the address of the previous (or the next) item:

struct item *get_link(struct item *p, const struct item *previous) {
    return (struct item *)(p->link ^ (uintptr_t)previous);
}

To avoid a warning on alignement issues, you may need to add an extra cast as:

return (struct item *)(void *)(p->link ^ (uintptr_t)previous);

uintptr_t is an integer type that is specified as having the same size as void *, hence can contain all the information from any data pointer. Converting a data pointer to uintptr_t and back with casts should yield the same pointer.

intptr_t is the corresponding signed type, which is of little use per se.

The XOR linked list hack is mostly of historical interest today. The only advantage is a small size saving that is hardly worth the added complication. It is much better to use regular doubly linked lists if you need to scan the list in both directions. The scan with this trick requires keeping the pointer to both the current item an the previous one in the direction of traversal, whereas regular doubly linked lists can be handled with a single pointer, hence can be manipulated and/or shared in a much simpler fashion.

Here is a sample implementation:

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

struct item {
    uintptr_t link;
    int data; // item payload. Can be any number of members of any type
};

struct xor_list {
    struct item *head;
    struct item *tail;
};

struct item *get_link(struct item *ip, const struct item *previous) {
    return (struct item *)(ip->link ^ (uintptr_t)previous);
}

struct item *get_next(struct item *ip, struct item **previous) {
    struct item *next = get_link(ip, *previous);
    *previous = ip;
    return next;
}

uintptr_t make_link(struct item *prev, const struct item *next) {
    return (uintptr_t)prev ^ (uintptr_t)next;
}

struct item *add_item(struct xor_list *lp, int data) {
    struct item *ip = malloc(sizeof(*ip));
    if (ip) {
        struct item *tail = lp->tail;
        ip->data = data;
        if (tail) {
            struct item *prev = get_link(lp->tail, NULL);
            ip->link = make_link(tail, NULL);
            tail->link = make_link(prev, ip);
            lp->tail = ip;
        } else {
            ip->link = make_link(NULL, NULL);
            lp->head = lp->tail = ip;
        }
    }
    return ip;
}

int main() {
    struct xor_list list = { NULL, NULL };
    struct item *ip, *prev;

    add_item(&list, 1);
    add_item(&list, 2);
    add_item(&list, 3);
    add_item(&list, 4);
    add_item(&list, 5);

    printf("traversing from head to tail:");
    for (prev = NULL, ip = list.head; ip; ip = get_next(ip, &prev)) {
        printf(" %d", ip->data);
    }
    printf("\n");

    printf("traversing from tail to head:");
    for (prev = NULL, ip = list.tail; ip; ip = get_next(ip, &prev)) {
        printf(" %d", ip->data);
    }
    printf("\n");
    return 0;
}