aboutsummaryrefslogtreecommitdiffstats
path: root/src/cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cache.c')
-rw-r--r--src/cache.c241
1 files changed, 178 insertions, 63 deletions
diff --git a/src/cache.c b/src/cache.c
index c2db00d..8d15728 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -1,17 +1,48 @@
+/*
+ * Copyright (C) 2018 "IoT.bzh"
+ * Author José Bollo <jose.bollo@iot.bzh>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>
+#include <ctype.h>
#include "cache.h"
+/**
+ * The cache structure is a blob of memory ('content')
+ * of 'count' bytes of only 'used' bytes.
+ * That blob containts at sequence of records of variable length
+ * Each records holds the following values in that given order:
+ * - length: 2 bytes unsigned integer LSB first, MSB second
+ * - hit count: 1 byte unsigned integer
+ * - value: 1 byte unsigned integer
+ * - client: zero terminated string
+ * - session: zero terminated string
+ * - user: zero terminated string
+ * - permission: zero terminated string
+ * -
+ */
struct cache
{
- uint32_t begin;
uint32_t used;
uint32_t count;
- char content[1];
+ uint8_t content[1];
};
static
@@ -20,57 +51,129 @@ lenat(
cache_t *cache,
uint32_t pos
) {
- uint32_t p, n;
- char c;
+ return ((uint32_t)cache->content[pos]) | (((uint32_t)cache->content[pos + 1]) << 8);
+}
- p = pos + 1;
- if (p >= cache->count)
- p -= cache->count;
- n = 4;
- while (n--) {
- do {
- c = cache->content[p++];
- if (p >= cache->count)
- p -= cache->count;
- } while(c);
- }
- return (p > pos ? p : (p + cache->count)) - pos;
+static
+void
+drop_at(
+ cache_t *cache,
+ uint32_t pos
+) {
+ uint32_t e, l;
+
+ l = lenat(cache, pos);
+ e = pos + l;
+ cache->used -= l;
+ if (cache->used > e)
+ memmove(&cache->content[pos], &cache->content[e], cache->used - e);
}
static
void
-drop_one(
+drop_lre(
cache_t *cache
) {
- uint32_t l = lenat(cache, cache->begin);
- cache->used -= l;
- cache->begin += l;
- if (cache->begin > cache->count)
- cache->begin -= cache->count;
+ uint32_t found = 0, iter = 0;
+ uint8_t hmin = 255, hint;
+
+ while (iter < cache->used) {
+ hint = cache->content[iter + 2];
+ if (hint < hmin)
+ found = iter;
+ iter += lenat(cache, iter);
+ }
+ if (found < cache->used)
+ drop_at(cache, found);
}
static
void
-addc(
+hit(
cache_t *cache,
- char c
+ uint32_t pos
) {
- uint32_t pos;
- if (cache->used == cache->count)
- drop_one(cache);
- pos = cache->begin + cache->used++;
- if (pos > cache->count)
- pos -= cache->count;
- cache->content[pos < cache->count ? pos : pos - cache->count] = c;
+ uint32_t iter = 0;
+ uint8_t hint;
+
+ while (iter < cache->used) {
+ if (iter == pos)
+ hint = 255;
+ else {
+ hint = cache->content[iter + 2];
+ if (hint)
+ hint--;
+ }
+ cache->content[iter + 2] = hint;
+ iter += lenat(cache, iter);
+ }
}
static
-void
-adds(
+const char*
+cmpi(
+ const char *head,
+ const char *other
+) {
+ char c;
+ while(toupper(c = *head++) == toupper(*other++))
+ if (!c)
+ return head;
+ return 0;
+}
+
+static
+const char*
+cmp(
+ const char *head,
+ const char *other
+) {
+ char c;
+ while((c = *head++) == *other++)
+ if (!c)
+ return head;
+ return 0;
+}
+
+
+static
+int
+match(
+ const char *head,
+ const char *client,
+ const char *session,
+ const char *user,
+ const char *permission
+) {
+ head = cmp(head, client);
+ if (head)
+ head = cmp(head, session);
+ if (head)
+ head = cmp(head, user);
+ if (head)
+ head = cmpi(head, permission);
+ return !!head;
+}
+
+static
+uint32_t
+search(
cache_t *cache,
- const char *s
+ const char *client,
+ const char *session,
+ const char *user,
+ const char *permission
) {
- do { addc(cache, *s); } while(*s++);
+ char *txt;
+ uint32_t iter = 0;
+
+ while (iter < cache->used) {
+ txt = (char*)&cache->content[iter + 4];
+ if (match(txt, client, session, user, permission))
+ return iter;
+ iter += lenat(cache, iter);
+ }
+ return iter;
}
int
@@ -82,17 +185,35 @@ cache_put(
const char *permission,
int value
) {
- if (cache == NULL
- || strlen(client) + strlen(session)
- + strlen(user) + strlen(permission)
- + 5 > cache->count)
+ uint32_t pos;
+ size_t size, scli, sses, susr, sper;
+
+ if (cache == NULL || value < 0 || value > 255)
return -EINVAL;
- addc(cache, (char)value);
- adds(cache, client);
- adds(cache, session);
- adds(cache, user);
- adds(cache, permission);
+ pos = search(cache, client, session, user, permission);
+ if (pos < cache->used)
+ cache->content[pos + 3] = (uint8_t)value;
+ else {
+ scli = strlen(client);
+ sses = strlen(session);
+ susr = strlen(user);
+ sper = strlen(permission);
+ size = scli + sses + susr + sper + 8;
+ if (size > 65535)
+ return -EINVAL;
+ if (size > cache->count)
+ return -ENOMEM;
+ while(cache->used + (uint32_t)size > cache->count)
+ drop_lre(cache);
+ pos = cache->used;
+ cache->content[pos + 0] = (uint8_t)(size & 255);
+ cache->content[pos + 1] = (uint8_t)((size >> 8) & 255);
+ cache->content[pos + 2] = (uint8_t)255;
+ cache->content[pos + 3] = (uint8_t)value;
+ stpcpy(1 + stpcpy(1 + stpcpy(1 + stpcpy((char*)&cache->content[pos + 4], client), session), user), permission);
+ cache->used += (uint32_t)size;
+ }
return 0;
}
@@ -104,6 +225,13 @@ cache_search(
const char *user,
const char *permission
) {
+ uint32_t pos;
+
+ pos = search(cache, client, session, user, permission);
+ if (pos < cache->used) {
+ hit(cache, pos);
+ return (int)cache->content[pos + 3];
+ }
return -ENOENT;
}
@@ -111,10 +239,8 @@ void
cache_clear(
cache_t *cache
) {
- if (cache) {
+ if (cache)
cache->used = 0;
- cache->begin = 0;
- }
}
int
@@ -124,29 +250,18 @@ cache_resize(
) {
cache_t *c = *cache, *nc;
- while (c && c->used > newsize)
- drop_one(c);
+ if (c)
+ while (c->used > newsize)
+ drop_lre(c);
- nc = malloc(newsize - 1 + sizeof *c);
+ nc = realloc(c, newsize - 1 + sizeof *c);
if (nc == NULL)
return -ENOMEM;
- nc->begin = 0;
nc->count = newsize;
- if (!c || c->used == 0)
+ if (!c)
nc->used = 0;
- else {
- if (c->begin + c->used <= c->count)
- memcpy(&nc->content[0], &c->content[c->begin], c->used);
- else {
- memcpy(&nc->content[0], &c->content[c->begin], c->count - c->begin);
- memcpy(&nc->content[c->count - c->begin], &c->content[0], c->used + c->begin - c->count);
- }
-
- nc->used = c->used;
- }
*cache = nc;
- free(c);
return 0;
}