GRASS Programmer's Manual  6.4.2(2012)
cache.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <sys/types.h>
00005 #include <unistd.h>
00006 #include <grass/G3d.h>
00007 #include "G3d_intern.h"
00008 #include "cachehash.h"
00009 
00010 /*---------------------------------------------------------------------------*/
00011 
00012 #define IS_ACTIVE_ELT(elt) (c->locks[elt] != 2)
00013 #define IS_NOT_ACTIVE_ELT(elt) (c->locks[elt] == 2)
00014 #define IS_LOCKED_ELT(elt) (c->locks[elt] == 1)
00015 #define IS_UNLOCKED_ELT(elt) (c->locks[elt] == 0)
00016 #define IS_NOT_IN_QUEUE_ELT(elt) (IS_LOCKED_ELT (elt))
00017 #define IS_IN_QUEUE_ELT(elt) (! IS_NOT_IN_QUEUE_ELT (elt))
00018 
00019 #define DEACTIVATE_ELT(elt) ((IS_LOCKED_ELT(elt) ? \
00020                               (c->nofUnlocked)++ : (0)), \
00021                              c->locks[elt] = 2)
00022 #define LOCK_ELT(elt) ((IS_LOCKED_ELT(elt) ? \
00023                         (0) : (c->nofUnlocked)--), \
00024                        (c->locks[elt] = 1))
00025 #define UNLOCK_ELT(elt) ((IS_LOCKED_ELT(elt) ? \
00026                           (c->nofUnlocked)++ : (0)), \
00027                          (c->locks[elt] = 0))
00028 
00029 #define ONE_UNLOCKED_ELT_ONLY (c->first == c->last)
00030 #define ARE_MIN_UNLOCKED (c->nofUnlocked <= c->minUnlocked)
00031 
00032 /*---------------------------------------------------------------------------*/
00033 
00034 void G3d_cache_reset(G3D_cache * c)
00035 {
00036     int i;
00037 
00038     for (i = 0; i < c->nofElts; i++) {
00039         DEACTIVATE_ELT(i);
00040         c->next[i] = i + 1;
00041         c->prev[i] = i - 1;
00042         c->names[i] = -1;
00043     }
00044 
00045     c->prev[0] = c->next[c->nofElts - 1] = -1;
00046     c->first = 0;
00047     c->last = c->nofElts - 1;
00048 
00049     c->autoLock = 0;
00050     c->nofUnlocked = c->nofElts;
00051     c->minUnlocked = 1;
00052 
00053     G3d_cache_hash_reset(c->hash);
00054 }
00055 
00056 /*---------------------------------------------------------------------------*/
00057 
00058 static int cache_dummy_fun(int tileIndex, const void *tileBuf, void *map)
00059 {
00060     return 1;
00061 }
00062 
00063 /*---------------------------------------------------------------------------*/
00064 
00065 void G3d_cache_dispose(G3D_cache * c)
00066 {
00067     if (c == NULL)
00068         return;
00069 
00070     G3d_cache_hash_dispose(c->hash);
00071 
00072     if (c->elts != NULL)
00073         G3d_free(c->elts);
00074     if (c->names != NULL)
00075         G3d_free(c->names);
00076     if (c->locks != NULL)
00077         G3d_free(c->locks);
00078     if (c->next != NULL)
00079         G3d_free(c->next);
00080     if (c->prev != NULL)
00081         G3d_free(c->prev);
00082 
00083     G3d_free(c);
00084 }
00085 
00086 /*---------------------------------------------------------------------------*/
00087 
00088 void *G3d_cache_new(int nofElts, int sizeOfElts, int nofNames,
00089                     int (*eltRemoveFun) (), void *eltRemoveFunData,
00090                     int (*eltLoadFun) (), void *eltLoadFunData)
00091 {
00092     G3D_cache *tmp;
00093     int i;
00094 
00095     tmp = G3d_malloc(sizeof(G3D_cache));
00096     if (tmp == NULL) {
00097         G3d_error("G3d_cache_new: error in G3d_malloc");
00098         return (void *)NULL;
00099     }
00100 
00101     tmp->hash = NULL;
00102 
00103     tmp->nofElts = nofElts;
00104     tmp->eltSize = sizeOfElts;
00105     tmp->elts = G3d_malloc(tmp->eltSize * tmp->nofElts);
00106     tmp->names = G3d_malloc(sizeof(int) * tmp->nofElts);
00107     tmp->locks = G3d_malloc(tmp->nofElts);
00108     tmp->next = G3d_malloc(sizeof(int) * tmp->nofElts);
00109     tmp->prev = G3d_malloc(sizeof(int) * tmp->nofElts);
00110 
00111     if ((tmp->elts == NULL) || (tmp->names == NULL) || (tmp->locks == NULL) ||
00112         (tmp->next == NULL) || (tmp->prev == NULL)) {
00113 
00114         G3d_cache_dispose(tmp);
00115         G3d_error("G3d_cache_new: error in G3d_malloc");
00116         return (void *)NULL;
00117     }
00118 
00119     /* Init the cache lock */
00120     for(i = 0; i < tmp->nofElts; i++)
00121         tmp->locks[i] = 0;
00122 
00123     tmp->eltRemoveFun = eltRemoveFun;
00124     tmp->eltRemoveFunData = eltRemoveFunData;
00125     tmp->eltLoadFun = eltLoadFun;
00126     tmp->eltLoadFunData = eltLoadFunData;
00127 
00128     tmp->hash = G3d_cache_hash_new(nofNames);
00129     if (tmp->hash == NULL) {
00130         G3d_cache_dispose(tmp);
00131         G3d_error("G3d_cache_new: error in G3d_cache_hash_new");
00132         return (void *)NULL;
00133     }
00134 
00135     G3d_cache_reset(tmp);
00136 
00137     return tmp;
00138 }
00139 
00140 /*---------------------------------------------------------------------------*/
00141 
00142 void
00143 G3d_cache_set_removeFun(G3D_cache * c, int (*eltRemoveFun) (),
00144                         void *eltRemoveFunData)
00145 {
00146     c->eltRemoveFun = eltRemoveFun;
00147     c->eltRemoveFunData = eltRemoveFunData;
00148 }
00149 
00150 /*---------------------------------------------------------------------------*/
00151 
00152 void
00153 G3d_cache_set_loadFun(G3D_cache * c, int (*eltLoadFun) (),
00154                       void *eltLoadFunData)
00155 {
00156     c->eltLoadFun = eltLoadFun;
00157     c->eltLoadFunData = eltLoadFunData;
00158 }
00159 
00160 /*---------------------------------------------------------------------------*/
00161 
00162 void *G3d_cache_new_read(int nofElts, int sizeOfElts, int nofNames,
00163                          read_fn * eltLoadFun, void *eltLoadFunData)
00164 {
00165     return G3d_cache_new(nofElts, sizeOfElts, nofNames,
00166                          cache_dummy_fun, NULL, eltLoadFun, eltLoadFunData);
00167 }
00168 
00169 /*---------------------------------------------------------------------------*/
00170 
00171 static void cache_queue_dequeue(G3D_cache * c, int index)
00172 {
00173     if (IS_NOT_IN_QUEUE_ELT(index))
00174         G3d_fatalError("cache_queue_dequeue: index not in queue");
00175 
00176     if (index == c->first)
00177         c->first = c->next[index];
00178     if (index == c->last)
00179         c->last = c->prev[index];
00180 
00181     if (c->next[index] != -1)
00182         c->prev[c->next[index]] = c->prev[index];
00183     if (c->prev[index] != -1)
00184         c->next[c->prev[index]] = c->next[index];
00185 
00186     c->next[index] = c->prev[index] = -1;
00187 }
00188 
00189 /*---------------------------------------------------------------------------*/
00190 
00191 static void cache_queue_enqueue(G3D_cache * c, int left, int index)
00192 {
00193     if (IS_IN_QUEUE_ELT(index))
00194         G3d_fatalError("cache_queue_enqueue: index already in queue");
00195 
00196     if (c->first == -1) {
00197         if (left != c->last)
00198             G3d_fatalError("cache_queue_enqueue: position out of range");
00199 
00200         c->first = c->last = index;
00201         return;
00202     }
00203 
00204     if (left >= 0 && IS_NOT_IN_QUEUE_ELT(left))
00205         G3d_fatalError("cache_queue_enqueue: position not in queue");
00206 
00207 
00208     if (left == -1) {
00209         c->next[index] = c->first;
00210         c->prev[c->first] = index;
00211         c->first = index;
00212 
00213         return;
00214     }
00215 
00216     c->prev[index] = left;
00217 
00218     if (c->next[left] == -1) {
00219         c->next[left] = index;
00220         c->last = index;
00221 
00222         return;
00223     }
00224 
00225     c->prev[c->next[left]] = index;
00226     c->next[index] = c->next[left];
00227     c->next[left] = index;
00228 }
00229 
00230 /*---------------------------------------------------------------------------*/
00231 
00232 static int cache_queue_get_top(G3D_cache * c)
00233 {
00234     int top;
00235 
00236     top = c->first;
00237 
00238     cache_queue_dequeue(c, c->first);
00239 
00240     return top;
00241 }
00242 
00243 /*---------------------------------------------------------------------------*/
00244 
00245 static void cache_queue_append(G3D_cache * c, int index)
00246 {
00247     cache_queue_enqueue(c, c->last, index);
00248 }
00249 
00250 /*---------------------------------------------------------------------------*/
00251 
00252 static void cache_queue_preppend(G3D_cache * c, int index)
00253 {
00254     cache_queue_enqueue(c, -1, index);
00255 }
00256 
00257 /*---------------------------------------------------------------------------*/
00258 
00259 /*---------------------------------------------------------------------------*/
00260 
00261                         /* EXPORTED FUNCTIONS */
00262 
00263 /*---------------------------------------------------------------------------*/
00264 
00265 /*---------------------------------------------------------------------------*/
00266 
00267 int G3d_cache_lock(G3D_cache * c, int name)
00268 {
00269     int index;
00270 
00271     index = G3d_cache_hash_name2index(c->hash, name);
00272     if (index == -1) {
00273         G3d_error("G3d_cache_lock: name not in cache");
00274         return 0;
00275     }
00276 
00277     if (IS_LOCKED_ELT(index))
00278         return 1;
00279     if (ONE_UNLOCKED_ELT_ONLY)
00280         return -1;
00281     if (ARE_MIN_UNLOCKED)
00282         return -1;
00283 
00284     cache_queue_dequeue(c, index);
00285     LOCK_ELT(index);
00286 
00287     return 1;
00288 }
00289 
00290 /*---------------------------------------------------------------------------*/
00291 
00292 void G3d_cache_lock_intern(G3D_cache * c, int index)
00293 {
00294     if (IS_LOCKED_ELT(index))
00295         return;
00296 
00297     cache_queue_dequeue(c, index);
00298     LOCK_ELT(index);
00299 }
00300 
00301 /*---------------------------------------------------------------------------*/
00302 
00303 int G3d_cache_unlock(G3D_cache * c, int name)
00304 {
00305     int index;
00306 
00307     index = G3d_cache_hash_name2index(c->hash, name);
00308     if (index == -1) {
00309         G3d_error("G3d_cache_unlock: name not in cache");
00310         return 0;
00311     }
00312 
00313     if (IS_UNLOCKED_ELT(index))
00314         return 1;
00315 
00316     cache_queue_append(c, index);
00317     UNLOCK_ELT(index);
00318 
00319     return 1;
00320 }
00321 
00322 /*---------------------------------------------------------------------------*/
00323 
00324 int G3d_cache_unlock_all(G3D_cache * c)
00325 {
00326     int index;
00327 
00328     for (index = 0; index < c->nofElts; index++)
00329         if (IS_LOCKED_ELT(index))
00330             if (!G3d_cache_unlock(c, c->names[index])) {
00331                 G3d_error("G3d_cache_unlock_all: error in G3d_cache_unlock");
00332                 return 0;
00333             }
00334 
00335     return 1;
00336 }
00337 
00338 /*---------------------------------------------------------------------------*/
00339 
00340 int G3d_cache_lock_all(G3D_cache * c)
00341 {
00342     int index;
00343 
00344     for (index = 0; index < c->nofElts; index++)
00345         if (IS_UNLOCKED_ELT(index))
00346             G3d_cache_lock_intern(c, index);
00347 
00348     return 1;
00349 }
00350 
00351 /*---------------------------------------------------------------------------*/
00352 
00353 void G3d_cache_autolock_on(G3D_cache * c)
00354 {
00355     c->autoLock = 1;
00356 }
00357 
00358 /*---------------------------------------------------------------------------*/
00359 
00360 void G3d_cache_autolock_off(G3D_cache * c)
00361 {
00362     c->autoLock = 0;
00363 }
00364 
00365 /*---------------------------------------------------------------------------*/
00366 
00367 void G3d_cache_set_minUnlock(G3D_cache * c, int nofMinUnLocked)
00368 {
00369     c->minUnlocked = nofMinUnLocked;
00370 }
00371 
00372 /*---------------------------------------------------------------------------*/
00373 
00374 static int cache_remove_elt(G3D_cache * c, int name, int doFlush)
00375 {
00376     int index;
00377 
00378     index = G3d_cache_hash_name2index(c->hash, name);
00379     if (index == -1) {
00380         G3d_error("G3d_cache_deactivate_elt : name not in cache");
00381         return 0;
00382     }
00383 
00384     if (IS_NOT_ACTIVE_ELT(index))
00385         return 1;
00386 
00387     if (IS_IN_QUEUE_ELT(index)) {
00388         cache_queue_dequeue(c, index);
00389         LOCK_ELT(index);
00390     }
00391 
00392     if (doFlush)
00393         if (!c->eltRemoveFun(name, c->elts + c->eltSize * index,
00394                              c->eltRemoveFunData)) {
00395             G3d_error("cache_remove_elt: error in c->eltRemoveFun");
00396             return 0;
00397         }
00398 
00399     cache_queue_preppend(c, index);
00400     DEACTIVATE_ELT(index);
00401 
00402     G3d_cache_hash_remove_name(c->hash, name);
00403 
00404     return 1;
00405 }
00406 
00407 /*---------------------------------------------------------------------------*/
00408 
00409 int G3d_cache_remove_elt(G3D_cache * c, int name)
00410 {
00411     if (!cache_remove_elt(c, name, 0)) {
00412         G3d_error("G3d_cache_remove_elt: error in cache_remove_elt");
00413         return 0;
00414     }
00415 
00416     return 1;
00417 }
00418 
00419 /*---------------------------------------------------------------------------*/
00420 
00421 int G3d_cache_flush(G3D_cache * c, int name)
00422 {
00423     if (!cache_remove_elt(c, name, 1)) {
00424         G3d_error("G3d_cache_flush: error in cache_remove_elt");
00425         return 0;
00426     }
00427 
00428     return 1;
00429 }
00430 
00431 /*---------------------------------------------------------------------------*/
00432 
00433 int G3d_cache_remove_all(G3D_cache * c)
00434 {
00435     int index;
00436 
00437     for (index = 0; index < c->nofElts; index++)
00438         if (IS_ACTIVE_ELT(index))
00439             if (!G3d_cache_remove_elt(c, c->names[index])) {
00440                 G3d_error
00441                     ("G3d_cache_remove_all: error in G3d_cache_remove_elt");
00442                 return 0;
00443             }
00444 
00445     return 1;
00446 }
00447 
00448 /*---------------------------------------------------------------------------*/
00449 
00450 int G3d_cache_flush_all(G3D_cache * c)
00451 {
00452     int index;
00453 
00454     for (index = 0; index < c->nofElts; index++)
00455         if (IS_ACTIVE_ELT(index))
00456             if (!G3d_cache_flush(c, c->names[index])) {
00457                 G3d_error("G3d_cache_flush_all: error in G3d_cache_flush");
00458                 return 0;
00459             }
00460 
00461     return 1;
00462 }
00463 
00464 /*---------------------------------------------------------------------------*/
00465 
00466 void *G3d_cache_elt_ptr(G3D_cache * c, int name)
00467 {
00468     int index, oldName, doUnlock;
00469 
00470     index = G3d_cache_hash_name2index(c->hash, name);
00471 
00472     if (index != -1) {
00473         if (c->autoLock)
00474             if (IS_UNLOCKED_ELT(index) && (!ONE_UNLOCKED_ELT_ONLY) &&
00475                 (!ARE_MIN_UNLOCKED))
00476                 G3d_cache_lock_intern(c, index);
00477 
00478         return c->elts + c->eltSize * index;
00479     }
00480 
00481     index = c->first;
00482     if (IS_ACTIVE_ELT(index)) {
00483         oldName = c->names[index];
00484         G3d_cache_hash_remove_name(c->hash, oldName);
00485         if (!c->eltRemoveFun(oldName, c->elts + c->eltSize * index,
00486                              c->eltRemoveFunData)) {
00487             G3d_error("G3d_cache_elt_ptr: error in c->eltRemoveFun");
00488             return NULL;
00489         }
00490     }
00491 
00492     G3d_cache_hash_load_name(c->hash, name, index);
00493 
00494     doUnlock = ((!c->autoLock) || ONE_UNLOCKED_ELT_ONLY || ARE_MIN_UNLOCKED);
00495 
00496     UNLOCK_ELT(index);
00497     c->names[index] = name;
00498     G3d_cache_lock_intern(c, index);
00499 
00500     if (doUnlock)
00501         if (!G3d_cache_unlock(c, name)) {
00502             G3d_error("G3d_cache_elt_ptr: error in G3d_cache_unlock");
00503             return NULL;
00504         }
00505 
00506     if (!c->eltLoadFun(name, c->elts + c->eltSize * index, c->eltLoadFunData)) {
00507         G3d_error("G3d_cache_elt_ptr: error in c->eltLoadFun");
00508         return NULL;
00509     }
00510 
00511     return c->elts + c->eltSize * index;
00512 }
00513 
00514 /*---------------------------------------------------------------------------*/
00515 
00516 int G3d_cache_load(G3D_cache * c, int name)
00517 {
00518     if (G3d_cache_elt_ptr(c, name) == NULL) {
00519         G3d_error("G3d_cache_load: error in G3d_cache_elt_ptr");
00520         return 0;
00521     }
00522 
00523     return 1;
00524 }
00525 
00526 /*---------------------------------------------------------------------------*/
00527 
00528 int G3d_cache_get_elt(G3D_cache * c, int name, void *dst)
00529 {
00530     const void *elt;
00531 
00532     elt = G3d_cache_elt_ptr(c, name);
00533     if (elt == NULL) {
00534         G3d_error("G3d_cache_get_elt: error in G3d_cache_elt_ptr");
00535         return 0;
00536     }
00537 
00538     memcpy(dst, elt, c->eltSize);
00539 
00540     return 1;
00541 }
00542 
00543 /*---------------------------------------------------------------------------*/
00544 
00545 int G3d_cache_put_elt(G3D_cache * c, int name, const void *src)
00546 {
00547     void *elt;
00548 
00549     elt = G3d_cache_elt_ptr(c, name);
00550     if (elt == NULL) {
00551         G3d_error("G3d_cache_put_elt: error in G3d_cache_elt_ptr");
00552         return 0;
00553     }
00554 
00555     memcpy(elt, src, c->eltSize);
00556 
00557     return 1;
00558 }
00559 
00560 /*---------------------------------------------------------------------------*/
00561 
00562 /*---------------------------------------------------------------------------*/
00563 
00564                         /* TEST FUNCTIONS */
00565 
00566 /*---------------------------------------------------------------------------*/
00567 
00568 /*---------------------------------------------------------------------------*/
00569 
00570 static void cache_test_print(G3D_cache * c)
00571 {
00572     int i, al;
00573     int *a;
00574 
00575     al = c->autoLock;
00576     G3d_cache_autolock_off(c);
00577 
00578     printf("\n--------------------------------\n");
00579     for (i = 0; i < c->nofElts; i++) {
00580         printf("elt %d: ", i);
00581         if (IS_NOT_ACTIVE_ELT(i)) {
00582             printf("na\n");
00583             continue;
00584         }
00585 
00586         a = (int *)G3d_cache_elt_ptr(c, c->names[i]);
00587         /*G3d_cache_get_elt (c, c->names[i], a); */
00588         printf("name %d val %d %s\n", c->names[i], a[17],
00589                (IS_LOCKED_ELT(i) ? "locked" :
00590                 IS_UNLOCKED_ELT(i) ? "unlocked" : ""));
00591     }
00592     printf("\n--------------------------------\n");
00593 
00594     if (al)
00595         G3d_cache_autolock_on(c);
00596 }
00597 
00598 /*---------------------------------------------------------------------------*/
00599 
00600 static int cache_test_flush_fun(int name, const void *eltPtr, void *data)
00601 {
00602     printf("flushing name %d value %d\n", name, ((const int *)eltPtr)[17]);
00603     return 0;
00604 }
00605 
00606 /*---------------------------------------------------------------------------*/
00607 
00608 typedef struct
00609 {
00610 
00611     int *value;
00612     int size;
00613 
00614 } cache_test_data_type;
00615 
00616 static int cache_test_load_fun(int name, void *eltPtr, void *data)
00617 {
00618     const void *src;
00619 
00620     printf("loading name %d value %d\n", name,
00621            ((cache_test_data_type *) data)->value[17]);
00622 
00623     src = ((cache_test_data_type *) data)->value;
00624     memcpy(eltPtr, src, ((cache_test_data_type *) data)->size);
00625 
00626     return 0;
00627 }
00628 
00629 /*---------------------------------------------------------------------------*/
00630 
00631 static cache_test_data_type ctd;
00632 
00633 static void cache_test_add(void *c, int name, int val)
00634 {
00635     static int firstTime = 1;
00636 
00637     if (firstTime) {
00638         ctd.value = G3d_malloc(((G3D_cache *) c)->eltSize * sizeof(int));
00639         firstTime = 0;
00640     }
00641 
00642     ctd.value[17] = val;
00643     ctd.size = ((G3D_cache *) c)->eltSize;
00644 
00645     G3d_cache_load(c, name);
00646 }
00647 
00648 /*---------------------------------------------------------------------------*/
00649 
00650 int MAIN()
00651 {
00652     void *c;
00653 
00654     c = G3d_cache_new(3, 76 * sizeof(int), 100000,
00655                       cache_test_flush_fun, NULL, cache_test_load_fun, &ctd);
00656 
00657     G3d_cache_autolock_on(c);
00658     cache_test_print(c);
00659     cache_test_add(c, 1111, -11);
00660     cache_test_print(c);
00661     cache_test_add(c, 2222, -22);
00662     cache_test_print(c);
00663     cache_test_add(c, 3333, -33);
00664     cache_test_print(c);
00665     cache_test_add(c, 4444, -44);
00666     cache_test_print(c);
00667     G3d_cache_unlock_all(c);
00668     cache_test_print(c);
00669     G3d_cache_load(c, 2222);
00670     cache_test_print(c);
00671     cache_test_add(c, 5555, -55);
00672     cache_test_print(c);
00673     cache_test_add(c, 6666, -66);
00674     cache_test_print(c);
00675     cache_test_add(c, 7777, -77);
00676     cache_test_print(c);
00677     cache_test_add(c, 8888, -88);
00678     cache_test_print(c);
00679     cache_test_add(c, 9999, -99);
00680     cache_test_print(c);
00681     G3d_cache_flush(c, 9999);
00682     cache_test_print(c);
00683     G3d_cache_flush_all(c);
00684     cache_test_print(c);
00685     cache_test_add(c, 1111, -11);
00686     cache_test_print(c);
00687     cache_test_add(c, 2222, -22);
00688     cache_test_print(c);
00689     cache_test_add(c, 3333, -33);
00690     cache_test_print(c);
00691     G3d_cache_reset(c);
00692     cache_test_print(c);
00693     cache_test_add(c, 1111, -11);
00694     cache_test_print(c);
00695     cache_test_add(c, 2222, -22);
00696     cache_test_print(c);
00697     cache_test_add(c, 3333, -33);
00698     cache_test_print(c);
00699 
00700     return 0;
00701 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines