settrie.cpp File Reference

#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include "settrie.h"

Include dependency graph for settrie.cpp:

Macros
#define	MURMUR_SEED   76493
	Just a 5 digit prime.

Typedefs
typedef SetTrie *	pSetTrie
typedef StringSet *	pStringSet
typedef std::map< int, pSetTrie >	SetTrieServer
typedef std::map< int, pStringSet >	IterServer
typedef std::map< int, pBinaryImage >	BinaryImageServer

Functions
uint64_t	MurmurHash64A (const void *key, int len)
	MurmurHash2, 64-bit versions, by Austin Appleby.
bool	image_put (pBinaryImage p_bi, void *p_data, int size)
bool	image_get (pBinaryImage p_bi, int &c_block, int &c_ofs, void *p_data, int size)
char *	image_block_as_string (uint8_t *p_in)
char *	image_block_as_string (ImageBlock &blk)
bool	string_as_image_block (ImageBlock &blk, char *p_in)
String	python_set_as_string (char *p_char)
char *	get_answer_buffer ()
void	set_answer_buffer_size (int size)
int	new_settrie ()
void	destroy_settrie (int st_id)
void	insert (int st_id, char *set, char *str_id)
char *	find (int st_id, char *set)
int	supersets (int st_id, char *set)
int	subsets (int st_id, char *set)
int	elements (int st_id, int set_id)
int	next_set_id (int st_id, int set_id)
int	num_sets (int st_id)
char *	set_name (int st_id, int set_id)
int	remove (int st_id, int set_id)
int	purge (int st_id, int dry_run)
int	iterator_size (int iter_id)
char *	iterator_next (int iter_id)
void	destroy_iterator (int iter_id)
void	destroy_binary_image (int image_id)
int	save_as_binary_image (int st_id)
bool	push_binary_image_block (int st_id, char *p_block)
int	binary_image_size (int image_id)
char *	binary_image_next (int image_id)
void	cleanup_globals ()

Variables
int	instance_num = 0
int	instance_iter = 0
SetTrieServer	instance = {}
IterServer	iterator = {}
BinaryImageServer	image = {}
int	max_id_length = 1024
char *	p_answer = nullptr
char	answer_block [8208]
const char	b64chars [] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
uint8_t	b64inverse [256] = {0}

Macro Definition Documentation

MURMUR_SEED

#define MURMUR_SEED   76493

Just a 5 digit prime.

Typedef Documentation

BinaryImageServer

typedef std::map<int, pBinaryImage> BinaryImageServer

IterServer

typedef std::map<int, pStringSet> IterServer

pSetTrie

typedef SetTrie* pSetTrie

pStringSet

typedef StringSet* pStringSet

SetTrieServer

typedef std::map<int, pSetTrie> SetTrieServer

Function Documentation

binary_image_next()

char * binary_image_next

(

int

image_id

)

Return the first unread binary images block in an iterator returned by a save_as_binary_image() call.

Parameters

image_id

The image_id returned by a previous save_as_binary_image() call.

Returns

The the binary image block serialized as base64 or an empty string on failure.

binary_image_size()

int binary_image_size

(

int

image_id

)

Return the number of unread binary images blocks in an iterator returned by a save_as_binary_image() call.

Parameters

image_id

The image_id returned by a previous save_as_binary_image() call.

Returns

The number of unread blocks in the iterator.

cleanup_globals()

void cleanup_globals

(

)

Free the memory allocated for the answer buffer.

destroy_binary_image()

void destroy_binary_image

(

int

image_id

)

Destroy an iterator for a binary image(returned by save_as_binary_image()).

Parameters

image_id

The image_id returned by a previous save_as_binary_image() call.

destroy_iterator()

void destroy_iterator

(

int

iter_id

)

Destroy an iterator (returned by subsets() or supersets()).

Parameters

iter_id

The iter_id returned by a previous subsets() or supersets() call.

destroy_settrie()

void destroy_settrie

(

int

st_id

)

Destroy a SetTrie object that was used via the Python interface.

Parameters

st_id

The st_id returned by a previous new_settrie() call.

elements()

int elements	(	int	st_id,
		int	set_id
	)

Return all the elements in a set from a SetTrie identified by set_id as an iterator of strings.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set_id	A valid set_id returned by a successful next_set_id() call.

Returns

0 on error or the empty set, or an iter_id > 0 that can be used to retrieve the result using iterator_next()/iterator_size() and must be explicitly destroyed via destroy_iterator()

find()

char * find	(	int	st_id,
		char *	set
	)

Find a Python set (serialized by a str() call) for a complete match inside a SetTrie object.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set	A Python set serialized by a str() call.

Returns

The str_id string that was given to the set when it was inserted.

get_answer_buffer()

char * get_answer_buffer

(

)

Return a buffer to write an answer that is as big as max_id_length. max_id_length tracks the largest set id used by insert.

image_block_as_string() [1/2]

char * image_block_as_string

(

ImageBlock &

blk

)

image_block_as_string() [2/2]

char * image_block_as_string

(

uint8_t *

p_in

)

image_get()

bool image_get ( pBinaryImage  p_bi, int &  c_block, int &  c_ofs, void *  p_data, int  size  )

inline

image_put()

bool image_put ( pBinaryImage  p_bi, void *  p_data, int  size  )

inline

insert()

void insert	(	int	st_id,
		char *	set,
		char *	str_id
	)

Insert a Python set (serialized by a str() call) into a SetTrie object.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set	A Python set serialized by a str() call.
str_id	An id representing this set that will be returned in searches.

