drlvm/vm/gc_gen/src/utils/vector_block.h

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Xiao-Feng Li, 2006/10/25
 */
 
#ifndef _VECTOR_BLOCK_H_
#define _VECTOR_BLOCK_H_

typedef struct Vector_Block{
  void* next; /* point to next block */
  POINTER_SIZE_INT* head;  /* point to the first filled entry */
  POINTER_SIZE_INT* tail;  /* point to the entry after the last filled one */
  POINTER_SIZE_INT* heap_end;   /* point to heap_end of the block (right after the last entry) */
  POINTER_SIZE_INT entries[1];
}Vector_Block;


/* this size better be 2's power */
#define VECTOR_BLOCK_DATA_SIZE_BYTES (2*KB)

#define VECTOR_BLOCK_HEADER_SIZE_BYTES ((POINTER_SIZE_INT)((Vector_Block*)0)->entries)
#define VECTOR_BLOCK_ENTRY_NUM ((VECTOR_BLOCK_DATA_SIZE_BYTES - VECTOR_BLOCK_HEADER_SIZE_BYTES) >> BIT_SHIFT_TO_BYTES_OF_POINTER_SIZE_INT )
#define VECTOR_BLOCK_LOW_MASK ((POINTER_SIZE_INT)(VECTOR_BLOCK_DATA_SIZE_BYTES - 1))
#define VECTOR_BLOCK_HIGH_MASK (~VECTOR_BLOCK_LOW_MASK)
#define VECTOR_BLOCK_HEADER(addr) ((Vector_Block *)((POINTER_SIZE_INT)(addr) & VECTOR_BLOCK_HIGH_MASK))

inline void vector_block_init(Vector_Block* block, unsigned int size)
{
  block->heap_end = (POINTER_SIZE_INT*)((POINTER_SIZE_INT)block + size);
  block->head = (POINTER_SIZE_INT*)block->entries;
  block->tail = (POINTER_SIZE_INT*)block->entries;
  memset(block->entries, 0, (POINTER_SIZE_INT)block->heap_end - (POINTER_SIZE_INT)block->entries);
  return;  
}

inline unsigned int vector_block_entry_count(Vector_Block* block)
{ return (unsigned int)(block->tail - block->head); }

inline Boolean vector_block_is_full(Vector_Block* block)
{ return block->tail == block->heap_end; }

/*
inline Boolean vector_block_is_empty(Vector_Block* block)
{ return block->tail == block->head; }

inline Boolean vector_block_is_full(Vector_Block* block)
{ return (block->tail - block->entries) == VECTOR_BLOCK_ENTRY_NUM; }
*/

inline Boolean vector_block_is_empty(Vector_Block* block)
{ return block->tail == block->head; }

inline void vector_block_add_entry(Vector_Block* block, POINTER_SIZE_INT value)
{
#ifdef _DEBUG 
  assert(value && !*(block->tail));
#endif

  *(block->tail++) = value; 
}

inline POINTER_SIZE_INT vector_block_get_entry(Vector_Block* block)
{
#ifdef _DEBUG
  assert(!vector_block_is_empty(block));
#endif

  POINTER_SIZE_INT value = *(block->head++);

#ifdef _DEBUG
  assert(value);
#endif
  return value;
}
inline void vector_block_set_at_index(Vector_Block* block, unsigned int index, POINTER_SIZE_INT value)
{
#ifdef _DEBUG 
  assert(index < VECTOR_BLOCK_ENTRY_NUM);
#endif
  block->entries[index] = value;
}
inline POINTER_SIZE_INT vector_block_get_at_index(Vector_Block* block, unsigned int index)
{
#ifdef _DEBUG 
  assert(index < VECTOR_BLOCK_ENTRY_NUM);
#endif
  return block->entries[index];
}

#define VECTOR_BLOCK_SHARE_BIT 0x01
#define VECTOR_BLOCK_FULL_BIT  0x02
#define VECTOR_BLOCK_SHARE_ID_SHIFT 0x05
#define VECTOR_BLOCK_EXCLUSIVE_ID 0xFFff
inline Boolean vector_block_is_shared(Vector_Block* block)
{
  return (Boolean)((POINTER_SIZE_INT)block->next & VECTOR_BLOCK_SHARE_BIT);
}

inline Boolean vector_block_is_set_full(Vector_Block* block)
{
  return (Boolean)((POINTER_SIZE_INT)block->next & VECTOR_BLOCK_FULL_BIT);
}

inline Boolean vector_block_set_full(Vector_Block* block)
{
  POINTER_SIZE_INT old_shared_var = (POINTER_SIZE_INT) block->next;
  POINTER_SIZE_INT new_shared_var = old_shared_var | VECTOR_BLOCK_FULL_BIT;

  while(TRUE){
    POINTER_SIZE_INT old_var = (POINTER_SIZE_INT)atomic_casptr((volatile void **)& block->next ,(void*) new_shared_var,(void*) old_shared_var);
    if(old_var == old_shared_var) return TRUE;
    old_shared_var = (POINTER_SIZE_INT) block->next;
    new_shared_var = old_shared_var | VECTOR_BLOCK_FULL_BIT;
  }
  assert(0);
  return FALSE;

}

