storage.c

是一个手机功能的模拟程序

/*
 * Copyright (C) Ericsson Mobile Communications AB, 2000.
 * Licensed to AU-System AB.
 * All rights reserved.
 *
 * This software is covered by the license agreement between
 * the end user and AU-System AB, and may be used and copied
 * only in accordance with the terms of the said agreement.
 *
 * Neither Ericsson Mobile Communications AB nor AU-System AB
 * assumes any responsibility or liability for any errors or inaccuracies in
 * this software, or any consequential, incidental or indirect damage arising
 * out of the use of the Generic WAP Client software.
 */
/*
 * Storage.c
 *
 * Module for storing and retrieving data records on persistent memory.
 *
 * Created by Anders Edenbrandt.
 *
 * Revision history: 
 *   990926, AED: Redesigned
 *   991019, AED: Fixed missing updates of currNode
 *   991110, AED: Fixed bug in ScanStorage
 *   991111, AED: Removed the use of currNode
 *   001213, AED: Conditional inclusion depending on whether
 *                any other module needs these routines.
 *
 */
#include "confvars.h"
#include "storage.h"
#include "cmmnrsrc.h"

#if USE_STORAGE

/*
 * The storage area will be divided into blocks of varying sizes.
 * Each block will have a two-word header, of 8 bytes. The first word
 * will hold the unique block ID, and the second word will hold the
 * block size. A block ID of 0 indicates that the block is currently
 * not allocated. All blocks have a size that is a multiple of 8 bytes.
 * 
 * At startup, the storage is scanned and all the block headers are read.
 * Using the information thus collected, a list is created in
 * main memory: this is called the block list, and it has one node
 * for each block and is sorted in order of positions in the storage area.
 *
 */

#define MINBLOCKSIZE   16      /* Minimum allowed size of a block */
#define START_ID       0x400   /* Block IDs 1-1024 are reserved, i.e.,
                                * this system will never allocate them. */


/*
 * The nodes in the block list:
 */
typedef struct ListNode_st {
  struct ListNode_st *next;
  UINT32             pos;
  UINT32             size;
  UINT32             id;
} ListNode;

/*
 * Each block in the storage has a header:
*/
typedef struct {
  UINT32   size;
  UINT32   id;
} BlockHeader;

/*
 * Macro to copy the contents of a block list node to the store.
 */
#define PUTHEADER(_stobj, _p) do { \
  BlockHeader hd; \
  hd.size = (_p)->size; \
  hd.id = (_p)->id; \
  (_stobj)->writeStorage ((_p)->pos, sizeof (BlockHeader), &hd); \
} while (0)


/*
 * Find the node in the block list with given ID.
 */
static ListNode *
IdToBlock (StorageObject *stobj, UINT32 id)
{
  ListNode *p;

  for (p = stobj->blocklist; p; p = p->next) {
    if (p->id == id)
      break;
  }

  return p;
}

/*
 * Return a new, unique ID, larger than any of IDs currently in use.
 */
static UINT32
AllocNewId (StorageObject *stobj)
{
  stobj->lastId += 1;

  return stobj->lastId;
}

/*
 * Scan the storage area, reading all block headers,
 * and create the block list.
 */
static BOOL
ScanStorage (StorageObject *stobj, UINT32 size)
{
  ListNode    *p, *np;
  BlockHeader hd;
  UINT32      pos;
  UINT32      oldsize, remsize;
  UINT32      largestId = START_ID;

  stobj->readStorage (0, 4, &oldsize);
  if (oldsize == 0) {
    /* The storage area has not been used before: */
    p = NEWARRAY (ListNode, 1);
    if (p == NULL)
      return 0;
    p->next = NULL;
    p->pos = 4;
    p->size = size - 4;
    p->id = 0;
    PUTHEADER (stobj, p);
    stobj->writeStorage (0, 4, &size);
    stobj->lastId = largestId;
    stobj->blocklist = p;

    return TRUE;
  }

  p = NULL;
  pos = 4;
  remsize = size - 4;
  while ((remsize >= MINBLOCKSIZE) && (pos + sizeof (BlockHeader) < oldsize)) {
    stobj->readStorage (pos, sizeof (BlockHeader), &hd);
    largestId = MAX (largestId, hd.id);

    if (hd.size > remsize) {
      /* We cannot fit all of this block: turn it into a free area */
      if ((p == NULL) || (p->id != 0)) {
        np = NEWARRAY (ListNode, 1);
        if (np == NULL)
          return FALSE;
        np->next = NULL;
        np->pos = pos;
        np->size = remsize;
        np->id = 0;
        PUTHEADER (stobj, np);
        if (p != NULL)
          p->next = np;
        else
          stobj->blocklist = np;
      }
      else {
        /* Join with previous free block */
        p->size += remsize;
        PUTHEADER (stobj, p);
      }
      remsize = 0;
      break;
    }

    /* The normal case: */
    np = NEWARRAY (ListNode, 1);
    if (np == NULL)
      return FALSE;
    np->next = NULL;
    np->pos = pos;
    np->size = hd.size;
    np->id = hd.id;
    if (p != NULL)
      p->next = np;
    else
      stobj->blocklist = np;
    if (np->id != 0)
      stobj->bytesUsed += np->size;

    pos += np->size;
    remsize -= np->size;
    p = np;
  } /* End of while loop */

  if (remsize > 0) {
    if ((p != NULL) && (p->id == 0)) {
      /* Join with previous free block */
      p->size += remsize;
      PUTHEADER (stobj, p);
    }
    else if (remsize >= MINBLOCKSIZE) {
      np = NEWARRAY (ListNode, 1);
      if (np == NULL)
        return FALSE;
      np->next = NULL;
      np->pos = pos;
      np->size = remsize;
      np->id = 0;
      PUTHEADER (stobj, np);
      if (p != NULL)
        p->next = np;
      else
        stobj->blocklist = np;
    }
  }

  stobj->lastId = largestId;
  stobj->writeStorage (0, 4, &size);
  
  return TRUE;
}

