// Return the size of the given block in multiples of the word size
static inline unsigned int block_size(const uint32_t* block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    //return (block[0] & 0x3FFFFFFF);
	return (*block)&(~0x7);

}

// RETURNS: true iff the given trie TR contains a member that equal to s
bool trie_member(trie TR, char *s) {
  REQUIRES(is_trie(TR));
  REQUIRES(s != NULL && strlen(s) > 0);

  tnode *T = tnode_lookup(TR->root, s, 0);

  return T != NULL && T->is_end;
}

bool trie_prefix(trie TR, char *s) {
  REQUIRES(is_trie(TR));
  REQUIRES(s != NULL && strlen(s) > 0);

  tnode *T = tnode_lookup(TR->root, s, 0);

  return T != NULL && T->middle != NULL;
}

// Mark the given block as free(1)/alloced(0) by marking the header and footer.
static inline void block_mark(uint32_t* block, int free) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    unsigned int next = block_size(block) + 1;
    block[0] = free ? block[0] & (int) 0xBFFFFFFF : block[0] | 0x40000000;
    block[next] = block[0];
}

// Set the size of the given block in multiples of 4 bytes
static inline void set_size(uint32_t* const block, unsigned int size) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));
    REQUIRES(size % 2 == 0);


    set_val(block, size);
}

// Return a pointer to the memory malloc should return
static inline uint32_t* block_mem(uint32_t* const block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));
    REQUIRES(aligned(block + 1));
    if (VERBOSE)
        printf("Heap size = %d bytes \n", (int)mem_heapsize());
    return block + 1;
}

static void checkblock(void *bp)
{
    REQUIRES (bp!=NULL);
    REQUIRES ((size_t)(bp)%8 == 0);
    if ((size_t)bp % 8)
      printf("Error: %p is not doubleword aligned\n", bp);
    if (GET(HDRP(GET_LOC(bp))) != GET(FTRP(GET_LOC(bp))))
      printf("Error: header does not match footer\n");
}

static int readRDNcomponent( INOUT STREAM *stream, 
							 INOUT DN_COMPONENT **dnComponentListPtrPtr,
							 IN_LENGTH_SHORT const int rdnDataLeft )
	{	
	CRYPT_ERRTYPE_TYPE dummy;
	BYTE stringBuffer[ MAX_ATTRIBUTE_SIZE + 8 ];
	void *value;
	const int rdnStart = stell( stream );
	int type, valueLength, valueStringType, stringTag;
	int flags = DN_FLAG_NOCHECK, status;

	assert( isWritePtr( stream, sizeof( STREAM ) ) );
	assert( isWritePtr( dnComponentListPtrPtr, sizeof( DN_COMPONENT * ) ) );

	REQUIRES( rdnDataLeft > 0 && rdnDataLeft < MAX_INTLENGTH_SHORT );
	REQUIRES( rdnStart > 0 && rdnStart < MAX_INTLENGTH_SHORT );

	/* Read the type information for this AVA */
	status = readAVA( stream, &type, &valueLength, &stringTag );
	if( cryptStatusError( status ) )
		return( status );
	if( valueLength <= 0 )
		{
		/* Skip broken AVAs with zero-length strings */
		return( CRYPT_OK );
		}
	status = sMemGetDataBlock( stream, &value, valueLength );
	if( cryptStatusOK( status ) )
		status = sSkip( stream, valueLength );
	if( cryptStatusError( status ) )
		return( status );
	ANALYSER_HINT( value != NULL );

	/* If there's room for another AVA, mark this one as being continued.  The
	   +10 value is the minimum length for an AVA: SEQUENCE { OID, value } 
	   (2-bytes SEQUENCE + 5 bytes OID + 2 bytes (tag + length) + 1 byte min-
	   length data).  We don't do a simple =/!= check to get around incorrectly 
	   encoded lengths */
	if( rdnDataLeft >= ( stell( stream ) - rdnStart ) + 10 )
		flags |= DN_FLAG_CONTINUED;

	/* Convert the string into the local character set */
	status = copyFromAsn1String( stringBuffer, MAX_ATTRIBUTE_SIZE, 
								 &valueLength, &valueStringType, value, 
								 valueLength, stringTag );
	if( cryptStatusError( status ) )
		return( status );

	/* Add the DN component to the DN.  If we hit a non-memory related error
	   we turn it into a generic CRYPT_ERROR_BADDATA error since the other
	   codes are somewhat too specific for this case, something like 
	   CRYPT_ERROR_INITED or an arg error isn't too useful for the caller */
	status = insertDNstring( dnComponentListPtrPtr, type, stringBuffer, 
							 valueLength, valueStringType, flags, &dummy );
	return( ( cryptStatusError( status ) && status != CRYPT_ERROR_MEMORY ) ? \
			CRYPT_ERROR_BADDATA : status );
	}

