Change poolHash to use internal collision resolution

Eliminate strdup() in doLookupId()

- Take advantage of the length-aware pool string->id lookup to avoid
  the need to copy and locally modify the canonized dirname. Makes
  the code cleaner and a little bit faster too.
- There are further possibilities in this direction, canonDir()
  could return an id instead of malloced memory but that doesn't
  remove the need for temporary bugg^H^Hffer to clean up the dir.

Lift directory name canonicalization into a helper function

- Suddenly it all seems so much clearer...
- Also try to better handle the theoretical realpath() errors: on
  failure the buffer contents are undefined and we shouldn't look
  at them, free the buf and return NULL.

Aargh, stupid thinko in rpmstrPoolStrlen() last id special case

- At the largest id, the end boundary is data, not offset size... doh

Unbreak fingerprinting when called twice for the same transaction set

- Fixes regression (yum updates barf with conflicts) from commit
  3b492620fb35a21d05b975e31130dc071f6fd8e2 which doesn't affect rpm
  itself but breaks some API users like yum that first run a
  test-transaction and if that succeeds, the same transaction is run
  for real. In that case we need to redo the whole fingerprint dance
  from scratch: throw away any former results and redo.
- Blaming Fedora 18 alpha preparations for not noticing this earlier:
  there have been no updates to F16/F17 in almost a week, effectively
  disabling a part of the regular rpm development QA :P

Oops, refactoring error in commit 327701572ff912413ec9564d29d946b4ab21a9f3

- sizeof() doesn't work very well for malloced arrays... not that it
  matters a whole lot, this isn't a path that will ever be executed
  afaict.

Ensure fingerprint subdirs have heading slashes

- Similar to commit ad99f4e84a5fea05edca59257b6e00d91d6c8a08 but at the
  other end of the name: not all subdirs will exist in the pool already
  but none of them exists without the heading slash. Saves another handful
  of megs on larger transactions.

Ensure directories have trailing slashes in doLookupId()

- In the old days, stripping trailing slashes made sense as its useless
  as it is and stripping it saved a bit of memory, but now with the
  directories in the pool things are different: while not all paths
  we'll see here necessarily exist in the pool already, NONE of them
  exists without the trailing slash, so stripping it out wastes gobs
  of memory.  Simplifies the code a bit and saves several megs of memory
  on larger transactions, what's not to like?

Further doLookupId() cleanup

- Refer to dirName when we haven't yet cleaned it up to clarify uses,
  only initialize the const cleaned dir name pointer after we've
  successfully cleaned it up. Rename cleanDirName to cdn to keep it
  sweet and short, and suggest the relation to cdnl and cdnbuf.

Elimiate one of the umphteen directory variables in doLookupId()

- Use dynamically allocated cdnbuf in the non-absolute path case (when
  exactly that occurs is another question) too instead of the on-stack
  dir[], making the two paths a bit more similar.

Avoid redundant ds -> id -> string lookups in rpmalAllFileSatisfiesDepend()

- We need to grab the dependency string in rpmalAllSatisfiesDepend()
  already to see whether its a file dependency or not, just pass that
  to the file deps to avoid redundant work.

Dont bother with separate notifications on multiple file dep matches

Avoid the string copy in rpmalAllFileSatisfiesDepend() now that we can

Make pool string->id operations properly length-aware

- Allow looking up and inserting partial key strings, this is useful
  in various cases where previously a local copy was needed for
  \0-terminating the key in the caller.
- Take advantage of rstrlenhash() in rpmstrPoolId(), previously the
  length was only interesting when adding so we wasted a strlen()
  on every call when the string was already in the pool.

Add length aware variant(s) of string hashing

- Being able to hash partial strings is needed for allowing string pool
  to operate on partial strings...

Enhanced string hash to permit calculating string length on the same call

- String hashing needs to walk the entire string anyhow, might as well
  take advantage of this and have it return the string length to avoid
  having to separately call strlen() in the cases where this matters.
- Move the implementation into rpmstrpool.c for inlining possibilities,
  rstrhash() is now just a wrapper to rstrlenhash(). The generic
  hash implementation could not take advantage of this anyway really.

Dont assume \0 terminated strings in rpmstrPoolPut()

- Before this, the slen argument was only good for avoiding an extra
  strlen() but being able to handle shove and lookup partial strings
  without local copy+modify in callers is handy, this is one of
  the prerequisites for that.

Use pool id's for hash table key, lookup strings from pool as needed

- The pool itself can address its contents by id alone, storing
  pointers to the strings only hurts as reallocation moving the
  data blob requires rehashing the whole thing needlessly.
