Wil must often operate on memory using only starting address and length. A large set of utility methods can be implemented knowing only this much about content.
A yv object for contiguous octet sequences represented in pointer-plus-length form was already introduced at the start in the demos root — so this page is a continuation of that demo. But here we begin again with basic state members.
Code for intersecting two yv runs won't be shown again; you need to see demos for that (cf vintersect«). But vintersect() is used by other yv methods (such as for slicing, cf »).
Struct yv is a description of contiguous memory with length in octets, just like an iovec but with convenience methods like construction and conversion with other types. And hash, and compare. And whatever else you want to do with a pointer and length. Wil also tends to add new yv methods porting std C string library methods for nul terminated strings, but without need for nul termination.
The last three inline methods above are casually used everywhere in demos with iovecs, making iovecs and yv interchangeable as values in many places because they convert to one another.
Just because memory is described doesn't mean it exists — in some apps it can make sense to use yv instances for unmapped memory, calculating values with pointers never dereferenced. Knowing what can be touched is someone else's job — yv doesn't care.
The empty constructor inits both members to zero. This means you can't make vectors of yv that are not touched in construction. (You should use iovec for that when necessary — it has no constructor; your iovec vectors have no time cost until used.)
In addition to api shown above, several other ways exist to init yv instances. Default assignment and copy construction are fine.
Wil uses vinit() to re-construct, and vclear() to zero. Conversion to and from std::string is just as easy as iovec. Of course, if you construct yv from std::string, the space only lives as long as std::string keeps it; so take care.
Method veq() comparing two yv instances for equality appeared first in the demos root (cf «) with more comments. Ordering two octet sequences lexicographically is done by vcmp() which orders bytes much the way memcmp() does: in binary.
But vcmp() differs from memcmp() by using separate lengths for each run, so either can end first and be considered less than when all preceding bytes are equal. You want this code rewritten in assembler when called often enough to show in profiles as a big consumer of cycles. This version is simple but doesn't pre-load memory, nor align addresses, nor compare multiple bytes at once.
Case insensitive compare in vicmp() is not shown for brevity, and because it's based on tolower() in ctype.h in the standard C library and is something of a kludge since it presumes too much about encoding. But the only lines differing from vcmp() are these:
This approach to case insensitive compare follows an optimization principle: do not canonicalize case until necessary. Be lazy.
(Wil shows prefixes and suffixes here because the code uses vicmp() for case insensitive compare just described above.)
These two methods select N bytes from the start or end of a run: vprefix(N) returns at most N leading bytes and vsuffix(N) returns at most N trailing bytes. At most v_n bytes is returned.
Boolean predicates vstarts() and vends() are true if yv starts or ends with exactly the pattern argument supplied. This is true when the subset of that length is equal to the pattern:
(Yes vends() is only one trailing letter different in name from vend() used with iterators elsewhere in this api (cf ») — sorry.)
Those boolean predicates also have case insensitive forms, but they assume an encoding understood by tolower() since that's how vicmp() makes case canonical when difference is seen.
If tolower() for lowercasing doesn't suit an actual encoding in your content, you can use this code as a template for your code.
This section shows the beginning of code to compare with intent to find longest matches. More of this sort of code appears in the compare demo, so this is only a taste showing the idea, which is counting bytes that match starting at a known position. Like vcmp() in the last section for yv ordering, this code can be redone in assembler when vsame() becomes a profile bottleneck. But it won't when more exotic variants more specific to a situation are used instead.
Wil mainly uses vsame() to test other code in compare demos, so speed is less important than a clear result in simple code. Overloading to match leading bytes in an iovec vector below is trivial using the ydvp iovec iterator shown in the iovec demo.
A call to vskip() toward the end uses a method shown in the next section — it removes the leading N bytes from a run.
Some yv methods divide octet sequences into pieces while parsing. Wil uses multiple temporary stack yv instances to keep track of various positions while scanning content in octet runs.
Wil often uses vtail() in conjunction with vsplit() below, for reasons that will become apparent. Note vsplit() resembles method vindex() shown column right (cf »).
Since vsplit() modifies the original yv (as well as arg outSecondHalf) you must pass in copies if you need originals unchanged; the return is the same as index() for two reasons: it helps document behavior, and you can test it for nil to see if dividing the original run in two happened. The following iterator class is based on vsplit().
Here's an example of a nested class starting with the last letter of the containing class but in uppercase. And since p means pointer or iter, the name Vp means vector iter. Normally that would iterate vector elements. But since that's boring and trivial for yv, instead this class visits yv subsets divided by an octet passed to vbegin().
Note the definition of inline yv::vbegin() after the definition of class yv::Vp so that class is defined. Some folks might not know it's this easy to delay inline definition. Wil does it casually at need.
Wil sometimes uses yv::Vp to iterate clumps of command line arguments passed as a single arg. Here's a bit of sample code showing what the iterator returns given a sample C string using colon as a separator marking subset divisions:
This code puts parentheses around each value returned from the iterator to make results clear. The output for this appears on stdout below. Note the empty string between 2nd and 4th values resulting from two adjacent colons in the input.
The purpose of using vtail() in the code is to remove colon : from iter output returned. (The name tail here treats a run like a list of octets where head is the first and tail is the rest. So calling vtail() removes the head octet and keeps the rest.)
It's trivially easy to iterate (for example) HTTP query parameters using this iterator, using a second nested iterator in the loop to find equal sign (=) between key and value. But a separate iterator for this specifically is often simpler, and more easily distinguishes all legal forms.
Especially when reading yv content from non-critical code, Wil just uses the standard C library to do simple things, even when it forces a copy to get a required end nul byte for C string termination. This tactic is good for placating coworkers who only ever use atoi() to convert strings to numbers; in test code Wil doesn't care. These methods get used in config and test code, but seldom elsewhere:
Wil uses scanf() on yv instances using vscanf(), which makes a temp local copy with an end nul first. The 2K upper limit on max content size is a reasonable compromise in normal coding contexts. This is usually another config time feature used during app setup.
Since a constant purpose of yv is avoiding memory scans to find end nuls in strings, this code using vsscanf() is a casual, expedient surrender under practical circumstances.
Wil suballocates memory from yv instances, especially when they describe a page or book meant for suballocation. In this sense yv acts like a heap that allocates by pointer bumping. All the yv space allocation methods below are inlines.
The following 4K constant is used to define size of one page; this isn't a portable way to do it, and it's wrong on some systems — typically those with 8K pages. But it makes this api simple, so go with it for now.
Method vtake() returns the next N bytes of yv or returns nil when N is more than what remains; the code looks like vskip() above (cf «) except a pointer is returned. The toy language under mu uses vtake() often for space allocation inside pages.
When new space must contain zeroes, Wil uses vcalloc() below instead of vtake(), which merely adds a memset() call. Pointer v_p isn't checked for nil first here or in vtake() because it's one of those places Wil thinks a crash is good on nil in runs used as heaps.
The behavior of method vpage() resembles system library call valloc() in effect: it returns page-aligned memory from yv, skipping as many bytes as needed to force alignment. Other kinds of aligned allocation are easily generalized from this code. Note yip32 is understood as a synonym for ptrdiff_t (as explained on the types page).
Because Wil already has heap apis to allocate pages, Wil uses this vpage() method only in special circumstances like suballocation from big swaths of pre-allocated space like shared memory.
Occasionally one needs a method for naive pattern search — for example when writing unit tests to show your superior Boyer-Moore algorithm returns correct answers, or when writing unit tests showing de-dup algorithms find expected patterns. Naive vfind() tries every possible position in turn while testing for equality.
An iterator finding all instances of a pattern is trivial to write using vfind() since you can restart the search in a smaller yv starting just after the returned address.
Case insensitive vifind() looks the same except for the loop:
The yv api aims to cover simple problems using pointer and length. Obviously production code should use faster search.
thorn: todo, names, fd, iovec, assert, log, run « Þ, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype
(mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)
Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.
Wil uses term run as a noun meaning "a contiguous sequence of x", and refers to yv as a run of octets, or just a run. This confuses a few folks (especially speakers of English as a second language) who think run is only a verb, and prefer words have only one meaning. But words have many meanings. Wil often uses run as a short synonym for sequence; this demo uses it to mean yv.
A yv run is not itself a string, but might contain a string. So yv has methods to manipulate some kinds of strings, e.g. runs of Latin1 octets (and later, Unicode codepoints). But it's up to code using yv to decide if string api use is right, and which encoding applies, because yv has no idea — it's all mechanism with no policy about content inside. The only thing yv represents is location and length in bytes. The meaning of content is app specific.
Later methods will support Unicode too, when Wil needs it. But yv still won't know if Unicode codepoints occur inside. Length of yv is always in octets, even when 16-bit or 32-bit character codepoints are inside.
Member v_p is not const, and const is cast away when you supply a const pointer as a value. This is intentional as a simplification. Wil experimented with a const ykv object with a const kv_p. But using this class induced much complexity in interfaces, implying baroque type hierarchies. So Wil passed on the idea; thus you must remember when content is const.
Wil often uses yv const& to mean content is const, even though technically it only means yv itself is const, not what it references.
The result of printing most þ objects depends on whether content inside or object structure is desired. The latter print — called a dump — reveals object structure, and is requested by quoting a value (see the quote demo) when using operator << writing to an out stream (see the out demo).
The usage example above emits output on stdout shown below. Line [3] writes the same thing that would appear if the left hand side was an instance of yfdw from the fd demo instead of the instance of yo (from the out demo) that it is. Line [5] calls vdump() whose code is listed below.
The interface for line [5] uses the nested yv::Pq class used for quoting (cf quote») from this part of the yv class api:
Most of this is boilerplate common to printing all þ objects: the quote, print, dump, and cite methods are standard, and only nested struct name Vq changes, because it always uppercases the prefix letter (V in this case) and merely wraps a yv instance to bind the desired version of overloaded operator<<().
The last line above uses yct to request cite format is covered more in the quote demo; another example appears in the iovec demo (cf iovec«).
In code shown below, hex dumps are done by yv::vhexmax() which appears in the hex demo instead of this demo. Similarly, the code handling crc generation appears in the crc demo instead of here. (Several other demo pages are little more than sub topics of this run demo.)
Dumping yv just calls vshow() with specific values, including the tag to use and max number of bytes to hex dump. An upper limit of 16K is arbitrary, and is driven mainly by subjective irritation at long dumps. The code for vshow() below in turn merely puts XML style tags around the hex dump. The crc32 hash aims to simplify rapid comparison of multiple dumps in output.
The print wrapper around dump methods usually looks exactly like this one, and is intended for use under gdb. And cite methods emit one line only. All the formatting work is done by yo's api (see out) which aims to make typical print usage as terse as possible. (Atypical comments are added here.)
Basic vhash() is a trivial wrapper around use of yh32's api for crc32 as shown in the crc demo. But case insensitive hashing involves a couple issues: batching consecutive runs for crc32 when possible, and choice of encoding. (This code uses isupper() and to tolower(), working well with Latin1.)
Logic to batch octets for conversion resembles code in the escape demo for delayed encoding. An earlier example appeared in the fd demo (cf «). When Wil needs a generalized partial mapping hash, he can pass in a map parameter showing which octets need to change. (And of course to hash strings in other codepoints, an efficient codepoint iter is needed for an encoding.)
Many yv methods answer questions about content described without altering it. Such methods — returning boolean true or false — are called predicates by convention and answer such questions as (e.g. vall()) Other queries count things in a run, like all appearances of an octet value:
Here's the api for several boolean predicates:
Of the last three visdigit() is easiest to explain, so it's shown first; it returns true if no octet returned false from isdigit(). Wil sometimes uses it when deciding whether a number seems intended. Note true is returned when a run is empty, so that must be checked separately if it matters.
Both variants of vall() return true as long as no byte in the run returns false from the map[] predicate passed as an argument. Both yum and yutm are maps where u is short for u8 (ie an octet); yum is an octet map and yutm is an octet type map. Both are explained and shown in the ctype demo, so coverage here is minimal. In effect, either type can be tested to see an octet is mapped, so map[c] here is similar to use of isdigit(c) above.
You can make arbitrary maps with yum because it has a value for all 256 possible octet inputs; yutm represents ctype.h semantics.
See the ctype demo for yum and yutm apis.
Other queries return different values, but it's hard to generalize about queries as a class. However, many examine octets one at a time — from the left or right side — until a specific condition is found, such as the first appearance of an octet value, or class of octet values. The next two methods act like std C library methods index() and rindex() (see man pages) without end nuls.
Wil wrote several yv methods similar to standard C library calls, but using explicit v_n length in yv instead of terminating nuls in C strings.
Both vspn() and vcspn() below use types yum and yutm mentioned in the last section on vall() (cf «). These are more efficient ways to express charsets than nul terminated C strings — each is a map in vector representation.
Method vspn() has the same meaning as strspn() in ISO C90 (see a man page for strspn) but avoids use of nul termination. In short, vspn() returns a count of octets at the start of yv true for acceptMap (ie acceptMap[c] is nonzero). You could build vall() shown earlier with this since:
- v.vspn(map)==v.v_n implies v.vall(map)
Method vcspn() spans the complement of the charset expressed by rejectMap, and has the same meaning as strcspn() in ISO C90 (see a man page for strcspn) but avoids use of nul termination.
In short, vcspn() returns a count of octets at the start of yv which are false for predicate rejectMap (ie rejectMap[c] is zero). If you find all these double negatives confusing, you might avoid using vcspn(). But if you already use strcspn() in C's std library, this is a direct replacement if you convert your charset to a yum or yutm map following recipes in the ctype demo.
The advantage of having both vspn() and vcspn() is that you can use one yum or yutm instance to count either matching or non-matching octets without needing to generate the complement of your one map.
(These two methods almost appeared in the ctype demo only, along with the yum or yutm map types; example usage is shown there. But other methods here are sufficiently similar to warrant listing them all together.)
As you can see from methods in this section, code using yum looks exactly the same as code using yutm when only operator[] is called. For this reason, only methods for yum need be listed; the version for yum looks the same.
The just completed ctype demo shows new yv method vpick() (cf vpick») resembling vspn() above, but selecting octets matching a yutm predicate and writing them to a yo out stream.
Wil must sometimes make a new yv instance with leading and trailing octets removed that appear in a map (satisfying the predicate it represents). The next vtrim() method shows how this is done for a yum map. As explained in the last paragraph above, the version for yutm looks exactly the same. (Just remember vtrim() is overloaded for yum and ytum.)
The yutm version is identical except input type is yutm. Note only the yv instance is modified — the content bytes are immutable.
Here we show rare yv methods modifying bytes described by a destination yv — vcopy() writes content of one yv (the src) into another (this) provided room is present. This is most likely true after space has just been allocated with the desired size. Writing to iovecs in the general case is often better done using yb in the buf demo. The simplest vcopy() is this one:
Instead of copying all bytes, you might want to pick and choose, copying only octets accepted by a map parameter. Here's a version of vcopy() which only copies a source octet c when acceptMap[c] is nonzero:
The yutm version of vcopy() is identical except input type is yutm. Content in destination this is not immutable because it's updated to make a copy of the source, to get a deep copy of the run. (A shallow copy of yv by copy construction is trivial; you must grasp why vcopy() is different.)
Other than vcopy() above, Wil has few yv methods that alter memory inside content described by yv. This section shows a few more miscellaneous methods treating the content as mutable.
The in demo shows in stream apis include this yi::iread() method that resembles a ::read() system call.
Reversing a string in place is a classic interview question Wil has answered countless times. Wil likes to counter with the question about how you exchange two adjacent subsets while maintaining order in each subset. (Yes, just reverse each subset separately and then everything together.)
Slices are treated more fully in the slice demo, and the iovec demo has a long section on slicing scatter-gather lists using iovec vectors, so this section is short. In constrast with most other objects when sliced, yv eagerly returns a new yv instance instead of delaying evaluation as long as possible by joining the original object with a slice subclass. (Wil fears over-subtle code would result from delayed yv slices using a hypothetical yvz subclass of yz.)
Instead of using yz::zabsolute() to resolve relative slices with negative values, which would force slices to resolve only inside yv, Wil currently allows both positions and lengths to be negative after adding negative values to v_n because he can still resolve the result by intersection with the original yv (see the demos root for vintersect() code). Wil interprets negative length to mean a run's start is the "end" at an address before v_p. It's unclear whether this is useful.
This sample illustrates positive and negative slice values:
That writes the following on stdout. Note how use of vintersect() in the last example limits a slice to a subset of the original yv.
demos « Þ
+ todo
+ names
+ fd
+ iovec
+ assert
+ log
+ run « Þ
+ hex
+ crc
+ buf
+ in
+ out
+ quote
+ escape
+ compare
+ file
+ deck
+ cow
+ arc
+ blob
+ tree
+ slice
+ rand
+ time
+ stat
+ hash
+ heap
+ node
+ primes
+ page
+ book
+ pile
+ stack
+ atomic
+ lock
+ mutex
+ thread
+ map
+ meter
+ list
+ iter
+ ctype