Skip to content

Instantly share code, notes, and snippets.

@bodokaiser
Last active March 6, 2023 03:51
Show Gist options
  • Save bodokaiser/5657156 to your computer and use it in GitHub Desktop.
Save bodokaiser/5657156 to your computer and use it in GitHub Desktop.
Example of how to use libuv`s QUEUE.

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 info@bnoordhuis.nl

Copyright © 2013, Bodo Kaiser i@bodokaiser.io

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.

build:
$(CC) -o queue.o 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;
}
/* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
*
* 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_ */
@misakar
Copy link

misakar commented Feb 14, 2017

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

@maciej-barczak-red
Copy link

Thank you for that 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment