/*
  Copyright (C) 1991, Marcus J. Ranum. All rights reserved.
  Slightly whacked by Andrew Molitor for use with MUSH.
  My apologies to the author..

  Also banged on by dcm@somewhere.or.other, Jellan on the muds,
  to be more complex and more efficient in the context of
  MUSH.

  This version then banged on by Andrew Molitor, 1992, to
  do MUSH but object-by-object, hiding the object part inside
  the cache layer. Upper layers think it's an attribute cache.

  */

#include "autoconf.h"
#include "copyright.h"
#ifndef	lint
static char *RCSid = "$Id: udb_ocache.c,v 1.8 1995/03/21 00:01:31 ambar Exp $";
USE(RCSid);
#endif

/*
  #define CACHE_DEBUG
  #define CACHE_VERBOSE
  */
#include "udb_defs.h"
#include "mudconf.h"

#ifdef	NOSYSTYPES_H
#include	<types.h>
#else
#include	<sys/types.h>
#endif

extern struct Obj *dddb_get();
extern void logf();

/*
  This is by far the most complex and kinky code in UnterMUD. You should
  never need to mess with anything in here - if you value your sanity.
  */


  typedef struct cache {
      Obj *op;
      struct cache *nxt;
      struct cache *prv;
  } Cache;

  typedef struct {
      Cache *head;
      Cache *tail;
  } Chain;

  typedef struct {
      Chain active;
      Chain mactive;
      Chain old;
      Chain mold;
      int count;
  }
CacheLst;

/* This is a MUSH specific definition, depending on Objname being an
   integer type of some sort. */

#define NAMECMP(a,b) ((a)->op) && (((a)->op)->name == (b)->object)

#define DEQUEUE(q, e)	if (e->nxt == (Cache *)NULL) \
q.tail = e->prv; \
else \
e->nxt->prv = e->prv; \
if (e->prv == (Cache *)NULL) \
q.head = e->nxt; \
else \
e->prv->nxt = e->nxt;

#define INSHEAD(q, e)	if (q.head == (Cache *)NULL) { \
						    q.tail = e; \
						    e->nxt = (Cache *)NULL; \
					    } else { \
						     q.head->prv = e; \
						     e->nxt = q.head; \
					     } \
					     q.head = e; \
					     e->prv = (Cache *)NULL;

#define INSTAIL(q, e)	if (q.head == (Cache *)NULL) { \
						    q.head = q.tail = e; \
						    e->prv = (Cache *)NULL; \
					    } else { \
						     q.tail->nxt = e; \
						     e->prv = q.tail; \
					     } \
					     q.tail = e; \
					     e->nxt = (Cache *)NULL;

static Cache *get_free_entry();
static int cache_write();
static void cache_clean();

static Attr *get_attrib();
static void set_attrib();
static void del_attrib();
static void FDECL(objfree, (Obj *));

/* initial settings for cache sizes */
static int cwidth = CACHE_WIDTH;
static int cdepth = CACHE_DEPTH;


/* ntbfw - main cache pointer and list of things to kill off */
static CacheLst *sys_c;

static int cache_initted = 0;
static int cache_frozen = 0;
static int cache_busy = 0;

/* cache stats gathering stuff. you don't like it? comment it out */
time_t cs_ltime;
int cs_writes = 0;		/* total writes */
int cs_reads = 0;		/* total reads */
int cs_dbreads = 0;		/* total read-throughs */
int cs_dbwrites = 0;		/* total write-throughs */
int cs_dels = 0;		/* total deletes */
int cs_checks = 0;		/* total checks */
int cs_rhits = 0;		/* total reads filled from cache */
int cs_ahits = 0;		/* total reads filled active cache */
int cs_whits = 0;		/* total writes to dirty cache */
int cs_fails = 0;		/* attempts to grab nonexistent */
int cs_resets = 0;		/* total cache resets */
int cs_syncs = 0;		/* total cache syncs */
int cs_objects = 0;		/* total cache size */


void 
cache_repl(cp, new)
    Cache *cp;
    Obj *new;
{
    if (cp->op != ONULL)
	objfree(cp->op);
    cp->op = new;
}

