hash_ops.c File Reference

Hash operations for copy/move detection. More...

#include <fcntl.h>
#include "global.h"
#include "waa.h"
#include "helper.h"
#include "hash_ops.h"
Include dependency graph for hash_ops.c:

Go to the source code of this file.

Data Structures

struct  hsh___list
 Structure for storing a number of data packets of size sizeof(void*). More...

Functions

Simple hash functions.



int hsh___new_bare (char *wcfile, char *name, int gdbm_mode, GDBM_FILE *output, char **fname_out)
 Bare open function for internal use.
int hsh__new (char *wcfile, char *name, int gdbm_mode, hash_t *output)
 -.
int hsh__collect_garbage (hash_t db, int *did_remove)
 -.
int hsh__close (hash_t db, int has_failed)
 -.
int hsh__fetch (hash_t db, datum key, datum *value)
 -.
int hsh__first (hash_t db, datum *key)
 -.
int hsh__next (hash_t db, datum *key, const datum *oldkey)
 -.
int hsh__store (hash_t db, datum key, datum value)
 -.
int hsh__store_charp (hash_t db, char *keyp, char *valuep)
 -.
Hash list manipulation.



int hsh__insert_pointer (hash_t hash, datum key, void *value)
 -.
int hsh__list_get (hash_t hash, datum current_key, datum *next_key, struct estat **arr[], int *found)
 -.
int hsh__register_delete (hash_t db, datum key)
 Registers some key for deletion on database close.

Detailed Description

Hash operations for copy/move detection.

The hash operations are binary clean; they don't care what kind of key/value data they store.

Storage considerations

The basic question is ... do we need an unlimited amount of list entries in any hash bucket, or do we not?

If we do, we have these possibilities:

Extending the key, counting entries.

The first entry is written as now.

inline_dotgraph_3.dot

If we find a second entry with the same key,

Storing a linked list in the hash.

Every entry is written with a header; the first for some given key gets the number 0, as an end-of-list marker.

inline_dotgraph_5.dot

If this key has a collision, we

Storing a verbatim array

If there's a limited number of entries (with known length) to store, an array with a defined size might be easiest.
A similar variant would be to simply concatenate the data in the hash buckets, with some suitable separator.

Conclusio

Barring other (better) ideas, the array solution is currently implemented; the array is of fixed-size, can store only pointers, and the function for getting a list allows returning a set of elements.


Definition in file hash_ops.c.


Function Documentation

int hsh___new_bare ( char *  wcfile,
char *  name,
int  gdbm_mode,
GDBM_FILE *  output,
char **  fname_out 
)

Bare open function for internal use.

*fname_out, if not NULL, gets an allocated copy of the filename.

STOPIF_CODE_ERR

Todo:
remove this bugfix sometime ...

Definition at line 184 of file hash_ops.c.

References GWD_MKDIR, HASH_TEMPORARY, hlp__strdup(), STOPIF, STOPIF_CODE_ERR, waa__get_gwd_flag(), waa__get_waa_directory(), waa_tmp_fn, and waa_tmp_path.

Referenced by hsh__new(), and hsh__register_delete().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__close ( hash_t  db,
int  has_failed 
)

-.

Close a property file.

If has_failed is set, some error has happened, and the registered keys are not used for deletion (like a ROLLBACK).

Definition at line 326 of file hash_ops.c.

References hash_s::db, DEBUGP, hash_s::filename, hsh__collect_garbage(), hsh__first(), IF_FREE, STOPIF, hash_s::to_delete, and waa__delete_byext().

Referenced by ci___send_user_props(), cm___dump_list(), cm___get_base_source(), cm___make_copy(), cm__detect(), prp__g_work(), prp__l_work(), prp__open_get_close(), prp__s_work(), prp__set_from_aprhash(), and up__fetch_decoder().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__collect_garbage ( hash_t  db,
int *  did_remove 
)

-.

Collect garbage in the hash table.

The previously marked keys in the hash table are removed; it is not checked for empty-ness nor reorganized.

Definition at line 287 of file hash_ops.c.

References hash_s::db, DEBUGP, STOPIF_CODE_ERR, and hash_s::to_delete.

