DataMuseum.dk

top - metrics - download

    Length: 10510 (0x290e)
    Types: TextFile
    Names: »gdbmstore.c«

└─⟦a05ed705a⟧ Bits:30007078 DKUUG GNU 2/12/89
    └─⟦0befd2614⟧ »./gdbm-0.8.tar.Z« 
        └─⟦b993d2893⟧ 
            └─⟦this⟧ »gdbm/gdbmstore.c« 

TextFile

/* gdbmstore.c - Add a new key/data pair to the database. */

/*  GNU DBM  - DataBase Manager (database subroutines) by Philip A. Nelson
    Copyright (C) 1989  Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    You may contact the author by:
       e-mail:  phil@wwu.edu
      us-mail:  Philip A. Nelson
                Computer Science Department
                Western Washington University
                Bellingham, WA 98226
        phone:  (206) 676-3035
       
*************************************************************************/


#include <stdio.h>
#include <sys/file.h>
#include <sys/types.h>
#include <sys/stat.h>
#include "gdbm.h"
#include "gdbmerrno.h"
extern gdbm_error gdbm_errno;


/* Add a new element to the database.  CONTENT is keyed by KEY.  The file on
   disk is updated to reflect the structure of the new database before returning
   from this procedure.  A return value of 0 means no errors.  A return value
   of -1 means that the item was not stored in the data base because the
   caller was not an official writer. */

int
gdbm_store (dbf, key, content)
     dbm_file_info *dbf;
     datum key;
     datum content;
{
  int new_hash_val;		/* The new hash value. */
  int elem_loc;			/* The location in hash bucket. */
  int file_adr;			/* The address of new space in the file.  */
  int num_bytes;		/* Used for error detection. */
  int free_adr;			/* For freeing a previous definition. */
  int free_size;		/* Size of the previous definition. */

  /* First check to make sure this guy is a writer. */
  if (dbf->read_write != DBM_WRITER)
    {
      gdbm_errno = READER_CANT_STORE;
      return -1;
    }

  /* Look for the key in the file.  A side effect loads the correct bucket. */
  elem_loc = _dbm_findkey (dbf, key);

  /* Compute the new hash value. */
  new_hash_val = _dbm_hash (key);

  /* Did we find the item? */
  if (elem_loc != -1)
    {
      /* Just replace the data. */
      free_adr  = dbf->bucket->h_table[elem_loc].data_pointer;
      free_size = dbf->bucket->h_table[elem_loc].key_size +
	          dbf->bucket->h_table[elem_loc].data_size;
    }
  else
    {
      /* This is a new item, prepare for the insert. */
      free_size = 0;
      while (dbf->bucket->count == dbf->header.bucket_elems)
	{
	  /* Split the current bucket. */
	  split_current(dbf, new_hash_val);
	}
      
      /* Find space to insert into bucket and set elem_loc to that place. */
      elem_loc = new_hash_val % dbf->header.bucket_elems;
      while (dbf->bucket->h_table[elem_loc].hash_value != -1)
	{  elem_loc = (elem_loc + 1) % dbf->header.bucket_elems; }

      /* We now have another element in the bucket.  Add the new information. */
      dbf->bucket->count += 1;
      dbf->bucket->h_table[elem_loc].hash_value = new_hash_val;
      strncpy (dbf->bucket->h_table[elem_loc].key_start, key.dptr, SMALL);
    }

  /* Get space in the file for the data.  */
  file_adr = _dbm_alloc (dbf, key.dsize+content.dsize, FALSE);

  /* Update current bucket data pointer and sizes. */
  dbf->bucket->h_table[elem_loc].data_pointer = file_adr;
  dbf->bucket->h_table[elem_loc].key_size = key.dsize;
  dbf->bucket->h_table[elem_loc].data_size = content.dsize;

  /* Write the data to the file. */
  _dbm_update (dbf, 0x77777707, file_adr, key.dsize+content.dsize,
	       dbf->bucket_adr, elem_loc);
  num_bytes = lseek (dbf->desc, file_adr, L_SET);
  if (num_bytes != file_adr) _dbm_fatal (dbf, "lseek error");
  num_bytes = write (dbf->desc, key.dptr, key.dsize);
  if (num_bytes != key.dsize) _dbm_fatal (dbf, "write error");
  num_bytes = write (dbf->desc, content.dptr, content.dsize);
  if (num_bytes != content.dsize) _dbm_fatal (dbf, "write error");

  /* Write current bucket to the file. */
  num_bytes = lseek (dbf->desc, dbf->bucket_adr, L_SET);
  if (num_bytes != dbf->bucket_adr) _dbm_fatal (dbf, "lseek error");
  num_bytes = write (dbf->desc, dbf->bucket, dbf->header.bucket_size);
  if (num_bytes != dbf->header.bucket_size) _dbm_fatal (dbf, "write error");

  /* Make sure all is written to medium. */
  fsync (dbf->desc);
  
  /* Free previous space if this is a replacement. */
  if (free_size != 0)
    _dbm_free (dbf, free_adr, free_size);

  /* Everything worked correctly. */
  _dbm_end_update (dbf);
  return 0;
  
}


