/* > C.lru - LRU data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "sperror.h"
#include "lru.h"

#include <stdio.h>

#ifdef MEMDEBUG
#include <mnemosyn.h>
#endif

/* General component routines */

LRU
LRU_new(int obj_len)
{
register LRU d;

 d = malloc(sizeof(struct LRU));

 if (d == NULL)
 {
 return NULL;
#ifdef never
 sperror(__LINE__,__FILE__,"Unexpected Out of Memory");
 sexit(1);
#endif
 }

 d->head = NULL;
 d->tail = NULL;
 d->obj_size = obj_len;
 d->size = 0;
 return d;
}

void
 LRU_free(LRU *d)
{
 if (*d == NULL)
 return;
 LRU_clear(d);
 free(*d);
 *d = NULL;
}

void
 LRU_clear(LRU *d)
{
link this_entry = (*d)->head;
link next_entry;

 if (*d == NULL)
 return;
 while (this_entry != NULL)
 {
 next_entry = this_entry->next;
 free(this_entry);
 this_entry = next_entry;
 }

 (*d)->head = (*d)->tail = NULL;
 (*d)->size = 0;
}

int
 LRU_copy(LRU d1, const LRU d2)
{
link p;
link l_new;
link last;
int size;

 if (d1->obj_size != d2->obj_size)
 return ERR;

 LRU_clear(&d1);

 last = (link) d1;
 size = d2->obj_size;

 for (p = d2->head; p != NULL; p = p->next)
 {
 l_new = malloc(sizeof(struct link) - 1 + size);
 if (l_new == NULL)
 {
 LRU_clear(&d1);
 return ERR;
 }
 last->next = l_new;
 memcpy(l_new->data, p->data, size);
 last = l_new;
 d1->size++;
 }

 last->next = NULL;
 d1->tail = last;

 return OK;
}

int
 LRU_equal(const LRU d1, const LRU d2)
{
int size;
link p1;
link p2;

 if (d1->obj_size != d2->obj_size)
 return 0;

 size = d1->obj_size;

 for
 (
 p1 = d1->head, p2 = d2->head;
 p1 != NULL && p2 != NULL;
 p1 = p1->next, p2 = p2->next
 )
 {
 if (memcmp(p1->data, p2->data, size) != 0)
 return 0;
 }

 return (p1 == p2);
}

int
 LRU_empty(const LRU d)
{
 return (d->head == NULL);
}

#ifdef testing
int
 LRU_size(const LRU d)
{
int i = 0;
link p;

 for (p = d->head; p != NULL; p = p->next)
 ++i;

 if (i != d->size)
 {
 sperror(__LINE__,__FILE__,"bad size in lru %d <> %d\n",i,d->size);
 sexit(1);
 }
 return i;
}
#endif

int
 LRU_iterate(const LRU d, int (*process) (void *))
{
int ret = 0;
link p;

 for (p = d->head; p != NULL; p = p->next)
 {
 ret = (*process) (p->data);

 /* Non-zero => stop processing here */

 if (ret != STATUS_CONTINUE)
 break;
 }

 /* Negative => Abnormal (error) termination */

 return (ret >= 0);
}

/* LRU-specific routines */

static int
 lru_addl(LRU d, int pos, const void *object, link l_new)
{

 if (l_new == NULL)
 return ERR;

 memcpy(l_new->data, object, d->obj_size);

 if (pos == MOST_RECENT)
 {
 l_new->next = d->head;
 d->head = l_new;
 if (d->tail == NULL)
 d->tail = d->head;
 } else
 {
 l_new->next = NULL;
 if (d->tail != NULL)
 ((link) d->tail)->next = l_new;
 d->tail = l_new;
 if (d->head == NULL)
 d->head = d->tail;
 }
 return OK;
}

int
 LRU_add(LRU d, int pos, const void *object)
{
link l_new;

 if ((l_new = malloc(sizeof(struct link) - 1 + d->obj_size)) == NULL)
 {
 return ERR;
#ifdef never
 sperror(__LINE__,__FILE__,"Unexpected Out of Memory");
 sexit(1);
#endif
 }
 d->size++;
#ifdef memcheck
 spprint("Allocated LRU member @ %p\n",l_new);
#endif
 return (lru_addl(d, pos, object, l_new));
}

