Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Reinventing the wheel.
Date: Sat, 22 Feb 2020 17:06:29 -0800
Organization: A noiseless patient Spider
Lines: 360
Message-ID: <86o8tqaz8q.fsf@linuxsc.com>
References: <7ca1c103-6910-48ad-8eee-b2f47e7b1db0@googlegroups.com> <r2mlau$tca$1@dont-email.me> <28633edd-9015-404a-949d-5a324c9267d9@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="5b1dd2a70f059f247db25722f2582bc8"; logging-data="24406"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+8FRhtNGtvfgl9qbSW6Kte4jXY1Va/n38="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:vV9lc2Sl1dGtc7DnAFhGT4lf9fw= sha1:gVvis0TmGa0h/d65RdjkKMl+xuE=
Xref: csiph.com comp.lang.c:150166

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> [garbled white space adjusted.. isn't google groups wonderful?]
>
> The key is a 32-bit integer, the value is 3 64-bit doubles, and
> the location is represented by a 32-bit unsigned integer.
>
> There's existing C++ code that does something similar to what my C
> code needs to do, though by a different algorithm.  Both algorithms
> need to deal with different versions of the same problem that I'm
> asking about.  The existing C++ code for dealing with this problem
> is functionally equivalent to the following simplified version:
>
>     std::vector<Value> storage;
>     std::map<std::pair<Key, Index> > newMap;
> 
>     // Inside the processing loop:
>     auto it = newMap.find(key);
>     if(it != newMap.end()) {
>         value = storage[it->second];
>         newMap.erase(it);
>     } else {
>         index = storage.size();
>         value = calculate_value(key);
>         storage.push_back(value);
>         newMap.push_back(std::make_pair(key, index));
>     }
>
> Later on, the values stored in storage get written to a file,
> along with various other data that includes indices referring to
> elements of that array.

If I understand what you're saying, what you are wanting to do (and
are still looking for) could be C code something like this, assuming
of course suitable definitions for the missing functions and types:

    typedef struct { double d[3]; } Value;

    static Value
    calculate_value( JKHashKey key ){
        return .. suitably constructed value ..;
    }

    void
    process_key_stream_example( Value *out, unsigned maximum_active_entries ){
        JKHashTable it = create_JKHashTable( maximum_active_entries );
        JKHashKey key;
        JKHashValue next = 0;

        while(  key = next_key()  ){
            JKHashValue *where = lookup_or_add_key_JKH( it, key );
            // lookup returns a pointer to where the index value can be stored
            if(  ! where  ){
                // oops, there was an error - handle appropriately
                continue;
            }

            if(  *where == -1  ){
                // New entries are given a default index value of -1
                out[ next ] = calculate_value( key );
                *where = next++;

            } else {
                // Stored value is at index previously saved in the hash table
                Value v = out[ *where ];
                remove_key_JKH( it, key );          

            }
        }

        release_JKHashTable( it );
    }

A header file defining the interface for those functions and types
might look like this (with appropriate header file bracketing
added, naturally):

    typedef struct JKHashTable_struct *JKHashTable;

    typedef   signed int   JKHashKey;
    typedef unsigned long  JKHashValue;

    extern  JKHashTable  create_JKHashTable( unsigned long maximum_active );
    extern  JKHashValue *lookup_or_add_key_JKH( JKHashTable, JKHashKey );
    extern  JKHashTable  remove_key_JKH( JKHashTable, JKHashKey );
    extern  JKHashTable  release_JKHashTable( JKHashTable );


This interface (presuming it has been saved suitably in a file
named 'jk-hash.h') can be implemented as follows.  Notes given
below.

/******************************************************************
*  Copyright (C) 2020 by Tim Rentsch.  All rights reserved.       *
*                                                                 *
*  Permission is granted to use this software in any way at all,  *
*  including derivative works, provided this copyright notice is  *
*  retained and subject to acknowledging and accepting my full    *
*  disclaimer of any and all liability.                           *
******************************************************************/

#include "jk-hash.h"

#include <stdlib.h>
#include <assert.h>

typedef unsigned long Index, Count, Extent, Mask, Bits;

