window-table.c

   1 /*
   2  * window-table.c
   3  *
   4  * Part of gwm, the Gratuitous Window Manager,
   5  *     by Gary Wong, <gtw@gnu.org>.
   6  *
   7  * Copyright (C) 2009  Gary Wong
   8  *
   9  *  This program is free software: you can redistribute it and/or modify
  10  *  it under the terms of version 3 of the GNU General Public License as
  11  *  published by the Free Software Foundation.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20  *
  21  * $Id$
  22  */
  23
  24 #include <config.h>
  25
  26 #include <assert.h>
  27 #include <stdlib.h>
  28 #include <xcb/xcb.h>
  29
  30 #include "gwm.h"
  31
  32 #include "window-table.h"
  33
  34 /* Cuckoo hashed window table: see _Cuckoo Hashing_, R. Pagh and F. Rodler,
  35    Journal of Algorithms 51 (2004), pp. 122-144. */
  36
  37 struct window_table windows, update_windows;
  38
  39 extern void table_init( struct window_table *table ) {
  40
  41     table->used = 0;
  42     table->n = 32;
  43     table->max = 24;
  44     table->hash = 0xBA97D5B1UL;
  45
  46     table->t[ 0 ] = xcalloc( table->n << 1, sizeof table->t[ 0 ][ 0 ] );
  47     table->t[ 1 ] = table->t[ 0 ] + table->n;
  48     table->values = xmalloc( table->n * sizeof *table->values );
  49 }
  50
  51 #if DEBUG
  52 extern void table_destroy( struct window_table *table ) {
  53
  54     free( table->t[ 0 ] );
  55     free( table->values );
  56 }
  57 #endif
  58
  59 static CONST int table_hash( struct window_table *table, int half,
  60                              xcb_window_t key ) {
  61
  62     unsigned long h0, h1;
  63     unsigned long long l;
  64
  65     if( half ) {
  66         h0 = table->hash ^ 0x79D9C6D4UL;
  67         h1 = table->hash * 0x6A391E85UL;
  68     } else {
  69         h0 = table->hash;
  70         h1 = table->hash ^ 0x52C694B6UL;
  71     }
  72
  73     l = key * h0;
  74     l ^= l >> 32;
  75     l *= h1;
  76     l ^= l >> 29;
  77
  78     return l & ( table->n - 1 );
  79 }
  80
  81 static PURE int table_lookup_index( struct window_table *table,
  82                                     xcb_window_t key ) {
  83
  84     int h;
  85
  86     assert( key );
  87
  88     h = table_hash( table, 0, key );
  89     if( table->t[ 0 ][ h ].key == key )
  90         return table->t[ 0 ][ h ].index;
  91
  92     h = table_hash( table, 1, key );
  93     if( table->t[ 1 ][ h ].key == key )
  94         return table->t[ 1 ][ h ].index;
  95
  96     return -1;
  97 }
  98
  99 extern PURE struct gwm_window *table_lookup( struct window_table *table,
 100                                              xcb_window_t key ) {
 101
 102     int index;
 103
 104     if( !key )
 105         return NULL;
 106
 107     return ( index = table_lookup_index( table, key ) ) >= 0 ?
 108         table->values[ index ] : NULL;
 109 }
 110
 111 static void table_insert_index( struct window_table *table, xcb_window_t key,
 112                                 int index );
 113
 114 static void table_rehash( struct window_table *table, unsigned long hash,
 115                           unsigned long n, unsigned long max ) {
 116
 117     int old_n = table->n;
 118     struct half_table *old_t[ 2 ];
 119     int i;
 120
 121     old_t[ 0 ] = table->t[ 0 ];
 122     old_t[ 1 ] = table->t[ 1 ];
 123
 124     table->hash = hash;
 125     table->n = n;
 126     table->max = max;
 127     table->used = 0;
 128
 129     table->t[ 0 ] = xcalloc( table->n << 1, sizeof table->t[ 0 ][ 0 ] );
 130     table->t[ 1 ] = table->t[ 0 ] + table->n;
 131     table->values = xrealloc( table->values, table->n * sizeof *table->values );
 132
 133     /* We've now gotten everything we want out of the old table.  Although
 134        table_insert might possibly cause inefficient re-entrancy, that case
 135        should be both harmless and exceedingly rare. */
 136     for( i = 0; i < old_n; i++ ) {
 137         if( old_t[ 0 ][ i ].key )
 138             table_insert_index( table, old_t[ 0 ][ i ].key,
 139                                 old_t[ 0 ][ i ].index );
 140         if( old_t[ 1 ][ i ].key )
 141             table_insert_index( table, old_t[ 1 ][ i ].key,
 142                                 old_t[ 1 ][ i ].index );
 143     }
 144
 145     free( old_t[ 0 ] );
 146 }
 147
 148 static void table_insert_index( struct window_table *table, xcb_window_t key,
 149                                 int index ) {
 150
 151     table->used++;
 152
 153     for(;;) {
 154         int i;
 155
 156         for( i = 0; i < table->max; i++ ) {
 157             int h = table_hash( table, i & 1, key );
 158             xcb_window_t old_key = table->t[ i & 1 ][ h ].key;
 159             int old_index = table->t[ i & 1 ][ h ].index;
 160
 161             table->t[ i & 1 ][ h ].key = key;
 162             table->t[ i & 1 ][ h ].index = index;
 163
 164             if( !old_key )
 165                 return;
 166
 167             key = old_key;
 168             index = old_index;
 169         }
 170
 171         /* Failure to insert: rehash. */
 172         table_rehash( table, table->hash + 0x5DB1BA96UL,
 173                       table->n, table->max );
 174     }
 175 }
 176
 177 static void table_insert( struct window_table *table, xcb_window_t key,
 178                           struct gwm_window *value ) {
 179
 180     if( !key )
 181         return;
 182
 183     assert( !table_lookup( table, key ) );
 184
 185     table->values[ table->used ] = value;
 186
 187     if( table->used > ( ( table->n * 3 ) >> 2 ) )
 188         /* Load becoming high: resize. */
 189         table_rehash( table, table->hash, table->n << 1, table->max + 4 );
 190
 191     table_insert_index( table, key, table->used );
 192 }
 193
 194 static void table_delete( struct window_table *table, xcb_window_t key ) {
 195
 196     int h;
 197     int i;
 198
 199     if( !key )
 200         return;
 201
 202     for( i = 0; i < 2; i++ ) {
 203         h = table_hash( table, i, key );
 204         if( table->t[ i ][ h ].key == key ) {
 205             int index;
 206             xcb_window_t replacement_key;
 207             struct gwm_window *replacement_value;
 208             int replacement_hash;
 209
 210             table->used--;
 211
 212             if( ( index = table->t[ i ][ h ].index ) < table->used ) {
 213                 /* Must replace our old index, to keep the values array
 214                    compact. */
 215                 table->values[ index ] = replacement_value =
 216                     table->values[ table->used ];
 217                 replacement_key = replacement_value->w;
 218
 219                 replacement_hash = table_hash( table, 0, replacement_key );
 220                 if( table->t[ 0 ][ replacement_hash ].key == replacement_key )
 221                     table->t[ 0 ][ replacement_hash ].index = index;
 222                 else {
 223                     replacement_hash = table_hash( table, 1, replacement_key );
 224                     assert( table->t[ 1 ][ replacement_hash ].key ==
 225                             replacement_key );
 226                     table->t[ 1 ][ replacement_hash ].index = index;
 227                 }
 228             }
 229
 230             table->t[ i ][ h ].key = 0;
 231
 232             if( table->used < ( ( table->n * 3 ) >> 4 ) && table->n > 32 )
 233                 /* Load becoming low: resize. */
 234                 table_rehash( table, table->hash, table->n >> 1,
 235                               table->max - 4 );
 236             return;
 237         }
 238     }
 239 }
 240
 241 extern void queue_window_update( struct gwm_window *window,
 242                                  int x, int y, int width, int height,
 243                                  int cleared ) {
 244
 245     /* FIXME Consider computing the region instead of the bounding box. */
 246
 247     if( !window->update.width || !window->update.height ) {
 248         /* New update region. */
 249         window->update.x = x;
 250         window->update.y = y;
 251         window->update.width = width;
 252         window->update.height = height;
 253
 254         if( !cleared )
 255             window->cleared = FALSE;
 256     } else {
 257         /* Compute the bounding box of the union of the old and new regions.
 258            If the bounding box is enlarged, we reset the cleared flag,
 259            because it is very likely that it now includes areas which
 260            were not in either of the two original regions (and therefore
 261            not guaranteed to be cleared). */
 262         if( x < window->update.x ) {
 263             window->update.width += window->update.x - x;
 264             window->update.x = x;
 265             window->cleared = FALSE;
 266         }
 267
 268         if( y < window->update.y ) {
 269             window->update.height += window->update.y - y;
 270             window->update.y = y;
 271             window->cleared = FALSE;
 272         }
 273
 274         if( x + width > window->update.x + window->update.width ) {
 275             window->update.width = x + width - window->update.x;
 276             window->cleared = FALSE;
 277         }
 278
 279         if( y + height > window->update.y + window->update.height ) {
 280             window->update.height = y + height - window->update.y;
 281             window->cleared = FALSE;
 282         }
 283     }
 284
 285     if( table_lookup( &update_windows, window->w ) )
 286         return;
 287
 288     table_insert( &update_windows, window->w, window );
 289 }
 290
 291 extern void window_update_done( struct gwm_window *window ) {
 292
 293     window->update.x = 0;
 294     window->update.y = 0;
 295     window->update.width = 0;
 296     window->update.height = 0;
 297     window->cleared = TRUE;
 298
 299     table_delete( &update_windows, window->w );
 300 }
 301
 302 extern MALLOC struct gwm_window *add_window( xcb_window_t w ) {
 303
 304     struct gwm_window *window;
 305
 306     if( table_lookup( &windows, w ) )
 307         return NULL; /* window already exists */
 308
 309     window = xmalloc( sizeof *window );
 310     window->w = w;
 311     window_update_done( window );
 312
 313     table_insert( &windows, window->w, window );
 314
 315     return window;
 316 }
 317
 318 extern void forget_window( struct gwm_window *window ) {
 319
 320     table_delete( &windows, window->w );
 321     table_delete( &update_windows, window->w );
 322     free( window );
 323 }
 324
 325 extern struct gwm_window *lookup_window( xcb_window_t w ) {
 326
 327     struct gwm_window *window;
 328
 329     for(;;) {
 330         window = table_lookup( &windows, w );
 331
 332         if( window && window->type == WINDOW_INCOMPLETE )
 333             /* Whoops... all this asynchronicity has gotten us ahead
 334                of ourselves.  Catch up on what we deferred, by waiting
 335                until the window is complete before we continue. */
 336             sync_with_callback( window->u.incomplete.sequence );
 337         else
 338             return window;
 339     }
 340 }