Skip to content

Instantly share code, notes, and snippets.

@ArnonEilat
Last active December 2, 2021 00:02
Show Gist options
  • Save ArnonEilat/4471278 to your computer and use it in GitHub Desktop.
Save ArnonEilat/4471278 to your computer and use it in GitHub Desktop.
Simple C implementation of queue. Usage example included.
#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
/* a link in the queue, holds the info and point to the next Node*/
typedef struct {
int info;
} DATA;
typedef struct Node_t {
DATA data;
struct Node_t *prev;
} NODE;
/* the HEAD of the Queue, hold the amount of node's that are in the queue*/
typedef struct Queue {
NODE *head;
NODE *tail;
int size;
int limit;
} Queue;
Queue *ConstructQueue(int limit);
void DestructQueue(Queue *queue);
int Enqueue(Queue *pQueue, NODE *item);
NODE *Dequeue(Queue *pQueue);
int isEmpty(Queue* pQueue);
Queue *ConstructQueue(int limit) {
Queue *queue = (Queue*) malloc(sizeof (Queue));
if (queue == NULL) {
return NULL;
}
if (limit <= 0) {
limit = 65535;
}
queue->limit = limit;
queue->size = 0;
queue->head = NULL;
queue->tail = NULL;
return queue;
}
void DestructQueue(Queue *queue) {
NODE *pN;
while (!isEmpty(queue)) {
pN = Dequeue(queue);
free(pN);
}
free(queue);
}
int Enqueue(Queue *pQueue, NODE *item) {
/* Bad parameter */
if ((pQueue == NULL) || (item == NULL)) {
return FALSE;
}
// if(pQueue->limit != 0)
if (pQueue->size >= pQueue->limit) {
return FALSE;
}
/*the queue is empty*/
item->prev = NULL;
if (pQueue->size == 0) {
pQueue->head = item;
pQueue->tail = item;
} else {
/*adding item to the end of the queue*/
pQueue->tail->prev = item;
pQueue->tail = item;
}
pQueue->size++;
return TRUE;
}
NODE * Dequeue(Queue *pQueue) {
/*the queue is empty or bad param*/
NODE *item;
if (isEmpty(pQueue))
return NULL;
item = pQueue->head;
pQueue->head = (pQueue->head)->prev;
pQueue->size--;
return item;
}
int isEmpty(Queue* pQueue) {
if (pQueue == NULL) {
return FALSE;
}
if (pQueue->size == 0) {
return TRUE;
} else {
return FALSE;
}
}
int main() {
int i;
Queue *pQ = ConstructQueue(7);
NODE *pN;
for (i = 0; i < 9; i++) {
pN = (NODE*) malloc(sizeof (NODE));
pN->data.info = 100 + i;
Enqueue(pQ, pN);
}
while (!isEmpty(pQ)) {
pN = Dequeue(pQ);
printf("\nDequeued: %d", pN->data);
free(pN);
}
DestructQueue(pQ);
return (EXIT_SUCCESS);
}
@Martinfx
Copy link

Martinfx commented Sep 12, 2017

Hi you have maybe memory leak.


Dequeued: 100
Dequeued: 101
Dequeued: 102
Dequeued: 103
Dequeued: 104
Dequeued: 105
Dequeued: 106==2070== 
==2070== HEAP SUMMARY:
==2070==     in use at exit: 4,128 bytes in 3 blocks
==2070==   total heap usage: 11 allocs, 8 frees, 4,264 bytes allocated
==2070== 
==2070== LEAK SUMMARY:
==2070==    definitely lost: 32 bytes in 2 blocks
==2070==    indirectly lost: 0 bytes in 0 blocks
==2070==      possibly lost: 0 bytes in 0 blocks
==2070==    still reachable: 4,096 bytes in 1 blocks
==2070==         suppressed: 0 bytes in 0 blocks
==2070== Rerun with --leak-check=full to see details of leaked memory
==2070== 
==2070== For counts of detected and suppressed errors, rerun with: -v
==2070== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

@reup97
Copy link

reup97 commented Apr 25, 2018

Inside the main function, the queue limit is set to 7, but you are attempting to add 9 nodes into it.

...
Queue *pQ = ConstructQueue(7);
    NODE *pN;

    for (i = 0; i < 9; i++) {
        pN = (NODE*) malloc(sizeof (NODE));
...

The exceeded nodes are not freed, hence results in the memory leak as @Martinfx mentioned.

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