typedef struct {
    JKHashKey    key;
  JKHashValue    value;
        Index    slot;
} Entry;

struct JKHashTable_struct {
       Extent    table_limit;
       Extent    entries_limit;
        Index   *table;
        Entry   *entries;
         Mask    slot_mask;
        Count    threshold;

        Index    entries_next;
        Count    occupied;
};


static  JKHashTable      initialize( JKHashTable, Extent, Extent );
static  JKHashValue     *lookup_or_add( JKHashTable it, JKHashKey key );
static  JKHashTable      remove_key( JKHashTable it, JKHashKey key );
static  JKHashTable      release( JKHashTable it );

static  JKHashTable      rebuild_table( JKHashTable );
static  JKHashTable      (checkit)( JKHashTable );
static  Index            slot_for( JKHashTable, JKHashKey );

static  Bits             rehash_for( Bits );
static  Extent           next_nonzero_power_of_two_at_least( Extent );
static  int              is_power_of_two( Bits );


JKHashTable
create_JKHashTable( unsigned long most ){
    JKHashTable it = most < -2 ? calloc( 1, sizeof *it ) : 0;
    Extent m = most + 2;
    Extent n = m + m + m/2;
    return  it ? initialize( it, m, n ) : 0;   
}

JKHashValue *
lookup_or_add_key_JKH( JKHashTable it, JKHashKey key ){
    return  it ? lookup_or_add( it, key ) : 0;
}

JKHashTable
remove_key_JKH( JKHashTable it, JKHashKey key ){
    return  it ? remove_key( it, key ) : 0;
}

JKHashTable
release_JKHashTable( JKHashTable it ){
    return  it ? release( it ) : 0;
}


/*****************************************************************************/
/***  Internal functions  ***/

JKHashTable
initialize( JKHashTable it, Extent entries_needed, Extent slots_needed ){
    it->table_limit     = next_nonzero_power_of_two_at_least( slots_needed );
    it->entries_limit   = entries_needed;
    it->table           = calloc( it->table_limit,   sizeof *it->table   );
    it->entries         = calloc( it->entries_limit, sizeof *it->entries );
    it->slot_mask       = it->table_limit-1;
    it->threshold       = it->entries_limit +
                          (it->table_limit - it->entries_limit) / 2;
    it->entries_next    = 0;
    it->occupied        = 0;

    if(  ! is_power_of_two( it->table_limit )     )     return  release( it );
    if(  it->table_limit <= it->entries_limit     )     return  release( it );
    if(  ! it->table                              )     return  release( it );
    if(  ! it->entries                            )     return  release( it );

    it->entries[ it->entries_next++ ].slot = -1;
    it->entries[ it->entries_next++ ].slot = -1;

    return  (checkit)( it );
}


JKHashValue *
lookup_or_add( JKHashTable it, JKHashKey key ){
    Index slot = slot_for( it, key );
    Entry *p = it->entries + it->table[ slot ];

    if(  p->slot == slot  )  return  (void) checkit( it ),  &p->value;

    if(  it->entries_next == it->entries_limit  )  return  0;

    if(  it->table[slot] == 0  )  it->occupied++;
    p = &it->entries[  it->table[slot] = it->entries_next++  ];
    *p = (Entry){ .key = key, .value = -1, .slot = slot };

    if(  it->occupied > it->threshold  )  rebuild_table( it );

    return  (void) checkit( it ),  &p->value;
}


JKHashTable
rebuild_table( JKHashTable it ){
    for(  Index s = 0;  s < it->table_limit;  s++  )  it->table[s] = 0;
    it->occupied = 0;

    for(  Index i = 2;  i < it->entries_next;  i++  ){
        Index slot = slot_for( it, it->entries[i].key );
        assert(  it->table[ slot ] == 0  );
        it->table[slot] = i;
        it->entries[i].slot = slot;
        it->occupied ++;
    }

    return  checkit( it );
}


JKHashTable
remove_key( JKHashTable it, JKHashKey key ){
    Index slot = slot_for( it, key );
    Entry *p = it->entries + it->table[slot];

    if(  it->table[slot] > 1  ){
        *p = it->entries[ --it->entries_next ];
        it->table[ p->slot ] = p - it->entries;
        it->table[ slot ] = 1;
    }

    return  checkit( it );
}


