path: root/window-table.c

/*
 * window-table.c
 *
 * Part of gwm, the Gratuitous Window Manager,
 *     by Gary Wong, <gtw@gnu.org>.
 *
 * Copyright (C) 2009  Gary Wong
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of version 3 of the GNU General Public License as
 *  published by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * $Id$
 */

#include <config.h>

#include <assert.h>
#include <stdlib.h>
#include <xcb/xcb.h>

#include "gwm.h"

#include "window-table.h"

/* Cuckoo hashed window table: see _Cuckoo Hashing_, R. Pagh and F. Rodler,
   Journal of Algorithms 51 (2004), pp. 122-144. */

struct window_table windows, update_windows;

extern void table_init( struct window_table *table ) {

    table->used = 0;
    table->n = 32;
    table->max = 24;
    table->hash = 0xBA97D5B1UL;

    table->t[ 0 ] = xcalloc( table->n << 1, sizeof table->t[ 0 ][ 0 ] );
    table->t[ 1 ] = table->t[ 0 ] + table->n;
    table->values = xmalloc( table->n * sizeof *table->values );
}

#if DEBUG
extern void table_destroy( struct window_table *table ) {

    free( table->t[ 0 ] );
    free( table->values );
}
#endif

static CONST int table_hash( struct window_table *table, int half,
			     xcb_window_t key ) {

    unsigned long h0, h1;
    unsigned long long l;
    
    if( half ) {
	h0 = table->hash ^ 0x79D9C6D4UL;
	h1 = table->hash * 0x6A391E85UL;
    } else {
	h0 = table->hash;
	h1 = table->hash ^ 0x52C694B6UL;
    }

    l = key * h0;
    l ^= l >> 32;
    l *= h1;
    l ^= l >> 29;

    return l & ( table->n - 1 );
}

static PURE int table_lookup_index( struct window_table *table,
				    xcb_window_t key ) {

    int h;

    assert( key );
    
    h = table_hash( table, 0, key );
    if( table->t[ 0 ][ h ].key == key )
	return table->t[ 0 ][ h ].index;
    
    h = table_hash( table, 1, key );
    if( table->t[ 1 ][ h ].key == key )
	return table->t[ 1 ][ h ].index;
    
    return -1;
}

extern PURE struct gwm_window *table_lookup( struct window_table *table,
					     xcb_window_t key ) {

    int index;

    if( !key )
	return NULL;

    return ( index = table_lookup_index( table, key ) ) >= 0 ?
	table->values[ index ] : NULL;
}

static void table_insert_index( struct window_table *table, xcb_window_t key,
				int index );

static void table_rehash( struct window_table *table, unsigned long hash,
			  unsigned long n, unsigned long max ) {

    int old_n = table->n;
    struct half_table *old_t[ 2 ];
    int i;

    old_t[ 0 ] = table->t[ 0 ];
    old_t[ 1 ] = table->t[ 1 ];

    table->hash = hash;
    table->n = n;
    table->max = max;
    table->used = 0;
    
    table->t[ 0 ] = xcalloc( table->n << 1, sizeof table->t[ 0 ][ 0 ] );
    table->t[ 1 ] = table->t[ 0 ] + table->n;
    table->values = xrealloc( table->values, table->n * sizeof *table->values );

    /* We've now gotten everything we want out of the old table.  Although
       table_insert might possibly cause inefficient re-entrancy, that case
       should be both harmless and exceedingly rare. */    
    for( i = 0; i < old_n; i++ ) {
	if( old_t[ 0 ][ i ].key )
	    table_insert_index( table, old_t[ 0 ][ i ].key,
				old_t[ 0 ][ i ].index );
	if( old_t[ 1 ][ i ].key )
	    table_insert_index( table, old_t[ 1 ][ i ].key,
				old_t[ 1 ][ i ].index );
    }
    
    free( old_t[ 0 ] );
}

static void table_insert_index( struct window_table *table, xcb_window_t key,
				int index ) {

    table->used++;
    
    for(;;) {
	int i;
    
	for( i = 0; i < table->max; i++ ) {
	    int h = table_hash( table, i & 1, key );
	    xcb_window_t old_key = table->t[ i & 1 ][ h ].key;
	    int old_index = table->t[ i & 1 ][ h ].index;

	    table->t[ i & 1 ][ h ].key = key;
	    table->t[ i & 1 ][ h ].index = index;
		
	    if( !old_key )
		return;

	    key = old_key;
	    index = old_index;
	}
	    
	/* Failure to insert: rehash. */
	table_rehash( table, table->hash + 0x5DB1BA96UL,
		      table->n, table->max );
    }
}

