parcel KinoSearch cnick Kino;

/** 
 * Hashtable.
 *
 * Values are stored by reference and may be any kind of Obj. By default, keys
 * are cloned and so must belong to a class that implements Clone(); however,
 * this behavior can be changed by overridding Make_Key(), e.g. to implement
 * efficient hash sets.
 */ 
class KinoSearch::Object::Hash inherits KinoSearch::Object::Obj {

    void          *entries;
    uint32_t       capacity;
    uint32_t       size;
    uint32_t       threshold;    /* rehashing trigger point */
    int32_t        iter_tick;    /* used when iterating */

    inert incremented Hash*
    new(uint32_t capacity = 0);

    /** 
     * @param capacity The number of elements that the hash will be asked to
     * hold initially.
     */
    inert Hash*
    init(Hash *self, uint32_t capacity = 0);

    /** Empty the hash of all key-value pairs.
     */
    void
    Clear(Hash *self);

    /** Store a key-value pair.  If <code>key</code> is not already present,
     * Make_Key() will be called to manufacture the internally used key.
     */
    void
    Store(Hash *self, Obj *key, decremented Obj *value);

    void
    Store_Str(Hash *self, const char *str, size_t len, 
              decremented Obj *value);

    /** Fetch the value associated with <code>key</code>.  
     * 
     * @return the value, or NULL if <code>key</code> is not present.
     */
    nullable Obj*
    Fetch(Hash *self, const Obj *key);

    nullable Obj*
    Fetch_Str(Hash *self, const char *key, size_t key_len);

    /** Attempt to delete a key-value pair from the hash.  
     *
     * @return the value if <code>key</code> exists and thus deletion
     * succeeds; otherwise NULL.
     */
    incremented nullable Obj*
    Delete(Hash *self, const Obj *key);

    incremented nullable Obj*
    Delete_Str(Hash *self, const char *key, size_t key_ley);

    /** Prepare to iterate over all the key-value pairs in the hash.
     *
     * @return the number of pairs which will be iterated over.
     */
    uint32_t 
    Iterate(Hash *self);

    /** Retrieve the next key-value pair from the hash, setting the supplied
     * pointers to point at them.  
     * 
     * @return true while iterating, false when the iterator has been
     * exhausted.
     */
    bool_t
    Next(Hash *self, Obj **key, Obj **value);

    /** Search for a key which Equals the key supplied, and return the key
     * rather than its value.
     */
    nullable Obj*
    Find_Key(Hash *self, const Obj *key, int32_t hash_sum);

    /** Return an VArray of pointers to the hash's keys.
     */
    incremented VArray*
    Keys(Hash *self);

    /** Return an VArray of pointers to the hash's values.
     */
    incremented VArray*
    Values(Hash *self);

    /** Create a key to be stored within the hash entry.  Implementations must
     * supply an object which produces the same Hash_Sum() value and tests
     * true for Equals().  By default, calls Clone().
     */
    public incremented Obj*
    Make_Key(Hash *self, Obj *key, int32_t hash_sum);

    uint32_t 
    Get_Capacity(Hash *self);

    /** Accessor for Hash's "size" member.
     * 
     * @return the number of key-value pairs.
     */
    public uint32_t 
    Get_Size(Hash *self);

    public bool_t
    Equals(Hash *self, Obj *other);

    public incremented Hash*
    Dump(Hash *self);

    public incremented Obj*
    Load(Hash *self, Obj *dump);

    public void
    Serialize(Hash *self, OutStream *outstream);

    public incremented Hash*
    Deserialize(Hash *self, InStream *instream);

    public void
    Destroy(Hash *self);
}

class KinoSearch::Object::Hash::HashTombStone 
    inherits KinoSearch::Object::Obj {

    uint32_t
    Get_RefCount(HashTombStone* self);

    incremented HashTombStone*
    Inc_RefCount(HashTombStone* self);

    uint32_t 
    Dec_RefCount(HashTombStone* self);
}

/* Copyright 2006-2011 Marvin Humphrey
 *
 * This program is free software; you can redistribute it and/or modify
 * under the same terms as Perl itself.
 */