int
 LRU_pop(LRU d, int pos)
{
link p;

 if (d->head == NULL)
 return ERR;

 else
 if (d->head == d->tail)
 {
 free(d->head);
 d->head = d->tail = NULL;
 } else
 if (pos == MOST_RECENT)
 {
 p = d->head;
 d->head = p->next;
 free(p);
 } else
 {
 p = d->head;
 while (p->next != (link) d->tail)
 p = p->next;
 p->next = NULL;
 free(d->tail);
#ifdef memcheck
 spprint("De-allocated LRU member @ %p\n",d->tail);
#endif
 d->tail = p;
 }
 d->size--;

 return OK;
}

int
 LRU_pop_most_recent(LRU d)
{
 return (LRU_pop(d, MOST_RECENT));
}

int
 LRU_pop_least_recent(LRU d)
{
 return (LRU_pop(d, LEAST_RECENT));
}

void *
 LRU_most_recent(const LRU d)
{
 if (d->head == NULL)
 return NULL;

 return ((link) d->head)->data;
}

void *
 LRU_least_recent(const LRU d)
{
 if (d->tail == NULL)
 return NULL;

 return ((link) d->tail)->data;
}

int
 LRU_used(LRU d, const void *object)
{
 /*
 Locate entry in LRU which contains object. Unlink it. Re-insert it to
 the head of the LRU
 */
link l_this = NULL, l = NULL, p = NULL, parent = NULL;

 /*
 Case 1: empty LRU. return false. Case 2: one element. Remove it and
 clear lru if matches. Return true. return false if no match. Case 3:
 found somewhere in list. Unhook. Case 4: not found. return false.
 */

 /* Case 1 */
 if (d == NULL)
 return (0 != 0);
 if (d->head == NULL)
 {
 assert(d->tail == NULL);
 return (0 != 0);
 }
 /* Case 2 */
 l_this = d->head;
 if (memcmp(l_this->data, object, d->obj_size) == 0)
 {
 /* Found the desired object. Now unhook. */
 l = d->head;
 if (d->head == d->tail)
 {
 /* Only one item */
 assert(l_this->next == NULL);
 d->tail = NULL;
 }
 d->head = l_this->next;
 lru_addl(d, MOST_RECENT, l->data, l);
 return (0 == 0);
 }
 parent = NULL;
 for (p = d->head; p != NULL; p = p->next)
 {
 /* Do something with 'p'. */
 if (memcmp(p->data, object, d->obj_size) == 0)
 {
 /* Case 3. Found the desired object. Now unhook. */
 l = p;
 if (p == d->tail)
 {
 assert(p->next == NULL);
 d->tail = parent;
 }
 parent->next = p->next;
 lru_addl(d, MOST_RECENT, l->data, l);
 return (0 == 0);
 }
 parent = p;
 }

 /* Case 4 */
 return (0 != 0);
}

int
 LRU_remove(LRU d, const void *object)
{
link l_this = NULL, l = NULL, p = NULL, parent = NULL;

 /*
 Case 1: empty LRU. return false. Case 2: one element. Remove it and
 clear lru if matches. Return true. return false if no match. Case 3:
 found somewhere in list. Unhook. Case 4: not found. return false.
 */

 /* Case 1 */
 if (d == NULL)
 return (0 != 0);
 if (d->head == NULL)
 {
 assert(d->tail == NULL);
 return (0 != 0);
 }
 /* Case 2 */
 l_this = d->head;
 if (memcmp(l_this->data, object, d->obj_size) == 0)
 {
 /* Found the desired object. Now unhook. */
 l = d->head;
 if (d->head == d->tail)
 {
 /* Only one item */
 assert(l_this->next == NULL);
 d->tail = NULL;
 }
 d->head = l_this->next;
 free(l);
 d->size--;
 return (0 == 0);
 }
 parent = NULL;
 for (p = d->head; p != NULL; p = p->next)
 {
 /* Do something with 'p'. */
 if (memcmp(p->data, object, d->obj_size) == 0)
 {
 /* Case 3. Found the desired object. Now unhook. */
 l = p;
 if (p == d->tail)
 {
 assert(p->next == NULL);
 d->tail = parent;
 }
 parent->next = p->next;
 free(l);
 d->size--;
 return (0 == 0);
 }
 parent = p;
 }

 /* Case 4 */
 return (0 != 0);
}

/*---------------------------------------------------------------------------*/

#ifdef DBMAIN
int
 print(void *ptr)
{
 printf("%d ", *(int *) ptr);
 return 1;
}

void
 LRU_dump(LRU d)
{
 printf("LRU: ");
 LRU_iterate(d, print);
 putchar('\n');
}

#endif

/*---------------------------------------------------------------------------*/

#ifdef DBMAIN

#define BUFLEN 255

