+static void
+jit_info_table_check (MonoJitInfoTable *table)
+{
+ int i;
+
+ for (i = 0; i < table->num_chunks; ++i) {
+ MonoJitInfoTableChunk *chunk = table->chunks [i];
+ int j;
+
+ g_assert (chunk->refcount > 0 /* && chunk->refcount <= 8 */);
+ if (chunk->refcount > 10)
+ printf("warning: chunk refcount is %d\n", chunk->refcount);
+ g_assert (chunk->num_elements <= MONO_JIT_INFO_TABLE_CHUNK_SIZE);
+
+ for (j = 0; j < chunk->num_elements; ++j) {
+ MonoJitInfo *this = chunk->data [j];
+ MonoJitInfo *next;
+
+ g_assert ((gint8*)this->code_start + this->code_size <= chunk->last_code_end);
+
+ if (j < chunk->num_elements - 1)
+ next = chunk->data [j + 1];
+ else if (i < table->num_chunks - 1) {
+ int k;
+
+ for (k = i + 1; k < table->num_chunks; ++k)
+ if (table->chunks [k]->num_elements > 0)
+ break;
+
+ if (k >= table->num_chunks)
+ return;
+
+ g_assert (table->chunks [k]->num_elements > 0);
+ next = table->chunks [k]->data [0];
+ } else
+ return;
+
+ g_assert ((gint8*)this->code_start + this->code_size <= (gint8*)next->code_start + next->code_size);
+ }
+ }
+}
+
+static MonoJitInfoTable*
+jit_info_table_realloc (MonoJitInfoTable *old)
+{
+ int i;
+ int num_elements = jit_info_table_num_elements (old);
+ int required_size;
+ int num_chunks;
+ int new_chunk, new_element;
+ MonoJitInfoTable *new;
+
+ /* number of needed places for elements needed */
+ required_size = (int)((long)num_elements * JIT_INFO_TABLE_FILL_RATIO_DENOM / JIT_INFO_TABLE_FILL_RATIO_NOM);
+ num_chunks = (required_size + MONO_JIT_INFO_TABLE_CHUNK_SIZE - 1) / MONO_JIT_INFO_TABLE_CHUNK_SIZE;
+
+ new = g_malloc (sizeof (MonoJitInfoTable) + sizeof (MonoJitInfoTableChunk*) * num_chunks);
+ new->num_chunks = num_chunks;
+
+ for (i = 0; i < num_chunks; ++i)
+ new->chunks [i] = jit_info_table_new_chunk ();
+
+ new_chunk = 0;
+ new_element = 0;
+ for (i = 0; i < old->num_chunks; ++i) {
+ MonoJitInfoTableChunk *chunk = old->chunks [i];
+ int chunk_num_elements = chunk->num_elements;
+ int j;
+
+ for (j = 0; j < chunk_num_elements; ++j) {
+ if (!IS_JIT_INFO_TOMBSTONE (chunk->data [j])) {
+ g_assert (new_chunk < num_chunks);
+ new->chunks [new_chunk]->data [new_element] = chunk->data [j];
+ if (++new_element >= JIT_INFO_TABLE_FILLED_NUM_ELEMENTS) {
+ new->chunks [new_chunk]->num_elements = new_element;
+ ++new_chunk;
+ new_element = 0;
+ }
+ }
+ }
+ }
+
+ if (new_chunk < num_chunks) {
+ g_assert (new_chunk == num_chunks - 1);
+ new->chunks [new_chunk]->num_elements = new_element;
+ g_assert (new->chunks [new_chunk]->num_elements > 0);
+ }
+
+ for (i = 0; i < num_chunks; ++i) {
+ MonoJitInfoTableChunk *chunk = new->chunks [i];
+ MonoJitInfo *ji = chunk->data [chunk->num_elements - 1];
+
+ new->chunks [i]->last_code_end = (gint8*)ji->code_start + ji->code_size;
+ }
+
+ return new;
+}
+
+static void
+jit_info_table_split_chunk (MonoJitInfoTableChunk *chunk, MonoJitInfoTableChunk **new1p, MonoJitInfoTableChunk **new2p)
+{
+ MonoJitInfoTableChunk *new1 = jit_info_table_new_chunk ();
+ MonoJitInfoTableChunk *new2 = jit_info_table_new_chunk ();
+
+ g_assert (chunk->num_elements == MONO_JIT_INFO_TABLE_CHUNK_SIZE);
+
+ new1->num_elements = MONO_JIT_INFO_TABLE_CHUNK_SIZE / 2;
+ new2->num_elements = MONO_JIT_INFO_TABLE_CHUNK_SIZE - new1->num_elements;
+
+ memcpy ((void*)new1->data, (void*)chunk->data, sizeof (MonoJitInfo*) * new1->num_elements);
+ memcpy ((void*)new2->data, (void*)(chunk->data + new1->num_elements), sizeof (MonoJitInfo*) * new2->num_elements);
+
+ new1->last_code_end = (gint8*)new1->data [new1->num_elements - 1]->code_start
+ + new1->data [new1->num_elements - 1]->code_size;
+ new2->last_code_end = (gint8*)new2->data [new2->num_elements - 1]->code_start
+ + new2->data [new2->num_elements - 1]->code_size;
+
+ *new1p = new1;
+ *new2p = new2;
+}
+
+static MonoJitInfoTable*
+jit_info_table_copy_and_split_chunk (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
+{
+ MonoJitInfoTable *new_table = g_malloc (sizeof (MonoJitInfoTable)
+ + sizeof (MonoJitInfoTableChunk*) * (table->num_chunks + 1));
+ int i, j;
+
+ new_table->num_chunks = table->num_chunks + 1;
+
+ j = 0;
+ for (i = 0; i < table->num_chunks; ++i) {
+ if (table->chunks [i] == chunk) {
+ jit_info_table_split_chunk (chunk, &new_table->chunks [j], &new_table->chunks [j + 1]);
+ j += 2;
+ } else {
+ new_table->chunks [j] = table->chunks [i];
+ ++new_table->chunks [j]->refcount;
+ ++j;
+ }
+ }
+
+ g_assert (j == new_table->num_chunks);
+
+ return new_table;
+}
+
+static MonoJitInfoTableChunk*
+jit_info_table_purify_chunk (MonoJitInfoTableChunk *old)
+{
+ MonoJitInfoTableChunk *new = jit_info_table_new_chunk ();
+ int i, j;
+
+ j = 0;
+ for (i = 0; i < old->num_elements; ++i) {
+ if (!IS_JIT_INFO_TOMBSTONE (old->data [i]))
+ new->data [j++] = old->data [i];
+ }
+
+ new->num_elements = j;
+ if (new->num_elements > 0)
+ new->last_code_end = (gint8*)new->data [j - 1]->code_start + new->data [j - 1]->code_size;
+ else
+ new->last_code_end = old->last_code_end;
+
+ return new;
+}
+
+static MonoJitInfoTable*
+jit_info_table_copy_and_purify_chunk (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
+{
+ MonoJitInfoTable *new_table = g_malloc (sizeof (MonoJitInfoTable)
+ + sizeof (MonoJitInfoTableChunk*) * table->num_chunks);
+ int i, j;
+
+ new_table->num_chunks = table->num_chunks;
+
+ j = 0;
+ for (i = 0; i < table->num_chunks; ++i) {
+ if (table->chunks [i] == chunk)
+ new_table->chunks [j++] = jit_info_table_purify_chunk (table->chunks [i]);
+ else {
+ new_table->chunks [j] = table->chunks [i];
+ ++new_table->chunks [j]->refcount;
+ ++j;
+ }
+ }
+
+ g_assert (j == new_table->num_chunks);
+
+ return new_table;
+}
+
+/* As we add an element to the table the case can arise that the chunk
+ * to which we need to add is already full. In that case we have to
+ * allocate a new table and do something about that chunk. We have
+ * several strategies:
+ *
+ * If the number of elements in the table is below the low watermark
+ * or above the high watermark, we reallocate the whole table.
+ * Otherwise we only concern ourselves with the overflowing chunk:
+ *
+ * If there are no tombstones in the chunk then we split the chunk in
+ * two, each half full.
+ *
+ * If the chunk does contain tombstones, we just make a new copy of
+ * the chunk without the tombstones, which will have room for at least
+ * the one element we have to add.
+ */
+static MonoJitInfoTable*
+jit_info_table_chunk_overflow (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
+{
+ int num_elements = jit_info_table_num_elements (table);
+ int i;
+
+ if (num_elements < JIT_INFO_TABLE_LOW_WATERMARK (table->num_chunks * MONO_JIT_INFO_TABLE_CHUNK_SIZE)
+ || num_elements > JIT_INFO_TABLE_HIGH_WATERMARK (table->num_chunks * MONO_JIT_INFO_TABLE_CHUNK_SIZE)) {
+ //printf ("reallocing table\n");
+ return jit_info_table_realloc (table);
+ }
+
+ /* count the number of non-tombstone elements in the chunk */
+ num_elements = 0;
+ for (i = 0; i < chunk->num_elements; ++i) {
+ if (!IS_JIT_INFO_TOMBSTONE (chunk->data [i]))
+ ++num_elements;
+ }
+
+ if (num_elements == MONO_JIT_INFO_TABLE_CHUNK_SIZE) {
+ //printf ("splitting chunk\n");
+ return jit_info_table_copy_and_split_chunk (table, chunk);
+ }
+
+ //printf ("purifying chunk\n");
+ return jit_info_table_copy_and_purify_chunk (table, chunk);
+}
+
+/* We add elements to the table by first making space for them by
+ * shifting the elements at the back to the right, one at a time.
+ * This results in duplicate entries during the process, but during
+ * all the time the table is in a sorted state. Also, when an element
+ * is replaced by another one, the element that replaces it has an end
+ * address that is equal to or lower than that of the replaced
+ * element. That property is necessary to guarantee that when
+ * searching for an element we end up at a position not higher than
+ * the one we're looking for (i.e. we either find the element directly
+ * or we end up to the left of it).
+ */