src/mesa/program/prog_cache.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2003 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28
  29 #include "main/glheader.h"
  30 #include "main/mtypes.h"
  31 #include "main/imports.h"
  32 #include "main/shaderobj.h"
  33 #include "program/prog_cache.h"
  34 #include "program/program.h"
  35
  36
  37 struct cache_item
  38 {
  39    GLuint hash;
  40    unsigned keysize;
  41    void *key;
  42    struct gl_program *program;
  43    struct cache_item *next;
  44 };
  45
  46 struct gl_program_cache
  47 {
  48    struct cache_item **items;
  49    struct cache_item *last;
  50    GLuint size, n_items;
  51 };
  52
  53
  54
  55 /**
  56  * Compute hash index from state key.
  57  */
  58 static GLuint
  59 hash_key(const void *key, GLuint key_size)
  60 {
  61    const GLuint *ikey = (const GLuint *) key;
  62    GLuint hash = 0, i;
  63
  64    assert(key_size >= 4);
  65
  66    /* Make a slightly better attempt at a hash function:
  67     */
  68    for (i = 0; i < key_size / sizeof(*ikey); i++)
  69    {
  70       hash += ikey[i];
  71       hash += (hash << 10);
  72       hash ^= (hash >> 6);
  73    }
  74
  75    return hash;
  76 }
  77
  78
  79 /**
  80  * Rebuild/expand the hash table to accomodate more entries
  81  */
  82 static void
  83 rehash(struct gl_program_cache *cache)
  84 {
  85    struct cache_item **items;
  86    struct cache_item *c, *next;
  87    GLuint size, i;
  88
  89    cache->last = NULL;
  90
  91    size = cache->size * 3;
  92    items = malloc(size * sizeof(*items));
  93    memset(items, 0, size * sizeof(*items));
  94
  95    for (i = 0; i < cache->size; i++)
  96       for (c = cache->items[i]; c; c = next) {
  97          next = c->next;
  98          c->next = items[c->hash % size];
  99          items[c->hash % size] = c;
 100       }
 101
 102    free(cache->items);
 103    cache->items = items;
 104    cache->size = size;
 105 }
 106
 107
 108 static void
 109 clear_cache(struct gl_context *ctx, struct gl_program_cache *cache,
 110             GLboolean shader)
 111 {
 112    struct cache_item *c, *next;
 113    GLuint i;
 114
 115    cache->last = NULL;
 116
 117    for (i = 0; i < cache->size; i++) {
 118       for (c = cache->items[i]; c; c = next) {
 119          next = c->next;
 120          free(c->key);
 121          if (shader) {
 122             _mesa_reference_shader_program(ctx,
 123                                            (struct gl_shader_program **)&c->program,
 124                                            NULL);
 125          } else {
 126             _mesa_reference_program(ctx, &c->program, NULL);
 127          }
 128          free(c);
 129       }
 130       cache->items[i] = NULL;
 131    }
 132
 133
 134    cache->n_items = 0;
 135 }
 136
 137
 138
 139 struct gl_program_cache *
 140 _mesa_new_program_cache(void)
 141 {
 142    struct gl_program_cache *cache = CALLOC_STRUCT(gl_program_cache);
 143    if (cache) {
 144       cache->size = 17;
 145       cache->items =
 146          calloc(cache->size, sizeof(struct cache_item *));
 147       if (!cache->items) {
 148          free(cache);
 149          return NULL;
 150       }
 151    }
 152    return cache;
 153 }
 154
 155
 156 void
 157 _mesa_delete_program_cache(struct gl_context *ctx, struct gl_program_cache *cache)
 158 {
 159    clear_cache(ctx, cache, GL_FALSE);
 160    free(cache->items);
 161    free(cache);
 162 }
 163
 164 void
 165 _mesa_delete_shader_cache(struct gl_context *ctx,
 166                           struct gl_program_cache *cache)
 167 {
 168    clear_cache(ctx, cache, GL_TRUE);
 169    free(cache->items);
 170    free(cache);
 171 }
 172
 173
 174 struct gl_program *
 175 _mesa_search_program_cache(struct gl_program_cache *cache,
 176                            const void *key, GLuint keysize)
 177 {
 178    if (cache->last &&
 179        cache->last->keysize == keysize &&
 180        memcmp(cache->last->key, key, keysize) == 0) {
 181       return cache->last->program;
 182    }
 183    else {
 184       const GLuint hash = hash_key(key, keysize);
 185       struct cache_item *c;
 186
 187       for (c = cache->items[hash % cache->size]; c; c = c->next) {
 188          if (c->hash == hash &&
 189              c->keysize == keysize &&
 190              memcmp(c->key, key, keysize) == 0) {
 191
 192             cache->last = c;
 193             return c->program;
 194          }
 195       }
 196
 197       return NULL;
 198    }
 199 }
 200
 201
 202 void
 203 _mesa_program_cache_insert(struct gl_context *ctx,
 204                            struct gl_program_cache *cache,
 205                            const void *key, GLuint keysize,
 206                            struct gl_program *program)
 207 {
 208    const GLuint hash = hash_key(key, keysize);
 209    struct cache_item *c = CALLOC_STRUCT(cache_item);
 210
 211    c->hash = hash;
 212
 213    c->key = malloc(keysize);
 214    memcpy(c->key, key, keysize);
 215    c->keysize = keysize;
 216
 217    c->program = program;  /* no refcount change */
 218
 219    if (cache->n_items > cache->size * 1.5) {
 220       if (cache->size < 1000)
 221          rehash(cache);
 222       else
 223          clear_cache(ctx, cache, GL_FALSE);
 224    }
 225
 226    cache->n_items++;
 227    c->next = cache->items[hash % cache->size];
 228    cache->items[hash % cache->size] = c;
 229 }
 230
 231 void
 232 _mesa_shader_cache_insert(struct gl_context *ctx,
 233                           struct gl_program_cache *cache,
 234                           const void *key, GLuint keysize,
 235                           struct gl_shader_program *program)
 236 {
 237    const GLuint hash = hash_key(key, keysize);
 238    struct cache_item *c = CALLOC_STRUCT(cache_item);
 239
 240    c->hash = hash;
 241
 242    c->key = malloc(keysize);
 243    memcpy(c->key, key, keysize);
 244    c->keysize = keysize;
 245
 246    c->program = (struct gl_program *)program;  /* no refcount change */
 247
 248    if (cache->n_items > cache->size * 1.5) {
 249       if (cache->size < 1000)
 250          rehash(cache);
 251       else
 252          clear_cache(ctx, cache, GL_TRUE);
 253    }
 254
 255    cache->n_items++;
 256    c->next = cache->items[hash % cache->size];
 257    cache->items[hash % cache->size] = c;
 258 }