13597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu/* 22f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * queue.c, queue 330bd6062e4b295f5f7bcaeb98165065310d29269Ho-Eun Ryu * 42f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * Copyright (c) 2009-2010 Wind River Systems, Inc. 52f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * 62f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * Licensed under the Apache License, Version 2.0 (the "License"); 72f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * you may not use this file except in compliance with the License. 82f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * You may obtain a copy of the License at 92f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * 102f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * http://www.apache.org/licenses/LICENSE-2.0 112f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * 122f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * Unless required by applicable law or agreed to in writing, software 132f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * distributed under the License is distributed on an "AS IS" BASIS, 142f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 152f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * See the License for the specific language governing permissions and 162f6e87e64736666857c1bbe2cb0692c1f4e56508Ho-Eun Ryu * limitations under the License. 173597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu */ 183597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 193597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu#include <stdlib.h> 203597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 213597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu#include <queue.h> 223597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 233597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline void __queue_init(struct queue *queue) 243597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 253597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = NULL; 263597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = NULL; 273597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length = 0; 283597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 293597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 303597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryustruct queue *queue_alloc(void) 313597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 323597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct queue *queue; 333597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 343597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue = malloc(sizeof(struct queue)); 353597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (queue) 363597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu __queue_init(queue); 373597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 383597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return queue; 393597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 403597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 413597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline void __queue_free(struct queue *queue) 423597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 433597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu free(queue); 443597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 453597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 463597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuvoid queue_free_all(struct queue *queue) 473597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 483597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *list = queue->head; 493597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 503597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu list_free_all(list); 513597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu __queue_init(queue); 523597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 533597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 543597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuvoid __queue_push_head(struct queue *queue, struct list *entry) 553597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 563597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = __list_add_head(queue->head, entry); 573597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (!queue->tail) 583597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = queue->head; 593597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 603597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length++; 613597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 623597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 633597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuint queue_push_head(struct queue *queue, void *data) 643597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 653597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry = list_alloc(data); 663597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 673597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (!entry) 683597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return -1; 693597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu else 703597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = __list_add_head(queue->head, entry); 713597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 723597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (!queue->tail) 733597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = queue->head; 743597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 753597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length++; 763597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return 0; 773597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 783597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 793597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuvoid __queue_push_tail(struct queue *queue, struct list *entry) 803597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 81f94dc0afb6e4af367787f758a77e510c0bfe6b8aywan queue->tail = list_add_tail(queue->tail, entry); 82f94dc0afb6e4af367787f758a77e510c0bfe6b8aywan if (queue->tail == NULL) { 83f94dc0afb6e4af367787f758a77e510c0bfe6b8aywan return; 848af4549cec855377507046127d9b9a45911eaf04ywan } 853597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (queue->tail->next) 863597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = queue->tail->next; 873597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu else 883597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = queue->tail; 893597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 903597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length++; 913597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 923597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 933597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuint queue_push_tail(struct queue *queue, void *data) 943597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 953597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry = list_alloc(data); 963597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 973597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (!entry) 983597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return -1; 993597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu else 1003597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = __list_add_tail(queue->tail, entry); 1013597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1023597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (queue->tail->next) 1033597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = queue->tail->next; 1043597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu else 1053597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = queue->tail; 1063597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1073597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length++; 1083597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return 0; 1093597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1103597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1113597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryustruct list *__queue_pop_head(struct queue *queue) 1123597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1133597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry = queue->head; 1143597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1153597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) { 1163597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = __list_remove(queue->head, entry); 1173597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (!queue->head) 1183597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = NULL; 1193597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1203597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length--; 1213597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu } 1223597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1233597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return entry; 1243597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1253597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1263597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuvoid *queue_pop_head(struct queue *queue) 1273597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1283597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry; 1293597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu void *data = NULL; 1303597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1313597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu entry = __queue_pop_head(queue); 1323597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) { 1333597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu data = entry->data; 1343597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu __list_free(entry); 1353597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu } 1363597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1373597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return data; 1383597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1393597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1403597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryustruct list *__queue_pop_tail(struct queue *queue) 1413597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1423597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry = queue->tail; 1433597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *prev; 1443597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1453597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) { 1463597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu prev = entry->prev; 1473597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->head = __list_remove(queue->head, entry); 1483597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->tail = prev; 1493597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu queue->length--; 1503597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu } 1513597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1523597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return entry; 1533597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1543597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1553597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuvoid *queue_pop_tail(struct queue *queue) 1563597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1573597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry; 1583597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu void *data = NULL; 1593597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1603597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu entry = __queue_pop_tail(queue); 1613597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) { 1623597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu data = entry->data; 1633597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu __list_free(entry); 1643597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu } 1653597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1663597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return data; 1673597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1683597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1693597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline struct list *__queue_peek_head(struct queue *queue) 1703597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1713597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return queue->head; 1723597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1733597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1743597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline struct list *__queue_peek_tail(struct queue *queue) 1753597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1763597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return queue->tail; 1773597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1783597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1793597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline void *queue_peek_head(struct queue *queue) 1803597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1813597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry; 1823597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu void *data = NULL; 1833597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1843597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu entry = __queue_peek_head(queue); 1853597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) 1863597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu data = entry->data; 1873597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1883597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return data; 1893597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 1903597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1913597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuinline void *queue_peek_tail(struct queue *queue) 1923597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 1933597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu struct list *entry; 1943597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu void *data = NULL; 1953597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 1963597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu entry = __queue_peek_tail(queue); 1973597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu if (entry) 1983597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu data = entry->data; 1993597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 2003597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return data; 2013597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 2023597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu 2033597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryuint queue_length(struct queue *queue) 2043597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu{ 2053597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu return queue->length; 2063597788ce7c666b2e86df3932968f0745f4b7bd1Ho-Eun Ryu} 207