JKHashTable
release( JKHashTable it ){
    free( it->table );
    free( it->entries );
    free( it );
    return  0;
}


JKHashTable
(checkit)( JKHashTable it ){
    Count occupied = 0;

    for(  Index slot = 0;  slot < it->table_limit;  slot++  ){
        if(  it->table[slot]  )  occupied++;
    }
    assert(  occupied == it->occupied  );
    for(  Index i = 0;  i < it->entries_next;  i++  ){
        Entry e = it->entries[i];
        assert(  i < 2  ||  e.slot < it->table_limit  );
        assert(  i < 2  ?  e.slot == -1  : it->table[ e.slot ] == i  );
        assert(  i < 2  ||  slot_for( it, e.key ) == e.slot  );
    }
    for(  Index slot = 0;  slot < it->table_limit;  slot++  ){
        Index k = it->table[ slot ];
        assert(  k < it->entries_next  );
        assert(  k < 2  ||  it->entries[k].slot == slot  );
    }

    return  it;
}


Index
slot_for( JKHashTable it, JKHashKey key ){
    Index   fill_slot = -1,   slot = key,   rehash = rehash_for( slot );
    Index j;

    do {
        j = it->table[  slot = slot+rehash & it->slot_mask  ];
        if(  j > 1  &&  it->entries[j].key == key  )  return  slot;
        if(  fill_slot == -1  &&  j < 2  )  fill_slot = slot;
    } while(  j  );

    return  assert( fill_slot < it->table_limit ),  fill_slot;
}


Bits
rehash_for( Bits hash ){
    static unsigned char skips[64] = {
         11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
         73, 79, 83, 89, 97,101,103,107,109,113,127,131,137,139,147,157,
        159,161,163,167,169,171,173,177,179,181,183,187,191,193,197,199,
        201,203,211,213,217,219,223,227,229,231,233,237,239,241,249,251,
    };
    return  hash < 64  ? skips[hash]  : rehash_for( hash/64 + hash%64 );
}


Extent
next_nonzero_power_of_two_at_least( Extent k ){
    Extent r = 1;
    while(  r != -1  &&  r+1 < k  )  r += r+1;
    return  r+1 ? r+1 : 1;
}


int
is_power_of_two( Bits b ){
    return  (b & b-1) == 0;
}

/*******************************************************************
* End of C source file jk-hash.c                                   *
*******************************************************************/


Notes:

The technique used is ordinary open addressing hashing, with double
hashing for the reprobes.  To deal with deletions, removed entries
are marked with a "tombstone" value that signifies an occupied, but
not being actively used, slot.  When there gets to be too many of
these -- more precisely, when occupancies exceed a pre-determined
threshold -- the table is rebuilt from the set of active entries,
so all "tombstone" slots disappear.

The only external dependencies are the standard library functions
calloc() and free(), and the assert() macro from assert.h.

There are a few assert()s in the primary code, which is to say outside
of the checkit() function.  The main reason these assertions are there
is to point something out to a reader, not to catch problems.

The function checkit() is for testing and also to show invariants
that hold while a hash table is active.  This function is called on
basically every action, and sometimes more than once for a given
top-level call, so it is expensive.  To turn it off (except for one
call just after initialization is done), give a '-Dcheckit(a)=(a)'
option on the compilation step.

In the function 'slot_for()', the initial hash value is simply taken
directly from the key.  If the keys aren't random enough, this is
the place to put in a suitable hashing function that mashes bits
of the key together so as to produce a good initial hash value.

I ran trials of various sizes, both in terms of maximum number of
active entries and how many keys total were processed.  In a trial
run (with checkit() disabled) with a maximum of 65536 entries active
at any one time, a stream of one billion keys (so a billion adds
and a billion removes, maintaining 65536 entries in the hash table
all the while) took about 60 seconds.

I expect this functionality isn't exactly what you want, but it
should be close enough so the code can be adapted fairly easily to
provide the functionality you need.