/*
 * Merge block with adjacent free blocks
 * Return: the pointer to the new free block 
 */
static void *coalesce(void *block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    uint32_t *prev_block = block_prev(block);
    uint32_t *next_block = block_next(block);
    int prev_free = block_free(prev_block);
    int next_free = block_free(next_block);
    unsigned int words = block_size(block);
    

    if (prev_free && next_free) {       // Case 4, both free

        block_delete(prev_block);
        block_delete(next_block);

        words += block_size(prev_block) + block_size(next_block) + 4;
        set_size(prev_block, words);
        block_mark(prev_block, FREE);
        block = (void *)prev_block;

        block_insert(block);
        ENSURES(in_list(block));    
    }

    else if (!prev_free && next_free) { // Case 2, next if free

        block_delete(next_block);

        words += block_size(next_block) + 2;
        set_size(block, words);
        block_mark(block, FREE);  

        block_insert(block);
        ENSURES(in_list(block));      
    }

    else if (prev_free && !next_free) { // Case 3, prev is free
        block_delete(prev_block);

        words += block_size(prev_block) + 2;
        set_size(prev_block, words);
        block_mark(prev_block, FREE);
        block = (void *)prev_block;

        block_insert(block);
        ENSURES(in_list(block));
    }

    else {                              // Case 1, both unfree
        block_insert(block);
        ENSURES(in_list(block));
        return block;
    }
    return block;
 } 

static int insertMemBlock( INOUT MEM_INFO_HEADER **allocatedListHeadPtr, 
						   INOUT MEM_INFO_HEADER **allocatedListTailPtr, 
						   INOUT MEM_INFO_HEADER *memHdrPtr )
	{
	MEM_INFO_HEADER *allocatedListHead = *allocatedListHeadPtr;
	MEM_INFO_HEADER *allocatedListTail = *allocatedListTailPtr;

	assert( isWritePtr( allocatedListHeadPtr, sizeof( MEM_INFO_HEADER * ) ) );
	assert( allocatedListHead == NULL || \
			isWritePtr( allocatedListHead, sizeof( MEM_INFO_HEADER ) ) );
	assert( isWritePtr( allocatedListTailPtr, sizeof( MEM_INFO_HEADER * ) ) );
	assert( allocatedListTail == NULL || \
			isWritePtr( allocatedListTail, sizeof( MEM_INFO_HEADER ) ) );
	assert( isWritePtr( memHdrPtr, sizeof( MEM_INFO_HEADER * ) ) );

	/* Precondition: The memory block list is empty, or there's at least a 
	   one-entry list present */
	REQUIRES( ( allocatedListHead == NULL && allocatedListTail == NULL ) || \
			  ( allocatedListHead != NULL && allocatedListTail != NULL ) );

	/* If it's a new list, set up the head and tail pointers and return */
	if( allocatedListHead == NULL )
		{
		/* In yet another of gcc's endless supply of compiler bugs, if the
		   following two lines of code are combined into a single line then
		   the write to the first value, *allocatedListHeadPtr, ends up 
		   going to some arbitrary memory location and only the second
		   write goes to the correct location (completely different code is
		   generated for the two writes)  This leaves 
		   krnlData->allocatedListHead as a NULL pointer, leading to an
		   exception being triggered the next time that it's accessed */
#if defined( __GNUC__ ) && ( __GNUC__ == 4 )
		*allocatedListHeadPtr = memHdrPtr;
		*allocatedListTailPtr = memHdrPtr;
#else
		*allocatedListHeadPtr = *allocatedListTailPtr = memHdrPtr;
#endif /* gcc 4.x compiler bug */

		return( CRYPT_OK );
		}

	/* It's an existing list, add the new element to the end */
	REQUIRES( checkMemBlockHdr( allocatedListTail ) );
	allocatedListTail->next = memHdrPtr;
	setMemChecksum( allocatedListTail );
	memHdrPtr->prev = allocatedListTail;
	*allocatedListTailPtr = memHdrPtr;

	/* Postcondition: The new block has been linked into the end of the 
	   list */
	ENSURES( allocatedListTail->next == memHdrPtr && \
			 memHdrPtr->prev == allocatedListTail && \
			 memHdrPtr->next == NULL );

	return( CRYPT_OK );
	}

