1 /*
2 * Copyright 2008-2014 Arsen Chaloyan
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 * $Id: apt_cyclic_queue.c 2136 2014-07-04 06:33:36Z achaloyan@gmail.com $
17 */
18
19 #include <stdlib.h>
20 #include "apt_cyclic_queue.h"
21
22 struct apt_cyclic_queue_t {
23 void **data;
24 apr_size_t max_size;
25 apr_size_t actual_size;
26 apr_size_t head;
27 apr_size_t tail;
28 };
29
30 static apt_bool_t apt_cyclic_queue_resize(apt_cyclic_queue_t *queue);
31
32
apt_cyclic_queue_create(apr_size_t size)33 APT_DECLARE(apt_cyclic_queue_t*) apt_cyclic_queue_create(apr_size_t size)
34 {
35 apt_cyclic_queue_t *queue = malloc(sizeof(apt_cyclic_queue_t));
36 queue->max_size = size;
37 queue->actual_size = 0;
38 queue->data = malloc(sizeof(void*) * queue->max_size);
39 queue->head = queue->tail = 0;
40 return queue;
41 }
42
apt_cyclic_queue_destroy(apt_cyclic_queue_t * queue)43 APT_DECLARE(void) apt_cyclic_queue_destroy(apt_cyclic_queue_t *queue)
44 {
45 if(queue->data) {
46 free(queue->data);
47 queue->data = NULL;
48 }
49 free(queue);
50 }
51
apt_cyclic_queue_push(apt_cyclic_queue_t * queue,void * obj)52 APT_DECLARE(apt_bool_t) apt_cyclic_queue_push(apt_cyclic_queue_t *queue, void *obj)
53 {
54 if(queue->actual_size >= queue->max_size) {
55 if(apt_cyclic_queue_resize(queue) != TRUE) {
56 return FALSE;
57 }
58 }
59
60 queue->data[queue->head] = obj;
61 queue->head = (queue->head + 1) % queue->max_size;
62 queue->actual_size++;
63 return TRUE;
64 }
65
apt_cyclic_queue_pop(apt_cyclic_queue_t * queue)66 APT_DECLARE(void*) apt_cyclic_queue_pop(apt_cyclic_queue_t *queue)
67 {
68 void *obj = NULL;
69 if(queue->actual_size) {
70 obj = queue->data[queue->tail];
71 queue->tail = (queue->tail + 1) % queue->max_size;
72 queue->actual_size--;
73 }
74 return obj;
75 }
76
apt_cyclic_queue_clear(apt_cyclic_queue_t * queue)77 APT_DECLARE(void) apt_cyclic_queue_clear(apt_cyclic_queue_t *queue)
78 {
79 queue->actual_size = 0;
80 queue->head = queue->tail = 0;
81 }
82
apt_cyclic_queue_is_empty(const apt_cyclic_queue_t * queue)83 APT_DECLARE(apt_bool_t) apt_cyclic_queue_is_empty(const apt_cyclic_queue_t *queue)
84 {
85 return queue->actual_size ? TRUE : FALSE;
86 }
87
apt_cyclic_queue_resize(apt_cyclic_queue_t * queue)88 static apt_bool_t apt_cyclic_queue_resize(apt_cyclic_queue_t *queue)
89 {
90 apr_size_t new_size = queue->max_size + queue->max_size/2;
91 void **new_data = malloc(sizeof(void*) * new_size);
92 apr_size_t offset;
93
94 offset = queue->max_size - queue->head;
95 memcpy(new_data, queue->data + queue->head, sizeof(void*) * offset);
96 if(queue->head) {
97 memcpy(new_data + offset, queue->data, sizeof(void*) * queue->head);
98 }
99
100 queue->tail = 0;
101 queue->head = queue->max_size;
102 queue->max_size = new_size;
103 free(queue->data);
104 queue->data = new_data;
105 return TRUE;
106 }
107