summaryrefslogtreecommitdiff
path: root/Objects/dictobject.c
Commit message (Collapse)AuthorAgeFilesLines
...
* Restore dicts' tp_compare slot, and change dict_richcompare to say itTim Peters2001-05-101-15/+3
| | | | | | | | | | | | | | | | | | | | doesn't know how to do LE, LT, GE, GT. dict_richcompare can't do the latter any faster than dict_compare can. More importantly, for cmp(dict1, dict2), Python *first* tries rich compares with EQ, LT, and GT one at a time, even if the tp_compare slot is defined, and dict_richcompare called dict_compare for the latter two because it couldn't do them itself. The result was a lot of wasted calls to dict_compare. Now dict_richcompare gives up at once the times Python calls it with LT and GT from try_rich_to_3way_compare(), and dict_compare is called only once (when Python gets around to trying the tp_compare slot). Continued mystery: despite that this cut the number of calls to dict_compare approximately in half in test_mutants.py, the latter still runs amazingly slowly. Running under the debugger doesn't show excessive activity in the dict comparison code anymore, so I'm guessing the culprit is somewhere else -- but where? Perhaps in the element (key/value) comparison code? We clearly spend a lot of time figuring out how to compare things.
* Repair typo in comment.Tim Peters2001-05-101-1/+1
|
* SF bug #422121 Insecurities in dict comparison.Tim Peters2001-05-101-34/+95
| | | | | | | Fixed a half dozen ways in which general dict comparison could crash Python (even cause Win98SE to reboot) in the presence of kay and/or value comparison routines that mutate the dict during dict comparison. Bugfix candidate.
* SF patch #421922: Implement rich comparison for dicts.Tim Peters2001-05-081-2/+72
| | | | | | d1 == d2 and d1 != d2 now work even if the keys and values in d1 and d2 don't support comparisons other than ==, and testing dicts for equality is faster now (especially when inequality obtains).
* Mchael Hudson pointed out that the code for detecting changes inGuido van Rossum2001-05-021-4/+4
| | | | | | dictionary size was comparing ma_size, the hash table size, which is always a power of two, rather than ma_used, wich changes on each insertion or deletion. Fixed this.
* Add experimental iterkeys(), itervalues(), iteritems() to dictGuido van Rossum2001-05-011-11/+85
| | | | | | | objects. Tests show that iteritems() is 5-10% faster than iterating over the dict and extracting the value with dict[key].
* Mondo changes to the iterator stuff, without changing how Python codeGuido van Rossum2001-04-231-2/+21
| | | | | | | | | | | | | | | | | | | | | | | | sees it (test_iter.py is unchanged). - Added a tp_iternext slot, which calls the iterator's next() method; this is much faster for built-in iterators over built-in types such as lists and dicts, speeding up pybench's ForLoop with about 25% compared to Python 2.1. (Now there's a good argument for iterators. ;-) - Renamed the built-in sequence iterator SeqIter, affecting the C API functions for it. (This frees up the PyIter prefix for generic iterator operations.) - Added PyIter_Check(obj), which checks that obj's type has a tp_iternext slot and that the proper feature flag is set. - Added PyIter_Next(obj) which calls the tp_iternext slot. It has a somewhat complex return condition due to the need for speed: when it returns NULL, it may not have set an exception condition, meaning the iterator is exhausted; when the exception StopIteration is set (or a derived exception class), it means the same thing; any other exception means some other error occurred.
* Iterators phase 1. This comprises:Guido van Rossum2001-04-201-0/+103
| | | | | | | | | | | | | | | | | | | | | | new slot tp_iter in type object, plus new flag Py_TPFLAGS_HAVE_ITER new C API PyObject_GetIter(), calls tp_iter new builtin iter(), with two forms: iter(obj), and iter(function, sentinel) new internal object types iterobject and calliterobject new exception StopIteration new opcodes for "for" loops, GET_ITER and FOR_ITER (also supported by dis.py) new magic number for .pyc files new special method for instances: __iter__() returns an iterator iteration over dictionaries: "for x in dict" iterates over the keys iteration over files: "for x in file" iterates over lines TODO: documentation test suite decide whether to use a different way to spell iter(function, sentinal) decide whether "for key in dict" is a good idea use iterators in map/filter/reduce, min/max, and elsewhere (in/not in?) speed tuning (make next() a slot tp_next???)
* Oops. Removed dictiter_new decl that wasn't supposed to go in yet.Guido van Rossum2001-04-201-2/+0
|
* Implement, test and document "key in dict" and "key not in dict".Guido van Rossum2001-04-201-1/+35
| | | | | | | | | I know some people don't like this -- if it's really controversial, I'll take it out again. (If it's only Alex Martelli who doesn't like it, that doesn't count as "real controversial" though. :-) That's why this is a separate checkin from the iterators stuff I'm about to check in next.
* Tim pointed out a remaining vulnerability in popitem(): theGuido van Rossum2001-04-161-5/+6
| | | | | | | | | | | PyTuple_New() could *conceivably* clear the dict, so move the test for an empty dict after the tuple allocation. It means that we waste time allocating and deallocating a 2-tuple when the dict is empty, but who cares. It also means that when the dict is empty *and* there's no memory to allocate a 2-tuple, we raise MemoryError, not KeyError -- but that may actually a good idea: if there's no room for a lousy 2-tuple, what are the chances that there's room for a KeyError instance?
* Tentative fix for a problem that Tim discovered at the last moment,Guido van Rossum2001-04-151-61/+110
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | and reported to python-dev: because we were calling dict_resize() in PyDict_Next(), and because GC's dict_traverse() uses PyDict_Next(), and because PyTuple_New() can cause GC, and because dict_items() calls PyTuple_New(), it was possible for dict_items() to have the dict resized right under its nose. The solution is convoluted, and touches several places: keys(), values(), items(), popitem(), PyDict_Next(), and PyDict_SetItem(). There are two parts to it. First, we no longer call dict_resize() in PyDict_Next(), which seems to solve the immediate problem. But then PyDict_SetItem() must have a different policy about when *it* calls dict_resize(), because we want to guarantee (e.g. for an algorithm that Jeremy uses in the compiler) that you can loop over a dict using PyDict_Next() and make changes to the dict as long as those changes are only value replacements for existing keys using PyDict_SetItem(). This is done by resizing *after* the insertion instead of before, and by remembering the size before we insert the item, and if the size is still the same, we don't bother to even check if we might need to resize. An additional detail is that if the dict starts out empty, we must still resize it before the insertion. That was the first part. :-) The second part is to make keys(), values(), items(), and popitem() safe against side effects on the dict caused by allocations, under the assumption that if the GC can cause arbitrary Python code to run, it can cause other threads to run, and it's not inconceivable that our dict could be resized -- it would be insane to write code that relies on this, but not all code is sane. Now, I have this nagging feeling that the loops in lookdict probably are blissfully assuming that doing a simple key comparison does not change the dict's size. This is not necessarily true (the keys could be class instances after all). But that's a battle for another day.
* Make PyDict_Next safe to use for loops that merely modify the valuesTim Peters2001-03-211-8/+32
| | | | | | associated with existing dict keys. This is a variant of part of Michael Hudson's patch #409864 "lazy fix for Pings bizarre scoping crash".
* Rich comparisons:Guido van Rossum2001-01-181-118/+45
| | | | | | | | | | | | | | | | | | | | | - Use PyObject_RichCompareBool() when comparing keys; this makes the error handling cleaner. - There were two implementations for dictionary comparison, an old one (#ifdef'ed out) and a new one. Got rid of the old one, which was abandoned years ago. - In the characterize() function, part of dictionary comparison, use PyObject_RichCompareBool() to compare keys and values instead. But continue to use PyObject_Compare() for comparing the final (deciding) elements. - Align the comments in the type struct initializer. Note: I don't implement rich comparison for dictionaries -- there doesn't seem to be much to be gained. (The existing comparison already decides that shorter dicts are always smaller than longer dicts.)
* dict_update has two boundary conditions: a.update(a) and a.update({})Jeremy Hylton2001-01-031-2/+2
| | | | Added test for second one.
* Add long-overdue docstrings to dict methods.Tim Peters2000-12-131-11/+53
|
* Typo repair in comments. Fell for GregS's .popitem() poke.Tim Peters2000-12-131-2/+6
|
* Bring comments up to date (e.g., they still said the table had to beTim Peters2000-12-131-23/+40
| | | | a prime size, which is in fact never true anymore ...).
* Add popitem() -- SF patch #102733.Guido van Rossum2000-12-121-0/+53
|
* Backing out my changes.Moshe Zadka2000-11-301-72/+0
| | | | Improved version coming soon to a Source Forge near you!
* Added .first{item,value,key}() to dictionaries.Moshe Zadka2000-11-301-0/+72
| | | | | Complete with docos and tests. OKed by Guido.
* REMOVED all CWI, CNRI and BeOpen copyright markings.Guido van Rossum2000-09-011-9/+0
| | | | This should match the situation in the 1.6b1 tree.
* Slight performance hack that also avoids requiring the existence of threadFred Drake2000-08-311-12/+124
| | | | | | | | state for dictionaries that have only been indexed by string keys. See the comments in SourceForge for more. This closes SourceForge patch #101309.
* Clear errors raised by PyObject_Compare() without losing any existingFred Drake2000-08-311-9/+44
| | | | | | | | | | exception context. This avoids improperly propogating errors raised by a user-defined __cmp__() by a subsequent lookup operation. This patch does *not* include the performance enhancement patch for dictionaries with string keys only; that will be checked in separately. This closes SourceForge patch #101277 and bug #112558.
* Barry's patch to implement the new setdefault() method.Guido van Rossum2000-08-081-0/+36
|
* Miscelaneous ANSIfications. I'm assuming here 'main' should take (int,Thomas Wouters2000-07-221-1/+1
| | | | | char**) and return an int even on PC platforms. If not, please fix PC/utils/makesrc.c ;-P
* Spelling fixes supplied by Rob W. W. Hooft. All these are fixes in eitherThomas Wouters2000-07-161-1/+1
| | | | | | | | | | comments, docstrings or error messages. I fixed two minor things in test_winreg.py ("didn't" -> "Didn't" and "Didnt" -> "Didn't"). There is a minor style issue involved: Guido seems to have preferred English grammar (behaviour, honour) in a couple places. This patch changes that to American, which is the more prominent style in the source. I prefer English myself, so if English is preferred, I'd be happy to supply a patch myself ;)
* Removed Py_PROTO and switched to ANSI C declarations in the dictTim Peters2000-07-041-104/+34
| | | | | | | implementation. This was really to test whether my new CVS+SSH setup is more usable than the old one -- and turns out it is (for whatever reason, it was impossible to do a commit before that involved more than one directory).
* Neil Schemenauer: small fixes for GCGuido van Rossum2000-07-011-0/+1
|
* Change copyright notice - 2nd try.Guido van Rossum2000-06-301-6/+0
|
* Change copyright notice.Guido van Rossum2000-06-301-22/+7
|
* final patches from Neil Schemenauer for garbage collectionJeremy Hylton2000-06-301-1/+3
|
* part 2 of Neil Schemenauer's GC patches:Jeremy Hylton2000-06-231-2/+2
| | | | | | | | This patch modifies the type structures of objects that participate in GC. The object's tp_basicsize is increased when GC is enabled. GC information is prefixed to the object to maintain binary compatibility. GC objects also define the tp_flag Py_TPFLAGS_GC.
* Round 1 of Neil Schemenauer's GC patches:Jeremy Hylton2000-06-231-0/+35
| | | | | This patch adds the type methods traverse and clear necessary for GC implementation.
* Vladimir Marangozov's long-awaited malloc restructuring.Guido van Rossum2000-05-031-4/+6
| | | | | | | | | | For more comments, read the patches@python.org archives. For documentation read the comments in mymalloc.h and objimpl.h. (This is not exactly what Vladimir posted to the patches list; I've made a few changes, and Vladimir sent me a fix in private email for a problem that only occurs in debug mode. I'm also holding back on his change to main.c, which seems unnecessary to me.)
* Add PyDict_Copy() function to C API for dicts. It returns a newJeremy Hylton2000-03-301-1/+15
| | | | dictionary that contains the same key/value pairs as p.
* Christian Tismer's "trashcan" patch:Guido van Rossum2000-03-131-0/+2
| | | | | | | | Added wrapping macros to dictobject.c, listobject.c, tupleobject.c, frameobject.c, traceback.c that safely prevends core dumps on stack overflow. Macros and functions in object.c, object.h. The method is an "elevator destructor" that turns cascading deletes into tail recursive behavior when some limit is hit.
* dict_has_key(): Accept only one parameter. PR#210 reported byFred Drake2000-02-231-4/+4
| | | | Andreas Jung <ajung@sz-sb.de>.
* Vladimir Marangozov contributed updated comments.Guido van Rossum1999-03-241-11/+8
|
* Remove dead code discovered by Vladimir Marangozov.Guido van Rossum1998-11-161-4/+2
|
* Slight rearrangement of code in lookdict() by Vladimir Marangozov, toGuido van Rossum1998-10-061-4/+3
| | | | make a common case slightly faster.
* Avoid using calloc(). This triggered an obscure bug on multiprocessorGuido van Rossum1998-07-161-1/+2
| | | | | | | Sparc Solaris 2.6 (fully patched!) that I don't want to dig into, but which I suspect is a bug in the multithreaded malloc library that only shows up when run on a multiprocessor. (The program wasn't using threads, it was just using the multithreaded C library.)
* Make sure that PyDict_GetItem[String]() *never* raises an exception.Guido van Rossum1998-05-141-2/+3
| | | | | If the argument is not a dictionary, simply return NULL. If the hash() on the key fails, clear the error.
* Use Py_Repr{Enter,Leave} to display recursive dictionaries in finite space.Guido van Rossum1998-04-101-5/+31
| | | | (Jeremy will hardly recognize his patch :-)
* Correct Barry's fix -- take care of {}.get(0).Guido van Rossum1997-10-201-0/+3
|
* dict_get(): Fixed a couple of stupid mistakes which caused crashes.Barry Warsaw1997-10-201-8/+2
| | | | Also got rid of some unnecessary code.
* dict_get(): New method for item access with different semantics thanBarry Warsaw1997-10-061-0/+38
| | | | | | | | | __getitem__(). This method never raises an exception; if the key is not in the dictionary, the second (optional) argument is returned. If the second argument is not provided and the key is missing, None is returned. mapp_methods: added "get" method.
* Don't intern the key string for getitem and delitem.Guido van Rossum1997-09-291-3/+1
|
* Made lookdict nearly twice as fast, resulting in a 5% overallGuido van Rossum1997-08-181-11/+13
| | | | improvement of pystone. Vladimir Marangozov.
* Reordered list of methods to hopefully put the most frequently usedGuido van Rossum1997-07-131-4/+4
| | | | ones near the front.
View Lorry Controller Status