Referenced by hsh__close().

Here is the caller graph for this function:

int hsh__fetch ( hash_t  db,
datum  key,
datum *  value 
)

-.

Read value associated with some key in db.

Definition at line 378 of file hash_ops.c.

References hash_s::db, and IF_FREE.

Referenced by cm___dump_list(), cm___get_base_source(), hsh__insert_pointer(), hsh__list_get(), and prp__fetch().

Here is the caller graph for this function:

int hsh__first ( hash_t  db,
datum *  key 
)

-.

Find first key.

Definition at line 394 of file hash_ops.c.

References hash_s::db.

Referenced by cm___dump_list(), hsh__close(), and prp__first().

Here is the caller graph for this function:

int hsh__insert_pointer ( hash_t  hash,
datum  key,
void *  value 
)

-.

For short-time storage (single program run): Insert the pointer value into the hash at key.

Definition at line 494 of file hash_ops.c.

References BUG_ON, hsh___list::count, hsh___list::entries, HASH__LIST_MAX, hsh__fetch(), hsh__store(), and STOPIF.

Referenced by cm___hash_register().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__list_get ( hash_t  hash,
datum  current_key,
datum *  next_key,
struct estat **  arr[],
int *  found 
)

-.

Get an list of found entries from hash addressed by current_key into the (statically allocated) arr.

If next_key is not NULL, it is set so that the next query can use this key for the next element. If *next_key==NULL, no next element is there; everything has been returned. If no (more) entry could be found, ENOENT is returned, and *found==0.

In case of storage via an array hsh__list must store some internal state; therefore only a single loop is (currently) possible.

Definition at line 563 of file hash_ops.c.

References BUG_ON, hsh___list::count, hsh___list::entries, HASH__LIST_MAX, hsh__fetch(), and STOPIF.

Referenced by cm___hash_list(), and cm___match_children().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__new ( char *  wcfile,
char *  name,
int  gdbm_mode,
hash_t output 
)

-.

Create a new hash for wcfile with the given name.

If flags is GDBM_NEWDB, the file gets deleted immediately; there's no need to keep it around any longer, and it's not defined where it gets located. If another open mode is used, the entry is always created in the WAA or CONF base directory for wcfile, ie. the hashed path for the working copy root.

Definition at line 258 of file hash_ops.c.

References hash_s::db, hash_s::filename, HASH_REMEMBER_FILENAME, hlp__calloc(), hsh___new_bare(), IF_FREE, and STOPIF.

Referenced by cm___dump_list(), cm___get_base_source(), cm___make_copy(), cm__detect(), and prp__open_byname().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__next ( hash_t  db,
datum *  key,
const datum *  oldkey 
)

-.

Find next key.

If oldkey==key the ->dptr is free()d; else the caller has to do that.

Definition at line 410 of file hash_ops.c.

References hash_s::db, and IF_FREE.

Referenced by cm___dump_list(), and prp__next().

Here is the caller graph for this function:

int hsh__register_delete ( hash_t  db,
datum  key 
)

Registers some key for deletion on database close.

Definition at line 609 of file hash_ops.c.

References DEBUGP, HASH_TEMPORARY, hsh___new_bare(), STOPIF, STOPIF_CODE_ERR, and hash_s::to_delete.

Referenced by ci___send_user_props(), and cm___get_base_source().

Here is the call graph for this function:

Here is the caller graph for this function:

int hsh__store ( hash_t  db,
datum  key,
datum  value 
)

-.

Store some value in the hash table.

Definition at line 432 of file hash_ops.c.

References hash_s::db, and STOPIF_CODE_ERR.

Referenced by hsh__insert_pointer(), hsh__store_charp(), and prp__store().

Here is the caller graph for this function:

int hsh__store_charp ( hash_t  db,
char *  keyp,
char *  valuep 
)

-.

Store character strings in the hash table.

The delimiting \0 is stored, too.

Definition at line 451 of file hash_ops.c.

References hsh__store().

Referenced by cm___make_copy().

Here is the call graph for this function:

Here is the caller graph for this function:


Generated for fsvs by  doxygen 1.6.1