void object_done()
{
#ifdef BJAM_NEWSTR_NO_ALLOCATE
    unsigned i;
    for ( i = 0; i < strhash.num; ++i )
    {
        while ( strhash.data[ i ] )
        {
            struct hash_item * item = strhash.data[ i ];
            strhash.data[ i ] = item->header.next;
            BJAM_FREE( item );
        }
    }
#else
    /* Reclaim string blocks. */
    while ( strblock_chain )
    {
        strblock * const n = strblock_chain->next;
        BJAM_FREE( strblock_chain );
        strblock_chain = n;
    }
#endif

    string_set_done( &strhash );

    if ( DEBUG_MEM )
    {
        out_printf( "%dK in strings\n", strtotal / 1024 );
        if ( strcount_in != strcount_out )
            out_printf( "--- %d strings of %d dangling\n", strcount_in -
                strcount_out, strcount_in );
    }
}

LIST * order( FRAME * frame, int flags )
{
    LIST * arg = lol_get( frame->args, 0 );
    LIST * result = L0;
    int src;
    LISTITER iter = list_begin( arg );
    LISTITER const end = list_end( arg );

    /* We need to create a graph of order dependencies between the passed
     * objects. We assume there are no duplicates passed to 'add_pair'.
     */
    int length = list_length( arg );
    int * * graph = ( int * * )BJAM_CALLOC( length, sizeof( int * ) );
    int * order = ( int * )BJAM_MALLOC( ( length + 1 ) * sizeof( int ) );

    for ( src = 0; iter != end; iter = list_next( iter ), ++src )
    {
        /* For all objects this one depends upon, add elements to 'graph'. */
        LIST * dependencies = var_get( frame->module, list_item( iter ) );
        int index = 0;
        LISTITER dep_iter = list_begin( dependencies );
        LISTITER const dep_end = list_end( dependencies );

        graph[ src ] = ( int * )BJAM_CALLOC( list_length( dependencies ) + 1,
            sizeof( int ) );
        for ( ; dep_iter != dep_end; dep_iter = list_next( dep_iter ) )
        {
            int const dst = list_index( arg, list_item( dep_iter ) );
            if ( dst != -1 )
                graph[ src ][ index++ ] = dst;
        }
        graph[ src ][ index ] = -1;
    }

    topological_sort( graph, length, order );

    {
        int index = length - 1;
        for ( ; index >= 0; --index )
        {
            int i;
            LISTITER iter = list_begin( arg );
            LISTITER const end = list_end( arg );
            for ( i = 0; i < order[ index ]; ++i, iter = list_next( iter ) );
            result = list_push_back( result, object_copy( list_item( iter ) ) );
        }
    }

    /* Clean up */
    {
        int i;
        for ( i = 0; i < length; ++i )
            BJAM_FREE( graph[ i ] );
        BJAM_FREE( graph );
        BJAM_FREE( order );
    }

    return result;
}

void exec_done( void )
{
    int i;
    for( i = 0; i < MAXJOBS; ++i )
    {
        if( ! cmdtab[i].action ) break;
        BJAM_FREE( cmdtab[i].action );
        BJAM_FREE( cmdtab[i].target );
    }
}

void hash_free( struct hash * hp )
{
    int i;
    if ( !hp )
        return;
    if ( hp->tab.base )
        BJAM_FREE( (char *)hp->tab.base );
    for ( i = 0; i <= hp->items.list; ++i )
        BJAM_FREE( hp->items.lists[ i ].base );
    BJAM_FREE( (char *)hp );
}

