upd_hashtable( ulong table, byte *key, int keylen, ulong newrecnum )
{
    TRUSTREC lastrec, rec;
    ulong hashrec, item;
    int msb;
    int level=0;
    int rc, i;

    hashrec = table;
  next_level:
    msb = key[level];
    hashrec += msb / ITEMS_PER_HTBL_RECORD;
    rc = tdbio_read_record( hashrec, &rec, RECTYPE_HTBL );
    if( rc ) {
	log_error("upd_hashtable: read failed: %s\n",	gpg_strerror (rc) );
	return rc;
    }

    item = rec.r.htbl.item[msb % ITEMS_PER_HTBL_RECORD];
    if( !item ) { /* insert a new item into the hash table */
	rec.r.htbl.item[msb % ITEMS_PER_HTBL_RECORD] = newrecnum;
	rc = tdbio_write_record( &rec );
	if( rc ) {
	    log_error("upd_hashtable: write htbl failed: %s\n",
							    gpg_strerror (rc) );
	    return rc;
	}
    }
    else if( item != newrecnum ) {  /* must do an update */
	lastrec = rec;
	rc = tdbio_read_record( item, &rec, 0 );
	if( rc ) {
	    log_error( "upd_hashtable: read item failed: %s\n",
							    gpg_strerror (rc) );
	    return rc;
	}

	if( rec.rectype == RECTYPE_HTBL ) {
	    hashrec = item;
	    level++;
	    if( level >= keylen ) {
		log_error( "hashtable has invalid indirections.\n");
		return GPG_ERR_TRUSTDB;
	    }
	    goto next_level;
	}
	else if( rec.rectype == RECTYPE_HLST ) { /* extend list */
	    /* see whether the key is already in this list */
	    for(;;) {
		for(i=0; i < ITEMS_PER_HLST_RECORD; i++ ) {
		    if( rec.r.hlst.rnum[i] == newrecnum ) {
			return 0; /* okay, already in the list */
		    }
		}
		if( rec.r.hlst.next ) {
		    rc = tdbio_read_record( rec.r.hlst.next,
						       &rec, RECTYPE_HLST);
		    if( rc ) {
			log_error ("upd_hashtable: read hlst failed: %s\n",
                                   gpg_strerror (rc) );
			return rc;
		    }
		}
		else
		    break; /* not there */
	    }
	    /* find the next free entry and put it in */
	    for(;;) {
		for(i=0; i < ITEMS_PER_HLST_RECORD; i++ ) {
		    if( !rec.r.hlst.rnum[i] ) {
			rec.r.hlst.rnum[i] = newrecnum;
			rc = tdbio_write_record( &rec );
			if( rc )
			    log_error ("upd_hashtable: write hlst failed: %s\n",
                                       gpg_strerror (rc));
			return rc; /* done */
		    }
		}
		if( rec.r.hlst.next ) {
		    rc = tdbio_read_record( rec.r.hlst.next,
						      &rec, RECTYPE_HLST );
		    if( rc ) {
			log_error ("upd_hashtable: read hlst failed: %s\n",
                                   gpg_strerror (rc));
			return rc;
		    }
		}
		else { /* add a new list record */
		    rec.r.hlst.next = item = tdbio_new_recnum();
		    rc = tdbio_write_record( &rec );
		    if( rc ) {
			log_error( "upd_hashtable: write hlst failed: %s\n",
							  gpg_strerror (rc) );
			return rc;
		    }
		    memset( &rec, 0, sizeof rec );
		    rec.rectype = RECTYPE_HLST;
		    rec.recnum = item;
		    rec.r.hlst.rnum[0] = newrecnum;
		    rc = tdbio_write_record( &rec );
		    if( rc )
			log_error( "upd_hashtable: write ext hlst failed: %s\n",
							  gpg_strerror (rc) );
		    return rc; /* done */
		}
	    } /* end loop over hlst slots */
	}
	else if( rec.rectype == RECTYPE_TRUST ) { /* insert a list record */
	    if( rec.recnum == newrecnum ) {
		return 0;
	    }
	    item = rec.recnum; /* save number of key record */
	    memset( &rec, 0, sizeof rec );
	    rec.rectype = RECTYPE_HLST;
	    rec.recnum = tdbio_new_recnum();
	    rec.r.hlst.rnum[0] = item;	     /* old keyrecord */
	    rec.r.hlst.rnum[1] = newrecnum; /* and new one */
	    rc = tdbio_write_record( &rec );
	    if( rc ) {
		log_error( "upd_hashtable: write new hlst failed: %s\n",
						  gpg_strerror (rc) );
		return rc;
	    }
	    /* update the hashtable record */
	    lastrec.r.htbl.item[msb % ITEMS_PER_HTBL_RECORD] = rec.recnum;
	    rc = tdbio_write_record( &lastrec );
	    if( rc )
		log_error ("upd_hashtable: update htbl failed: %s\n",
                           gpg_strerror (rc));
	    return rc; /* ready */
	}
	else {
	    log_error( "hashtbl %lu: %lu/%d points to an invalid record %lu\n",
		       table, hashrec, (msb % ITEMS_PER_HTBL_RECORD), item);
	    list_trustdb(NULL);
	    return GPG_ERR_TRUSTDB;
	}
    }

    return 0;
}