Example of how to use libuv`s QUEUE.

README.md

libuv

QUEUE

Circularly linked list libuv uses to store requests, handles and other dynamic stuff.

Installation

To execute just download all files and enter make && ./queue.c into command line. There are no additional dependencies required.

Documentation

The main idea of a circularly linked list is to have an array of two void* pointers:

void* QUEUE[2];

The first item (q[0]) of an QUEUE instance points to the previous node. The first item (q[1]) of an QUEUE instance points to the next node or if it is the last node in the whole QUEUE chain it will point again to the first node (so the chain is closed).

All struct instances we now want to insert into such a QUEUE now must have itself a property of type QUEUE. This property will act as node in the queue chain. If we want to receive our struct instance back the QUEUE macro QUEUE_DATA will return a calculated memory address of the struct belonging to the selected QUEUE node. Through this we then can access the properties of our origin struct.

License

Copyright © 2013, Ben Noordhuis [email protected]

Copyright © 2013, Bodo Kaiser [email protected]

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

Makefile

build:
  $(CC) -o queue.o queue.c

queue.c

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

/**
 * A pointer to a list node.
 */
static QUEUE* q;

/**
 * Our circulary list.
 */
static QUEUE queue;

/**
 * Our item struct we want to store in queue.
 */
struct user_s {
    int age;
    char* name;

    QUEUE node;
};

int main() {
    /**
     * This will be our user pointer.
     * It will point to the user we received from the queue.
     */
    struct user_s* user;

    /**
     * John is 44.
     */
    struct user_s john;
    john.name = "john";
    john.age = 44;


    /**
     * Henry is 32.
     */
    struct user_s henry;
    henry.name = "henry";
    henry.age = 32;
    
    /**
     * Willy is 99.
     */
    struct user_s willy;   
    willy.name = "willy";
    willy.age = 99;

    /**
     * Initialize the queue of each user.
     */
    QUEUE_INIT(&queue);
    QUEUE_INIT(&john.node);
    QUEUE_INIT(&henry.node);
    QUEUE_INIT(&willy.node);

    /**
     * Lets insert each user to the tail of the list.
     */
    QUEUE_INSERT_TAIL(&queue, &john.node);
    QUEUE_INSERT_TAIL(&queue, &henry.node);
    QUEUE_INSERT_TAIL(&queue, &willy.node);

    /**
     * Retrieve a pointer to our first user john.
     */
    q = QUEUE_HEAD(&queue);

    /**
     * Should retrieve the user behind the "q" pointer.
     */
    user = QUEUE_DATA(q, struct user_s, node);

    /**
     * Should output the name of john.
     */
    printf("Received first inserted user: %s who is %d.\n", 
            user->name, user->age);

    /**
     * Now lets remove john from the queue.
     */
    QUEUE_REMOVE(q);

    /**
     * Lets output the other two users through a for each loop.
     */
    QUEUE_FOREACH(q, &queue) {
        user = QUEUE_DATA(q, struct user_s, node);

        printf("Received rest inserted users: %s who is %d.\n",
            user->name, user->age);    
    }

    return 0;
}

queue.h

/* Copyright (c) 2013, Ben Noordhuis <[email protected]>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef QUEUE_H_
#define QUEUE_H_

typedef void *QUEUE[2];

/* Private macros. */
#define QUEUE_NEXT(q)       ((*(q))[0])
#define QUEUE_PREV(q)       ((*(q))[1])
#define QUEUE_PREV_NEXT(q)  (QUEUE_NEXT((QUEUE *) QUEUE_PREV(q)))
#define QUEUE_NEXT_PREV(q)  (QUEUE_PREV((QUEUE *) QUEUE_NEXT(q)))

/* Public macros. */
#define QUEUE_DATA(ptr, type, field)                                          \
  ((type *) ((char *) (ptr) - ((long) &((type *) 0)->field)))

#define QUEUE_FOREACH(q, h)                                                   \
  for ((q) = (*(h))[0]; (q) != (h); (q) = (*(q))[0])

#define QUEUE_EMPTY(q)                                                        \
  (QUEUE_NEXT(q) == (q))

#define QUEUE_HEAD(q)                                                         \
  (QUEUE_NEXT(q))

#define QUEUE_INIT(q)                                                         \
  do {                                                                        \
    QUEUE_NEXT(q) = (q);                                                      \
    QUEUE_PREV(q) = (q);                                                      \
  }                                                                           \
  while (0)

#define QUEUE_ADD(h, n)                                                       \
  do {                                                                        \
    QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n);                                       \
    QUEUE_NEXT_PREV(n) = QUEUE_PREV(h);                                       \
    QUEUE_PREV(h) = QUEUE_PREV(n);                                            \
    QUEUE_PREV_NEXT(h) = (h);                                                 \
  }                                                                           \
  while (0)

#define QUEUE_SPLIT(h, q, n)                                                  \
  do {                                                                        \
    QUEUE_PREV(n) = QUEUE_PREV(h);                                            \
    QUEUE_PREV_NEXT(n) = (n);                                                 \
    QUEUE_NEXT(n) = (q);                                                      \
    QUEUE_PREV(h) = QUEUE_PREV(q);                                            \
    QUEUE_PREV_NEXT(h) = (h);                                                 \
    QUEUE_PREV(q) = (n);                                                      \
  }                                                                           \
  while (0)

#define QUEUE_INSERT_HEAD(h, q)                                               \
  do {                                                                        \
    QUEUE_NEXT(q) = QUEUE_NEXT(h);                                            \
    QUEUE_PREV(q) = (h);                                                      \
    QUEUE_NEXT_PREV(q) = (q);                                                 \
    QUEUE_NEXT(h) = (q);                                                      \
  }                                                                           \
  while (0)

#define QUEUE_INSERT_TAIL(h, q)                                               \
  do {                                                                        \
    QUEUE_NEXT(q) = (h);                                                      \
    QUEUE_PREV(q) = QUEUE_PREV(h);                                            \
    QUEUE_PREV_NEXT(q) = (q);                                                 \
    QUEUE_PREV(h) = (q);                                                      \
  }                                                                           \
  while (0)

#define QUEUE_REMOVE(q)                                                       \
  do {                                                                        \
    QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q);                                       \
    QUEUE_NEXT_PREV(q) = QUEUE_PREV(q);                                       \
  }                                                                           \
  while (0)

#endif /* QUEUE_H_ */

thanks for excellent examples!╰(°▽°)╯

Thank you for that 👍