1// mgo - MongoDB driver for Go
2//
3// Copyright (c) 2010-2012 - Gustavo Niemeyer <gustavo@niemeyer.net>
4//
5// All rights reserved.
6//
7// Redistribution and use in source and binary forms, with or without
8// modification, are permitted provided that the following conditions are met:
9//
10// 1. Redistributions of source code must retain the above copyright notice, this
11//    list of conditions and the following disclaimer.
12// 2. Redistributions in binary form must reproduce the above copyright notice,
13//    this list of conditions and the following disclaimer in the documentation
14//    and/or other materials provided with the distribution.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
20// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27package mgo
28
29type queue struct {
30	elems               []interface{}
31	nelems, popi, pushi int
32}
33
34func (q *queue) Len() int {
35	return q.nelems
36}
37
38func (q *queue) Push(elem interface{}) {
39	//debugf("Pushing(pushi=%d popi=%d cap=%d): %#v\n",
40	//       q.pushi, q.popi, len(q.elems), elem)
41	if q.nelems == len(q.elems) {
42		q.expand()
43	}
44	q.elems[q.pushi] = elem
45	q.nelems++
46	q.pushi = (q.pushi + 1) % len(q.elems)
47	//debugf(" Pushed(pushi=%d popi=%d cap=%d): %#v\n",
48	//       q.pushi, q.popi, len(q.elems), elem)
49}
50
51func (q *queue) Pop() (elem interface{}) {
52	//debugf("Popping(pushi=%d popi=%d cap=%d)\n",
53	//       q.pushi, q.popi, len(q.elems))
54	if q.nelems == 0 {
55		return nil
56	}
57	elem = q.elems[q.popi]
58	q.elems[q.popi] = nil // Help GC.
59	q.nelems--
60	q.popi = (q.popi + 1) % len(q.elems)
61	//debugf(" Popped(pushi=%d popi=%d cap=%d): %#v\n",
62	//       q.pushi, q.popi, len(q.elems), elem)
63	return elem
64}
65
66func (q *queue) expand() {
67	curcap := len(q.elems)
68	var newcap int
69	if curcap == 0 {
70		newcap = 8
71	} else if curcap < 1024 {
72		newcap = curcap * 2
73	} else {
74		newcap = curcap + (curcap / 4)
75	}
76	elems := make([]interface{}, newcap)
77
78	if q.popi == 0 {
79		copy(elems, q.elems)
80		q.pushi = curcap
81	} else {
82		newpopi := newcap - (curcap - q.popi)
83		copy(elems, q.elems[:q.popi])
84		copy(elems[newpopi:], q.elems[q.popi:])
85		q.popi = newpopi
86	}
87	for i := range q.elems {
88		q.elems[i] = nil // Help GC.
89	}
90	q.elems = elems
91}
92