Skip to content

Instantly share code, notes, and snippets.

@cwchentw cwchentw/integer.c
Last active Feb 9, 2019

Embed
What would you like to do?
Generic Queue in Void Pointer (Apache 2.0)
#include <stdlib.h>
#include "integer.h"
struct _int {
int data;
};
Int* int_new(int n)
{
Int *i = malloc(sizeof(Int));
if (i == NULL) {
return i;
}
i->data = n;
return i;
}
void int_copy(void **dest, void *src)
{
*dest = malloc(sizeof(Int));
((Int *) (*dest))->data = int_value((Int *) src);
}
int int_value(Int *self)
{
return self->data;
}
void int_free(void *self)
{
if (!self) {
return;
}
free(self);
}
#ifndef INTEGER_H
#define INTEGER_H
typedef struct _int Int;
Int* int_new(int n);
int int_value(Int *self);
void int_copy(void **, void *);
void int_free(void *self);
#endif // INTEGER_H
#include <assert.h>
#include "integer.h" // Home-made `int`-wrapping box class.
#include "queue.h"
int main()
{
// Queue: NULL
Queue *queue = queue_new(int_copy, int_free);
Int *temp;
// Queue: 9 -> NULL
queue_push_front(queue, int_new(9));
temp = (Int *) queue_peek_front(queue);
assert(int_value(temp) == 9);
temp = (Int *) queue_peek_rear(queue);
assert(int_value(temp) == 9);
// Queue: 4 -> 9 -> NULL
queue_push_front(queue, int_new(4));
temp = (Int *) queue_peek_front(queue);
assert(int_value(temp) == 4);
temp = (Int *) queue_peek_rear(queue);
assert(int_value(temp) == 9);
// Queue: 4 -> 9 -> 5 -> NULL
queue_push_rear(queue, int_new(5));
temp = (Int *) queue_peek_front(queue);
assert(int_value(temp) == 4);
temp = (Int *) queue_peek_rear(queue);
assert(int_value(temp) == 5);
// Queue: 9 -> 5 -> NULL
temp = (Int *) queue_pop_front(queue);
assert(int_value(temp) == 4);
int_free(temp);
temp = (Int *) queue_peek_front(queue);
assert(int_value(temp) == 9);
temp = (Int *) queue_peek_rear(queue);
assert(int_value(temp) == 5);
// Queue: 9 -> NULL
temp = (Int *) queue_pop_rear(queue);
assert(int_value(temp) == 5);
int_free(temp);
temp = (Int *) queue_peek_front(queue);
assert(int_value(temp) == 9);
temp = (Int *) queue_peek_rear(queue);
assert(int_value(temp) == 9);
// Queue: NULL
temp = (Int *) queue_pop_rear(queue);
assert(int_value(temp) == 9);
int_free(temp);
queue_free(queue);
return 0;
}
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include "queue.h"
typedef struct node {
item_t data;
struct node *prev;
struct node *next;
} Node;
static Node* node_new(item_t data);
struct queue {
copyFn item_copy;
freeFn item_free;
Node *head;
Node *tail;
};
static Node* node_new(item_t data)
{
Node *node = malloc(sizeof(Node));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
Queue* queue_new(copyFn item_copy, freeFn item_free)
{
Queue *lt = malloc(sizeof(Queue));
lt->item_copy = item_copy;
lt->item_free = item_free;
lt->head = NULL;
lt->tail = NULL;
return lt;
}
bool queue_is_empty(Queue *self)
{
return self->head == NULL;
}
item_t queue_peek_front(Queue *self)
{
if (self->head == NULL) {
return NULL;
}
return self->head->data;
}
item_t queue_peek_rear(Queue *self)
{
if (self->head == NULL) {
return NULL;
}
return self->tail->data;
}
void queue_push_front(Queue *self, item_t data)
{
Node *node = node_new(data);
if (self->head == NULL) {
self->head = node;
self->tail = node;
return;
}
node->next = self->head;
self->head->prev = node;
self->head = node;
}
item_t queue_pop_front(Queue *self)
{
assert(!queue_is_empty(self));
if (self->head == self->tail) {
item_t popped;
self->item_copy(&popped, self->head->data);
self->item_free(self->head->data);
free(self->head);
self->head = NULL;
self->tail = NULL;
return popped;
}
Node *curr = self->head;
item_t popped;
self->item_copy(&popped, curr->data);
self->head = self->head->next;
self->item_free(curr->data);
free(curr);
return popped;
}
void queue_push_rear(Queue *self, item_t data)
{
Node *node = node_new(data);
if (self->tail == NULL) {
self->head = node;
self->tail = node;
return;
}
self->tail->next = node;
node->prev = self->tail;
self->tail = node;
}
item_t queue_pop_rear(Queue *self)
{
assert(!queue_is_empty(self));
if (self->head == self->tail) {
item_t popped;
self->item_copy(&popped, self->tail->data);
self->item_free(self->tail->data);
free(self->tail);
self->head = NULL;
self->tail = NULL;
return popped;
}
Node *curr = self->tail;
item_t popped;
self->item_copy(&popped, curr->data);
self->tail = self->tail->prev;
self->item_free(curr->data);
free(curr);
return popped;
}
void queue_free(void *self)
{
if (self == NULL) {
return;
}
freeFn fn = ((Queue *) self)->item_free;
Node *curr = ((Queue *) self)->head;
Node *temp = NULL;
while (curr != NULL) {
temp = curr;
curr = curr->next;
(*fn)(temp->data);
free(temp);
}
free(self);
}
#ifndef GENERIC_LIST_H
#define GENERIC_LIST_H
#include <stdbool.h>
typedef void * item_t;
typedef void (*copyFn) (void **, void *);
typedef void (*freeFn) (void *);
typedef struct queue Queue;
Queue* queue_new(copyFn, freeFn);
bool queue_is_empty(Queue *self);
item_t queue_peek_front(Queue *self);
item_t queue_peek_rear(Queue *self);
void queue_push_front(Queue *self, item_t data);
item_t queue_pop_front(Queue *self);
void queue_push_rear(Queue *self, item_t data);
item_t queue_pop_rear(Queue *self);
void queue_free(void *self);
#endif // GENERIC_LIST_H
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.