int
cache_init(width, depth)
    int width, depth;
{
    int x;
    int y;
    Cache *np, *cp;
    CacheLst *sp;
    static char *ncmsg = "cache_init: cannot allocate cache: ";

    if (cache_initted || sys_c != (CacheLst *) NULL)
	return (0);

    /* If either dimension is specified as non-zero, change it to */
    /* that, otherwise use default. Treat dimensions deparately.  */

    if (width)
	cwidth = width;
    if (depth)
	cdepth = depth;

    sp = sys_c = (CacheLst *) XMALLOC((unsigned) cwidth * sizeof(CacheLst),
				      "cache_init.1");
    if (sys_c == (CacheLst *) NULL) {
	logf(ncmsg, (char *) -1, "\n", (char *) NULL);
	return (-1);
    }
    /* Pre-allocate the initial cache entries in one chunk */
    cp = (Cache *) XMALLOC(cwidth * cdepth * sizeof(Cache), "cache_init.2");
    if (cp == (Cache *) NULL) {
	logf(ncmsg, (char *) -1, "\n", (char *) NULL);
	return (-1);
    }
    for (x = 0; x < cwidth; x++, sp++) {
	sp->active.head = sp->old.head = (Cache *) NULL;
	sp->old.tail = (Cache *) NULL;
	sp->mactive.head = sp->mold.head = (Cache *) NULL;
	sp->mactive.tail = sp->mold.tail = (Cache *) NULL;
	sp->count = cdepth;

	for (y = 0; y < cdepth; y++) {

	    np = cp++;
	    if ((np->nxt = sp->old.head) != (Cache *) NULL)
		np->nxt->prv = np;
	    else
		sp->old.tail = np;

	    np->prv = (Cache *) NULL;
	    np->op = (Obj *) NULL;

	    sp->old.head = np;
	    cs_objects++;
	}
    }

    /* mark caching system live */
    cache_initted++;

    time(&cs_ltime);

    return (0);
}

void 
cache_reset(trim)
    int trim;
{
    int x;
    CacheLst *sp;

    if (!cache_initted)
	return;

    /* unchain and rechain each active list at head of old chain */
    sp = sys_c;
    for (x = 0; x < cwidth; x++, sp++) {
	if (sp->active.head != CNULL) {
	    sp->active.tail->nxt = sp->old.head;

	    if (sp->old.head != CNULL)
		sp->old.head->prv = sp->active.tail;
	    if (sp->old.tail == CNULL)
		sp->old.tail = sp->active.tail;

	    sp->old.head = sp->active.head;
	    sp->active.head = CNULL;
	}
	if (!cache_busy && sp->mactive.head != CNULL) {
	    sp->mactive.tail->nxt = sp->mold.head;

	    if (sp->mold.head != CNULL)
		sp->mold.head->prv = sp->mactive.tail;
	    if (sp->mold.tail == CNULL)
		sp->mold.tail = sp->mactive.tail;

	    sp->mold.head = sp->mactive.head;
	    sp->mactive.head = CNULL;
	}
    }
    cs_resets++;
}




/*
  search the cache for an object, and if it is not found, thaw it.
  this code is probably a little bigger than it needs be because I
  had fun and unrolled all the pointer juggling inline.
  */
Attr *
cache_get(nam)
    Aname *nam;
{
    Cache *cp;
    CacheLst *sp;
    int hv = 0;
    Obj *ret;

    /* firewall */
    if (nam == (Aname *) NULL || !cache_initted) {
#ifdef	CACHE_VERBOSE
	logf("cache_get: NULL object name - programmer error\n", (char *) NULL);
#endif
	return ((Attr *) NULL);
    }
#ifdef	CACHE_DEBUG
    printf("get %d/%d\n", nam->object, nam->attrnum);
#endif

    cs_reads++;

    /* We search the cache for the right Obj, then find the Attrib inside
       that. */

    hv = nam->object % cwidth;
    sp = &sys_c[hv];

    /* search active chain first */
    for (cp = sp->active.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    cs_rhits++;
	    cs_ahits++;
#ifdef	CACHE_DEBUG
	    printf("return active cache -- %d\n", cp->op);
#endif
	    /* Found the Obj, return the Attr within it */

	    return (get_attrib(nam, cp->op));
	}
    }

    /* search modified active chain next. */
    for (cp = sp->mactive.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    cs_rhits++;
	    cs_ahits++;

#ifdef	CACHE_DEBUG
	    printf("return modified active cache -- %d\n", cp->op);
#endif
	    return (get_attrib(nam, cp->op));
	}
    }

    /* search in-active chain now */
    for (cp = sp->old.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* dechain from in-active chain */
	    DEQUEUE(sp->old, cp);
	    /* insert at head of active chain */
	    INSHEAD(sp->active, cp);

	    /* done */
	    cs_rhits++;
#ifdef	CACHE_DEBUG
	    printf("return old cache -- %d\n", cp->op);
#endif
	    return (get_attrib(nam, cp->op));
	}
    }

    /* search modified in-active chain now */
    for (cp = sp->mold.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* dechain from modified in-active chain */
	    DEQUEUE(sp->mold, cp);

	    /* insert at head of modified active chain */
	    INSHEAD(sp->mactive, cp);

	    /* done */
	    cs_rhits++;

#ifdef	CACHE_DEBUG
	    printf("return modified old cache -- %d\n", cp->op);
#endif
	    return (get_attrib(nam, cp->op));
	}
    }

    /* DARN IT - at this point we have a certified, type-A cache miss */

    /* thaw the object from wherever. */

    if ((ret = DB_GET(&(nam->object))) == (Obj *) NULL) {
	cs_fails++;
	cs_dbreads++;
#ifdef	CACHE_DEBUG
	printf("Object %d not in db\n", nam->object);
#endif
	return ((Attr *) NULL);
    } else
	cs_dbreads++;

    if ((cp = get_free_entry(sp)) == CNULL)
	return ((Attr *) NULL);

    cp->op = ret;

    /* relink at head of active chain */
    INSHEAD(sp->active, cp);

