← Back to branch summary

~ps10gel/ubuntu/xenial/trafficserver/6.2.0

« back to all changes in this revision

Viewing changes to lib/ts/llqueue.cc

  • Committer: Bazaar Package Importer
  • Author(s): Arno Toell
  • Date: 2011-01-13 11:49:18 UTC
  • Revision ID: james.westby@ubuntu.com-20110113114918-vu422h8dknrgkj15
Tags: upstream-2.1.5-unstable
Import upstream version 2.1.5-unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/ts/llqueue.cc
 
1
/** @file
 
2
 
 
3
  Implementation of a simple linked list queue
 
4
 
 
5
  @section license License
 
6
 
 
7
  Licensed to the Apache Software Foundation (ASF) under one
 
8
  or more contributor license agreements.  See the NOTICE file
 
9
  distributed with this work for additional information
 
10
  regarding copyright ownership.  The ASF licenses this file
 
11
  to you under the Apache License, Version 2.0 (the
 
12
  "License"); you may not use this file except in compliance
 
13
  with the License.  You may obtain a copy of the License at
 
14
 
 
15
      http://www.apache.org/licenses/LICENSE-2.0
 
16
 
 
17
  Unless required by applicable law or agreed to in writing, software
 
18
  distributed under the License is distributed on an "AS IS" BASIS,
 
19
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
20
  See the License for the specific language governing permissions and
 
21
  limitations under the License.
 
22
 */
 
23
 
 
24
#include "ink_config.h"
 
25
 
 
26
#include <stdio.h>
 
27
#include <stdlib.h>
 
28
#if !defined(freebsd) && !defined(darwin)
 
29
#include <malloc.h>
 
30
#endif
 
31
#include <assert.h>
 
32
#include <limits.h>
 
33
 
 
34
#include "ink_unused.h" /* MAGIC_EDITING_TAG */
 
35
#include "ink_llqueue.h"
 
36
#include "errno.h"
 
37
 
 
38
#define RECORD_CHUNK 1024
 
39
 
 
40
// These are obviously not used anywhere, I don't know if or how they
 
41
// were supposed to work, but #ifdef'ing them out of here for now.
 
42
#ifdef NOT_USED_HERE
 
43
static LLQrec *
 
44
newrec(LLQ * Q)
 
45
{
 
46
  LLQrec * new_val;
 
47
  int i;
 
48
 
 
49
  if (Q->free != NULL) {
 
50
    new_val = Q->free;
 
51
    Q->free = Q->free->next;
 
52
    return new_val;
 
53
  }
 
54
 
 
55
 
 
56
  Q->free = (LLQrec *) xmalloc(RECORD_CHUNK * sizeof(LLQrec));
 
57
 
 
58
  if (!Q->free)
 
59
    return NULL;
 
60
 
 
61
  for (i = 0; i < RECORD_CHUNK; i++)
 
62
    Q->free[i].next = &Q->free[i + 1];
 
63
 
 
64
  Q->free[RECORD_CHUNK - 1].next = NULL;
 
65
 
 
66
 
 
67
  new_val = Q->free;
 
68
  Q->free = Q->free->next;
 
69
 
 
70
  return new_val;
 
71
}
 
72
 
 
73
// Not used either ...
 
74
static void
 
75
freerec(LLQ * Q, LLQrec * rec)
 
76
{
 
77
  rec->next = Q->free;
 
78
  Q->free = rec;
 
79
}
 
80
#endif
 
81
 
 
82
LLQ *
 
83
create_queue()
 
84
{
 
85
  const char *totally_bogus_name = "create_queue";
 
86
  LLQ * new_val;
 
87
 
 
88
  new_val = (LLQ *) xmalloc(sizeof(LLQ));
 
89
  if (!new_val)
 
90
    return NULL;
 
91
 
 
92
#if defined(darwin)
 
93
  static int qnum = 0;
 
94
  char sname[NAME_MAX];
 
95
  qnum++;
 
96
  snprintf(sname,NAME_MAX,"%s%d",totally_bogus_name,qnum);
 
97
  ink_sem_unlink(sname); // FIXME: remove, semaphore should be properly deleted after usage
 
98
  new_val->sema = ink_sem_open(sname, O_CREAT | O_EXCL, 0777, 0);
 
99
#else /* !darwin */
 
100
  ink_sem_init(&(new_val->sema), 0);
 
101
#endif /* !darwin */
 
102
  ink_mutex_init(&(new_val->mux), totally_bogus_name);
 
103
 
 
104
  new_val->head = new_val->tail = new_val->free = NULL;
 
105
  new_val->len = new_val->highwater = 0;
 
106
 
 
107
  return new_val;
 
108
}
 
109
 
 
110
// matching delete function, only for empty queue!
 
111
void
 
112
delete_queue(LLQ * Q)
 
113
{
 
114
  // There seems to have been some ideas of making sure that this queue is
 
115
  // actually empty ...
 
116
  //
 
117
  //    LLQrec * qrec;
 
118
  if (Q) {
 
119
    xfree(Q);
 
120
  }
 
121
  return;
 
122
}
 
123
 
 
124
int
 
125
enqueue(LLQ * Q, void *data)
 
