Log of /python/trunk/Objects/setobject.c

Untabify C files. Will watch buildbots.

Issue 8436: set.__init__ accepts keyword args

Issue #7818: set().test_c_api() doesn't expect a set('abc'), modify the set.

The set types can also be called without arguments.

#8030: make builtin type docstrings more consistent: use "iterable" instead of "seq(uence)", use "new" to show that set() always returns a new object.

Issue 7263: Fix set.intersection() docstring.

Issue 6573: Fix set.union() for cases where self is in the argument chain.

Issue #3680: Reference cycles created through a dict, set or deque iterator did not get collected.

#4069: aSet.remove(otherSet) would always report the empty frozenset([]) as the missing key.
Now it correctly refers to the initial otherset.

Reviewed by Raymond. Will backport to 2.6.

Mention exception in docstring

Issue 2235: __hash__ is once again inherited by default, but inheritance can be blocked explicitly so that collections.Hashable remains meaningful

Added additional __sizeof__ implementations and addressed comments made in
Issue3122.

Multi-arg form for set.difference() and set.difference_update().

Handle the case with zero arguments.

Let set.intersection() and set.intersection_update() take multiple input arguments.

Let set.union() and set.update() accept multiple inputs.

This reverts r63675 based on the discussion in this thread:

 http://mail.python.org/pipermail/python-dev/2008-June/079988.html

Python 2.6 should stick with PyString_* in its codebase.  The PyBytes_* names
in the spirit of 3.0 are available via a #define only.  See the email thread.

Issue 2855: Fix obscure crasher by slowing down the entire module.  Mimics what was done to dictionaries in r59223.

Renamed PyString to PyBytes

Frozensets do not benefit from autoconversion.

dict.copy() rises from the ashes.  Revert r60687.

Add -3 warnings that set.copy(), dict.copy(), and defaultdict.copy() will go away in Py3.x

Unified naming convention for free lists and their limits. All free lists
in Object/ are named ``free_list``, the counter ``numfree`` and the upper
limit is a macro ``PyName_MAXFREELIST`` inside an #ifndef block.

The chances should make it easier to adjust Python for platforms with
less memory, e.g. mobile phones.

Ensure that PySet_Add() operates on a newly created frozenset, like PyTuple_SetItem does.

Add PyFrozenSet_Check(), which was not needed before; The list of Py*Set_Check* macros seems to be complete now.

Add missing NEWS entries about all this.

Factor-out common code with a new macro

Make PySet_Add() work with frozensets.
Works like PyTuple_SetItem() to build-up values in a brand new frozenset.
Also, PyFrozenSet_New() is now guaranteed to produce a distinct new frozenset.

Revert PySet_Add() changes.

Update test code for change to PySet_Add().

Make PySet_Add() work with frozensets.  Works like PyTuple_SetItem() to build-up values in a brand new frozenset.

Changes 54857 and 54840 broke code and were reverted in Py2.5 just before
it was released, but that reversion never made it to the Py2.6 head.

#1629: Renamed Py_Size, Py_Type and Py_Refcnt to Py_SIZE, Py_TYPE and Py_REFCNT. Macros for b/w compatibility are available.

Backport of _abccoll.py by Benjamin Arangueren, issue 1383.
With some changes of my own thrown in (e.g. backport of r58107).

Reposition the decref (spotted by eagle-eye norwitz).

Add set.isdisjoint()

Add a bunch of GIL release/acquire points in tp_print implementations and for
PyObject_Print().

Closes issue #1164.

PEP 3123: Provide forward compatibility with Python 3.0, while keeping
backwards compatibility. Add Py_Refcnt, Py_Type, Py_Size, and
PyVarObject_HEAD_INIT.

Fix a bug in test_c_api() that caused a negative refcount.

Extend work on rev 52962 and 53829 eliminating redundant PyObject_Hash() calls and fixing set/dict interoperability.

Fixup set/dict interoperability.

Extend work on revision 52962:  Eliminate redundant calls to PyObject_Hash().

Bypass set specific optimizations for set and frozenset subclasses.

Bug #1648179:  set.update() not recognizing __iter__ overrides in dict subclasses.

SF #1486663 -- Allow keyword args in subclasses of set() and frozenset().

For sets with cyclical reprs, emit an ellipsis instead of infinitely recursing.

Port Georg's dictobject.c fix keys that were tuples got unpacked on the way to setting a KeyError (svn revision 52535, sf bug 
1576657).

Port Armin's fix for a dict resize vulnerability (svn revision 46589, sf bug 1456209).

Eliminate two redundant calls to PyObject_Hash().

Fix warnings with HP's C compiler.  It doesn't recognize that infinite
loops are, um, infinite.  These conditions should not be able to happen.

Will backport.

Fix refcounts and add error checks.

