1// Copyright 2006 Google Inc. All Rights Reserved.
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//      http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// queue.cc : simple thread safe queue implementation
16
17#include <stdlib.h>
18
19// This file must work with autoconf on its public version,
20// so these includes are correct.
21#include "queue.h"
22#include "sattypes.h"
23
24// Page entry queue implementation follows.
25// Push inserts pages, pop returns a random entry.
26
27
28PageEntryQueue::PageEntryQueue(uint64 queuesize) {
29  // There must always be one empty queue location,
30  // since in == out => empty.
31  q_size_ = queuesize + 1;
32  pages_ = new struct page_entry[q_size_];
33  nextin_ = 0;
34  nextout_ = 0;
35  popped_ = 0;
36  pushed_ = 0;
37  pthread_mutex_init(&q_mutex_, NULL);
38}
39PageEntryQueue::~PageEntryQueue() {
40  delete[] pages_;
41  pthread_mutex_destroy(&q_mutex_);
42}
43
44// Add a page into this queue.
45int PageEntryQueue::Push(struct page_entry *pe) {
46  int result = 0;
47  int64 nextnextin;
48
49  if (!pe)
50    return 0;
51
52  pthread_mutex_lock(&q_mutex_);
53  nextnextin = (nextin_ + 1) % q_size_;
54
55  if (nextnextin != nextout_) {
56    pages_[nextin_] = *pe;
57
58    nextin_ = nextnextin;
59    result = 1;
60
61    pushed_++;
62  }
63
64  pthread_mutex_unlock(&q_mutex_);
65
66  return result;
67}
68
69// Retrieve a random page from this queue.
70int PageEntryQueue::PopRandom(struct page_entry *pe) {
71  int result = 0;
72  int64 lastin;
73  int64 entries;
74  int64 newindex;
75  struct page_entry tmp;
76
77  if (!pe)
78    return 0;
79
80  // TODO(nsanders): we should improve random to get 64 bit randoms, and make
81  // it more thread friendly.
82  uint64 rand = random();
83
84  int retval = pthread_mutex_lock(&q_mutex_);
85  if (retval)
86    logprintf(0, "Process Error: pthreads mutex failure %d\n", retval);
87
88
89  if (nextin_ != nextout_) {
90    // Randomized fetch.
91    // Swap random entry with next out.
92    {
93      lastin = (nextin_ - 1 + q_size_) % q_size_;
94      entries = (lastin - nextout_ + q_size_) % q_size_;
95
96      newindex = nextout_;
97      if (entries)
98        newindex = ((rand % entries) + nextout_) % q_size_;
99
100      // Swap the pages.
101      tmp = pages_[nextout_];
102      pages_[nextout_] = pages_[newindex];
103      pages_[newindex] = tmp;
104    }
105
106    // Return next out page.
107    *pe = pages_[nextout_];
108
109    nextout_ = (nextout_ + 1) % q_size_;
110    result = 1;
111
112    popped_++;
113  }
114
115  pthread_mutex_unlock(&q_mutex_);
116
117  return result;
118}
119