GRASS Programmer's Manual
6.4.2(2012)
|
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 }