Implement queue with O(1) operations, and correct some math.

1 files changed, 16 insertions, 2 deletions

diff --git a/src/or/or.h b/src/or/or.h
index ce4fbd074e..c9eb4a3f91 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -835,16 +835,30 @@ typedef struct var_cell_t {
 typedef struct packed_cell_t {
   struct packed_cell_t *next; /**< Next cell queued on this circuit. */
   char body[CELL_NETWORK_SIZE]; /**< Cell as packed for network. */
-  struct timeval packed_timeval; /**< When was this cell packed? */
 } packed_cell_t;
 
+/** Number of cells added to a circuit queue including their insertion
+ * time on 10 millisecond detail; used for buffer statistics. */
+typedef struct insertion_time_elem_t {
+  struct insertion_time_elem_t *next;
+  uint32_t insertion_time; /**< When were cells inserted (in 10 ms steps
+                             * starting at 0:00 of the current day)? */
+  unsigned counter; /**< How many cells were inserted? */
+} insertion_time_elem_t;
+
+/** Queue of insertion times. */
+typedef struct insertion_time_queue_t {
+  struct insertion_time_elem_t *first;
+  struct insertion_time_elem_t *last;
+} insertion_time_queue_t;
+
 /** A queue of cells on a circuit, waiting to be added to the
  * or_connection_t's outbuf. */
 typedef struct cell_queue_t {
   packed_cell_t *head; /**< The first cell, or NULL if the queue is empty. */
   packed_cell_t *tail; /**< The last cell, or NULL if the queue is empty. */
   int n; /**< The number of cells in the queue. */
-  smartlist_t *insertion_times;
+  insertion_time_queue_t *insertion_times;
 } cell_queue_t;
 
 /** Beginning of a RELAY cell payload. */