#ifdef	CACHE_DEBUG
    printf("returning attr %d, object %d loaded into cache -- %d\n",
	   nam->attrnum, nam->object, cp->op);
#endif
    return (get_attrib(nam, ret));
}




/*
  put an object back into the cache. this is complicated by the
  fact that when a function calls this with an object, the object
  is *already* in the cache, since calling functions operate on
  pointers to the cached objects, and may or may not be actively
  modifying them. in other words, by the time the object is handed
  to cache_put, it has probably already been modified, and the cached
  version probably already reflects those modifications!

  so - we do a couple of things: we make sure that the cached
  object is actually there, and set its dirty bit. if we can't
  find it - either we have a (major) programming error, or the
  *name* of the object has been changed, or the object is a totally
  new creation someone made and is inserting into the world.

  in the case of totally new creations, we simply accept the pointer
  to the object and add it into our environment. freeing it becomes
  the responsibility of the cache code. DO NOT HAND A POINTER TO
  CACHE_PUT AND THEN FREE IT YOURSELF!!!!

  There are other sticky issues about changing the object pointers
  of MUDs and their names. This is left as an exercise for the
  reader.
  */
int
#ifdef IN_MEM_COMPRESSION
cache_put(nam, obj, len)
#else
cache_put(nam, obj)
#endif
    Aname *nam;
    Attr *obj;
{
    Cache *cp;
    CacheLst *sp;
    Obj *newobj;
    int hv = 0;

    /* firewall */
    if (obj == (Attr *) NULL || nam == (Aname *) NULL || !cache_initted) {
#ifdef	CACHE_VERBOSE
	logf("cache_put: NULL object/name - programmer error\n", (char *) NULL);
#endif
	return (1);
    }
    cs_writes++;

    /* generate hash */
    hv = nam->object % cwidth;
    sp = &sys_c[hv];

    /* step one, search active chain, and if we find the obj, dirty it */
    for (cp = sp->active.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* Right object, set the attribute */
#ifdef IN_MEM_COMPRESSION
	    set_attrib(nam, cp->op, obj, len);
#else
	    set_attrib(nam, cp->op, obj);
#endif
#ifdef	CACHE_DEBUG
	    printf("cache_put object %d, attr %d -- %d\n",
		   nam->object, nam->attrnum, cp->op);
#endif
	    DEQUEUE(sp->active, cp);
	    INSHEAD(sp->mactive, cp);
	    cs_whits++;
	    return (0);
	}
    }

    /* step two, search modified active chain, and if we find the obj, we're done */
    for (cp = sp->mactive.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* Right object, set the attribute */
#ifdef IN_MEM_COMPRESSION
	    set_attrib(nam, cp->op, obj, len);
#else
	    set_attrib(nam, cp->op, obj);
#endif
#ifdef	CACHE_DEBUG
	    printf("cache_put object %d,attr %d -- %d\n",
		   nam->object, nam->attrnum, cp->op);
#endif
	    cs_whits++;
	    return (0);
	}
    }

    /* step three, search in-active chain.  If we find it, move it to the mod active */
    for (cp = sp->old.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* Right obj. Set the attrib. */
#ifdef IN_MEM_COMPRESSION
	    set_attrib(nam, cp->op, obj, len);
#else
	    set_attrib(nam, cp->op, obj);
#endif
#ifdef	CACHE_DEBUG
	    printf("cache_put object %d, attr %d -- %d\n",
		   nam->object, nam->attrnum, cp->op);
#endif
	    DEQUEUE(sp->old, cp);
	    INSHEAD(sp->mactive, cp);
	    cs_whits++;
	    return (0);
	}
    }

    /* step four, search modified in-active chain */
    for (cp = sp->mold.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {

	    /* Right object. Set the attribute. */
#ifdef IN_MEM_COMPRESSION
	    set_attrib(nam, cp->op, obj, len);
#else
	    set_attrib(nam, cp->op, obj);
#endif
#ifdef	CACHE_DEBUG
	    printf("cache_put %d,%d %d\n",
		   nam->object, nam->attrnum, cp->op);
#endif
	    DEQUEUE(sp->mold, cp);
	    INSHEAD(sp->mactive, cp);
	    cs_whits++;
	    return (0);
	}
    }

    /* Ok, now the fact that we're caching objects, and pretending
       to cache attributes starts to *hurt*. We gotta try to
       get the object in to cache, see.. */

    newobj = DB_GET(&(nam->object));
    if (newobj == (Obj *) NULL) {

	/* SHIT! Totally NEW object! */

	newobj = (Obj *) XMALLOC(sizeof(Obj), "cache_put");
	if (newobj == (Obj *) NULL)
	    return (1);

	newobj->atrs = ATNULL;
	newobj->name = nam->object;
    }
    /* Now we got the thing, hang the new version of the attrib on it. */