void cleanup_child(int i, int status) 
{
    int         rstat;
    struct tms  new_time;
    timing_info time_info;

    cmdtab[ i ].pid = 0;

    /* Set reason for exit if not timed out. */
    if ( WIFEXITED( status ) ) {
        cmdtab[ i ].exit_reason = 0 == WEXITSTATUS( status )
            ? EXIT_OK : EXIT_FAIL;
    }

    /* Print out the rule and target name. */
    out_action( cmdtab[ i ].action, cmdtab[ i ].target,
        cmdtab[ i ].command, cmdtab[ i ].buffer[ OUT ],
        cmdtab[ i ].buffer[ ERR ], cmdtab[ i ].exit_reason
    );

    times( &new_time );

    time_info.system = (double)( new_time.tms_cstime - old_time.tms_cstime ) / CLOCKS_PER_SEC;
    time_info.user   = (double)( new_time.tms_cutime - old_time.tms_cutime ) / CLOCKS_PER_SEC;
    time_info.start  = cmdtab[ i ].start_dt;
    time_info.end    = time( 0 );

    old_time = new_time;

    if ( intr )
        rstat = EXEC_CMD_INTR;
    else if ( status != 0 )
        rstat = EXEC_CMD_FAIL;
    else
        rstat = EXEC_CMD_OK;

    /* Assume -p0 in effect so only pass buffer[ 0 ]
     * containing merged output.
     */
     (*cmdtab[ i ].func)( cmdtab[ i ].closure, rstat, &time_info, cmdtab[ i ].command, cmdtab[ i ].buffer[ 0 ] );

     BJAM_FREE( cmdtab[ i ].buffer[ OUT ] );
     cmdtab[ i ].buffer[ OUT ] = 0;

     BJAM_FREE( cmdtab[ i ].buffer[ ERR ] );
     cmdtab[ i ].buffer[ ERR ] = 0;

     BJAM_FREE( cmdtab[ i ].command );
     cmdtab[ i ].command = 0;

     cmdtab[ i ].func = 0;
     cmdtab[ i ].closure = 0;
     cmdtab[ i ].start_time = 0;
}

LIST *order( PARSE *parse, FRAME *frame )
{
    LIST* arg = lol_get( frame->args, 0 );
    LIST* tmp;
    LIST* result = 0;
    int src;

    /* We need to create a graph of order dependencies between
       the passed objects. We assume that there are no duplicates
       passed to 'add_pair'.
    */
    int length = list_length(arg);
    int** graph = (int**)BJAM_CALLOC(length, sizeof(int*));
    int* order = (int*)BJAM_MALLOC((length+1)*sizeof(int));

    for(tmp = arg, src = 0; tmp; tmp = tmp->next, ++src) {
        /* For all object this one depend upon, add elements
           to 'graph' */
        LIST* dependencies = var_get(tmp->string);
        int index = 0;

        graph[src] = (int*)BJAM_CALLOC(list_length(dependencies)+1, sizeof(int));
        for(; dependencies; dependencies = dependencies->next) {
            int dst = list_index(arg, dependencies->string);
            if (dst != -1)
                graph[src][index++] = dst;
        }
        graph[src][index] = -1;
    }

    topological_sort(graph, length, order);

    {
        int index = length-1;
        for(; index >= 0; --index) {
            int i;
            tmp = arg;
            for (i = 0; i < order[index]; ++i, tmp = tmp->next);
            result = list_new(result, tmp->string);
        }
    }

    /* Clean up */
    {
        int i;
        for(i = 0; i < length; ++i)
            BJAM_FREE(graph[i]);
        BJAM_FREE(graph);
        BJAM_FREE(order);
    }

    return result;
}

static void ps_map_destroy( struct ps_map * map )
{
    size_t i;
    for ( i = 0; i < map->table_size; ++i )
    {
        struct ps_map_entry * pos;
        for ( pos = map->table[ i ]; pos; )
        {
            struct ps_map_entry * tmp = pos->next;
            BJAM_FREE( pos );
            pos = tmp;
        }
    }
    BJAM_FREE( map->table );
}

