1 /************************************************************************** 2 * 3 * Copyright 2003 Tungsten Graphics, Inc., Cedar Park, Texas. 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 TUNGSTEN GRAPHICS 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 void *key; 41 struct gl_program *program; 42 struct cache_item *next; 43 }; 44 45 struct gl_program_cache 46 { 47 struct cache_item **items; 48 struct cache_item *last; 49 GLuint size, n_items; 50 }; 51 52 53 54 /** 55 * Compute hash index from state key. 56 */ 57 static GLuint 58 hash_key(const void *key, GLuint key_size) 59 { 60 const GLuint *ikey = (const GLuint *) key; 61 GLuint hash = 0, i; 62 63 assert(key_size >= 4); 64 65 /* Make a slightly better attempt at a hash function: 66 */ 67 for (i = 0; i < key_size / sizeof(*ikey); i++) 68 { 69 hash += ikey[i]; 70 hash += (hash << 10); 71 hash ^= (hash >> 6); 72 } 73 74 return hash; 75 } 76 77 78 /** 79 * Rebuild/expand the hash table to accomodate more entries 80 */ 81 static void 82 rehash(struct gl_program_cache *cache) 83 { 84 struct cache_item **items; 85 struct cache_item *c, *next; 86 GLuint size, i; 87 88 cache->last = NULL; 89 90 size = cache->size * 3; 91 items = (struct cache_item**) malloc(size * sizeof(*items)); 92 memset(items, 0, size * sizeof(*items)); 93 94 for (i = 0; i < cache->size; i++) 95 for (c = cache->items[i]; c; c = next) { 96 next = c->next; 97 c->next = items[c->hash % size]; 98 items[c->hash % size] = c; 99 } 100 101 free(cache->items); 102 cache->items = items; 103 cache->size = size; 104 } 105 106 107 static void 108 clear_cache(struct gl_context *ctx, struct gl_program_cache *cache, 109 GLboolean shader) 110 { 111 struct cache_item *c, *next; 112 GLuint i; 113 114 cache->last = NULL; 115 116 for (i = 0; i < cache->size; i++) { 117 for (c = cache->items[i]; c; c = next) { 118 next = c->next; 119 free(c->key); 120 if (shader) { 121 _mesa_reference_shader_program(ctx, 122 (struct gl_shader_program **)&c->program, 123 NULL); 124 } else { 125 _mesa_reference_program(ctx, &c->program, NULL); 126 } 127 free(c); 128 } 129 cache->items[i] = NULL; 130 } 131 132 133 cache->n_items = 0; 134 } 135 136 137 138 struct gl_program_cache * 139 _mesa_new_program_cache(void) 140 { 141 struct gl_program_cache *cache = CALLOC_STRUCT(gl_program_cache); 142 if (cache) { 143 cache->size = 17; 144 cache->items = (struct cache_item **) 145 calloc(1, cache->size * sizeof(struct cache_item)); 146 if (!cache->items) { 147 free(cache); 148 return NULL; 149 } 150 } 151 return cache; 152 } 153 154 155 void 156 _mesa_delete_program_cache(struct gl_context *ctx, struct gl_program_cache *cache) 157 { 158 clear_cache(ctx, cache, GL_FALSE); 159 free(cache->items); 160 free(cache); 161 } 162 163 void 164 _mesa_delete_shader_cache(struct gl_context *ctx, 165 struct gl_program_cache *cache) 166 { 167 clear_cache(ctx, cache, GL_TRUE); 168 free(cache->items); 169 free(cache); 170 } 171 172 173 struct gl_program * 174 _mesa_search_program_cache(struct gl_program_cache *cache, 175 const void *key, GLuint keysize) 176 { 177 if (cache->last && 178 memcmp(cache->last->key, key, keysize) == 0) { 179 return cache->last->program; 180 } 181 else { 182 const GLuint hash = hash_key(key, keysize); 183 struct cache_item *c; 184 185 for (c = cache->items[hash % cache->size]; c; c = c->next) { 186 if (c->hash == hash && memcmp(c->key, key, keysize) == 0) { 187 cache->last = c; 188 return c->program; 189 } 190 } 191 192 return NULL; 193 } 194 } 195 196 197 void 198 _mesa_program_cache_insert(struct gl_context *ctx, 199 struct gl_program_cache *cache, 200 const void *key, GLuint keysize, 201 struct gl_program *program) 202 { 203 const GLuint hash = hash_key(key, keysize); 204 struct cache_item *c = CALLOC_STRUCT(cache_item); 205 206 c->hash = hash; 207 208 c->key = malloc(keysize); 209 memcpy(c->key, key, keysize); 210 211 c->program = program; /* no refcount change */ 212 213 if (cache->n_items > cache->size * 1.5) { 214 if (cache->size < 1000) 215 rehash(cache); 216 else 217 clear_cache(ctx, cache, GL_FALSE); 218 } 219 220 cache->n_items++; 221 c->next = cache->items[hash % cache->size]; 222 cache->items[hash % cache->size] = c; 223 } 224 225 void 226 _mesa_shader_cache_insert(struct gl_context *ctx, 227 struct gl_program_cache *cache, 228 const void *key, GLuint keysize, 229 struct gl_shader_program *program) 230 { 231 const GLuint hash = hash_key(key, keysize); 232 struct cache_item *c = CALLOC_STRUCT(cache_item); 233 234 c->hash = hash; 235 236 c->key = malloc(keysize); 237 memcpy(c->key, key, keysize); 238 239 c->program = (struct gl_program *)program; /* no refcount change */ 240 241 if (cache->n_items > cache->size * 1.5) { 242 if (cache->size < 1000) 243 rehash(cache); 244 else 245 clear_cache(ctx, cache, GL_TRUE); 246 } 247 248 cache->n_items++; 249 c->next = cache->items[hash % cache->size]; 250 cache->items[hash % cache->size] = c; 251 } 252
