05aa1b8dfade93a4e5f1d6dc1297a1f456c8cadf
[vte.git] / src / ring.c
1 /*
2  * Copyright (C) 2002 Red Hat, Inc.
3  *
4  * This is free software; you can redistribute it and/or modify it under
5  * the terms of the GNU Library General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this program; if not, write to the Free Software
16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17  */
18
19 #ident "$Id$"
20 #include "../config.h"
21 #include <stdio.h>
22 #include <string.h>
23 #include <glib.h>
24 #include "debug.h"
25 #include "ring.h"
26
27 struct _VteRing {
28         VteRingFreeFunc free;
29         gpointer user_data;
30         gpointer *array;
31         long delta, length, max;
32 };
33
34 #ifdef VTE_DEBUG
35 static void
36 vte_ring_validate(VteRing *ring)
37 {
38         long i;
39         for (i = ring->delta; i < ring->delta + ring->length; i++) {
40                 g_assert(vte_ring_contains(ring, i));
41                 g_assert(ring->array[i % ring->max] != NULL);
42         }
43 }
44 #endif
45
46 VteRing *
47 vte_ring_new(long max_elements, VteRingFreeFunc free, gpointer data)
48 {
49         VteRing *ret = g_malloc0(sizeof(VteRing));
50         ret->user_data = data;
51         ret->delta = ret->length = 0;
52         ret->max = max_elements;
53         ret->array = g_malloc0(sizeof(gpointer) * ret->max);
54         ret->free = free;
55         return ret;
56 }
57
58 void
59 vte_ring_insert(VteRing *ring, long position, gpointer data)
60 {
61         long point, i;
62 #ifdef VTE_DEBUG
63         if (vte_debug_on(VTE_DEBUG_MISC)) {
64                 fprintf(stderr, "Inserting at position %ld.\n", position);
65                 fprintf(stderr, " Delta = %ld, Length = %ld, Max = %ld.\n",
66                         ring->delta, ring->length, ring->max);
67         }
68 #endif
69         g_return_if_fail(position >= ring->delta);
70         g_return_if_fail(position <= ring->delta + ring->length);
71         g_return_if_fail(data != NULL);
72
73         /* Initial insertion, or append. */
74         if (position == ring->length + ring->delta) {
75                 /* If there was something there before, free it. */
76                 if (ring->array[position % ring->max] && ring->free) {
77                         ring->free(ring->array[position % ring->max],
78                                    ring->user_data);
79                 }
80                 ring->array[position % ring->max] = data;
81                 if (ring->length == ring->max) {
82                         ring->delta++;
83                 } else {
84                         ring->length++;
85                 }
86 #ifdef VTE_DEBUG
87                 if (vte_debug_on(VTE_DEBUG_MISC)) {
88                         fprintf(stderr, " Delta = %ld, Length = %ld, "
89                                 "Max = %ld.\n",
90                                 ring->delta, ring->length, ring->max);
91                 }
92                 vte_ring_validate(ring);
93 #endif
94                 return;
95         }
96
97         /* All other cases. */
98         point = ring->delta + ring->length - 1;
99         while (point < 0) {
100                 point += ring->max;
101         }
102
103         /* If the buffer's full, then the last item will be lost. */
104         if (ring->length == ring->max) {
105                 if (ring->free && ring->array[point % ring->max]) {
106                         ring->free(ring->array[point % ring->max],
107                                    ring->user_data);
108                 }
109         }
110
111         /* Bubble the rest down.  This isn't as slow as you probably think
112          * it is due to the pattern of usage. */
113         if (ring->length != ring->max) {
114                 /* We'll need to copy the last item, too. */
115                 point++;
116         }
117         for (i = point; i > position; i--) {
118                 ring->array[i % ring->max] = ring->array[(i - 1) % ring->max];
119         }
120         ring->array[position % ring->max] = data;
121         ring->length = MIN(ring->length + 1, ring->max);
122 #ifdef VTE_DEBUG
123         if (vte_debug_on(VTE_DEBUG_MISC)) {
124                 fprintf(stderr, " Delta = %ld, Length = %ld, Max = %ld.\n",
125                         ring->delta, ring->length, ring->max);
126         }
127         vte_ring_validate(ring);
128 #endif
129 }
130
131 void
132 vte_ring_remove(VteRing *ring, long position, gboolean free)
133 {
134         long i;
135 #ifdef VTE_DEBUG
136         if (vte_debug_on(VTE_DEBUG_MISC)) {
137                 fprintf(stderr, "Removing item at position %ld.\n", position);
138                 fprintf(stderr, " Delta = %ld, Length = %ld, Max = %ld.\n",
139                         ring->delta, ring->length, ring->max);
140         }
141 #endif
142         /* Remove the data at this position. */
143         if (ring->array[position % ring->max] && ring->free) {
144                 ring->free(ring->array[position % ring->max],
145                            ring->user_data);
146         }
147         ring->array[position % ring->max] = NULL;
148
149         /* Bubble the rest of the buffer up one notch.  This is also less
150          * of a problem than it might appear, again due to usage patterns. */
151         for (i = position; i < ring->delta + ring->length - 1; i++) {
152                 ring->array[i % ring->max] = ring->array[(i + 1) % ring->max];
153         }
154         if (ring->length > 0) {
155                 ring->array[(ring->delta + ring->length - 1) % ring->max] = NULL;
156                 ring->length--;
157         }
158 #ifdef VTE_DEBUG
159         if (vte_debug_on(VTE_DEBUG_MISC)) {
160                 fprintf(stderr, " Delta = %ld, Length = %ld, Max = %ld.\n",
161                         ring->delta, ring->length, ring->max);
162         }
163         vte_ring_validate(ring);
164 #endif
165 }
166
167 void
168 vte_ring_append(VteRing *ring, gpointer data)
169 {
170         vte_ring_insert(ring, ring->delta + ring->length, data);
171 }
172
173 gpointer
174 vte_ring_at(VteRing *ring, long position)
175 {
176         if (ring->array[position % ring->max] == NULL) {
177                 g_error("NULL at %ld(%ld) delta %ld, length %ld.\n",
178                         position, position % ring->max,
179                         ring->delta, ring->length);
180         }
181         g_assert(ring->array[position % ring->max] != NULL);
182         return ring->array[position % ring->max];
183 }
184
185 gboolean
186 vte_ring_contains(VteRing *ring, long position)
187 {
188         return (position >= ring->delta) &&
189                (position < (ring->delta + ring->length));
190 }
191
192 long
193 vte_ring_delta(VteRing *ring)
194 {
195         return ring->delta;
196 }
197
198 long
199 vte_ring_length(VteRing *ring)
200 {
201         return ring->length;
202 }
203
204 long
205 vte_ring_next(VteRing *ring)
206 {
207         return ring->delta + ring->length;
208 }
209
210 void
211 vte_ring_free(VteRing *ring, gboolean free)
212 {
213         long i;
214         if (free) {
215                 for (i = 0; i < ring->max; i++) {
216                         if (ring->array[i]) {
217                                 ring->free(ring->array[i], ring->user_data);
218                                 ring->array[i] = NULL;
219                         }
220                 }
221         }
222         g_free(ring->array);
223         memset(ring, 0, sizeof(ring));
224         g_free(ring);
225 }
226
227 #ifdef RING_MAIN
228 static void
229 scrolled_off(gpointer freed, gpointer data)
230 {
231         long *l = (long *)freed;
232         char *fmt = data;
233         g_print(fmt, *l);
234 }
235
236 int
237 main(int argc, char **argv)
238 {
239         long i, j, k, bias;
240         const int size = 8;
241         long values[24];
242         long lone = 42;
243         long *value;
244         VteRing *ring;
245
246         for (i = 0; i < G_N_ELEMENTS(values); i++) {
247                 values[i] = i;
248         }
249
250         ring = vte_ring_new(size, scrolled_off, "Lost value %ld.\n");
251         bias = 0;
252         fprintf(stderr, "Initializing.\n");
253         for (i = 0; i + bias <= G_N_ELEMENTS(values); i++) {
254                 k = 0;
255                 fprintf(stderr, "[%ld] ", i);
256                 for (j = 0; j < G_N_ELEMENTS(values); j++) {
257                         value = vte_ring_index(ring, long *, j);
258                         if (value) {
259                                 fprintf(stderr, "%s%ld->%ld",
260                                         (k > 0) ? ", " : "",
261                                         j, *value);
262                                 k++;
263                         }
264                 }
265                 fprintf(stderr, "\n");
266                 fprintf(stderr, "[%ld] max %ld, delta %ld, length %ld = {",
267                         i, ring->max, ring->delta, ring->length);
268                 for (j = 0; j < size; j++) {
269                         value = ring->array[j];
270                         if (j > 0) {
271                                 fprintf(stderr, ", ");
272                         }
273                         if (value) {
274                                 fprintf(stderr, "%ld", *value);
275                         }
276                 }
277                 fprintf(stderr, "}\n");
278                 if (i == 3) {
279                         fprintf(stderr, "Removing item 3.\n");
280                         vte_ring_remove(ring, 4, TRUE);
281                         bias--;
282                 } else
283                 if (i == 10) {
284                         fprintf(stderr, "Inserting item 7.\n");
285                         vte_ring_insert(ring, 7, &lone);
286                         bias--;
287                 } else
288                 if (i == 20) {
289                         fprintf(stderr, "Inserting item 13.\n");
290                         vte_ring_insert(ring, 13, &lone);
291                         bias--;
292                 } else
293                 if (i < G_N_ELEMENTS(values)) {
294                         fprintf(stderr, "Appending item.\n");
295                         vte_ring_append(ring, &values[i + bias]);
296                 }
297         }
298
299         vte_ring_free(ring, TRUE);
300
301         return 0;
302 }
303 #endif