126
{
 
127
  LLQrec * new_val;
 
128
 
 
129
  ink_mutex_acquire(&(Q->mux));
 
130
 
 
131
//new_val= newrec(Q);
 
132
  new_val = (LLQrec *) xmalloc(sizeof(LLQrec));
 
133
 
 
134
  if (!new_val) {
 
135
    ink_mutex_release(&(Q->mux));
 
136
    return 0;
 
137
  }
 
138
 
 
139
  new_val->data = data;
 
140
  new_val->next = NULL;
 
141
 
 
142
  if (Q->tail)
 
143
    Q->tail->next = new_val;
 
144
  Q->tail = new_val;
 
145
 
 
146
  if (Q->head == NULL)
 
147
    Q->head = Q->tail;
 
148
 
 
149
  Q->len++;
 
150
  if (Q->len > Q->highwater)
 
151
    Q->highwater = Q->len;
 
152
  ink_mutex_release(&(Q->mux));
 
153
#if defined(darwin)
 
154
  ink_sem_post(Q->sema);
 
155
#else
 
156
  ink_sem_post(&(Q->sema));
 
157
#endif
 
158
  return 1;
 
159
}
 
160
 
 
161
uint64_t
 
162
queue_len(LLQ * Q)
 
163
{
 
164
  uint64_t len;
 
165
 
 
166
  /* Do I really need to grab the lock here? */
 
167
  /* ink_mutex_acquire(&(Q->mux)); */
 
168
  len = Q->len;
 
169
  /* ink_mutex_release(&(Q->mux)); */
 
170
  return len;
 
171
}
 
172
 
 
173
uint64_t
 
174
queue_highwater(LLQ * Q)
 
175
{
 
176
  uint64_t highwater;
 
177
 
 
178
  /* Do I really need to grab the lock here? */
 
179
  /* ink_mutex_acquire(&(Q->mux)); */
 
180
  highwater = Q->highwater;
 
181
  /* ink_mutex_release(&(Q->mux)); */
 
182
  return highwater;
 
183
}
 
184
 
 
185
 
 
186
 
 
187
/*
 
188
 *---------------------------------------------------------------------------
 
189
 *
 
190
 * queue_is_empty
 
191
 *
 
192
 *  Is the queue empty?
 
193
 *
 
194
 * Results:
 
195
 *  nonzero if empty, zero else.
 
196
 *
 
197
 * Side Effects:
 
198
 *  none.
 
199
 *
 
200
 * Reentrancy:     n/a.
 
201
 * Thread Safety:  safe.
 
202
 * Mem Management: n/a.
 
203
 *
 
204
 *---------------------------------------------------------------------------
 
205
 */
 
206
int
 
207
queue_is_empty(LLQ * Q)
 
208
{
 
209
  uint64_t len;
 
210
 
 
211
  len = queue_len(Q);
 
212
 
 
213
  if (len)
 
214
    return 0;
 
215
  else
 
216
    return 1;
 
217
}
 
218
 
 
219
void *
 
220
dequeue(LLQ * Q)
 
221
{
 
222
  LLQrec * rec;
 
223
  void *d;
 
224
#if defined(darwin)
 
225
  ink_sem_wait(Q->sema);
 
226
#else
 
227
  ink_sem_wait(&(Q->sema));
 
228
#endif
 
229
  ink_mutex_acquire(&(Q->mux));
 
230
 
 
231
 
 
232
  if (Q->head == NULL) {
 
233
 
 
234
    ink_mutex_release(&(Q->mux));
 
235
 
 
236
    return NULL;
 
237
  }
 
238
 
 
239
  rec = Q->head;
 
240
 
 
241
  Q->head = Q->head->next;
 
242
  if (Q->head == NULL)
 
243
    Q->tail = NULL;
 
244
 
 
245
  d = rec->data;
 
246
//freerec(Q, rec);
 
247
  xfree(rec);
 
248
 
 
249
  Q->len--;
 
250
  ink_mutex_release(&(Q->mux));
 
251
 
 
252
  return d;
 
253
}
 
254
 
 
255
 
 
256
 
 
257
#ifdef LLQUEUE_MAIN
 
258
 
 
259
void *
 
260
testfun(void *unused)
 
261
{
 
262
  int num;
 
263
  LLQ *Q;
 
264
 
 
265
  Q = create_queue();
 
266
  assert(Q);
 
267
 
 
268
  do {
 
269
    scanf("%d", &num);
 
270
    if (num == 0) {
 
271
      printf("DEQUEUE: %d\n", (int) dequeue(Q));
 
272
    } else if (num == -1) {
 
273
      printf("queue_is_empty: %d\n", queue_is_empty(Q));
 
274
    } else {
 
275
      printf("enqueue: %d\n", num);
 
276
      enqueue(Q, (void *) num);
 
277
    }
 
278
  } while (num >= -1);
 
279
 
 
280
  return NULL;
 
281
}
 
282
 
 
283
/*
 
284
 * test harness-- hit Ctrl-C if it blocks or you get tired.
 
285
 */
 
286
void
 
287
main()
 
288
{
 
289
  assert(thr_create(NULL, 0, testfun, (void *) NULL, THR_NEW_LWP, NULL) == 0);
 
290
  while (1) {
 
291
    ;
 
292
  }
 
293
}
 
294
 
 
295
#endif