#ifdef IN_MEM_COMPRESSION
    set_attrib(nam, newobj, obj, len);
#else
    set_attrib(nam, newobj, obj);
#endif
    /* add it to the cache */
    if ((cp = get_free_entry(sp)) == CNULL)
	return (1);

    cp->op = newobj;

    /* link at head of modified active chain */
    INSHEAD(sp->mactive, cp);

#ifdef	CACHE_DEBUG
    printf("cache_put %d/%d new in cache %d\n", nam->object, nam->attrnum, cp->op);
#endif

    /* e finito ! */
    return (0);
}

static Cache *
get_free_entry(sp)
    CacheLst *sp;
{
    Cache *cp;

    /* if there are no old cache object holders left, allocate one */
    if ((cp = sp->old.tail) == CNULL) {

	if (!cache_busy && !cache_frozen &&
	    (cp = sp->mold.tail) != CNULL) {
	    /* unlink old cache chain tail */
	    if (cp->prv != CNULL) {
		sp->mold.tail = cp->prv;
		cp->prv->nxt = cp->nxt;
	    } else		/* took last one */
		sp->mold.head = sp->mold.tail = CNULL;

#ifdef	CACHE_DEBUG
	    printf("clean object %d from cache %d\n",
		   (cp->op)->name, cp->op);
#endif
	    if ((cp->op)->at_count == 0) {
		if (DB_DEL(&((cp->op)->name), x))
		    return (CNULL);
		cs_dels++;
	    } else {
		if (DB_PUT(cp->op, &((cp->op)->name)))
		    return (CNULL);
		cs_dbwrites++;
	    }
	} else {
	    if ((cp = (Cache *) XMALLOC(sizeof(Cache),
					"get_free_entry")) == CNULL)
		fatal("cache get_free_entry: malloc failed",
		      (char *) -1, (char *) NULL);

	    cp->op = (Obj *) NULL;
	    sp->count++;
	    cs_objects++;
	}
    } else {

	/* unlink old cache chain tail */
	if (cp->prv != CNULL) {
	    sp->old.tail = cp->prv;
	    cp->prv->nxt = cp->nxt;
	} else			/* took last one */
	    sp->old.head = sp->old.tail = CNULL;
    }

    /* free object's data */

    cache_repl(cp, ONULL);
    return (cp);
}

