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     } else {
 254         /* Compute the bounding box of the union of the old and new regions. */
 255         if( x < window->update.x ) {
 256             window->update.width += window->update.x - x;
 257             window->update.x = x;
 258         }
 259
 260         if( y < window->update.y ) {
 261             window->update.height += window->update.y - y;
 262             window->update.y = y;
 263         }
 264
 265         if( x + width > window->update.x + window->update.width )
 266             window->update.width = x + width - window->update.x;
 267
 268         if( y + height > window->update.y + window->update.height )
 269             window->update.height = y + height - window->update.y;
 270     }
 271
 272     if( !cleared )
 273         window->cleared = FALSE;
 274
 275     if( table_lookup( &update_windows, window->w ) )
 276         return;
 277
 278     table_insert( &update_windows, window->w, window );
 279 }
 280
 281 extern void window_update_done( struct gwm_window *window ) {
 282
 283     window->update.x = 0;
 284     window->update.y = 0;
 285     window->update.width = 0;
 286     window->update.height = 0;
 287     window->cleared = TRUE;
 288
 289     table_delete( &update_windows, window->w );
 290 }
 291
 292 extern MALLOC struct gwm_window *add_window( xcb_window_t w ) {
 293
 294     struct gwm_window *window;
 295
 296     if( table_lookup( &windows, w ) )
 297         return NULL; /* window already exists */
 298
 299     window = xmalloc( sizeof *window );
 300     window->w = w;
 301     window_update_done( window );
 302
 303     table_insert( &windows, window->w, window );
 304
 305     return window;
 306 }
 307
 308 extern void forget_window( struct gwm_window *window ) {
 309
 310     table_delete( &windows, window->w );
 311     table_delete( &update_windows, window->w );
 312     free( window );
 313 }
 314
 315 extern struct gwm_window *lookup_window( xcb_window_t w ) {
 316
 317     struct gwm_window *window;
 318
 319     for(;;) {
 320         window = table_lookup( &windows, w );
 321
 322         if( window && window->type == WINDOW_INCOMPLETE )
 323             /* Whoops... all this asynchronicity has gotten us ahead
 324                of ourselves.  Catch up on what we deferred, by waiting
 325                until the window is complete before we continue. */
 326             sync_with_callback( window->u.incomplete.sequence );
 327         else
 328             return window;
 329     }
 330 }