int yyline()
{
    struct include * i = incp;

    if ( !incp )
        return EOF;

    /* Once we start reading from the input stream, we reset the include
     * insertion point so that the next include file becomes the head of the
     * list.
     */

    /* If there is more data in this line, return it. */
    if ( *i->string )
        return *i->string++;

    /* If we are reading from an internal string list, go to the next string. */
    if ( i->strings )
    {
        if ( *i->strings )
        {
            ++i->line;
            i->string = *(i->strings++);
            return *i->string++;
        }
    }
    else
    {
        /* If necessary, open the file. */
        if ( !i->file )
        {
            FILE * f = stdin;
            if ( strcmp( object_str( i->fname ), "-" ) && !( f = fopen( object_str( i->fname ), "r" ) ) )
                perror( object_str( i->fname ) );
            i->file = f;
        }

        /* If there is another line in this file, start it. */
        if ( i->file && fgets( i->buf, sizeof( i->buf ), i->file ) )
        {
            ++i->line;
            i->string = i->buf;
            return *i->string++;
        }
    }

    /* This include is done. Free it up and return EOF so yyparse() returns to
     * parse_file().
     */

    incp = i->next;

    /* Close file, free name. */
    if ( i->file && ( i->file != stdin ) )
        fclose( i->file );
    object_free( i->fname );
    BJAM_FREE( (char *)i );

    return EOF;
}

static void cmd_sem_unlock( TARGET * t )
{
    CMD * cmd = ( CMD * )t->cmds;
    TARGETS * iter;
    /* Release the semaphores. */
    for ( iter = cmd->unlock; iter; iter = iter->next )
    {
        if ( DEBUG_EXECCMD )
            printf( "SEM: %s is now free\n", object_str(
                iter->target->name ) );
        --iter->target->asynccnt;
        assert( iter->target->asynccnt <= 0 );
    }
    for ( iter = cmd->unlock; iter; iter = iter->next )
    {
        /* Find a waiting target that's ready */
        while ( iter->target->parents )
        {
            TARGETS * first = iter->target->parents;
            TARGET * t1 = first->target;

            /* Pop the first waiting CMD */
            if ( first->next )
                first->next->tail = first->tail;
            iter->target->parents = first->next;
            BJAM_FREE( first );

            if ( cmd_sem_lock( t1 ) )
            {
                push_state( &state_stack, t1, NULL, T_STATE_MAKE1C );
                break;
            }
        }
    }
}

LIST *
list_sort(
    LIST *l)
{
    int len, ii;
    char** strings;
    LIST* listp;
    LIST* result = 0;

    if (!l)
        return L0;

    len = list_length(l);
    strings = (char**)BJAM_MALLOC( len * sizeof(char*) );

    listp = l;
    for (ii = 0; ii < len; ++ii) {
        strings[ii] = listp->string;
        listp = listp->next;
    }

    qsort(strings, len, sizeof(char*), str_ptr_compare);

    for (ii = 0; ii < len; ++ii) {
        result = list_append( result, list_new(0, strings[ii]) );
    }

    BJAM_FREE(strings);

    return result;
}

static void ps_map_rehash( struct ps_map * map )
{
    struct ps_map old = *map;
    size_t i;
    map->table = BJAM_MALLOC( map->table_size * 2 * sizeof( struct ps_map_entry * ) );
    map->table_size *= 2;
    for ( i = 0; i < map->table_size; ++i )
    {
        map->table[ i ] = NULL;
    }
    for ( i = 0; i < old.table_size; ++i )
    {
        struct ps_map_entry * pos;
        for ( pos = old.table[ i ]; pos; )
        {
            struct ps_map_entry * tmp = pos->next;

            unsigned hash_val = list_hash( pos->key );
            unsigned bucket = hash_val % map->table_size;
            pos->next = map->table[ bucket ];
            map->table[ bucket ] = pos;

            pos = tmp;
        }
    }
    BJAM_FREE( old.table );
}

void cmd_free( CMD * cmd )
{
    lol_free( &cmd->args );
    list_free( cmd->shell );
    string_free( cmd->buf );
    BJAM_FREE( (void *)cmd );
}