static int 
cache_write(cp)
    Cache *cp;
{
    while (cp != CNULL) {
#ifdef	CACHE_DEBUG
	printf("sync %d -- %d\n", cp->op->name, cp->op);
#endif
	if (cp->op->at_count == 0) {
	    if (DB_DEL(&((cp->op)->name), x)) {
		log_db_err(cp->op->name, 0, "delete");
		return (1);
	    }
	    cs_dels++;
	} else {
	    if (DB_PUT(cp->op, &((cp->op)->name))) {
		log_db_err(cp->op->name, 0, "write");
		return (1);
	    }
	    cs_dbwrites++;
	}
	cp = cp->nxt;
    }
    return (0);
}

static void 
cache_clean(sp)
    CacheLst *sp;
{
    /* move the modified inactive chain to the inactive chain */
    if (sp->mold.head != NULL) {
	if (sp->old.head == NULL) {
	    sp->old.head = sp->mold.head;
	    sp->old.tail = sp->mold.tail;
	} else {
	    sp->old.tail->nxt = sp->mold.head;
	    sp->mold.head->prv = sp->old.tail;
	    sp->old.tail = sp->mold.tail;
	}
	sp->mold.head = sp->mold.tail = CNULL;
    }
    /* same for the modified active chain */
    if (sp->mactive.head != CNULL) {
	if (sp->active.head == CNULL) {
	    sp->active.head = sp->mactive.head;
	    sp->active.tail = sp->mactive.tail;
	} else {
	    sp->active.tail->nxt = sp->mactive.head;
	    sp->mactive.head->prv = sp->active.tail;
	    sp->active.tail = sp->mactive.tail;
	}
	sp->mactive.head = sp->mactive.tail = CNULL;
    }
}

int 
NDECL(cache_sync)
{
    int x;
    CacheLst *sp;

    cs_syncs++;

    if (!cache_initted)
	return (1);

    if (cache_frozen)
	return (0);

    cache_reset(0);

    for (x = 0, sp = sys_c; x < cwidth; x++, sp++) {
	if (cache_write(sp->mold.head))
	    return (1);
	if (cache_write(sp->mactive.head))
	    return (1);
	cache_clean(sp);
    }
    return (0);
}

/*
  Mark this attr as deleted in the cache. The object will flush back to
  disk without it, eventually.
  */
void
cache_del(nam)
    Aname *nam;
{
    Cache *cp;
    CacheLst *sp;
    Obj *obj;
    int hv = 0;

    if (nam == (Aname *) NULL || !cache_initted)
	return;

#ifdef CACHE_DEBUG
    printf("cache_del: object %d, attr %d\n", nam->object, nam->attrnum);
#endif

    cs_dels++;

    hv = nam->object % cwidth;
    sp = &sys_c[hv];

    /* mark dead in cache */
    for (cp = sp->active.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    DEQUEUE(sp->active, cp);
	    INSHEAD(sp->mactive, cp);
	    del_attrib(nam, cp->op);
	    return;
	}
    }
    for (cp = sp->mactive.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    del_attrib(nam, cp->op);
	    return;
	}
    }

    for (cp = sp->old.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    DEQUEUE(sp->old, cp);
	    INSHEAD(sp->mactive, cp);
	    del_attrib(nam, cp->op);
	    return;
	}
    }
    for (cp = sp->mold.head; cp != CNULL; cp = cp->nxt) {
	if (NAMECMP(cp, nam)) {
	    DEQUEUE(sp->mold, cp);
	    INSHEAD(sp->mactive, cp);
	    del_attrib(nam, cp->op);
	    return;
	}
    }

    /* If we got here, the object the attribute's on isn't in cache */
    /* At all.  So we get to fish it off of disk, nuke the attrib,  */
    /* and shove the object in cache, so it'll be flushed back later */

    obj = DB_GET(&(nam->object));
    if (obj == (Obj *) NULL)
	return;

    if ((cp = get_free_entry(sp)) == CNULL)
	return;

    del_attrib(nam, obj);

    cp->op = obj;

    INSHEAD(sp->mactive, cp);
    return;
}

/*
  And now a totally new suite of functions for manipulating
  attributes within an Obj. Woo. Woo. Andrew.

  */