- We now store just the key id in the hash buckets, and lookup the
  actual string for comparison from the pool. This avoids the
  need to rehash on realloc and saves memory too, and this is one of
  the biggest reasons for wanting a separate hash implementation for
  the string pool. Incidentally, this is how libsolv does it too.
- Individual bucket allocation becomes rather wasteful now: a bucket
  stores a single integer, and a single pointer to the next bucket,
  a pointer  which can be twice the size of the key data it holds.
  Further tuning and cleaning up after the marriage of these two
  datatypes left after the honeymoon is over...

Move the string pool struct definition earlier so we can reference it...

Inline poolHashfindEntry() into GetEntry(), nothing else needs it

Eliminate key comparison and hash function vectors from poolHash

- As the pool is hardwired to single hash type, these dont make
  any sense here and the extra indirection will only hurt performance.

More poolHash multiple data-value cleanups

- The only data associated with a pool key is a single id, we dont need
  an array for that
- Change poolHash get-entry return the id directly instead of pointer array

Eliminate redundant data counting from poolHash

- There's a strict 1:1 relation between keys and data in the string
  pool, this keeping count of data is pointless.

Eliminate unnecessary key and data free-functionality from poolHash

Pull a private hash-implementation copy to string pool

- The string pool is more specialized a data structure to be efficiently
  handled with the generic hash table implementation in rpmhash.[CH]
  and really requires quite a different approach.
