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