newtree234()freetree234()add234()addpos234()index234()find234()findrel234()findpos234()findrelpos234()del234()delpos234()count234()splitpos234()split234()join234()join234r()copytree234()This chapter documents a variety of utility APIs provided for the general use of the rest of the Puzzles code.
Platforms' local random number generators vary widely in quality and seed size. Puzzles therefore supplies its own high-quality random number generator, with the additional advantage of giving the same results if fed the same seed data on different platforms. This allows game random seeds to be exchanged between different ports of Puzzles and still generate the same games.
Unlike the ANSI C rand() function, the Puzzles random number generator has an explicit state object called a random_state. One of these is managed by each mid-end, for example, and passed to the back end to generate a game with.
random_new()random_state *random_new(char *seed, int len);
Allocates, initialises and returns a new random_state. The input data is used as the seed for the random number stream (i.e. using the same seed at a later time will generate the same stream).
The seed data can be any data at all; there is no requirement to use printable ASCII, or NUL-terminated strings, or anything like that.
random_copy()random_state *random_copy(random_state *tocopy);
Allocates a new random_state, copies the contents of another random_state into it, and returns the new state. If exactly the same sequence of functions is subseqently called on both the copy and the original, the results will be identical. This may be useful for speculatively performing some operation using a given random state, and later replaying that operation precisely.
random_free()void random_free(random_state *state);
Frees a random_state.
random_bits()unsigned long random_bits(random_state *state, int bits);
Returns a random number from 0 to 2^bits-1 inclusive. bits should be between 1 and 32 inclusive.
random_upto()unsigned long random_upto(random_state *state, unsigned long limit);
Returns a random number from 0 to limit-1 inclusive.
random_state_encode()char *random_state_encode(random_state *state);
Encodes the entire contents of a random_state in printable ASCII. Returns a dynamically allocated string containing that encoding. This can subsequently be passed to random_state_decode() to reconstruct the same random_state.
random_state_decode()random_state *random_state_decode(char *input);
Decodes a string generated by random_state_encode() and reconstructs an equivalent random_state to the one encoded, i.e. it should produce the same stream of random numbers.
This function has no error reporting; if you pass it an invalid string it will simply generate an arbitrary random state, which may turn out to be noticeably non-random.
shuffle()void shuffle(void *array, int nelts, int eltsize, random_state *rs);
Shuffles an array into a random order. The interface is much like ANSI C qsort(), except that there's no need for a compare function.
array is a pointer to the first element of the array. nelts is the number of elements in the array; eltsize is the size of a single element (typically measured using sizeof). rs is a random_state used to generate all the random numbers for the shuffling process.
Puzzles has some central wrappers on the standard memory allocation functions, which provide compile-time type checking, and run-time error checking by means of quitting the application if it runs out of memory. This doesn't provide the best possible recovery from memory shortage, but on the other hand it greatly simplifies the rest of the code, because nothing else anywhere needs to worry about NULL returns from allocation.
snew()var = snew(type);
This macro takes a single argument which is a type name. It allocates space for one object of that type. If allocation fails it will call fatal() and not return; so if it does return, you can be confident that its return value is non-NULL.
The return value is cast to the specified type, so that the compiler will type-check it against the variable you assign it into. Thus, this ensures you don't accidentally allocate memory the size of the wrong type and assign it into a variable of the right one (or vice versa!).
snewn()var = snewn(n, type);
This macro is the array form of snew(). It takes two arguments; the first is a number, and the second is a type name. It allocates space for that many objects of that type, and returns a type-checked non-NULL pointer just as snew() does.
sresize()var = sresize(var, n, type);
This macro is a type-checked form of realloc(). It takes three arguments: an input memory block, a new size in elements, and a type. It re-sizes the input memory block to a size sufficient to contain that many elements of that type. It returns a type-checked non-NULL pointer, like snew() and snewn().
The input memory block can be NULL, in which case this function will behave exactly like snewn(). (In principle any ANSI-compliant realloc() implementation ought to cope with this, but I've never quite trusted it to work everywhere.)
sfree()void sfree(void *p);
This function is pretty much equivalent to free(). It is provided with a dynamically allocated block, and frees it.
The input memory block can be NULL, in which case this function will do nothing. (In principle any ANSI-compliant free() implementation ought to cope with this, but I've never quite trusted it to work everywhere.)
dupstr()char *dupstr(const char *s);
This function dynamically allocates a duplicate of a C string. Like the snew() functions, it guarantees to return non-NULL or not return at all.
(Many platforms provide the function strdup(). As well as guaranteeing never to return NULL, my version has the advantage of being defined everywhere, rather than inconveniently not quite everywhere.)
free_cfg()void free_cfg(config_item *cfg);
This function correctly frees an array of config_items, including walking the array until it gets to the end and freeing precisely those sval fields which are expected to be dynamically allocated.
(See section 2.3.8 for details of the config_item structure.)
Many games require complex algorithms for generating random puzzles, and some require moderately complex algorithms even during play. A common requirement during these algorithms is for a means of maintaining sorted or unsorted lists of items, such that items can be removed and added conveniently.
For general use, Puzzles provides the following set of functions which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced tree structure, with the property that all lookups, insertions, deletions, splits and joins can be done in O(log N) time.)
All these functions expect you to be storing a tree of void * pointers. You can put anything you like in those pointers.
By the use of per-node element counts, these tree structures have the slightly unusual ability to look elements up by their numeric index within the list represented by the tree. This means that they can be used to store an unsorted list (in which case, every time you insert a new element, you must explicitly specify the position where you wish to insert it). They can also do numeric lookups in a sorted tree, which might be useful for (for example) tracking the median of a changing data set.
As well as storing sorted lists, these functions can be used for storing ‘maps’ (associative arrays), by defining each element of a tree to be a (key, value) pair.
newtree234()tree234 *newtree234(cmpfn234 cmp);
Creates a new empty tree, and returns a pointer to it.
The parameter cmp determines the sorting criterion on the tree. Its prototype is
typedef int (*cmpfn234)(void *, void *);
If you want a sorted tree, you should provide a function matching this prototype, which returns like strcmp() does (negative if the first argument is smaller than the second, positive if it is bigger, zero if they compare equal). In this case, the function addpos234() will not be usable on your tree (because all insertions must respect the sorting order).
If you want an unsorted tree, pass NULL. In this case you will not be able to use either add234() or del234(), or any other function such as find234() which depends on a sorting order. Your tree will become something more like an array, except that it will efficiently support insertion and deletion as well as lookups by numeric index.
freetree234()void freetree234(tree234 *t);
Frees a tree. This function will not free the elements of the tree (because they might not be dynamically allocated, or you might be storing the same set of elements in more than one tree); it will just free the tree structure itself. If you want to free all the elements of a tree, you should empty it before passing it to freetree234(), by means of code along the lines of
while ((element = delpos234(tree, 0)) != NULL)
sfree(element); /* or some more complicated free function */
add234()void *add234(tree234 *t, void *e);
Inserts a new element e into the tree t. This function expects the tree to be sorted; the new element is inserted according to the sort order.
If an element comparing equal to e is already in the tree, then the insertion will fail, and the return value will be the existing element. Otherwise, the insertion succeeds, and e is returned.
addpos234()void *addpos234(tree234 *t, void *e, int index);
Inserts a new element into an unsorted tree. Since there is no sorting order to dictate where the new element goes, you must specify where you want it to go. Setting index to zero puts the new element right at the start of the list; setting index to the current number of elements in the tree puts the new element at the end.
Return value is e, in line with add234() (although this function cannot fail except by running out of memory, in which case it will bomb out and die rather than returning an error indication).
index234()void *index234(tree234 *t, int index);
Returns a pointer to the indexth element of the tree, or NULL if index is out of range. Elements of the tree are numbered from zero.
find234()void *find234(tree234 *t, void *e, cmpfn234 cmp);
Searches for an element comparing equal to e in a sorted tree.
If cmp is NULL, the tree's ordinary comparison function will be used to perform the search. However, sometimes you don't want that; suppose, for example, each of your elements is a big structure containing a char * name field, and you want to find the element with a given name. You could achieve this by constructing a fake element structure, setting its name field appropriately, and passing it to find234(), but you might find it more convenient to pass just a name string to find234(), supplying an alternative comparison function which expects one of its arguments to be a bare name and the other to be a large structure containing a name field.
Therefore, if cmp is not NULL, then it will be used to compare e to elements of the tree. The first argument passed to cmp will always be e; the second will be an element of the tree.
(See section 5.3.1 for the definition of the cmpfn234 function pointer type.)
The returned value is the element found, or NULL if the search is unsuccessful.
findrel234()void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
This function is like find234(), but has the additional ability to do a relative search. The additional parameter relation can be one of the following values:
REL234_EQ
e. This is exactly the behaviour of find234().
REL234_LT
e. e may be NULL, in which case it finds the greatest element in the whole tree (which could also be done by index234(t, count234(t)-1)).
REL234_LE
e. (That is, find an element that compares equal to e if possible, but failing that settle for something just less than it.)
REL234_GT
e. e may be NULL, in which case it finds the smallest element in the whole tree (which could also be done by index234(t, 0)).
REL234_GE
e. (That is, find an element that compares equal to e if possible, but failing that settle for something just bigger than it.)
Return value, as before, is the element found or NULL if no element satisfied the search criterion.
findpos234()void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
This function is like find234(), but has the additional feature of returning the index of the element found in the tree; that index is written to *index in the event of a successful search (a non-NULL return value).
index may be NULL, in which case this function behaves exactly like find234().
findrelpos234()void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
int *index);
This function combines all the features of findrel234() and findpos234().
del234()void *del234(tree234 *t, void *e);
Finds an element comparing equal to e in the tree, deletes it, and returns it.
The input tree must be sorted.
The element found might be e itself, or might merely compare equal to it.
Return value is NULL if no such element is found.
delpos234()void *delpos234(tree234 *t, int index);
Deletes the element at position index in the tree, and returns it.
Return value is NULL if the index is out of range.
count234()int count234(tree234 *t);
Returns the number of elements currently in the tree.
splitpos234()tree234 *splitpos234(tree234 *t, int index, int before);
Splits the input tree into two pieces at a given position, and creates a new tree containing all the elements on one side of that position.
If before is TRUE, then all the items at or after position index are left in the input tree, and the items before that point are returned in the new tree. Otherwise, the reverse happens: all the items at or after index are moved into the new tree, and those before that point are left in the old one.
If index is equal to 0 or to the number of elements in the input tree, then one of the two trees will end up empty (and this is not an error condition). If index is further out of range in either direction, the operation will fail completely and return NULL.
This operation completes in O(log N) time, no matter how large the tree or how balanced or unbalanced the split.
split234()tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
Splits a sorted tree according to its sort order.
rel can be any of the relation constants described in section 5.3.7, except for REL234_EQ. All the elements having that relation to e will be transferred into the new tree; the rest will be left in the old one.
The parameter cmp has the same semantics as it does in find234(): if it is not NULL, it will be used in place of the tree's own comparison function when comparing elements to e, in such a way that e itself is always the first of its two operands.
Again, this operation completes in O(log N) time, no matter how large the tree or how balanced or unbalanced the split.
join234()tree234 *join234(tree234 *t1, tree234 *t2);
Joins two trees together by concatenating the lists they represent. All the elements of t2 are moved into t1, in such a way that they appear after the elements of t1. The tree t2 is freed; the return value is t1.
If you apply this function to a sorted tree and it violates the sort order (i.e. the smallest element in t2 is smaller than or equal to the largest element in t1), the operation will fail and return NULL.
This operation completes in O(log N) time, no matter how large the trees being joined together.
join234r()tree234 *join234r(tree234 *t1, tree234 *t2);
Joins two trees together in exactly the same way as join234(), but this time the combined tree is returned in t2, and t1 is destroyed. The elements in t1 still appear before those in t2.
Again, this operation completes in O(log N) time, no matter how large the trees being joined together.
copytree234()tree234 *copytree234(tree234 *t, copyfn234 copyfn,
void *copyfnstate);
Makes a copy of an entire tree.
If copyfn is NULL, the tree will be copied but the elements will not be; i.e. the new tree will contain pointers to exactly the same physical elements as the old one.
If you want to copy each actual element during the operation, you can instead pass a function in copyfn which makes a copy of each element. That function has the prototype
typedef void *(*copyfn234)(void *state, void *element);
and every time it is called, the state parameter will be set to the value you passed in as copyfnstate.
This section contains all the utility functions which didn't sensibly fit anywhere else.
TRUE and FALSE
The main Puzzles header file defines the macros TRUE and FALSE, which are used throughout the code in place of 1 and 0 (respectively) to indicate that the values are in a boolean context. For code base consistency, I'd prefer it if submissions of new code followed this convention as well.
max() and min()
The main Puzzles header file defines the pretty standard macros max() and min(), each of which is given two arguments and returns the one which compares greater or less respectively.
These macros may evaluate their arguments multiple times. Avoid side effects.
PI
The main Puzzles header file defines a macro PI which expands to a floating-point constant representing pi.
(I've never understood why ANSI's <math.h> doesn't define this. It'd be so useful!)
obfuscate_bitmap()void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);
This function obscures the contents of a piece of data, by cryptographic methods. It is useful for games of hidden information (such as Mines, Guess or Black Box), in which the game ID theoretically reveals all the information the player is supposed to be trying to guess. So in order that players should be able to send game IDs to one another without accidentally spoiling the resulting game by looking at them, these games obfuscate their game IDs using this function.
Although the obfuscation function is cryptographic, it cannot properly be called encryption because it has no key. Therefore, anybody motivated enough can re-implement it, or hack it out of the Puzzles source, and strip the obfuscation off one of these game IDs to see what lies beneath. (Indeed, they could usually do it much more easily than that, by entering the game ID into their own copy of the puzzle and hitting Solve.) The aim is not to protect against a determined attacker; the aim is simply to protect people who wanted to play the game honestly from accidentally spoiling their own fun.
The input argument bmp points at a piece of memory to be obfuscated. bits gives the length of the data. Note that that length is in bits rather than bytes: if you ask for obfuscation of a partial number of bytes, then you will get it. Bytes are considered to be used from the top down: thus, for example, setting bits to 10 will cover the whole of bmp[0] and the top two bits of bmp[1]. The remainder of a partially used byte is undefined (i.e. it may be corrupted by the function).
The parameter decode is FALSE for an encoding operation, and TRUE for a decoding operation. Each is the inverse of the other. (There's no particular reason you shouldn't obfuscate by decoding and restore cleartext by encoding, if you really wanted to; it should still work.)
The input bitmap is processed in place.
bin2hex()char *bin2hex(const unsigned char *in, int inlen);
This function takes an input byte array and converts it into an ASCII string encoding those bytes in (lower-case) hex. It returns a dynamically allocated string containing that encoding.
This function is useful for encoding the result of obfuscate_bitmap() in printable ASCII for use in game IDs.
hex2bin()unsigned char *hex2bin(const char *in, int outlen);
This function takes an ASCII string containing hex digits, and converts it back into a byte array of length outlen. If there aren't enough hex digits in the string, the contents of the resulting array will be undefined.
This function is the inverse of bin2hex().
game_mkhighlight()void game_mkhighlight(frontend *fe, float *ret,
int background, int highlight, int lowlight);
It's reasonably common for a puzzle game's graphics to use highlights and lowlights to indicate ‘raised’ or ‘lowered’ sections. Fifteen, Sixteen and Twiddle are good examples of this.
Puzzles using this graphical style are running a risk if they just use whatever background colour is supplied to them by the front end, because that background colour might be too light to see any highlights on at all. (In particular, it's not unheard of for the front end to specify a default background colour of white.)
Therefore, such puzzles can call this utility function from their colours() routine (section 2.8.6). You pass it your front end handle, a pointer to the start of your return array, and three colour indices. It will:
frontend_default_colour() (section 4.40) to fetch the front end's default background colour
ret array.
Thus, ret[background*3] to ret[background*3+2] will be set to RGB values defining a sensible background colour, and similary highlight and lowlight will be set to sensible colours.