void bst_insert(bst B, elem x)
{
  REQUIRES(is_bst(B));
  REQUIRES(x != NULL);

  B->root = tree_insert(B->root, x, B);

  ENSURES(is_bst(B));
  return;
}

gmacError_t
Mode::memset(accptr_t addr, int c, size_t size)
{
    REQUIRES(addr != 0);
    REQUIRES(size > 0);

    gmacError_t ret;
    ret = Parent::memset(addr, c, size);

    return ret;
}

static int deleteItemFunction( DEVICE_INFO *deviceInfo,
							   const KEYMGMT_ITEM_TYPE itemType,
							   const CRYPT_KEYID_TYPE keyIDtype,
							   const void *keyID, const int keyIDlength )
	{
	HARDWARE_INFO *hardwareInfo = deviceInfo->deviceHardware;
	MESSAGE_KEYMGMT_INFO getkeyInfo, deletekeyInfo;
	int status;

	assert( isWritePtr( deviceInfo, sizeof( DEVICE_INFO ) ) );
	assert( isReadPtr( keyID, keyIDlength ) );

	REQUIRES( itemType == KEYMGMT_ITEM_PUBLICKEY || \
			  itemType == KEYMGMT_ITEM_PRIVATEKEY );
	REQUIRES( keyIDtype == CRYPT_KEYID_NAME );
	REQUIRES( keyIDlength > 0 && keyIDlength <= CRYPT_MAX_TEXTSIZE );

	/* Perform the delete both from the PKCS #15 storage object and the
	   native storage.  This gets a bit complicated because in order to 
	   find the hardware object we have to extract the storageID, and in
	   order to get that we have to instantiate a dummy private-key object
	   to contain it.  In addition if the object that's stored isn't a
	   private-key object then there's no associated cryptographic 
	   hardware object.  To handle this we try and instantiate a dummy
	   private-key object in order to get the storageID.  If this succeeds,
	   we locate the underlying hardware object and delete it.  Finally, we
	   delete the PKCS #15 object, either a pure public-key/certificate 
	   object or the private-key metadata for the cryptographic hardware
	   object */
	if( hardwareInfo->iCryptKeyset == CRYPT_ERROR )
		return( CRYPT_ERROR_NOTINITED );
	setMessageKeymgmtInfo( &getkeyInfo, keyIDtype, keyID, keyIDlength,
						   NULL, 0, KEYMGMT_FLAG_NONE );
	status = krnlSendMessage( hardwareInfo->iCryptKeyset,
							  IMESSAGE_KEY_GETKEY, &getkeyInfo,
							  KEYMGMT_ITEM_PRIVATEKEY );
	if( cryptStatusOK( status ) )
		{
		int keyHandle;

		/* It's a private-key object, get its hardware reference and delete 
		   it.  If this fails we continue anyway because we know that 
		   there's also a PKCS #15 object to delete */
		status = getHardwareReference( getkeyInfo.cryptHandle, &keyHandle );
		if( cryptStatusOK( status ) )
			( void ) hwDeleteItem( keyHandle );
		krnlSendNotifier( getkeyInfo.cryptHandle, IMESSAGE_DECREFCOUNT );
		}
	setMessageKeymgmtInfo( &deletekeyInfo, keyIDtype, keyID, keyIDlength,
						   NULL, 0, KEYMGMT_FLAG_NONE );
	return( krnlSendMessage( hardwareInfo->iCryptKeyset,
							 IMESSAGE_KEY_DELETEKEY, &deletekeyInfo,
							 itemType ) );
	}