/* Split the current bucket.  This includes moving all items in the bucket to
   a new bucket.  This doesn't require any disk reads because all hash values
   are stored in the buckets.  Splitting the current bucket may require
   doubling the size of the hash directory.  */
static
split_current(dbf, next_insert)
     dbm_file_info *dbf;
     int next_insert;
{
  hash_bucket *bucket[2]; 	/* Pointers to the new buckets. */
  int          index;		/* Used in array indexing. */
  int	       select;		/* Used to index bucket during movement. */
  int          new_bits;	/* The number of bits for the new buckets. */
  int	       new_adr;		/* File address of the new bucket. */
  int          elem_loc;	/* Location in new bucket to put element. */
  bucket_element *old_el;	/* Pointer into the old bucket. */
  int          dir_start;	/* Used in updating the directory. */
  int          dir_end;
  int          dir_adr; 	/* Address of the new directory. */
  int          dir_size;	/* Size of the new directory. */
  int          old_adr; 	/* Address of the old directory. */
  int          old_size; 	/* Size of the old directory. */
  int	      *new_dir;		/* Pointer to the new directory. */
  int	       num_bytes;	/* For use with write. */

  /* Allocate space for new buckets. */
  bucket[0] = (hash_bucket *) malloc (dbf->header.bucket_size);
  if (bucket[0] == NULL) _dbm_fatal (dbf, "malloc error");
  bucket[1] = (hash_bucket *) malloc (dbf->header.bucket_size);
  if (bucket[1] == NULL) _dbm_fatal (dbf, "malloc error");
  new_bits = dbf->bucket->bucket_bits+1;
  _dbm_new_bucket (dbf, bucket[0], new_bits);
  _dbm_new_bucket (dbf, bucket[1], new_bits);
  
  /* Double the directory size if necessary. */
  if (dbf->header.dir_bits == dbf->bucket->bucket_bits)
    {
      dir_size = dbf->header.dir_size * 2;
      dir_adr  = _dbm_alloc (dbf, dir_size, TRUE);
      new_dir  = (int *) malloc (dir_size);
      if (new_dir == NULL) _dbm_fatal (dbf, "malloc error");
      for (index = 0; index < dbf->header.dir_size / sizeof (int); index++)
	{
	  new_dir[2*index]   = dbf->dir[index];
	  new_dir[2*index+1] = dbf->dir[index];
	}

      /* Write out new directory. */
      num_bytes = lseek (dbf->desc, dir_adr, L_SET);
      if (num_bytes != dir_adr) _dbm_fatal (dbf, "lseek error");
      num_bytes = write (dbf->desc, new_dir, dir_size);
      if (num_bytes != dir_size) _dbm_fatal (dbf, "write error");
      fsync (dbf->desc);

      /* Update header. */
      old_adr = dbf->header.dir;
      dbf->header.dir = dir_adr;
      old_size = dbf->header.dir_size;
      dbf->header.dir_size = dir_size;
      dbf->header.dir_bits = new_bits;
      num_bytes = lseek (dbf->desc, 0, L_SET);
      if (num_bytes != 0) _dbm_fatal (dbf, "lseek error");
      num_bytes = write (dbf->desc, &dbf->header, sizeof (dbm_file_header));
      if (num_bytes != sizeof (dbm_file_header)) _dbm_fatal (dbf, "write error");
      fsync (dbf->desc);

      /* Now update dbf.  */
      dbf->bucket_dir *= 2;
      free (dbf->dir);
      dbf->dir = new_dir;
      _dbm_free (dbf, old_adr, old_size);
      
    }

  /* Copy all elements in dbf->bucket into the new buckets. */
  for (index = 0; index < dbf->header.bucket_elems; index++)
    {
      old_el = & (dbf->bucket->h_table[index]);
      select = (old_el->hash_value >> (31-new_bits)) & 1;
      elem_loc = old_el->hash_value % dbf->header.bucket_elems;
      while (bucket[select]->h_table[elem_loc].hash_value != -1)
	elem_loc = (elem_loc + 1) % dbf->header.bucket_elems;
      bucket[select]->h_table[elem_loc] = *old_el;
      bucket[select]->count += 1;
    }

  /* Update the directory. Current bucket address for bucket[0]. No need to
     change entries in the directory for bucket[0].  Get a new file address
     for bucket[1].  We need to change the entries in the directory to point
     to the bucket[1].  */
  new_adr = _dbm_alloc (dbf, dbf->header.bucket_size, TRUE);
  dir_start = (dbf->bucket_dir >> (dbf->header.dir_bits - new_bits)) | 1;
  dir_end = (dir_start + 1) << (dbf->header.dir_bits - new_bits);
  dir_start = dir_start << (dbf->header.dir_bits - new_bits);
  for (index = dir_start; index < dir_end; index++)
    dbf->dir[index] = new_adr;
  
  /* Write the new buckets and directory to disk.  */
  _dbm_update (dbf, 0x77777708, new_adr, dbf->header.bucket_size,
		 dbf->bucket_adr, dbf->bucket_dir);
  num_bytes = lseek (dbf->desc, new_adr, L_SET);
  if (num_bytes != new_adr ) _dbm_fatal (dbf, "lseek error");
  num_bytes = write (dbf->desc, bucket[1], dbf->header.bucket_size);
  if (num_bytes != dbf->header.bucket_size ) _dbm_fatal (dbf, "write error");
  num_bytes = lseek (dbf->desc, dbf->bucket_adr, L_SET);
  if (num_bytes != dbf->bucket_adr ) _dbm_fatal (dbf, "lseek error");
  num_bytes = write (dbf->desc, bucket[0], dbf->header.bucket_size);
  if (num_bytes != dbf->header.bucket_size ) _dbm_fatal (dbf, "write error");
  num_bytes = lseek (dbf->desc, dbf->header.dir, L_SET);
  if (num_bytes != dbf->header.dir ) _dbm_fatal (dbf, "lseek error");
  num_bytes = write (dbf->desc, dbf->dir, dbf->header.dir_size);
  if (num_bytes != dbf->header.dir_size ) _dbm_fatal (dbf, "write error");
  fsync (dbf->desc);
  _dbm_end_update (dbf);

  /* Make the correct new bucket the current one and free the other space. */
  dbf->bucket_dir = next_insert >> (31-dbf->header.dir_bits);
  dbf->bucket_adr = dbf->dir[dbf->bucket_dir];
  free (dbf->bucket);
  if (dbf->bucket_adr == new_adr)
    {
      dbf->bucket = bucket[1];
      free(bucket[0]);
    }
  else
    {
      dbf->bucket = bucket[0];
      free(bucket[1]);
    }
}