Last active
June 17, 2024 10:48
-
-
Save rlapz/b343370619bd1f111e459886233f890a to your computer and use it in GitHub Desktop.
queue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
typedef void (*Func) (void *udata); | |
typedef struct node { | |
Func func; | |
void *udata; | |
struct node *next; | |
} Node; | |
typedef struct { | |
size_t len; | |
size_t cap; | |
size_t max_cap; | |
Node *first; | |
Node *last; | |
Node *resv; /* reserved nodes: avoid unnecessary malloc (reuse) */ | |
} CList; | |
static int clist_init(CList *c, size_t init_size, size_t max_cap); | |
static void clist_deinit(CList *c); | |
static int clist_queue(CList *c, Func func, void *udata); | |
/* Don't free() the returned node */ | |
static Node *clist_dequeue(CList *c); | |
/* resv list */ | |
static void _clist_append(CList *c, Node *new_node); | |
static Node *_clist_pop(CList *c); | |
static void _clist_destroy(CList *c); | |
static int | |
clist_init(CList *c, size_t init_size, size_t max_cap) | |
{ | |
c->resv = NULL; | |
for (size_t i = 0; i < init_size; i++) { | |
Node *const node = malloc(sizeof(Node)); | |
if (node == NULL) { | |
_clist_destroy(c); | |
return -1; | |
} | |
_clist_append(c, node); | |
} | |
c->len = 0; | |
c->cap = init_size; | |
c->max_cap = max_cap; | |
c->first = NULL; | |
c->last = NULL; | |
return 0; | |
} | |
static void | |
clist_deinit(CList *c) | |
{ | |
Node *node; | |
while ((node = clist_dequeue(c)) != NULL); | |
_clist_destroy(c); | |
c->first = NULL; | |
c->last = NULL; | |
} | |
static int | |
clist_queue(CList *c, Func func, void *udata) | |
{ | |
Node *new_node = _clist_pop(c); | |
if (new_node == NULL) { | |
if (c->cap >= c->max_cap) | |
return -1; | |
new_node = malloc(sizeof(Node)); | |
if (new_node == NULL) | |
return -1; | |
printf("need alloc\n"); | |
c->cap++; | |
} | |
if (c->last == NULL) | |
c->first = new_node; | |
else | |
c->last->next = new_node; | |
new_node->func = func; | |
new_node->udata = udata; | |
new_node->next = NULL; | |
c->last = new_node; | |
c->len++; | |
return 0; | |
} | |
static Node * | |
clist_dequeue(CList *c) | |
{ | |
Node *const ret = c->first; | |
if ((ret == NULL) || (c->len == 0)) | |
return NULL; | |
c->first = ret->next; | |
if (c->first == NULL) | |
c->last = NULL; | |
_clist_append(c, ret); | |
c->len--; | |
return ret; | |
} | |
static void | |
_clist_append(CList *c, Node *new_node) | |
{ | |
new_node->next = c->resv; | |
c->resv = new_node; | |
} | |
static Node * | |
_clist_pop(CList *c) | |
{ | |
Node *const ret = c->resv; | |
if (ret != NULL) | |
c->resv = ret->next; | |
return ret; | |
} | |
static void | |
_clist_destroy(CList *c) | |
{ | |
Node *node; | |
while ((node = _clist_pop(c)) != NULL) | |
free(node); | |
c->resv = NULL; | |
} | |
// test | |
static void | |
func(void *v) | |
{ | |
printf("%p: %d\n", v, *((int *)v)); | |
} | |
static void | |
test0(void) | |
{ | |
CList list; | |
if (clist_init(&list, 1, 100) < 0) | |
return; | |
int arr[10]; | |
for (int i = 0; i < 10; i++) | |
arr[i] = i; | |
for (int i = 0; i < 10; i ++) | |
clist_queue(&list, func, &arr[i]); | |
Node *n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
n->func = NULL; | |
n->udata = NULL; | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
for (int i = 0; i < 5; i ++) | |
clist_queue(&list, func, &arr[i]); | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
n = clist_dequeue(&list); | |
if (n != NULL) | |
n->func(n->udata); | |
printf("len: %zu, cap: %zu, max: %zu\n", list.len, list.cap, list.max_cap); | |
clist_deinit(&list); | |
} | |
int | |
main(void) | |
{ | |
test0(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment