1e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly/*-------------------------------------------------------------------------- 2dd5743ee305c8db17facba3e0176a3d07adc7499Rom LemarchandCopyright (c) 2010-2011, Code Aurora Forum. All rights reserved. 3e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 4e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyRedistribution and use in source and binary forms, with or without 5e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellymodification, are permitted provided that the following conditions are met: 6e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly * Redistributions of source code must retain the above copyright 7e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly notice, this list of conditions and the following disclaimer. 8e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly * Redistributions in binary form must reproduce the above copyright 9e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly notice, this list of conditions and the following disclaimer in the 10e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly documentation and/or other materials provided with the distribution. 11dd5743ee305c8db17facba3e0176a3d07adc7499Rom Lemarchand * Neither the name of Code Aurora nor 12e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly the names of its contributors may be used to endorse or promote 13e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly products derived from this software without specific prior written 14e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly permission. 15e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 16e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyAND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyIMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 19e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyNON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 20e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyCONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 21e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyEXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 22e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyPROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 23e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyOR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 24e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyWHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 25e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyOTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 26e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly--------------------------------------------------------------------------*/ 28e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly/* 29e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Queue with Linked list 30e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly*/ 31e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 32e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include "queue.h" 33e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include <stdio.h> 34e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include <stdlib.h> 35e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 36e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 37e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellytypedef struct Node 38e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 39e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly void *element; 40e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly struct Node *next; 41e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} Node; 42e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 43e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellystruct Queue 44e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 45e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Node *head; 46e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Node *tail; 47e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly int current_size; 48e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly}; 49e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 50e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyQueue *alloc_queue() 51e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 52e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Queue *q = (Queue *) malloc(sizeof(Queue)); 53e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (q) 54e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 55e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->head = q->tail = NULL; 56e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->current_size = 0; 57e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 58e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly return q; 59e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 60e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 61e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid free_queue(Queue *q) 62e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 63e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly while (q->current_size) 64e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 65e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly pop(q); 66e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 67e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 68e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 69e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid free_queue_and_qelement(Queue *q) 70e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 71e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly while (q->current_size) 72e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 73e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly void *element = pop(q); 74e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (element) 75e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly free(element); 76e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 77e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 78e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 79e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyint push(Queue *q, void * element) 80e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 81e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Node *new_node = (Node *) malloc(sizeof(Node)); 82e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 83e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (new_node == NULL) 84e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly return -1; 85e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 86e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly new_node->element = element; 87e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly new_node->next = NULL; 88e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 89e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (q->current_size == 0) 90e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 91e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->head = new_node; 92e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 93e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly else 94e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 95e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->tail->next = new_node; 96e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 97e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 98e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->tail = new_node; 99e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->current_size++; 100e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 101e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly return 0; 102e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 103e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 104e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid *pop(Queue *q) 105e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 106e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly Node *temp; 107e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly void *element; 108e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 109e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (q->current_size == 0) 110e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly return NULL; 111e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 112e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly temp = q->head; 113e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly element = temp->element; 114e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 115e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly if (q->current_size == 1) 116e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 117e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->head = q->tail = NULL; 118e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 119e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly else 120e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly { 121e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->head = q->head->next; 122e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly } 123e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 124e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly free(temp); 125e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly q->current_size--; 126e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly return element; 127e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 128e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 129