/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- q_grow
- q_create
- q_preallocate
- q_empty
- q_addtail
- q_remhead
- q_destroy
- q_getstart
- q_getend
- q_getsize
- q_getguy
- q_peek
- q_len
1 /*
2 * Queue of void pointers. See queue.h for details.
3 */
4
5 #include <types.h>
6 #include <kern/errno.h>
7 #include <lib.h>
8 #include <queue.h>
9
10 struct queue {
11 int size;
12 int nextwrite; // next element to write to (was head)
13 int nextread; // next element to read from (was tail)
14 void **data;
15 };
16
17 static
18 int
19 q_grow(struct queue *q, int targetsize)
20 {
21 void **olddata = q->data;
22 int onr = q->nextread;
23 int onw = q->nextwrite;
24 int osize = q->size;
25
26 int nsize;
27 void **ndata;
28
29 int i, result;
30
31 nsize = q->size;
32 while (nsize < targetsize) {
33 nsize *= 2;
34 /* prevent infinite loop */
35 KASSERT(nsize > 0);
36 }
37 ndata = kmalloc(nsize * sizeof(void *));
38 if (ndata == NULL) {
39 return ENOMEM;
40 }
41 q->size = nsize;
42 q->data = ndata;
43 q->nextread = q->nextwrite = 0;
44
45 for (i=onr; i!=onw; i = (i+1)%osize) {
46 result = q_addtail(q, olddata[i]);
47 KASSERT(result==0);
48 }
49 kfree(olddata);
50 return 0;
51 }
52
53 struct queue *
54 q_create(int size)
55 {
56 struct queue *q = kmalloc(sizeof(struct queue));
57 if (q==NULL) {
58 return NULL;
59 }
60 q->size = size;
61 q->data = kmalloc(size * sizeof(void *));
62 if (q->data==NULL) {
63 kfree(q);
64 return NULL;
65 }
66 q->nextread = q->nextwrite = 0;
67 return q;
68 }
69
70 int
71 q_preallocate(struct queue *q, int size)
72 {
73 int result = 0;
74
75 KASSERT(q->size > 0);
76
77 if (size > q->size) {
78 result = q_grow(q, size);
79 }
80 return result;
81 }
82
83 inline
84 int
85 q_empty(struct queue *q)
86 {
87 return q->nextwrite == q->nextread;
88 }
89
90 int
91 q_addtail(struct queue *q, void *ptr)
92 {
93 int nextnext, result;
94
95 KASSERT(q->size > 0);
96
97 nextnext = (q->nextwrite+1) % q->size;
98 if (nextnext==q->nextread) {
99 result = q_grow(q, q->size+1);
100 if (result) {
101 return result;
102 }
103 nextnext = (q->nextwrite+1) % q->size;
104 }
105 q->data[q->nextwrite] = ptr;
106 q->nextwrite = nextnext;
107 return 0;
108 }
109
110 void *
111 q_remhead(struct queue *q)
112 {
113 void *ret;
114
115 KASSERT(q->size > 0);
116
117 KASSERT(!q_empty(q));
118 ret = q->data[q->nextread];
119 q->nextread = (q->nextread+1)%q->size;
120 return ret;
121 }
122
123 void
124 q_destroy(struct queue *q)
125 {
126 KASSERT(q_empty(q));
127 kfree(q->data);
128 kfree(q);
129 }
130
131 /* These are really intended only for debugging. */
132 int
133 q_getstart(struct queue *q)
134 {
135 return q->nextread;
136 }
137
138 int
139 q_getend(struct queue *q)
140 {
141 return q->nextwrite;
142 }
143
144 int
145 q_getsize(struct queue *q)
146 {
147 return q->size;
148 }
149
150 void *
151 q_getguy(struct queue *q, int index)
152 {
153 // note that we don't check to make sure the access isn't in the
154 // unused part of the queue space. we probably should.
155
156 KASSERT(index>=0 && index<q->size);
157 return q->data[index];
158 }
159
160 void *
161 q_peek(struct queue *q)
162 {
163 void *ret;
164
165 KASSERT(q);
166 KASSERT(q->size > 0);
167
168 if (q_empty(q)) {
169 ret = 0;
170 } else {
171 ret = q->data[q->nextread];
172 }
173 return ret;
174 }
175
176 int
177 q_len(struct queue *theq)
178 {
179 int count = 0;
180 int tmp = theq->nextread;
181 while (tmp != theq->nextwrite) {
182 tmp = (tmp+1) % theq->size;
183 count++;
184 }
185 return count;
186 }