void object_free( OBJECT * obj )
{
    object_validate( obj );
#ifdef BJAM_NO_MEM_CACHE
    BJAM_FREE( object_get_item( obj ) );
#endif
    ++strcount_out;
}

static int read_descriptor( int i, int s )
{
    int ret;
    char buffer[ BUFSIZ ];

    while ( 0 < ( ret = fread( buffer, sizeof( char ), BUFSIZ - 1,
        cmdtab[ i ].stream[ s ] ) ) )
    {
        buffer[ ret ] = 0;

        /* Copy it to our output if appropriate */
        if ( ! ( cmdtab[ i ].flags & EXEC_CMD_QUIET ) )
        {
            if ( s == OUT && ( globs.pipe_action != 2 ) )
                out_data( buffer );
            else if ( s == ERR && ( globs.pipe_action & 2 ) )
                err_data( buffer );
        }

        if ( !cmdtab[ i ].buffer[ s ] )
        {
            /* Never been allocated. */
            if ( globs.max_buf && ret > globs.max_buf )
            {
                ret = globs.max_buf;
                buffer[ ret ] = 0;
            }
            cmdtab[ i ].buf_size[ s ] = ret + 1;
            cmdtab[ i ].buffer[ s ] = (char*)BJAM_MALLOC_ATOMIC( ret + 1 );
            memcpy( cmdtab[ i ].buffer[ s ], buffer, ret + 1 );
        }
        else
        {
            /* Previously allocated. */
            if ( cmdtab[ i ].buf_size[ s ] < globs.max_buf || !globs.max_buf )
            {
                char * tmp = cmdtab[ i ].buffer[ s ];
                int const old_len = cmdtab[ i ].buf_size[ s ] - 1;
                int const new_len = old_len + ret + 1;
                cmdtab[ i ].buf_size[ s ] = new_len;
                cmdtab[ i ].buffer[ s ] = (char*)BJAM_MALLOC_ATOMIC( new_len );
                memcpy( cmdtab[ i ].buffer[ s ], tmp, old_len );
                memcpy( cmdtab[ i ].buffer[ s ] + old_len, buffer, ret + 1 );
                BJAM_FREE( tmp );
            }
        }
    }

    /* If buffer full, ensure last buffer char is newline so that jam log
     * contains the command status at beginning of it own line instead of
     * appended to end of the previous output.
     */
    if ( globs.max_buf && globs.max_buf <= cmdtab[ i ].buf_size[ s ] )
        cmdtab[ i ].buffer[ s ][ cmdtab[ i ].buf_size[ s ] - 2 ] = '\n';

    return feof( cmdtab[ i ].stream[ s ] );
}

static void clear_state_freelist()
{
    while ( state_freelist )
    {
        state * const pState = state_freelist;
        state_freelist = state_freelist->prev;
        BJAM_FREE( pState );
    }
}

void cmdlist_free( CMDLIST * l )
{
    while ( l )
    {
        CMDLIST * tmp = l->next;
        BJAM_FREE( l );
        l = tmp;
    }
}

static void clear_state_freelist()
{
	while(state_freelist != NULL)
	{
		state *pState = state_freelist;
		state_freelist = state_freelist->prev;
		BJAM_FREE(pState);
	}
}

void cmd_free( CMD * cmd )
{
    cmdlist_free( cmd->next );
    lol_free( &cmd->args );
    list_free( cmd->shell );
    string_free( cmd->buf );
    freetargets( cmd->unlock );
    BJAM_FREE( (void *)cmd );
}

static void hash_mem_free(size_t datalen, void * data)
{
    if (sizeof(HASHDATA) == datalen)
    {
        BJAM_FREE_RAW(data);
    }
    else
    {
        BJAM_FREE(data);
    }
}

/*
 * exec_done - free resources.
 */
void exec_done( void )
{
    if ( process_queue.read_okay )
    {
        CloseHandle( process_queue.read_okay );
    }
    if ( process_queue.write_okay )
    {
        CloseHandle( process_queue.write_okay );
    }
    BJAM_FREE( cmdtab );
}