iterator_next()

char * iterator_next

(

int

iter_id

)

Return the first unread item in an iterator (returned by subsets() or supersets()).

Parameters

iter_id

The iter_id returned by a previous subsets() or supersets() call.

Returns

The str_id of an insert()-ed set that matches the query.

iterator_size()

int iterator_size

(

int

iter_id

)

Return the number of unread items in an iterator (returned by subsets() or supersets()).

Parameters

iter_id

The iter_id returned by a previous subsets() or supersets() call.

Returns

The number of unread items in the iterator.

MurmurHash64A()

uint64_t MurmurHash64A	(	const void *	key,
		int	len
	)

MurmurHash2, 64-bit versions, by Austin Appleby.

(from https://sites.google.com/site/murmurhash/) a 64-bit hash for 64-bit platforms

All code is released to the public domain. For business purposes, Murmurhash is under the MIT license.

The same caveats as 32-bit MurmurHash2 apply here - beware of alignment and endian-ness issues if used across multiple platforms.

Parameters

key	address of the memory block to hash.
len	Number of bytes to hash.

Returns

64-bit hash of the memory block.

new_settrie()

int new_settrie

(

)

Create a new SetTrie object that can be used via the Python interface.

Returns

A unique ID that can be passed as the st_id parameter for any method in the Python interface.

To free the resources allocated by this ID, the (python) caller must call destroy_settrie() with the st_id and never use the same st_id after that.

next_set_id()

int next_set_id	(	int	st_id,
		int	set_id
	)

Return the integer set_id of the next set stored in a SetTrie after a given set_id to iterate over all the sets in the object.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set_id	A valid set_id returned by previous call or the constant -1 to return the first set. Note that 0 may be the set_id of the empty set in case the empty set is in the SetTrie.

Returns

A unique integer set_id that can be used for iterating, calling set_name() or elements(). On error, it will return -3 if the st_id or the set_id is invalid and -2 if the set_id given is the last set in the object or the object is empty.

num_sets()

int num_sets

(

int

st_id

)

Return the number of sets in a SetTrie object.

Parameters

st_id

The st_id returned by a previous new_settrie() call.

Returns

The number or -1 on invalid st_id.

purge()

int purge ( int  st_id, int  dry_run  )

extern

Purges (reassigns node integer ids and frees RAM) after a series of remove() calls.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
dry_run	If nonzero, does nothing and returns the number of dirty nodes.

Returns

A positive num_dirty_nodes on dry_run, zero on successful completion or a negative error code.

push_binary_image_block()

bool push_binary_image_block	(	int	st_id,
		char *	p_block
	)

Pushes raw image blocks into an initially empty SetTrie object and finally creates it already populated with the binary image.

Parameters

st_id	The st_id returned by a previous new_settrie() call. The object must be empty (never inserted).
p_block	If non-empty, a block in the right order making a binary image obtained for a previous save_as_binary_image() call. If empty, an order to .load() the SetTrie object and destroyed the previously stored blocks.

Returns

True on success.

python_set_as_string()

String python_set_as_string

(

char *

p_char

)

remove()

int remove ( int  st_id, int  set_id  )

extern

Removes a set from the object by its unique integer id.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set_id	A valid set_id returned by a successful next_set_id() call.

Returns

0 on success or a negative error code.

save_as_binary_image()

int save_as_binary_image

(

int

st_id

)

Saves a SetTrie object as a BinaryImage.

Parameters

st_id

The st_id returned by a previous new_settrie() call.

Returns

0 on error, or a binary_image_id > 0 which is the same as st_id and must be destroyed using destroy_binary_image()

set_answer_buffer_size()

void set_answer_buffer_size ( int  size )

inline

Check if the current set id is larger than max_id_length. If so, reallocate the buffer to the new size.

Parameters

size	The new size of the id.

set_name()

char * set_name	(	int	st_id,
		int	set_id
	)

Return the name (Python id) of a set stored in a SetTrie identified by its binary (int) set_id.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set_id	A valid set_id returned by a successful next_set_id() call.

Returns

An empty string on any error and the Python id of the set if both st_id and set_id are valid.

string_as_image_block()

bool string_as_image_block	(	ImageBlock &	blk,
		char *	p_in
	)

subsets()

int subsets	(	int	st_id,
		char *	set
	)

Find all the subsets of a given Python set (serialized by a str() call) stored inside a SetTrie object.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set	A Python set serialized by a str() call.

Returns

0 if no sets were found, or an iter_id > 0 that can be used to retrieve the result using iterator_next()/iterator_size() and must be explicitly destroyed via destroy_iterator()

supersets()

int supersets	(	int	st_id,
		char *	set
	)

Find all the supersets of a given Python set (serialized by a str() call) stored inside a SetTrie object.

Parameters

st_id	The st_id returned by a previous new_settrie() call.
set	A Python set serialized by a str() call.

Returns

0 if no sets were found, or an iter_id > 0 that can be used to retrieve the result using iterator_next()/iterator_size() and must be explicitly destroyed via destroy_iterator()

Variable Documentation

answer_block

char answer_block[8208]

b64chars

const char b64chars[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

b64inverse

uint8_t b64inverse[256] = {0}

image

BinaryImageServer image = {}

instance

SetTrieServer instance = {}

instance_iter

int instance_iter = 0

instance_num

int instance_num = 0

iterator

IterServer iterator = {}

max_id_length

int max_id_length = 1024

p_answer

char* p_answer = nullptr