Branch data Line data Source code
1 : : // $Id: Queue.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include <string.h>
8 : :
9 : : #include "Queue.h"
10 : :
11 : 3 : BaseQueue::BaseQueue(int size)
12 : : {
13 : 3 : const int DEFAULT_CHUNK_SIZE = 10;
14 : :
15 : 3 : chunk_size = DEFAULT_CHUNK_SIZE;
16 : :
17 : 3 : head = tail = num_entries = 0;
18 : :
19 [ # # ][ - + ]: 3 : if ( size < 0 )
20 : : {
21 : 0 : entry = new ent[1];
22 : 0 : max_entries = 0;
23 : : }
24 : : else
25 : : {
26 [ # # ][ + - ]: 3 : if ( (entry = new ent[chunk_size+1]) )
27 : 3 : max_entries = chunk_size;
28 : : else
29 : : {
30 : 0 : entry = new ent[1];
31 : 0 : max_entries = 0;
32 : : }
33 : : }
34 : 3 : }
35 : :
36 : 0 : void BaseQueue::push_front(ent a)
37 : : {
38 [ # # ]: 0 : if ( num_entries == max_entries )
39 : : {
40 : 0 : resize(max_entries+chunk_size); // make more room
41 : 0 : chunk_size *= 2;
42 : : }
43 : :
44 : 0 : ++num_entries;
45 [ # # ]: 0 : if ( head )
46 : 0 : entry[--head] = a;
47 : : else
48 : : {
49 : 0 : head = max_entries;
50 : 0 : entry[head] = a;
51 : : }
52 : 0 : }
53 : :
54 : 0 : void BaseQueue::push_back(ent a)
55 : : {
56 [ # # ]: 0 : if ( num_entries == max_entries )
57 : : {
58 : 0 : resize(max_entries+chunk_size); // make more room
59 : 0 : chunk_size *= 2;
60 : : }
61 : :
62 : 0 : ++num_entries;
63 [ # # ]: 0 : if ( tail < max_entries )
64 : 0 : entry[tail++] = a;
65 : : else
66 : : {
67 : 0 : entry[tail] = a;
68 : 0 : tail = 0;
69 : : }
70 : 0 : }
71 : :
72 : 0 : ent BaseQueue::pop_front()
73 : : {
74 [ # # ]: 0 : if ( ! num_entries )
75 : 0 : return 0;
76 : :
77 : 0 : --num_entries;
78 [ # # ]: 0 : if ( head < max_entries )
79 : 0 : return entry[head++];
80 : : else
81 : : {
82 : 0 : head = 0;
83 : 0 : return entry[max_entries];
84 : : }
85 : : }
86 : :
87 : 0 : ent BaseQueue::pop_back()
88 : : {
89 [ # # ]: 0 : if ( ! num_entries )
90 : 0 : return 0;
91 : :
92 : 0 : --num_entries;
93 [ # # ]: 0 : if ( tail )
94 : 0 : return entry[--tail];
95 : : else
96 : : {
97 : 0 : tail = max_entries;
98 : 0 : return entry[tail];
99 : : }
100 : : }
101 : :
102 : 0 : int BaseQueue::resize(int new_size)
103 : : {
104 [ # # ]: 0 : if ( new_size < num_entries )
105 : 0 : new_size = num_entries; // do not lose any entries
106 : :
107 [ # # ]: 0 : if ( new_size != max_entries )
108 : : {
109 : : // Note, allocate extra space, so that we can always
110 : : // use the [max_entries] element.
111 : : // ### Yin, why not use realloc()?
112 : 0 : ent* new_entry = new ent[new_size+1];
113 : :
114 [ # # ]: 0 : if ( new_entry )
115 : : {
116 [ # # ]: 0 : if ( head <= tail )
117 : : memcpy( new_entry, entry + head,
118 : 0 : sizeof(ent) * num_entries );
119 : : else
120 : : {
121 : 0 : int len = num_entries - tail;
122 : : memcpy( new_entry, entry + head,
123 : 0 : sizeof(ent) * len );
124 : : memcpy( new_entry + len, entry,
125 : 0 : sizeof(ent) * tail );
126 : : }
127 [ # # ]: 0 : delete [] entry;
128 : 0 : entry = new_entry;
129 : 0 : max_entries = new_size;
130 : 0 : head = 0;
131 : 0 : tail = num_entries;
132 : : }
133 : : else
134 : : { // out of memory
135 : : }
136 : : }
137 : :
138 : 0 : return max_entries;
139 : : }
|