/*
 * Initialize the storage object to be of the indicated size.
 * "rfp" and "wfp" are pointers to the functions that will be used
 * to read and write from the store.
 * Returns FALSE in case of error, TRUE otherwise.
 */
BOOL
Storage_Init (StorageObject *stobj, UINT32 size,
              ReadFunction *rfp, WriteFunction *wfp)
{
  if (stobj == NULL) {
    return FALSE;
  }

  if (size < MINBLOCKSIZE + 4)
    return FALSE;

  /* Truncate to nearest multiple of 8 */
  size = ((size + 4) & ~7) - 4;

  stobj->size = size;
  stobj->bytesUsed = 0;
  stobj->blocklist = NULL;
  stobj->lastId = START_ID;

  stobj->readStorage = rfp;
  stobj->writeStorage = wfp;

  if (!ScanStorage (stobj, size)) {
    return FALSE;
  }

  return TRUE;
}

/*
 * Prepare a storage object for close down.
 * After a call to this routine, the storage object can not be used
 * further. It will require a new call to Storage_Init first.
 */
void
Storage_Finalize (StorageObject *stobj)
{
  ListNode *p, *tmp;

  if ((stobj == NULL) || (stobj->blocklist == NULL)) {
    return;
  }

  /* Free all nodes in the block list. */
  p = stobj->blocklist;
  while (p) {
    tmp = p;
    p = p->next;
    DEALLOC (&tmp);
  }
  stobj->blocklist = NULL;
  stobj->size = 0;
  stobj->bytesUsed = 0;
}

/*
 * Change the storage area to have the new indicated size.
 * This might require that some data is discarded, in which
 * case arbitrary data blocks might be deleted.
 * Returns FALSE in case of error.
 */
BOOL
Storage_ChangeSize (StorageObject *stobj, UINT32 newSize)
{
  ListNode *p, *tmp;

  if ((stobj == NULL) || (stobj->blocklist == NULL)) {
    return FALSE;
  }

  if (newSize < MINBLOCKSIZE + 4)
    return FALSE;

  /* Truncate to nearest multiple of 8 */
  newSize = ((newSize + 4) & ~7) - 4;

  /* Free all nodes in the block list. */
  p = stobj->blocklist;
  while (p) {
    tmp = p;
    p = p->next;
    DEALLOC (&tmp);
  }
  stobj->blocklist = NULL;
  stobj->size = newSize;
  stobj->bytesUsed = 0;

  if (!ScanStorage (stobj, newSize)) {
    return FALSE;
  }

  return TRUE;
}

#define BUFSIZE 64

/*
 * Copy data from one location in the store to another.
 * This routine does not handle overlapping data areas!
 */
static VOID
CopyData (StorageObject *stobj, UINT32 dstpos, UINT32 srcpos, UINT32 len)
{
  BYTE   buf[BUFSIZE];
  UINT32 n;

  while (len > 0) {
    n = MIN (BUFSIZE, len);
    n = stobj->readStorage (srcpos, n, buf);
    stobj->writeStorage (dstpos, n, buf);
    srcpos += n;
    dstpos += n;
    len -= n;
  }
}

/*
 * Compact the storage area, i.e., try to form larger free blocks.
 * This routine does not necessarily complete the compaction process,
 * rather it tries to make progress towards a complete compaction.
 * Returns TRUE if progress was made, FALSE otherwise.
 * As long as the function returns TRUE, it may be beneficial to
 * call the function again.
 */
BOOL
Storage_Compact (StorageObject *stobj)
{
  ListNode *p, *pn, *pnn;