Mercurial > urweb

comparison src/c/urweb.c @ 2279:32a407902d3b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Rewrite LRU cache. Now uses one big hash table and is less buggy.
author Ziv Scully <ziv@mit.edu>
date Wed, 11 Nov 2015 20:01:48 -0500
parents b49d22a4eda8
children 985c8016b592
comparison
equal deleted inserted replaced
2278:b7615e0ac4b0 2279:32a407902d3b
4530 } 4530 }
4531 4531
4532 4532
4533 // Sqlcache 4533 // Sqlcache
4534 4534
4535 void uw_Sqlcache_listDelete(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) { 4535 void uw_Sqlcache_freeValue(uw_Sqlcache_Value *value) {
4536 if (list->first == entry) {
4537 list->first = entry->next;
4538 }
4539 if (list->last == entry) {
4540 list->last = entry->prev;
4541 }
4542 if (entry->prev) {
4543 entry->prev->next = entry->next;
4544 }
4545 if (entry->next) {
4546 entry->next->prev = entry->prev;
4547 }
4548 entry->prev = NULL;
4549 entry->next = NULL;
4550 --(list->size);
4551 }
4552
4553 void uw_Sqlcache_listAdd(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) {
4554 if (list->last) {
4555 list->last->next = entry;
4556 entry->prev = list->last;
4557 list->last = entry;
4558 } else {
4559 list->first = entry;
4560 list->last = entry;
4561 }
4562 ++(list->size);
4563 }
4564
4565 void uw_Sqlcache_listBump(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) {
4566 uw_Sqlcache_listDelete(list, entry);
4567 uw_Sqlcache_listAdd(list, entry);
4568 }
4569
4570 // TODO: deal with time properly.
4571
4572 time_t uw_Sqlcache_getTimeNow() {
4573 return time(NULL);
4574 }
4575
4576 time_t uw_Sqlcache_timeMax(time_t x, time_t y) {
4577 return difftime(x, y) > 0 ? x : y;
4578 }
4579
4580 void uw_Sqlcache_free(uw_Sqlcache_CacheValue *value) {
4581 if (value) { 4536 if (value) {
4582 free(value->result); 4537 free(value->result);
4583 free(value->output); 4538 free(value->output);
4584 free(value); 4539 free(value);
4585 } 4540 }
4586 } 4541 }
4587 4542
4588 void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_CacheEntry* entry) { 4543 void uw_Sqlcache_freeEntry(uw_Sqlcache_Entry* entry) {
4589 //uw_Sqlcache_listUw_Sqlcache_Delete(cache->lru, entry); 4544 if (entry) {
4590 HASH_DELETE(hh, cache->table, entry); 4545 free(entry->key);
4591 uw_Sqlcache_free(entry->value); 4546 uw_Sqlcache_freeValue(entry->value);
4592 free(entry->key); 4547 free(entry);
4593 free(entry); 4548 }
4594 } 4549 }
4595 4550
4596 uw_Sqlcache_CacheValue *uw_Sqlcache_checkHelper(uw_Sqlcache_Cache *cache, char **keys, int timeInvalid) { 4551 // TODO: pick a number.
4597 char *key = keys[cache->height]; 4552 unsigned int uw_Sqlcache_maxSize = 1234567890;
4598 uw_Sqlcache_CacheEntry *entry; 4553
4599 HASH_FIND(hh, cache->table, key, strlen(key), entry); 4554 void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry) {
4600 timeInvalid = uw_Sqlcache_timeMax(timeInvalid, cache->timeInvalid); 4555 HASH_DEL(cache->table, entry);
4601 if (entry && difftime(entry->timeValid, timeInvalid) > 0) { 4556 uw_Sqlcache_freeEntry(entry);
4602 if (cache->height == 0) { 4557 }
4603 // At height 0, entry->value is the desired value. 4558
4604 //uw_Sqlcache_listBump(cache->lru, entry); 4559 uw_Sqlcache_Entry *uw_Sqlcache_find(uw_Sqlcache_Cache *cache, char *key, size_t len, int bump) {
4605 return entry->value; 4560 uw_Sqlcache_Entry *entry = NULL;
4606 } else { 4561 HASH_FIND(hh, cache->table, key, len, entry);
4607 // At height n+1, entry->value is a pointer to a cache at heignt n. 4562 if (entry && bump) {
4608 return uw_Sqlcache_checkHelper(entry->value, keys, timeInvalid); 4563 // Bump for LRU purposes.
4609 } 4564 HASH_DEL(cache->table, entry);
4610 } else { 4565 // Important that we use [entry->key], because [key] might be ephemeral.
4611 return NULL; 4566 HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry);
4612 } 4567 }
4613 } 4568 return entry;
4614 4569 }
4615 uw_Sqlcache_CacheValue *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys) { 4570
4616 return uw_Sqlcache_checkHelper(cache, keys, 0); 4571 void uw_Sqlcache_add(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry, size_t len) {
4617 } 4572 HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry);
4618 4573 if (HASH_COUNT(cache->table) > uw_Sqlcache_maxSize) {
4619 void uw_Sqlcache_storeHelper(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value, int timeNow) { 4574 // Deletes the first element of the cache.
4620 uw_Sqlcache_CacheEntry *entry; 4575 uw_Sqlcache_delete(cache, cache->table);
4621 char *key = keys[cache->height]; 4576 }
4622 HASH_FIND(hh, cache->table, key, strlen(key), entry); 4577 }
4623 if (!entry) { 4578
4624 entry = malloc(sizeof(uw_Sqlcache_CacheEntry)); 4579 unsigned long uw_Sqlcache_getTimeNow(uw_Sqlcache_Cache *cache) {
4625 entry->key = strdup(key); 4580 return ++cache->timeNow;
4626 entry->value = NULL; 4581 }
4627 HASH_ADD_KEYPTR(hh, cache->table, entry->key, strlen(entry->key), entry); 4582
4628 } 4583 unsigned long uw_Sqlcache_timeMax(unsigned long x, unsigned long y) {
4629 entry->timeValid = timeNow; 4584 return x > y ? x : y;
4630 if (cache->height == 0) { 4585 }
4631 //uw_Sqlcache_listAdd(cache->lru, entry); 4586
4632 uw_Sqlcache_free(entry->value); 4587 char uw_Sqlcache_keySep = '_';
4633 entry->value = value; 4588
4634 //if (cache->lru->size > MAX_SIZE) { 4589 char *uw_Sqlcache_allocKeyBuffer(char **keys, int numKeys) {
4635 //uw_Sqlcache_delete(cache, cache->lru->first); 4590 size_t len = 0;
4636 // TODO: return flushed value. 4591 while (numKeys-- > 0) {
4637 //} 4592 char* k = keys[numKeys];
4638 } else { 4593 if (!k) {
4639 if (!entry->value) { 4594 // Can only happen when flushihg, in which case we don't need anything past the null key.
4640 uw_Sqlcache_Cache *newuw_Sqlcache_Cache = malloc(sizeof(uw_Sqlcache_Cache)); 4595 break;
4641 newuw_Sqlcache_Cache->table = NULL; 4596 }
4642 newuw_Sqlcache_Cache->timeInvalid = timeNow; 4597 // Leave room for separator.
4643 newuw_Sqlcache_Cache->lru = cache->lru; 4598 len += 1 + strlen(k);
4644 newuw_Sqlcache_Cache->height = cache->height - 1; 4599 }
4645 entry->value = newuw_Sqlcache_Cache; 4600 char *buf = malloc(len+1);
4646 } 4601 // If nothing is copied into the buffer, it should look like it has length 0.
4647 uw_Sqlcache_storeHelper(entry->value, keys, value, timeNow); 4602 buf[0] = 0;
4648 } 4603 return buf;
4649 } 4604 }
4650 4605
4651 void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value) { 4606 char *uw_Sqlcache_keyCopy(char *buf, char *key) {
4652 uw_Sqlcache_storeHelper(cache, keys, value, uw_Sqlcache_getTimeNow()); 4607 *buf++ = uw_Sqlcache_keySep;
4653 } 4608 return stpcpy(buf, key);
4654 4609 }
4655 void uw_Sqlcache_flushHelper(uw_Sqlcache_Cache *cache, char **keys, int timeNow) { 4610
4656 uw_Sqlcache_CacheEntry *entry; 4611 // The NUL-terminated prefix of [key] below always looks something like "_k1_k2_k3..._kn".
4657 char *key = keys[cache->height]; 4612 // TODO: strlen(key) = buf - key?
4658 if (key) { 4613
4659 HASH_FIND(hh, cache->table, key, strlen(key), entry); 4614 uw_Sqlcache_Value *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys, int numKeys) {
4660 if (entry) { 4615 char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
4661 if (cache->height == 0) { 4616 char *buf = key;
4662 uw_Sqlcache_delete(cache, entry); 4617 time_t timeInvalid = cache->timeInvalid;
4618 uw_Sqlcache_Entry *entry;
4619 while (numKeys-- > 0) {
4620 buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]);
4621 size_t len = buf - key;
4622 entry = uw_Sqlcache_find(cache, key, len, 1);
4623 if (!entry) {
4624 free(key);
4625 return NULL;
4626 }
4627 timeInvalid = uw_Sqlcache_timeMax(timeInvalid, entry->timeInvalid);
4628 }
4629 free(key);
4630 uw_Sqlcache_Value *value = entry->value;
4631 return value && value->timeValid > timeInvalid ? value : NULL;
4632 }
4633
4634 void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, int numKeys, uw_Sqlcache_Value *value) {
4635 char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
4636 char *buf = key;
4637 time_t timeNow = uw_Sqlcache_getTimeNow(cache);
4638 uw_Sqlcache_Entry *entry;
4639 while (numKeys-- > 0) {
4640 buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]);
4641 size_t len = buf - key;
4642 entry = uw_Sqlcache_find(cache, key, len, 1);
4643 if (!entry) {
4644 entry = malloc(sizeof(uw_Sqlcache_Entry));
4645 entry->key = strdup(key);
4646 entry->value = NULL;
4647 entry->timeInvalid = 0; // ASK: is this okay?
4648 uw_Sqlcache_add(cache, entry, len);
4649 }
4650 }
4651 free(key);
4652 uw_Sqlcache_freeValue(entry->value);
4653 entry->value = value;
4654 entry->value->timeValid = timeNow;
4655 }
4656
4657 void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys, int numKeys) {
4658 char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
4659 char *buf = key;
4660 time_t timeNow = uw_Sqlcache_getTimeNow(cache);
4661 uw_Sqlcache_Entry *entry;
4662 while (numKeys-- > 0) {
4663 char *k = keys[numKeys];
4664 if (!k) {
4665 if (entry) {
4666 entry->timeInvalid = timeNow;
4663 } else { 4667 } else {
4664 uw_Sqlcache_flushHelper(entry->value, keys, timeNow); 4668 // Haven't found an entry yet, so the first key was null.
4669 cache->timeInvalid = timeNow;
4665 } 4670 }
4666 } 4671 free(key);
4667 } else { 4672 return;
4668 // Null key means invalidate the entire subtree. 4673 }
4669 cache->timeInvalid = timeNow; 4674 buf = uw_Sqlcache_keyCopy(buf, k);
4670 } 4675 size_t len = buf - key;
4671 } 4676 entry = uw_Sqlcache_find(cache, key, len, 0);
4672 4677 if (!entry) {
4673 void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys) { 4678 free(key);
4674 uw_Sqlcache_flushHelper(cache, keys, uw_Sqlcache_getTimeNow()); 4679 return;
4675 } 4680 }
4681 }
4682 free(key);
4683 // All the keys were non-null and the relevant entry is present, so we delete it.
4684 uw_Sqlcache_delete(cache, entry);
4685 }