static void add_block_to_list(int index, void* block){
    REQUIRES(0 <= index && index <= NUM_FREE_LISTS);
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    set_prev_pointer(block, NULL);
    set_next_pointer(block, free_lists[index]);

    if(free_lists[index] != NULL) set_prev_pointer(free_lists[index], block);
    free_lists[index] = block;
}

// GIVEN: a tnode T and a non-empty string s[i,)
// RETURNS: if s[i,) is a prefix of T, return the node that corresponding
// to the last char of s, otherwise return NULL
tnode *tnode_lookup(tnode *T, char *s, size_t i) {
  REQUIRES(is_tnode_root(T));
  REQUIRES(s != NULL);
  REQUIRES(i < strlen(s));

  if (T == NULL) return NULL;
  if (s[i] < T->c) return tnode_lookup(T->left, s, i);
  if (s[i] > T->c) return tnode_lookup(T->right, s, i);
  if (s[i+1] == '\0') return T;

  return tnode_lookup(T->middle, s, i+1);
}

bool is_heap_except_down(heap H, int n)
{
  REQUIRES(is_safe_heap(H));
  REQUIRES(1 <= n && n < H->next);
  for (int i = 2; i < H->next; i++)
  {
    ASSERT(2 <= i);
    if (!(i/2 == n || ok_above(H, i/2, i)))
      return false;
  }
  return true;
}

queue_elem deq(queue *Q) {
  REQUIRES(is_queue(Q));
  REQUIRES(!queue_empty(Q));

  queue_elem x = Q->front->data;  /* save old queue element to return */
  list *q = Q->front;             /* save old list node to free */
  Q->front = Q->front->next;
  free(q);                      /* free old list node */

  ENSURES(is_queue(Q));
  return x;                     /* return old queue element */
}

int dynCreate( OUT DYNBUF *dynBuf, 
			   IN_HANDLE const CRYPT_HANDLE cryptHandle,
			   IN_ATTRIBUTE const CRYPT_ATTRIBUTE_TYPE attributeType )
	{
	assert( isWritePtr( dynBuf, sizeof( DYNBUF ) ) );

	REQUIRES( isHandleRangeValid( cryptHandle ) );
	REQUIRES( isAttribute( attributeType ) || \
			  isInternalAttribute( attributeType ) );

	return( getDynData( dynBuf, cryptHandle, IMESSAGE_GETATTRIBUTE_S,
						attributeType ) );
	}

// DETAILS: s might contains '*' which representa arbitrary number of arbitrary
// character
// EFFECT: add all members in the given T that match the given string
// s to q
void trie_member_generalized(trie T, char *s, Queue q) {
  REQUIRES(is_trie(T));
  REQUIRES(s != NULL);
  REQUIRES(is_Queue(q));

  struct strbuf *sb = strbuf_new(8);
  tnode_lookup_generalized(T->root, s, 0, strlen(s), sb, q);
  free(strbuf_dealloc(sb));

  ENSURES(is_Queue(q));
  return;

}

// Return the header to the successor free block
static inline uint32_t* block_succ(uint32_t* const block) {
    REQUIRES(block != NULL);
    REQUIRES(in_heap(block));

    uint32_t * address = heap_listp + block[2];

    ENSURES(address != NULL);
    ENSURES(in_heap(address));

    if (address == heap_listp)
        return NULL;
    else 
        return address;
}