int
 main(int argc, char **argv)
{
#ifdef DBMAIN /* Not using PMoore's Deque test at the moment. Maybe
 later. */
 /* my debug */
char buf[BUFLEN];
int i;
LRU numbers;

 numbers = LRU_new(sizeof(int));
 if (argc == 1)
 {
 for (;;)
 {
 printf(">");
 fgets(buf, BUFLEN, stdin);

 if (buf[0] == '\n' || buf[0] == '\0')
 {
 continue;
 } else
 if (strcmp(buf, "help\n") == 0)
 {
 fprintf(stderr, "commands are: add <n>, use <n>, del <n>, print, and quit.\n");
 } else
 if ((strcmp(buf, "quit\n") == 0)
 || (strcmp(buf, "q\n") == 0)
 || (strcmp(buf, "exit\n") == 0))
 {
 LRU_clear(&numbers);
 free(numbers);
 exit(0);
 } else
 if (strcmp(buf, "print\n") == 0)
 {
 LRU_dump(numbers);
 } else
 if (strcmp(buf, "size\n") == 0)
 {
 fprintf(stderr, "LRU: size = %d\n", LRU_size(numbers));
 } else
 if (sscanf(buf, "add %d", &i) == 1)
 {
 LRU_add(numbers, MOST_RECENT, &i);
 } else
 if (sscanf(buf, "del %d", &i) == 1)
 {
 if (!LRU_remove(numbers, &i))
 {
 fprintf(stderr, "LRU: %d not present\n", i);
 }
 } else
 if (sscanf(buf, "use %d", &i) == 1)
 {
 if (!LRU_used(numbers, &i))
 {
 fprintf(stderr, "LRU: %d not present\n", i);
 }
 } else
 {
 buf[strlen(buf) - 1] = '\0';
 fprintf(stderr, "Unknown command '%s'\n", buf);
 }
 }
 } else
 {
 i = 67;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 9999;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 45;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 33;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 123;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 0;
 LRU_add(numbers, MOST_RECENT, &i);
 i = 45;
 LRU_remove(numbers, &i);
 i = 33;
 LRU_used(numbers, &i);
 fprintf(stderr, "Output should be \"33 0 123 9999 67\"\n");
 LRU_dump(numbers);
 LRU_clear(&numbers);
 free(numbers);
 }
#else
char buf[BUFLEN], str[BUFLEN];
int i, j, num;
LRU d[10];

 for (i = 0; i < 10; ++i)
 d[i] = LRU_new(sizeof(int));

 for (;;)
 {
 printf(">");
 fgets(buf, BUFLEN, stdin);

 if (buf[0] == '\n' || buf[0] == '\0')
 continue;
 else
 if (sscanf(buf, "clear %1d", &i) == 1)
 LRU_clear(&(d[i]));
 else
 if (sscanf(buf, "copy %1d %1d", &i, &j) == 2)
 LRU_copy(d[i], d[j]);
 else
 if (sscanf(buf, "equal %1d %1d", &i, &j) == 2)
 printf("%s\n", (LRU_equal(d[i], d[j]) ? "yes" : "no"));
 else
 if (sscanf(buf, "empty %1d", &i) == 1)
 printf("%s\n", (LRU_empty(d[i]) ? "yes" : "no"));
 else
 if (sscanf(buf, "size %1d", &i) == 1)
 printf("%d\n", LRU_size(d[i]));
 else
 if (sscanf(buf, "dump %1d", &i) == 1)
 LRU_dump(d[i]);
 else
 if (sscanf(buf, "add %1d %s %d", &i, str, &num) == 3)
 LRU_add(d[i], (str[0] == 'f'), &num);
 else
 if (sscanf(buf, "pop %1d %s", &i, str) == 2)
 LRU_pop(d[i], (str[0] == 'f'));
 else
 if (sscanf(buf, "MOST_RECENT %1d", &i) == 1)
 {
int *p = LRU_most_recent(d[i]);

 if (p == NULL)
 printf("Empty\n");
 else
 printf("%d\n", *p);
 } else
 if (sscanf(buf, "LEAST_RECENT %1d", &i) == 1)
 {
int *p = LRU_least_recent(d[i]);

 if (p == NULL)
 printf("Empty\n");
 else
 printf("%d\n", *p);
 } else
 if (strncmp(buf, "quit", 4) == 0)
 break;
 else
 printf("Mistake\n");
 }

 printf("Deleting d[0-9]\n");
 for (i = 0; i < 10; ++i)
 printf("%d has %d members \n",i,LRU_size(d[i]));
 for (i = 0; i < 10; ++i)
 LRU_free(&(d[i]));

#endif
 return 0;
}

#endif