static Attr *
get_attrib(anam, obj)
    Aname *anam;
    Obj *obj;
{
    int lo, mid, hi;
    Attrib *a;

#ifdef CACHE_DEBUG
    printf("get_attrib: object %d, attr %d, obj ptr %d\n",
	   anam->object, anam->attrnum, obj);
#endif

    /* Binary search for the attribute */

    lo = 0;
    hi = obj->at_count - 1;
    a = obj->atrs;
    while (lo <= hi) {
	mid = ((hi - lo) >> 1) + lo;
	if (a[mid].attrnum == anam->attrnum) {
	    return (Attr *) a[mid].data;
	    break;
	} else if (a[mid].attrnum > anam->attrnum) {
	    hi = mid - 1;
	} else {
	    lo = mid + 1;
	}
    }
#ifdef CACHE_DEBUG
    printf("get_attrib: not found.\n");
#endif
    return ((Attr *) NULL);	/* Not found */
}

static void
#ifdef IN_MEM_COMPRESSION
set_attrib(anam, obj, value, len)
    Aname *anam;
    Obj *obj;
    Attr *value;
    int len;

#else
set_attrib(anam, obj, value)
    Aname *anam;
    Obj *obj;
    Attr *value;

#endif
{
    int hi, lo, mid;
    Attrib *a;

    /* Demands made elsewhere insist that we cope with the
       case of an empty object. */

    if (obj->atrs == ATNULL) {
	a = (Attrib *) XMALLOC(sizeof(Attrib), "set_attrib");
	if (a == ATNULL)	/* Fail silently. It's a game. */
	    return;

	obj->atrs = a;
	obj->at_count = 1;
	a[0].attrnum = anam->attrnum;
	a[0].data = (char *) value;
#ifdef IN_MEM_COMPRESSION
	a[0].size = len;
#else
	a[0].size = ATTR_SIZE(value);
#endif
	return;
    }
    /* Binary search for the attribute */

    lo = 0;
    hi = obj->at_count - 1;

    a = obj->atrs;
    while (lo <= hi) {
	mid = ((hi - lo) >> 1) + lo;
	if (a[mid].attrnum == anam->attrnum) {
	    free(a[mid].data);
	    a[mid].data = (char *) value;
#ifdef IN_MEM_COMPRESSION
	    a[mid].size = len;
#else
	    a[mid].size = ATTR_SIZE(value);
#endif
	    return;
	} else if (a[mid].attrnum > anam->attrnum) {
	     hi = mid - 1;
	} else {
	    lo = mid + 1;
	}
    }

    /*
     * If we get here, we didn't find it, so lo = hi + 1, and the
     * attribute should be inserted between them.
     */

    a = (Attrib *) realloc(obj->atrs, (obj->at_count + 1) * sizeof(Attrib));

    if (!a) {
	/* Silently fail. It's just a game. */

	return;
    }

    /* move the stuff upwards one slot */
    if (lo < obj->at_count)
	bcopy((char *)&(a[lo]), (char *)&(a[lo + 1]),
		(obj->at_count - lo) * sizeof(Attrib));

    a[lo].data = value;
    a[lo].attrnum = anam->attrnum;
#ifdef IN_MEM_COMPRESSION
    a[lo].size = len;
#else
    a[lo].size = ATTR_SIZE(value);
#endif
    obj->at_count = obj->at_count + 1;
    obj->atrs = a;

}

static void
del_attrib(anam, obj)
    Aname *anam;
    Obj *obj;
{
    int hi, lo, mid;
    Attrib *a;

#ifdef CACHE_DEBUG
    printf("del_attrib: deleteing attr %d on object %d (%d)\n", anam->attrnum,
	   obj->name, anam->object);
#endif

    if (!obj->at_count || !obj->atrs)
	return;

    if (obj->at_count < 0)
	abort();

    /* Binary search for the attribute */

    lo = 0;
    hi = obj->at_count - 1;
    a = obj->atrs;
    while (lo <= hi) {
	mid = ((hi - lo) >> 1) + lo;
	if (a[mid].attrnum == anam->attrnum) {
	    free(a[mid].data);
	    obj->at_count -= 1;
	    if (mid != obj->at_count)
		bcopy((char *)(a + mid + 1), (char *)(a + mid),
		    (obj->at_count - mid) * sizeof(Attrib));
	    return;
	} else if (a[mid].attrnum > anam->attrnum) {
	    hi = mid - 1;
	} else {
	    lo = mid + 1;
	}
    }
}

/* And something to free all the goo on an Obj, as well as the Obj. */

static void
objfree(o)
    Obj *o;
{
    int i;
    Attrib *a;

    if (!o->atrs) {
	free(o);
	return;
    }
    a = o->atrs;
    for (i = 0; i < o->at_count; i++)
	free(a[i].data);

    free(a);
    free(o);
}