Branch data Line data Source code
1 : : // $Id: Queue.h 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #ifndef queue_h
6 : : #define queue_h
7 : :
8 : : // BaseQueue.h --
9 : : // Interface for class BaseQueue, current implementation is as an
10 : : // array of ent's. This implementation was chosen to optimize
11 : : // getting to the ent's rather than inserting and deleting.
12 : : // Also push's and pop's from the front or the end of the queue
13 : : // are very efficient. The only really expensive operation
14 : : // is resizing the list, which involves getting new space
15 : : // and moving the data. Resizing occurs automatically when inserting
16 : : // more elements than the list can currently hold. Automatic
17 : : // resizing is done one "chunk_size" of elements at a time and
18 : : // always increases the size of the list. Resizing to zero
19 : : // (or to less than the current value of num_entries)
20 : : // will decrease the size of the list to the current number of
21 : : // elements. Resize returns the new max_entries.
22 : : //
23 : : // Entries must be either a pointer to the data or nonzero data with
24 : : // sizeof(data) <= sizeof(void*).
25 : :
26 : : #include "List.h"
27 : :
28 : : class BaseQueue {
29 : : public:
30 [ + - ]: 3 : ~BaseQueue() { delete[] entry; }
31 : :
32 : 0 : int length() const { return num_entries; }
33 : : int resize(int = 0); // 0 => size to fit current number of entries
34 : :
35 : : // remove all entries without delete[] entry
36 : : void clear() { head = tail = num_entries = 0; }
37 : :
38 : : // helper functions for iterating over queue
39 : 0 : int front() const { return head; }
40 : 0 : int back() const { return tail; }
41 [ # # ]: 0 : void incr(int& index) { index < max_entries ? ++index : index = 0; }
42 : :
43 : : protected:
44 : : BaseQueue(int = 0);
45 : :
46 : : void push_front(ent); // add in front of queue
47 : : void push_back(ent); // add at end of queue
48 : : ent pop_front(); // return and remove the front of queue
49 : : ent pop_back(); // return and remove the end of queue
50 : :
51 : : // return nth *PHYSICAL* entry of queue (do not remove)
52 : 0 : ent operator[](int i) const { return entry[i]; }
53 : :
54 : : ent* entry;
55 : : int chunk_size; // increase size by this amount when necessary
56 : : int max_entries; // entry's index range: 0 .. max_entries
57 : : int num_entries;
58 : : int head; // beginning of the queue in the ring
59 : : int tail; // just beyond the end of the queue in the ring
60 : : };
61 : :
62 : : // Queue.h -- interface for class Queue
63 : : // Use: to get a list of pointers to class foo you should:
64 : : // 1) declare(PQueue,foo); (declare interest in lists of foo*'s)
65 : : // 2) variables are declared like:
66 : : // PQueue(foo) bar; (bar is of type list of foo*'s)
67 : :
68 : : // For queues of "type"
69 : : #define Queue(type) type ## Queue
70 : :
71 : : // For queues of pointers to "type"
72 : : #define PQueue(type) type ## PQueue
73 : :
74 : : #define Queuedeclare(type) \
75 : : struct Queue(type) : BaseQueue \
76 : : { \
77 : : Queue(type)() : BaseQueue(0) {} \
78 : : Queue(type)(int sz) : BaseQueue(sz) {} \
79 : : \
80 : : void push_front(type a) { BaseQueue::push_front(ent(a)); } \
81 : : void push_back(type a) { BaseQueue::push_back(ent(a)); } \
82 : : type pop_front() { return type(BaseQueue::pop_front()); }\
83 : : type pop_back() { return type(BaseQueue::pop_back()); } \
84 : : \
85 : : type operator[](int i) const \
86 : : { return type(BaseQueue::operator[](i)); } \
87 : : }; \
88 : :
89 : : #define PQueuedeclare(type) \
90 : : struct PQueue(type) : BaseQueue \
91 : : { \
92 : : PQueue(type)() : BaseQueue(0) {} \
93 : : PQueue(type)(int sz) : BaseQueue(sz) {} \
94 : : \
95 : : void push_front(type* a){ BaseQueue::push_front(ent(a)); } \
96 : : void push_back(type* a) { BaseQueue::push_back(ent(a)); } \
97 : : type* pop_front() \
98 : : { return (type*)BaseQueue::pop_front(); } \
99 : : type* pop_back() \
100 : : { return (type*)BaseQueue::pop_back(); } \
101 : : \
102 : : type* operator[](int i) const \
103 : : { return (type*)BaseQueue::operator[](i); } \
104 : : }; \
105 : :
106 : : // Macro to visit each queue element in turn.
107 : : #define loop_over_queue(queue, iterator) \
108 : : int iterator; \
109 : : for ( iterator = (queue).front(); iterator != (queue).back(); \
110 : : (queue).incr(iterator) ) \
111 : :
112 : : #endif /* queue_h */
|
