Home | History | Annotate | Download | only in src 
      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 
     28 PageEntryQueue::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 }
     39 PageEntryQueue::~PageEntryQueue() {
     40   delete[] pages_;
     41   pthread_mutex_destroy(&q_mutex_);
     42 }
     43 
     44 // Add a page into this queue.
     45 int 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.
     70 int 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