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 <limits.h>
#if HAVE_STDINT_H
#include <stdint.h>
#endif
#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 INIT 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( unsigned long hash, int n, int half,
			     xcb_window_t key ) {

    unsigned long h0, h1;
#if defined( UINT64_MAX ) || defined( uint64_t )
    uint64_t l;
#else
    unsigned long l;
#endif
    
    if( half ) {
	h0 = hash ^ 0x79D9C6D4UL;
	h1 = hash * 0x6A391E85UL;
    } else {
	h0 = hash;
	h1 = hash ^ 0x52C694B6UL;
    }

#if defined( UINT64_MAX ) || defined( uint64_t ) || ULONG_MAX > 0xFFFFFFFFUL
    l = key * h0;
    l ^= l >> 32;
    l *= h1;
    l ^= l >> 29;
#else
    l = key * h0;
    l ^= l >> 16;
    l *= h1;
    l ^= l >> 13;
    l *= h0;
    l ^= l >> 15;
#endif
    
    return l & ( n - 1 );
}

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

    int h;

    assert( key );
    
    h = table_hash( table->hash, table->n, 0, key );
    if( table->t[ 0 ][ h ].key == key )
	return table->t[ 0 ][ h ].index;
    
    h = table_hash( table->hash, table->n, 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 ) {

    for(;;) {
	int i;
    
	table->used++;

	for( i = 0; i < table->max; i++ ) {
	    int h = table_hash( table->hash, table->n, 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->hash, table->n, 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->hash, table->n, 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->hash, table->n, 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;
    }
}

struct window_stack window_stack;

extern INIT void stack_init( struct window_stack *stack ) {

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

    stack->t[ 0 ] = xcalloc( stack->n << 1, sizeof stack->t[ 0 ][ 0 ] );
    stack->t[ 1 ] = stack->t[ 0 ] + stack->n;
}

#if DEBUG
extern void stack_destroy( struct window_stack *stack ) {

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

extern PURE struct stacking_order *stack_lookup( struct window_stack *stack,
						 xcb_window_t key ) {

    int h;

    if( !key )
	return NULL;

    h = table_hash( stack->hash, stack->n, 0, key );
    if( stack->t[ 0 ][ h ].window == key )
	return &stack->t[ 0 ][ h ];

    h = table_hash( stack->hash, stack->n, 1, key );
    if( stack->t[ 1 ][ h ].window == key )
	return &stack->t[ 1 ][ h ];

    return NULL;
}

static void stack_insert( struct window_stack *stack, xcb_window_t window,
			  xcb_window_t lower_window,
			  xcb_window_t higher_window );

static void stack_rehash( struct window_stack *stack, unsigned long hash,
			  unsigned long n, unsigned long max ) {

    int old_n = stack->n;
    struct stacking_order *old_t[ 2 ];
    int i;

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

    stack->hash = hash;
    stack->n = n;
    stack->max = max;
    stack->used = 0;

    stack->t[ 0 ] = xcalloc( stack->n << 1, sizeof stack->t[ 0 ][ 0 ] );
    stack->t[ 1 ] = stack->t[ 0 ] + stack->n;

    /* We've now gotten everything we want out of the old stack.  Although
       stack_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 ].window )
	    stack_insert( stack, old_t[ 0 ][ i ].window,
			  old_t[ 0 ][ i ].lower_window,
			  old_t[ 0 ][ i ].higher_window );
	if( old_t[ 1 ][ i ].window )
	    stack_insert( stack, old_t[ 1 ][ i ].window,
			  old_t[ 1 ][ i ].lower_window,
			  old_t[ 1 ][ i ].higher_window );
    }

    free( old_t[ 0 ] );
}

static void stack_insert( struct window_stack *stack, xcb_window_t window,
			  xcb_window_t lower_window,
			  xcb_window_t higher_window ) {

    for(;;) {
	int i;

	stack->used++;

	for( i = 0; i < stack->max; i++ ) {
	    int h = table_hash( stack->hash, stack->n, i & 1, window );
	    xcb_window_t old_window = stack->t[ i & 1 ][ h ].window;
	    xcb_window_t old_lower, old_higher;

	    if( old_window ) {
		old_lower = stack->t[ i & 1 ][ h ].lower_window;
		old_higher = stack->t[ i & 1 ][ h ].higher_window;
	    }

	    stack->t[ i & 1 ][ h ].window = window;
	    stack->t[ i & 1 ][ h ].lower_window = lower_window;
	    stack->t[ i & 1 ][ h ].higher_window = higher_window;

	    if( !old_window )
		return;

	    window = old_window;
	    lower_window = old_lower;
	    higher_window = old_higher;
	}

	/* Failure to insert: rehash. */
	stack_rehash( stack, stack->hash + 0x5DB1BA96UL,
		      stack->n, stack->max );
    }
}

static void stack_insert_new( struct window_stack *stack, xcb_window_t window,
			      xcb_window_t lower_window,
			      xcb_window_t higher_window ) {

    if( !window )
	return;

    assert( !stack_lookup( stack, window ) );

    if( stack->used > ( ( stack->n * 3 ) >> 2 ) )
	/* Load becoming high: resize. */
	stack_rehash( stack, stack->hash, stack->n << 1, stack->max + 4 );

    stack_insert( stack, window, lower_window, higher_window );
}

extern void stack_insert_singleton( struct window_stack *stack,
				    xcb_window_t key ) {

    if( !key )
	return;

    stack_insert_new( stack, key, key, key );

    assert( stack_lookup( stack, key ) );
}

extern void stack_insert_above( struct window_stack *stack,
				xcb_window_t key, xcb_window_t lower_window ) {

    struct stacking_order *l, *h;
    xcb_window_t higher_window;

    if( !key )
	return;

    l = stack_lookup( stack, lower_window );
    assert( l );
    higher_window = l->higher_window;

    stack_insert_new( stack, key, lower_window, higher_window );
    /* It's essential to repeat the lookup of lower_window, because inserting
       the new entry might have disturbed the existing ones. */
    l = stack_lookup( stack, lower_window );
    h = stack_lookup( stack, higher_window );
    h->lower_window = key;
    l->higher_window = key;

    assert( stack_lookup( stack, key ) );
    assert( l );
    assert( h );
}

extern void stack_remove( struct window_stack *stack, xcb_window_t window ) {

    struct stacking_order *l, *h, *entry;
    int hash, i;

    if( !window )
	return;

    entry = stack_lookup( stack, window );
    assert( entry );

    l = stack_lookup( stack, entry->lower_window );
    assert( l );

    h = stack_lookup( stack, entry->higher_window );
    assert( h );

    l->higher_window = entry->higher_window;
    h->lower_window = entry->lower_window;

    for( i = 0; i < 2; i++ ) {
	hash = table_hash( stack->hash, stack->n, i, window );
	if( stack->t[ i ][ hash ].window == window ) {
	    stack->t[ i ][ hash ].window = 0;

	    if( stack->used < ( ( stack->n * 3 ) >> 4 ) && stack->n > 32 )
		/* Load becoming low: resize. */
		stack_rehash( stack, stack->hash, stack->n >> 1,
			      stack->max - 4 );

	    assert( !stack_lookup( stack, window ) );

	    return;
	}
    }

    assert( FALSE );
}

extern void stack_move_above( struct window_stack *stack,
			      xcb_window_t window,
			      xcb_window_t lower_window ) {

    struct stacking_order *l, *h, *entry;

    if( !window || window == lower_window )
	return;

    entry = stack_lookup( stack, window );
    assert( entry );

    if( entry->lower_window == lower_window )
	return;

    l = stack_lookup( stack, entry->lower_window );
    assert( l );

    h = stack_lookup( stack, entry->higher_window );
    assert( h );

    l->higher_window = entry->higher_window;
    h->lower_window = entry->lower_window;

    l = stack_lookup( stack, lower_window );
    assert( l );

    h = stack_lookup( stack, l->higher_window );
    assert( h );

    h->lower_window = window;
    l->higher_window = window;
    entry->lower_window = lower_window;
    entry->higher_window = h->window;

    assert( stack_lookup( stack, window ) );
}

extern xcb_window_t stack_real_below( struct window_stack *stack,
				      xcb_window_t window ) {

    xcb_window_t search;

    if( !window )
	return 0;

    for( search = stack_lookup( stack, window )->lower_window;
	 search != window && ( search & STACK_MASK ) != STACK_END;
	 search = stack_lookup( stack, search )->lower_window )
	if( !( search & STACK_MASK ) )
	    return search;

    return 0;
}