[Bug #1414697] Change docstring of set/frozenset types to specify that the contents are unique.  Raymond, please feel free to edit or revert.

otherset is known to be non-NULL based on checks before and DECREF after.
DECREF otherset rather than XDECREF in error conditions too.

Reported by Klockwork #154.

Use Py_ssize_t

Clear dummy and emptyfrozenset, so that we don't have
dangling references in case of a Py_Initialize/Py_Finalize
cycle.

Ignore the references to the dummy objects used as deleted keys
in dicts and sets when computing the total number of references.

Remove "static forward" declaration. Move constructors
after the type objects.

SF patch #1458476 with modifications based on discussions in python-dev.  This
adds the following API calls: PySet_Clear(), _PySet_Next(), and
_PySet_Update().  The latter two are considered non-public.  Tests and
documentation (for the public API) are included.

Remove unnecessary casts in type object initializers.

Tighten an overbroad and misleading assertion.
(Reported by Jim Jewett.)

Use Py_ssize_t for PySet_Size() like all the other Py*_Size() functions.

Merge ssize_t branch.

Renamed _length_cue() to __length_hint__().  See:
http://mail.python.org/pipermail/python-dev/2006-February/060524.html

Remove some shadowed variables

Prevent name pollution by making lots of internal functions static.

Convert iterator __len__() methods to a private API.

No longer ignore exceptions raised by comparisons during key lookup.
Inspired by Armin Rigo's suggestion to do the same with dictionaries.

Disallow keyword arguments for type constructors that don't use them.
(fixes bug #1119418)

* Add a fast equality check path for frozensets where the hash value has
  already been computed.
* Apply a GET_SIZE macro().

Add shortcuts for a|a and a&a.

Results of a line-by-line comparison back to dictobject.c.

* set_merge() cannot assume that the table doesn't resize during iteration.

* convert some unnecessary tests to asserts -- they were necessary in
  dictobject.c because PyDict_Next() is a public function.  The same is
  not true for set_next().

* re-arrange the order of functions to more closely match the order
  in dictobject.c.  This makes it must easier to compare the two
  and ought to simplify any issues of maintaining both.

Numerous fix-ups to C API and docs.  Added tests for C API.

DECREF --> XDECREF

Add a C API for sets and frozensets.

More function re-ordering (placing like functions together).

* Bring lookkey() and lookkey_string() closer to dict version.
* Use set_next() for looping in issubset() and frozenset_hash().
* Re-order the presentation of cmp and hash functions.

* Fix SF #1257731.  Make __contains__(), remove(), and discard() only do
  a frozenset conversion when the initial search attempt fails with a
  TypeError and the key is some type of set.  Add a testcase.

* Eliminate a duplicate if-stmt.

* Add short-circuit code for in-place operations with self (such as
  s|=s, s&=s, s-=s, or s^=s).  Add related tests.

* Improve names for several variables and functions.

* Provide alternate table access functions (next, contains, add, and discard)
  that work with an entry argument instead of just a key.  This improves
  set-vs-set operations because we already have a hash value for each key
  and can avoid unnecessary calls to PyObject_Hash().  Provides a 5% to 20%
  speed-up for quick hashing elements like strings and integers.  Provides
  much more substantial improvements for slow hashing elements like tuples
  or objects defining a custom __hash__() function.

* Have difference operations resize() when 1/5 of the elements are dummies.
  Formerly, it was 1/6.  The new ratio triggers less frequently and only
  in cases that it can resize quicker and with greater benefit.  The right
  answer is probably either 1/4, 1/5, or 1/6.  Picked the middle value for
  an even trade-off between resize time and the space/time costs of dummy
  entries.

* Bring in INIT_NONZERO_SET_SLOTS macro from dictionary code.
* Bring in free list from dictionary code.
* Improve several comments.
* Differencing can leave many dummy entries.  If more than
  1/6 are dummies, then resize them away.
* Factor-out common code with new macro, PyAnySet_CheckExact.

* Removed checked_error flag which no longer provides any benefit.
* Have issubset() control its own loop instead of using set_next_internal().

* set_new() doesn't need to zero the structure a second time after tp_alloc
  has already done the job.
* Use a macro form of PyErr_Occurred() inside the set_lookkey() function.

Factor away a redundant clear() function.

* Improve a variable name:  entry0 --> table.
* Give set_lookkey_string() a fast alternate path when no dummy entries
  are present.
* Have set_swap_bodies() reset the hash field to -1 whenever either of
  bodies is not a frozenset.  Maintains the invariant of regular sets
  always having -1 in the hash field; otherwise, any mutation would make
  the hash value invalid.
* Use an entry pointer to simplify the code in frozenset_hash().

* Move copyright notice to top and indicate derivation from sets.py and
  dictobject.c.
* Have frozenset_hash() use entry->hash instead of re-computing each
  individual hash with PyObject_Hash(o);
* Finalize the dummy entry before a system exit.

Model set.pop() after dict.popitem().

* Improve code for the empty frozenset singleton:
  - Handle both frozenset() and frozenset([]).
  - Do not use singleton for frozenset subclasses.
  - Finalize the singleton.
  - Add test cases.
* Factor-out set_update_internal() from set_update().  Simplifies the
  code for several internal callers.
* Factor constant expressions out of loop in set_merge_internal().
* Minor comment touch-ups.

Fix build on gcc: PySetIter_Type should be static in definition
part also.

Improve variable names.

Fix frozenset() ref count and a comment typo.

Comment on the set_swap_bodies() helper function.

Revised the set() and frozenset() implementaion to use its own internal
data structure instead of using dictionaries.  Reduces memory consumption
by 1/3 and provides modest speed-ups for most set operations.

SF patch #1200018:  Restore GC support to set objects

Reverts 1.26 and 1.27.
And adds cycle testing.

SF 1062353:  set pickling problems

Support automatic pickling of dictionaries in instance of set subclasses.

Use Py_CLEAR().  Add unrelated test.

Moved SunPro warning suppression into pyport.h and out of individual
modules and objects.

Fixed end-of-loop code not reached warning when using SunPro C

Remove a function no longer in use.

Remove unnecessary GC support.  Sets cannot have cycles.

Futher improvements to frozenset hashing (based on Yitz Gale's battery of
tests which nicely highly highlight weaknesses).

* Initial value is now a large prime.
* Pre-multiply by the set length to add one more basis of differentiation.
* Work a bit harder inside the loop to scatter bits from sources that
  may have closely spaced hash values.

All of this is necessary to make up for keep the hash function commutative.
Fortunately, the hash value is cached so the call to frozenset_hash() will
only occur once per set.

Fixups to the hash function for frozensets.

* Non-zero initial value so that hash(frozenset()) != hash(0).
* Final permutation to differentiate nested sets.
* Add logic to make sure that -1 is not a possible hash value.

Make sets and deques weak referencable.

The copy module now handles sets directly.  The __copy__ methods are no
longer needed.

* Simplify and speedup logic for tp_print.
* Speed-up intersection whenever PyDict_Next can be used.

Speedup set.update by using the override mode for PyDict_Merge().

Improve algorithm for set.difference when the input is not a set.

* Refactor set.__contains__()
* Use Py_RETURN_NONE everywhere.
* Fix-up the firstpass check for the tp_print slot.

Refactor set.discard() and set.remove().

Use dictionary specific looping idiom where possible.
Simplifies and speeds-up the code.

* Added a new method flag, METH_COEXIST.

* Used the flag to optimize set.__contains__(), dict.__contains__(),
  dict.__getitem__(), and list.__getitem__().

Expose dict_contains() and PyDict_Contains() with is about 10% faster
than PySequence_Contains() and more clearly applicable to dicts.

Apply the new function in setobject.c where __contains__ checking is
ubiquitous.

Factor out more duplicate code.

Stop GCC warning about int literal that's so long that it becomes an
unsigned int (on a 32-bit machine), by adding an explicit 'u' to the
literal (a prime used to improve the hash function for frozenset).

* Checkin remaining documentation
* Add more tests
* Refactor and neaten the code a bit.
* Rename union_update() to update().
* Improve the algorithms (making them a closer to sets.py).

* Simplify hash function and add test to show effectiveness of the hash
  function.

* Add a better test for deepcopying.

* Add tests to show the __init__() function works like it does for list
  and tuple.  Add related test.

* Have shallow copies of frozensets return self.  Add related test.

* Have frozenset(f) return f if f is already a frozenset. Add related test.

* Beefed-up some existing tests.

Extend temporary hashability to remove() and discard().
Brings the functionality back in line with sets.py.

Allow temporary hashability for the __contains__ test.
(Requested by Alex Martelli.)

issubset() and issuperset() to work with general iterables

Three minor performance improvements:

* Improve the hash function to increase the chance that distinct sets will
  have distinct xor'd hash totals.

* Use PyDict_Merge where possible (it is faster than an equivalent iter/set
  pair).

* Don't rebuild dictionaries where the input already has one.

Implement straightforward suggestions from gcc warnings (remove unused
variable, add extra braces).

Use PySequence_Contains() instead of direct access macro.

Various fixups (most suggested by Armin Rigo).

Fix output spacing typo

* Migrate set() and frozenset() from the sandbox.
* Install the unittests, docs, newsitem, include file, and makefile update.
* Exercise the new functions whereever sets.py was being used.

Includes the docs for libfuncs.tex.  Separate docs for the types are
forthcoming.