- For starters, import a private copy generated roughly with:
      gcc -E -DHASHTYPE=poolHash \
             -DHTKEYTYPE="const char *" -DHTDATATYPE=rpmsid rpmhash.C
  ...and clean it up a bit: eliminate unused functions (except for
  stats which we'll want to keep for debug purposes), make remaining
  functions static and overall tidy up from the mess 'gcc -E' created.
  Lots of redundant fluff here still, to be cleaned up gradually...
- This doesn't change anything at all, but opens up the playground
  for tuning the pool hash implementation in ways the generic version
  could not (at least sanely) be.

Rename string pool hash type to poolHash

- No changes other than a rename for next steps...

Permit key imports even if signature checking is disabled (RhBug:856225)

- Since commit 290fcbbe6b3ca2fb1d5e4a7269a32a94f8a1563a, key imports
  on transaction sets where signature checking is disabled would fail
  due to keyring not getting loaded at all. A regression of sorts,
  in other words. As a minimal fix, temporarily enable sigcheck vsflags
  during keyring loading.

Lift string pool rehash into a separate helper function

- This way we have exactly one place for controlling hash (re)creation
  size strategies etc.

Use a saner pool hash resize hint

- The previous size hint would actually cause us to shrink the hash
  bucket allocation, requiring the hash to resize itself immediately
  afterwards. As if the rehashes weren't expensive enough already...

Be more selective about legacy retrofits on package read

- Missing RPMTAG_DIRNAME can mean either a package with uncompressed
  filenames OR a new package with no files, in which case the retrofits
  should not be performed. Also a newer package can be built with
  --nodirtokens, requiring filelist compression but no other retrofits.
- Test for immutable region presence for more accurate v3 package
  detection, if not present do a full retrofit. For others, explicitly
  test for OLDFILENAMES presence and only compress the filelist if needed.e

Switch rpmdb basename finding to use pool id's instead of strings

- Ids are both faster to hash/compare and cheaper to store than string
  pointers. Not a huge win but a win anyway...

Cleanup + optimize doLookupId() a bit

- Eliminate redundant second strlen() on dirName on entry, and avoid
  the first one as well by grabbing the length from pool instead.
- Reorganize the initializations and declarations a bit for clarity.

Remove leftover variable from previous commit

- Should've been in commit 1770fca303c5c5abdb27040649b458b59494823

Change fpLookupList() to operate on pool id's only

Do the low-level fingerprint lookup based on pool id arguments

- When at all possible, we'd prefer working on id's instead of
  actual strings, change the lowest-level fingerprint lookup to
  use those, doLookup() is now just a wrapper to handle string ->
  pool id conversion before doing the actual work. This shouldn't
  affect anything at all yet.

Switch fingerprinting to use the global string pool

- Transaction preparation fingerprinting now shares all the strings from
  rpmfi's etc. Rpmdb basename iterator still needs a private pool
  as there's nowhere to get a pool handle (for now at least).
- We no longer need to (and actually we couldn't) freeze the
  pool before fingerprinting.

Allow passing a shared pool for finger print cache

- Both callers updated to still use a private pool so no practical
  change here.

Remove scareMemory remnants from the internal API, fixup callers

Switch fingerprint subDir to pool ids

- <gulp> but no anomalies noted by test-suite, valgrind or
  a bit of manual testing. Time will tell...
- Memory is no longer scarce or scary, the strings are simply owned
  by the pool in all circumstances. Eliminate scareMemory foobar
  from the fingerprinting internals.

Switch fingerprint basename to pool ids

- For now we're doing a fair amount of extra work and wasting memory
  as data is in different pools so we need to copy to get the strings
  and ids into our private pool. This will go away later.

Switch fingerprint cache-entry dirnames to pool ids

- This is fairly straightforward (or supposed to be...) especially
  now that its all hidden behind APIs. Note that we no longer bother
  precalculating the hash as a pool-id's hash is a no-cost operation,
  for strings it was far more expensive.

Add a string pool to fingerprint cache (but not yet used)

Make fingerprint struct opaque outside fprint.c

- rpmfi cannot know anything about the storage, so rpmfiFpxIndex()
  cannot be... change it to rpmfiFps() which only returns the pointer
  we got from fpLookupList()
- Change fpCacheGetByFp() to assume it gets passed an array of fps,
  and take an additional index argument. Return the fingerprint
  pointer on success, NULL on not found to allow further operations
  on the fp without knowing its internals.

Change fpLookup() to return malloced memory (on first call)

- If the fingerprint pointer passed to it is NULL then allocate space
  for a new fingerprint, otherwise reuse the previous space. This should
  allow optimizing the case where repeatedly calling and directory
  doesn't change inside fpc so callers dont need special-case code
  for this. For now, we dont care about optimizations, other than
  making it possible later.

Make fingerprint cache entry opaque, add some kind of API for the needed bits

- Only disk-space calculations need the actual entry contents, add
  getter for dir name and device. We're passing the cache to these
  getters too: its not currently unusedd but will be needed for
  directory name pool id->string translation once we get there...

Hide away the FP_EQUAL macros

Change fpLookupList() to return malloced memory

- Eliminates one place where knowledge about fingerprint internals
  has been needed, now rpmfi just gets (an supposedly) opaque blob back.

Add internal API for fingerprint lookup-and-compare

- Replace the direct hackery in rpmdb internals with a little less
  direct hackery...

Bury the fingerprint hash-types into fprint.c, clean up

- fprint.h only needs rpmtypes.h now, remove historical leftovers
- Avoids having to define the hash types multiple times as they're
  now buried out of sight
- fpHashFunction() and fpLookupSubdir() can now be made static, do so...

Move the entire fingerprint cache population into fprint.c

- Rename addFingerprints() to fpCachePopulate() and move into fprint.c.
  This doesn't really belong here as it requires fprint becoming aware
  of transactions and all, but at least these are all controlled API
  accesses unlike where in transaction.c this was messing with somebody
  elses data structures directly.
- Move the by-fingerprint creation to fpCachePopulate() so it gets
  lazily done as needed and copy the original hash-size heuristics
  back here.

Hide by-fingerprint hash into fingerprint cache, add minimal API bits

- For now, always create the by-fingerprint hash although rpmdb usage
  doesn't need it. Next steps will fix...
- Add wrapper API for retrieving the records, adjust callers
- No functional changes, at least intended ones... just first steps
  towards eliminating the hash-jungle and forcing a single API
  through which this stuff gets handled

Make fingerprint cache opaque outside fprint.c

- Not that it matters much when everything else is wide open but gotta
  start with something...

Convert our dependency checking code to use the new rpmdsMatches()

- Instead of adding three more pool-aware versions of the old API's,
  convert the main callers to the newew more flexible API. As a
  "minor side-effect" these now use the transaction string-pool as well,
  so ALL our pre-transaction dependency sets are now using the global
  pool.

Unify the three rpmdsFooMatchesDep() functions into one

- These all do more or less the same thing, easily handled with a common
  function that takes a couple of more extra parameters. The old variants
  become just wrappers to call the pool-aware rpmdsMatches() with suitable
  arguments.

Use transaction string pool for rpmlib() dependencies too

- This wasn't possible with the former static rpmlib() dependency set
  as it would've kept the potentially huge global pool referenced
  throughout process lifetime.

Add pool-aware version of rpmdsRpmlib()

Hang rpmlib() dependency set onto transaction set

- Eliminates the cumbersome static rpmlib ds instance which can never
  be freed, as a member of the transaction set it simply gets cleaned
  out along with other transaction (dependency) data.

Use transaction string pool for ensureOlder() dependency sets

Use transaction string pool for findPos() dependency sets

Put transaction element "self" dependency set into global pool too

Add pool-aware versions of rpmdsThis() and rpmdsSingle()

- Pooh ... I mean pool ... bah. The previous  versions become simple
  wrappers to the pool-aware ones, using a private pool always.
  rpmdsCurrent() doesn't need pool-variant as its inherits its pool
  from the parent.

Simplify single ds creation

- Eliminate the pre-created pool wtf'ery (what was I thinking?), just
  create a ds with zero id's and fill them up once we have the ds.

Add a string equality check function to string pool API

- As a special case, two strings (ids) from the same pool can be tested for
  equality in constant time (integer comparison). If the pools differ,
  a regular string comparison is needed.

Whoopsie, unbreak checking of installed dependencies

- The dependency sets created from installed headers during rpmtsCheck()
  were using a private pool and thus ids not matching with the ones
  in the global pool. Oops. Somehow none of our test-suite cases
  caught this, looks like we'll need more tests... Also the safe-guard
  assert()'s are in all the wrong places for catching this particular
  problem. Doh :)
- There's a chicken-and-egg situation involved: in order to do this,
  the global pool needs to be in unfrozen state during rpmtsCheck(),
  which was not possible before switching rpmal provides (and files)
  to pool ids. Now that it *is* using pool id's, move the freeze-point
  to rpmtsPrepare() as the fingerprinting has similar issues with
  moving strings.

Only rehash the pool on insert if the data area actually moved

- realloc() might not need to actually move the data, and when it
  doesn't we dont need to do the very expensive rehash either.
  Unsurprisingly makes things a whole lot faster.

Switch rpmal file hash to use pool id's instead of strings

Switch rpmal provide hash to use pool id's instead of strings

Add a some transition-period asserts to ensure pool-usage sanity

Allow keeping hash table around on pool freeze, adjust callers

- Pool id -> string always works with a frozen pool, but in some cases
  we'll need to go the other way, allow caller to specify whether
  string -> id lookups should be possible on frozen pool.
- On glibc, realloc() to smaller size doesn't move the data but on
  other platforms (including valgrind) it can and does move, which
  would require a full rehash. For now, just leave all the data
  alone unless we're also freeing the hash, the memory savings
  isn't much for a global pool (which is where this matters)

Add getters for rpmds dependency name and EVR pool ids

Add getters for rpmfi base- and directory name pool id's

Pass transaction pool to rpmal (but not used yet)

Actually enable the global transaction string pool

- With this, practically all transaction member file (base- and dirname)
  and dependency strings get now stored in a giant transaction global
  string pool. Greenpeace applaudes us for all the rain-forests that
  will be saved by the memory savings... not. Some memory is saved
  but the real wins only start when everything is converted to use
  pool id's instead of string pointers. Also we're still creating
  a ridiculous number of private pools from various sources, but
  we gotta start someplace.

Add infastructure for global transaction set string pool

- Add a pool pointer to to ts members struct and a getter function
- Grab the global pool for rpmte dependency- and file info creation,
  if its NULL then the sets will use private pools of their own.
- Add the (currently) required magic voodoo rain-dance to freeze and
  unfreeze the pool as necessary wrt new element additions: for
  current rpmal and fingerprinting to work, the string pointers
  must be immovable.
- This is infrastructure only: nothing creates the global pool yet,
  so everything is still using private pools.

String pool id 0 equals NULL

- Pool id 0 is special case for "not found". Return an actual NULL
  instead of an empty string.

Avoid doing anything if pool is already frozen

Add getter methods for rpmds and rpmfi string pool handle

Delay transaction added packages rpmal creation until required

- We're not using the added rpmal for anything before rpmtsCheck() and/or
  rpmtsOrder(), so this shouldn't break anything either. This is probably
  a more or less temporary setup to make string pointer -> pool id
  transition a bit easier.

Add an nternal rpmal create+populate helper function, use for erased packages

- We'll need this shortly for added packages too...

Oops, only private pool should be frozen on ds create

Add an alternative rpmds constructor to allow shared pool usage

- rpmdsNewPool() allows specifying shared/private pool, and rpmdsNew()
  is now just a wrapper to always call it with NULL (ie private) pool.

Freeze the rpmlib dependency set pool on successful return

- ...to avoid wasting memory on the relatively static data. We could
  handle the rpmlib ds singleton behavior here too but it would change
  semantics. Ponder about it later...
- Would be nicer to have rpmdsMerge() freeze on return, but that
  gets called in loops so we'd be doing a whole lot of huffing and
  puffing recreating the pools on each entry.

Further split single ds creation into two, sigh

- Allow rpmdsCurrent() to share the pool and id's of its "parent" ds
  instead of having to repeatedly create and tear down entire pools
  just for a couple of strings. Used by python bindings for rpmds
  iteration so we'll want to be reasonably efficient.
- For now, rpmdsSingle() and rpmdsThis() always get a private pool,
  wasteful as it might be, but at least now we can freeze them.

Unify the common parts of rpmds creation into a helper function

- No functional changes, just sanity-refactoring

Eliminate assert()'s from rpmdsMerge()

- These "can't happen" cases where EVR/Flags in source ds are missing
  are just as easy to handle as is dying, handling is saner...

Eliminate assert()'s from rpmdsDup()

- The "can't happen" case where EVR/Flags are not present is just as
  easily handled as dying.

Switch dependency sets to use string pool storage for names and evrs

- Always push dependency names and versions into string pool (private
  for now). This is terribly wasteful for single ds items, even more
  so for rpmdsCurrent() but to keep the initial switch-over changes
  to minimum we'll deal with those later.
- While we freeze the pool for ds data from headers, single ds items
  are on purpose not frozen for now, due to interactions with
  rpmdsCurrent() and rpmds merging.
- Eliminate no longer needed rpmdsDupArgv(), we're now just copying
  a bunch of integers around. Sanitize rpmdsMerge() now that we can:
  realloc and shift the data instead of recreating all of N, EVR
  and Flags.

Fix segfault on rpmstrPoolId() on frozen pool

- String -> id lookups need the hash table in place even if we're not
  adding. We could do a linear search in such a case but...

Make rpmstrPoolUnfreeze() safe to call on unfrozen pool

Rename td2pool as rpmtdToPool, export and optimize

- Using rpmtd iteration for this is slow and stupid as we keep
  pointlessly re-re-re-re-re-validating the tag type and indexes.
- Change argument order to source -> destination
- Move to rpmtd.c where it belongs and make public with a decent
  name. Not sure if this is the kind of an API we really want to make
  public but ... at least for now it'll do.

Eliminate direct rpmds name (and flags) access on rpmdsNew()

Clean up rpmdsSearch() a bit

- Eliminate numerous repeated direct accesses to [o]ds N, EVR and Flags,
  instead use getter functions and local variable for ods name which
  does not change.

Add internal indexed variants of rpmds N, EVR and Flags getters

- We'll need these to eliminate the remaining direct accesses to
  N, EVR (and Flags) on random access patterns such as rpmdsSearch().

Clean up rpmdsFind() a bit

- Eliminate numerous repeated direct accesses to [o]ds N, EVR and Flags,
  instead grab them into local variables through getter functions as
  needed: on entry for ods which doesn't change, for ds in the loop
  as we're changing ds->i here.

Split rpmds EVR comparison into function of its own

- The EVR comparison is a distinct operation of its own: rpmdsCompare()
  looks at the other properties, EVR comparison is done if needed.
  Doesn't affect speed or functionality, but cuts down on the
  big number of local variables and has the nice side-effect of
  making the xstrdup() allocations local within rpmdsCompareEVR()

Use getter functions for name, evr and flags in rpmdsCurrent()

Clean up rpmdsCompare() a bit

- Eliminate numerous repeated direct accesses to ds N, EVR and Flags,
  instead grab them into local variables through getter functions
  as they are needed. Besides making it easier on the eyes, makes the
  function safe(r) wrt illegal iterator values etc.

Clean up rpmdsNewDNEVR() a bit

- Eliminate numerous repeated direct accesses to ds N, EVR and Flags,
  instead grab them into local variables at entry. This also makes
  the function safe illegal iterator values (ie calling when iteration
  not started), previously the bounds were not checked.

And now, on to the embarrassing string-pool reimplementation bugs, take I

- String pool offset resize was off by one, oops
- String pool data-area resize requires rehashing all the strings,
  as the key pointers change. Ouch. Should be avoidable by extending
  rpmhash to allow passing the pool itself around in comparisons as "self"
  and using offsets as keys, but for now working counts more than speed.
- The unfreeze-sizehint calculation could be negative. Turn the initial
  size into constant and use that as a minimum, otherwise rehashing
  uses (more or less arbitrary) heuristics to come up with some number.
  Lots of fine-tuning ahead...

Switch file info set base- and dirnames storage to string pool

- Always push base and dir names into file info sets string pool,
  whether private or shared. For basenames, this can save significant
  space even in a private pool, for dirnames private pool is moot
  as the names are already unique, shared pool is quite another story.
- Adjust fpLookupList() to take a pool and id's as arguments.
- This introduces a fair amount of overhead, so things will be somewhat
  slower until the transition to pool id's is (more) complete. Sometimes
  things have to get worse before they get better... Other than that,
  this should be entirely invisible to callers.