static void table_insert( struct window_table *table, xcb_window_t key,
			  struct gwm_window *value ) {

    if( !key )
	return;

    assert( !table_lookup( table, key ) );
    
    table->values[ table->used ] = value;
    
    if( table->used > ( ( table->n * 3 ) >> 2 ) )
	/* Load becoming high: resize. */
	table_rehash( table, table->hash, table->n << 1, table->max + 4 );

    table_insert_index( table, key, table->used );
}

static void table_delete( struct window_table *table, xcb_window_t key ) {

    int h;
    int i;
    
    if( !key )
	return;

    for( i = 0; i < 2; i++ ) {
	h = table_hash( table, i, key );
	if( table->t[ i ][ h ].key == key ) {
	    int index;
	    xcb_window_t replacement_key;
	    struct gwm_window *replacement_value;
	    int replacement_hash;
	    
	    table->used--;
	    
	    if( ( index = table->t[ i ][ h ].index ) < table->used ) {
		/* Must replace our old index, to keep the values array
		   compact. */
		table->values[ index ] = replacement_value =
		    table->values[ table->used ];
		replacement_key = replacement_value->w;

		replacement_hash = table_hash( table, 0, replacement_key );
		if( table->t[ 0 ][ replacement_hash ].key == replacement_key )
		    table->t[ 0 ][ replacement_hash ].index = index;
		else {
		    replacement_hash = table_hash( table, 1, replacement_key );
		    assert( table->t[ 1 ][ replacement_hash ].key ==
			    replacement_key );
		    table->t[ 1 ][ replacement_hash ].index = index;
		}
	    }
	    
	    table->t[ i ][ h ].key = 0;
	    
	    if( table->used < ( ( table->n * 3 ) >> 4 ) && table->n > 32 )
		/* Load becoming low: resize. */
		table_rehash( table, table->hash, table->n >> 1,
			      table->max - 4 );
	    return;
	}
    }
}

extern void queue_window_update( struct gwm_window *window,
				 int x, int y, int width, int height,
				 int cleared ) {

    /* FIXME Consider computing the region instead of the bounding box. */

    if( !window->update.width || !window->update.height ) {
	/* New update region. */
	window->update.x = x;
	window->update.y = y;
	window->update.width = width;
	window->update.height = height;
	
	if( !cleared )
	    window->cleared = FALSE;
    } else {
	/* Compute the bounding box of the union of the old and new regions.
	   If the bounding box is enlarged, we reset the cleared flag,
	   because it is very likely that it now includes areas which
	   were not in either of the two original regions (and therefore
	   not guaranteed to be cleared). */
	if( x < window->update.x ) {
	    window->update.width += window->update.x - x;
	    window->update.x = x;
	    window->cleared = FALSE;
	}

	if( y < window->update.y ) {
	    window->update.height += window->update.y - y;
	    window->update.y = y;
	    window->cleared = FALSE;
	}

	if( x + width > window->update.x + window->update.width ) {
	    window->update.width = x + width - window->update.x;
	    window->cleared = FALSE;
	}

	if( y + height > window->update.y + window->update.height ) {
	    window->update.height = y + height - window->update.y;
	    window->cleared = FALSE;
	}
    }
    
    if( table_lookup( &update_windows, window->w ) )
	return;

    table_insert( &update_windows, window->w, window );
}

extern void window_update_done( struct gwm_window *window ) {

    window->update.x = 0;
    window->update.y = 0;
    window->update.width = 0;
    window->update.height = 0;
    window->cleared = TRUE;

    table_delete( &update_windows, window->w );
}

extern MALLOC struct gwm_window *add_window( xcb_window_t w ) {

    struct gwm_window *window;
    
    if( table_lookup( &windows, w ) )
	return NULL; /* window already exists */

    window = xmalloc( sizeof *window );
    window->w = w;
    window_update_done( window );
    
    table_insert( &windows, window->w, window );

    return window;
}

extern void forget_window( struct gwm_window *window ) {

    if( pointer_demux == window->w )
	pointer_demux = XCB_NONE;
    
    table_delete( &windows, window->w );
    table_delete( &update_windows, window->w );
    free( window );
}

extern struct gwm_window *lookup_window( xcb_window_t w ) {

    struct gwm_window *window;
    
    for(;;) {
	window = table_lookup( &windows, w );

	if( window && window->type == WINDOW_INCOMPLETE )
	    /* Whoops... all this asynchronicity has gotten us ahead
	       of ourselves.  Catch up on what we deferred, by waiting
	       until the window is complete before we continue. */
	    sync_with_callback( window->u.incomplete.sequence );
	else
	    return window;
    }
}