inline Boolean vector_block_set_shared(Vector_Block* block, unsigned int share_id)
{
  POINTER_SIZE_INT new_shared_var = (POINTER_SIZE_INT)((share_id << VECTOR_BLOCK_SHARE_ID_SHIFT) | VECTOR_BLOCK_SHARE_BIT);
  POINTER_SIZE_INT old_shared_var = (POINTER_SIZE_INT) block->next;
  if(old_shared_var != 0) return FALSE;

  while(TRUE){
    POINTER_SIZE_INT old_var = (POINTER_SIZE_INT)atomic_casptr((volatile void **)& block->next ,(void*) new_shared_var,(void*) old_shared_var);
    if(old_var == old_shared_var) return TRUE;
    old_shared_var = (POINTER_SIZE_INT) block->next;
    if(old_shared_var != 0) return FALSE;
  }    
}

inline Boolean vector_block_not_full_set_unshared(Vector_Block* block)
{
  POINTER_SIZE_INT new_shared_var = (POINTER_SIZE_INT) 0;
  POINTER_SIZE_INT old_shared_var = (POINTER_SIZE_INT) block->next;

  if(old_shared_var & VECTOR_BLOCK_FULL_BIT) return FALSE;

  while(TRUE){
    POINTER_SIZE_INT old_var = (POINTER_SIZE_INT)atomic_casptr((volatile void **)& block->next ,(void*) new_shared_var,(void*) old_shared_var);
    if(old_var == old_shared_var) return TRUE;
    old_shared_var = (POINTER_SIZE_INT) block->next;
    if(old_shared_var & VECTOR_BLOCK_FULL_BIT) return FALSE;    
  }
  assert(0);
  return FALSE;
}

inline Boolean vector_block_set_exclusive(Vector_Block* block)
{
  POINTER_SIZE_INT new_shared_var = (POINTER_SIZE_INT)((VECTOR_BLOCK_EXCLUSIVE_ID << VECTOR_BLOCK_SHARE_ID_SHIFT) | VECTOR_BLOCK_SHARE_BIT);
  POINTER_SIZE_INT old_shared_var = (POINTER_SIZE_INT) block->next;
  if(old_shared_var & VECTOR_BLOCK_SHARE_BIT) return FALSE;

  while(TRUE){
    POINTER_SIZE_INT old_var = (POINTER_SIZE_INT)atomic_casptr((volatile void **)& block->next ,(void*) new_shared_var,(void*) old_shared_var);
    if(old_var == old_shared_var) return TRUE;
    old_shared_var = (POINTER_SIZE_INT) block->next;
    if(old_shared_var & VECTOR_BLOCK_SHARE_BIT) return FALSE;
  }
}

inline void vector_block_clear(Vector_Block* block)
{
  block->head = (POINTER_SIZE_INT*)block->entries;
  block->tail = (POINTER_SIZE_INT*)block->entries;
#ifdef _DEBUG
  memset(block->entries, 0, (POINTER_SIZE_INT)block->heap_end - (POINTER_SIZE_INT)block->entries);
#endif
}

inline void vector_block_set_zero(Vector_Block* block)
{
  block->head = (POINTER_SIZE_INT*)block->entries;
  block->tail = (POINTER_SIZE_INT*)block->entries;
  memset(block->entries, 0, (POINTER_SIZE_INT)block->heap_end - (POINTER_SIZE_INT)block->entries);
}

/* Below is for sequential local access */
inline POINTER_SIZE_INT* vector_block_iterator_init(Vector_Block* block)
{  return block->head;  }

inline POINTER_SIZE_INT* vector_block_iterator_advance(Vector_Block* block, POINTER_SIZE_INT* iter)
{  return ++iter; }

inline Boolean vector_block_iterator_end(Vector_Block* block, POINTER_SIZE_INT* iter)
{  return iter == block->tail; }

inline POINTER_SIZE_INT* vector_block_get_last_entry(Vector_Block* block)
{ return block->tail; }

/* Below is to use Vector_Block as stack (for trace-forwarding DFS order ) */
inline void vector_stack_init(Vector_Block* block)
{ 
  block->tail = block->heap_end;
  block->head = block->heap_end;  
}

inline void vector_stack_clear(Vector_Block* block)
{
  vector_stack_init(block);
#ifdef _DEBUG
  memset(block->entries, 0, (POINTER_SIZE_INT)block->heap_end - (POINTER_SIZE_INT)block->entries);
#endif
}

inline Boolean vector_stack_is_empty(Vector_Block* block)
{  return (block->head == block->tail); }

/*
inline Boolean vector_stack_is_empty(Vector_Block* block)
{ return (block->head - block->entries) == VECTOR_BLOCK_ENTRY_NUM; }
*/

inline Boolean vector_stack_is_full(Vector_Block* block)
{  return (block->head == block->entries); }

inline void vector_stack_push(Vector_Block* block, POINTER_SIZE_INT value)
{ 
  block->head--;
#ifdef _DEBUG
  assert(value && !*(block->head));
#endif
  *(block->head) = value;
}

inline POINTER_SIZE_INT vector_stack_pop(Vector_Block* block)
{   
  POINTER_SIZE_INT value = *block->head;
#ifdef _DEBUG
  *block->head = 0;
#endif
  block->head++;
  return value;
}

inline POINTER_SIZE_INT vector_stack_read(Vector_Block* block, int idx)
{
	return block->head[idx];
}

inline void vector_block_integrity_check(Vector_Block* block)
{
  POINTER_SIZE_INT* iter = vector_block_iterator_init(block);
  while(!vector_block_iterator_end(block, iter)){
    assert(*iter);
    iter = vector_block_iterator_advance(block, iter);
  }    
  return;
}

#endif /* #ifndef _VECTOR_BLOCK_H_ */