1e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly/*-------------------------------------------------------------------------- 261a2c6a19dbd06a317a419623020e02056661876Praveen ChavanCopyright (c) 2010-2011, 2013, The Linux Foundation. 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. 116eec4d1ea65df853450a6e158718981cba900bf6Shashank Mittal * Neither the name of The Linux Foundation 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/* 2961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Queue with Linked list 3061a2c6a19dbd06a317a419623020e02056661876Praveen Chavan */ 31e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 32e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include "queue.h" 33e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include <stdio.h> 34e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly#include <stdlib.h> 35e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 36e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 3761a2c6a19dbd06a317a419623020e02056661876Praveen Chavantypedef struct Node { 3861a2c6a19dbd06a317a419623020e02056661876Praveen Chavan void *element; 3961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan struct Node *next; 40e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} Node; 41e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 4261a2c6a19dbd06a317a419623020e02056661876Praveen Chavanstruct Queue { 4361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Node *head; 4461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Node *tail; 4561a2c6a19dbd06a317a419623020e02056661876Praveen Chavan int current_size; 46e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly}; 47e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 48e7273837b521d16f87dd5fb6eea3750a51ea92daNick PellyQueue *alloc_queue() 49e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 5061a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Queue *q = (Queue *) malloc(sizeof(Queue)); 5161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 5261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (q) { 5361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->head = q->tail = NULL; 5461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->current_size = 0; 5561a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } 5661a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 5761a2c6a19dbd06a317a419623020e02056661876Praveen Chavan return q; 58e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 59e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 60e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid free_queue(Queue *q) 61e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 6261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan while (q->current_size) { 6361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan pop(q); 6461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } 65e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 66e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 67e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid free_queue_and_qelement(Queue *q) 68e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 6961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan while (q->current_size) { 7061a2c6a19dbd06a317a419623020e02056661876Praveen Chavan void *element = pop(q); 7161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 7261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (element) 7361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan free(element); 7461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } 75e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 76e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 77e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyint push(Queue *q, void * element) 78e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 7961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Node *new_node = (Node *) malloc(sizeof(Node)); 80e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 8161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (new_node == NULL) 8261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan return -1; 83e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 8461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan new_node->element = element; 8561a2c6a19dbd06a317a419623020e02056661876Praveen Chavan new_node->next = NULL; 86e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 8761a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (q->current_size == 0) { 8861a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->head = new_node; 8961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } else { 9061a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->tail->next = new_node; 9161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } 92e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 9361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->tail = new_node; 9461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->current_size++; 95e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 9661a2c6a19dbd06a317a419623020e02056661876Praveen Chavan return 0; 97e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 98e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 99e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pellyvoid *pop(Queue *q) 100e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly{ 10161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan Node *temp; 10261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan void *element; 10361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 10461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (q->current_size == 0) 10561a2c6a19dbd06a317a419623020e02056661876Praveen Chavan return NULL; 10661a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 10761a2c6a19dbd06a317a419623020e02056661876Praveen Chavan temp = q->head; 10861a2c6a19dbd06a317a419623020e02056661876Praveen Chavan element = temp->element; 10961a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 11061a2c6a19dbd06a317a419623020e02056661876Praveen Chavan if (q->current_size == 1) { 11161a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->head = q->tail = NULL; 11261a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } else { 11361a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->head = q->head->next; 11461a2c6a19dbd06a317a419623020e02056661876Praveen Chavan } 11561a2c6a19dbd06a317a419623020e02056661876Praveen Chavan 11661a2c6a19dbd06a317a419623020e02056661876Praveen Chavan free(temp); 11761a2c6a19dbd06a317a419623020e02056661876Praveen Chavan q->current_size--; 11861a2c6a19dbd06a317a419623020e02056661876Praveen Chavan return element; 119e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly} 120e7273837b521d16f87dd5fb6eea3750a51ea92daNick Pelly 121