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