[vte] [ring] Allocate main row array in powers of two

[Behdad Esfahbod <behdad src gnome org>]

commit 0a855cc5c15f986607e9d2b1c77801792db796fc
Author: Behdad Esfahbod <behdad behdad org>
Date:   Sat Sep 5 23:58:33 2009 -0400

    [ring] Allocate main row array in powers of two
    
    This way we can use a bitwise-and to index, instead of int division

 src/ring.c |   39 +++++++++++++++++++++++++--------------
 src/ring.h |    4 ++--
 2 files changed, 27 insertions(+), 16 deletions(-)
---
diff --git a/src/ring.c b/src/ring.c
index 7a8bfb5..3d01e1b 100644
--- a/src/ring.c
+++ b/src/ring.c
@@ -311,8 +311,8 @@ _vte_ring_validate (VteRing * ring)
 	guint i, max;
 	g_assert(ring != NULL);
 	_vte_debug_print(VTE_DEBUG_RING,
-			" Delta = %u, Length = %u, Max = %u.\n",
-			ring->delta, ring->length, ring->max);
+			" Delta = %u, Length = %u, Max = %u, Mask = %x.\n",
+			ring->delta, ring->length, ring->max, ring->mask);
 	g_assert(ring->length <= ring->max);
 	max = ring->delta + ring->length;
 	for (i = ring->delta; i < max; i++)
@@ -322,6 +322,7 @@ _vte_ring_validate (VteRing * ring)
 #define _vte_ring_validate(ring) G_STMT_START {} G_STMT_END
 #endif
 
+#define VTE_RING_MASK_FOR_MAX_ROWS(max_rows) ((1 << g_bit_storage ((max_rows) - 1)) - 1)
 /**
  * _vte_ring_new:
  * @max_rows: the maximum size the new ring will be allowed to reach
@@ -335,7 +336,8 @@ _vte_ring_new (guint max_rows)
 {
 	VteRing *ring = g_slice_new0(VteRing);
 	ring->max = MAX(max_rows, 2);
-	ring->array = g_malloc0(sizeof(ring->array[0]) * ring->max);
+	ring->mask = VTE_RING_MASK_FOR_MAX_ROWS (ring->max);
+	ring->array = g_malloc0 (sizeof (ring->array[0]) * (ring->mask + 1));
 
 	_vte_debug_print(VTE_DEBUG_RING, "New ring %p.\n", ring);
 	_vte_ring_validate(ring);
@@ -355,7 +357,7 @@ void
 _vte_ring_free (VteRing *ring)
 {
 	guint i;
-	for (i = 0; i < ring->max; i++)
+	for (i = 0; i <= ring->mask; i++)
 		_vte_row_data_fini (&ring->array[i]);
 	g_free(ring->array);
 	g_slice_free(VteRing, ring);
@@ -373,7 +375,7 @@ _vte_ring_free (VteRing *ring)
 void
 _vte_ring_resize (VteRing *ring, guint max_rows)
 {
-	guint position, end, old_max;
+	guint position, end, old_max, old_mask;
 	VteRowData *old_array;
 
 	max_rows = MAX(max_rows, 2);
@@ -384,16 +386,27 @@ _vte_ring_resize (VteRing *ring, guint max_rows)
 	_vte_debug_print(VTE_DEBUG_RING, "Resizing ring.\n");
 	_vte_ring_validate(ring);
 
+	end = ring->delta + ring->length;
+
 	old_max = ring->max;
+	old_mask = ring->mask;
 	old_array = ring->array;
 
 	ring->max = max_rows;
-	ring->array = g_malloc0(sizeof(ring->array[0]) * ring->max);
+	ring->mask = VTE_RING_MASK_FOR_MAX_ROWS (ring->max);
+	if (ring->mask != old_mask) {
+		ring->array = g_malloc0 (sizeof (ring->array[0]) * (ring->mask + 1));
+
+		for (position = ring->delta; position < end; position++) {
+			_vte_row_data_fini (_vte_ring_index(ring, position));
+			*_vte_ring_index(ring, position) = old_array[position & old_mask];
+			old_array[position & old_mask].cells = NULL;
+		}
 
-	end = ring->delta + ring->length;
-	for (position = ring->delta; position < end; position++) {
-		_vte_row_data_fini (_vte_ring_index(ring, position));
-		*_vte_ring_index(ring, position) = old_array[position % old_max];
+		for (position = 0; position <= old_mask; position++)
+			_vte_row_data_fini (&old_array[position]);
+
+		g_free (old_array);
 	}
 
 	if (ring->length > ring->max) {
@@ -401,8 +414,6 @@ _vte_ring_resize (VteRing *ring, guint max_rows)
 	  ring->delta = end - ring->max;
 	}
 
-	g_free (old_array);
-
 	_vte_ring_validate(ring);
 }
 
@@ -436,7 +447,7 @@ _vte_ring_insert_internal (VteRing * ring, guint position)
 	_vte_ring_validate(ring);
 
 	for (i = ring->delta + ring->length; i > position; i--)
-		_vte_ring_swap (ring, i % ring->max, (i - 1) % ring->max);
+		_vte_ring_swap (ring, i & ring->mask, (i - 1) & ring->mask);
 
 	row = _vte_row_data_init(_vte_ring_index(ring, position));
 	if (ring->length < ring->max)
@@ -501,7 +512,7 @@ _vte_ring_remove (VteRing * ring, guint position)
 	_vte_ring_validate(ring);
 
 	for (i = position; i < ring->delta + ring->length - 1; i++)
-		_vte_ring_swap (ring, i % ring->max, (i + 1) % ring->max);
+		_vte_ring_swap (ring, i & ring->mask, (i + 1) & ring->mask);
 
 	if (ring->length > 0)
 		ring->length--;
diff --git a/src/ring.h b/src/ring.h
index 34c9510..db72d66 100644
--- a/src/ring.h
+++ b/src/ring.h
@@ -139,7 +139,7 @@ void _vte_row_data_shrink (VteRowData *row, guint max_len);
 typedef struct _VteRing VteRing;
 
 struct _VteRing {
-	guint delta, length, max;
+	guint delta, length, max, mask;
 	VteRowData *array;
 };
 
@@ -149,7 +149,7 @@ struct _VteRing {
 #define _vte_ring_delta(__ring) ((__ring)->delta + 0)
 #define _vte_ring_length(__ring) ((__ring)->length + 0)
 #define _vte_ring_next(__ring) ((__ring)->delta + (__ring)->length)
-#define _vte_ring_index(__ring, __position) (&(__ring)->array[(__position) % (__ring)->max])
+#define _vte_ring_index(__ring, __position) (&(__ring)->array[(__position) & (__ring)->mask])
 
 VteRing *_vte_ring_new (guint max_rows);
 void _vte_ring_free (VteRing *ring);