5 #if PY_VERSION_HEX < 0x02050000
11 staticforward PyTypeObject Trie_Type;
19 trie_trie(PyObject* self, PyObject* args)
24 if (!PyArg_ParseTuple(args,":trie"))
26 if(!(trie = Trie_new()))
27 return PyErr_NoMemory();
28 if(!(trieobj = PyObject_New(trieobject, &Trie_Type)))
31 return (PyObject*)trieobj;
35 _decref_objects(const unsigned char *key, const void *value, void *data)
37 Py_DECREF((PyObject *)value);
41 trie_dealloc(PyObject* self)
43 trieobject *mp = (trieobject *)self;
44 Trie_iterate(mp->trie, _decref_objects, NULL);
50 trie_length(trieobject *mp)
52 return Trie_len(mp->trie);
56 trie_subscript(trieobject *mp, PyObject *py_key)
61 /* Make sure key is a string. */
62 if(!PyString_Check(py_key)) {
63 PyErr_SetString(PyExc_TypeError, "key must be a string");
66 key = (unsigned char *)PyString_AS_STRING(py_key);
67 py_value = (PyObject *)Trie_get(mp->trie, key);
69 PyErr_SetString(PyExc_KeyError, (char *)key);
76 trie_ass_sub(trieobject *mp, PyObject *py_key, PyObject *py_value)
81 /* Make sure key is a string. */
82 if(!PyString_Check(py_key)) {
83 PyErr_SetString(PyExc_TypeError, "key must be a string");
86 key = (unsigned char *)PyString_AS_STRING((char *)py_key);
88 /* Check to see whether something already exists at that key. If
89 there's already an object there, then I will have to remove it.
91 py_prev = (PyObject *)Trie_get(mp->trie, key);
96 /* The client wants to delete a key from a dictionary. The Trie
97 API doesn't support this, so I will just overwrite it with
100 /* If the key doesn't exist, raise a KeyError. */
102 PyErr_SetString(PyExc_KeyError, (char *)key);
105 Trie_set(mp->trie, key, NULL);
107 /* The client wants to set a key in the dictionary. */
110 if(Trie_set(mp->trie, key, py_value)) {
111 PyErr_SetString(PyExc_AssertionError, "error setting trie");
118 static char has_key__doc__[] =
119 "D.has_key(k) -> 1 if D has a key k, else 0";
122 trie_has_key(trieobject *mp, PyObject *py_key)
127 /* Make sure key is a string. */
128 if(!PyString_Check(py_key)) {
129 PyErr_SetString(PyExc_TypeError, "key must be a string");
132 key = (unsigned char *)PyString_AS_STRING(py_key);
133 has_key = Trie_has_key(mp->trie, key);
134 return PyInt_FromLong((long)has_key);
138 trie_has_key_onearg(trieobject *mp, PyObject *py_args)
141 if(!PyArg_ParseTuple(py_args, "O", &py_arg))
143 return trie_has_key(mp, py_arg);
148 static char has_prefix__doc__[] =
149 "D.has_prefix(k) -> 1 if D has a prefix k, else 0";
152 trie_has_prefix(trieobject *mp, PyObject *py_prefix)
154 unsigned char *prefix;
157 /* Make sure prefix is a string. */
158 if(!PyString_Check(py_prefix)) {
159 PyErr_SetString(PyExc_TypeError, "k must be a string");
162 prefix = (unsigned char *)PyString_AS_STRING(py_prefix);
163 has_prefix = Trie_has_prefix(mp->trie, prefix);
164 return PyInt_FromLong((long)has_prefix);
168 trie_has_prefix_onearg(trieobject *mp, PyObject *py_args)
171 if(!PyArg_ParseTuple(py_args, "O", &py_arg))
173 return trie_has_prefix(mp, py_arg);
176 static char with_prefix__doc__[] =
177 "D.with_prefix(prefix) -> list of D's keys that begins with prefix";
180 _trie_with_prefix_helper(const unsigned char *key, const void *value,
183 PyObject *py_list = (PyObject *)data;
189 if(!(py_key = PyString_FromString((const char *)key)))
191 PyList_Append(py_list, py_key);
196 trie_with_prefix(trieobject *mp, PyObject *py_prefix)
198 unsigned char *prefix;
201 /* Make sure prefix is a string. */
202 if(!PyString_Check(py_prefix)) {
203 PyErr_SetString(PyExc_TypeError, "k must be a string");
206 prefix = (unsigned char *)PyString_AS_STRING(py_prefix);
208 if(!(py_list = PyList_New(0)))
210 Trie_with_prefix(mp->trie, prefix,
211 _trie_with_prefix_helper, (void *)py_list);
212 if(PyErr_Occurred()) {
220 trie_with_prefix_onearg(trieobject *mp, PyObject *py_args)
223 if(!PyArg_ParseTuple(py_args, "O", &py_arg))
225 return trie_with_prefix(mp, py_arg);
229 static char keys__doc__[] =
230 "D.keys() -> list of D's keys";
233 _trie_keys_helper(const unsigned char *key, const void *value, void *data)
235 PyObject *py_list = (PyObject *)data;
241 if(!(py_key = PyString_FromString((char *)key)))
243 PyList_Append(py_list, py_key);
248 trie_keys(trieobject *mp)
252 if(!(py_list = PyList_New(0)))
254 Trie_iterate(mp->trie, _trie_keys_helper, (void *)py_list);
255 if(PyErr_Occurred()) {
263 trie_keys_noargs(trieobject *mp, PyObject *py_args)
265 if(PyTuple_Size(py_args) != 0) {
266 PyErr_SetString(PyExc_ValueError, "no args expected");
269 return trie_keys(mp);
272 static char values__doc__[] =
273 "D.values() -> list of D's values";
276 _trie_values_helper(const unsigned char *key, const void *value, void *data)
278 PyObject *py_list = (PyObject *)data;
281 PyList_Append(py_list, (PyObject *)value);
285 trie_values(trieobject *mp)
289 if(!(py_list = PyList_New(0)))
291 Trie_iterate(mp->trie, _trie_values_helper, (void *)py_list);
292 if(PyErr_Occurred()) {
300 trie_values_noargs(trieobject *mp, PyObject *py_args)
302 if(PyTuple_Size(py_args) != 0) {
303 PyErr_SetString(PyExc_ValueError, "no args expected");
306 return trie_values(mp);
309 static char get__doc__[] =
310 "D.get(k[,d]) -> D[k] if D.has_key(k), else d. d defaults to None.";
313 trie_get(trieobject *mp, PyObject *args)
317 PyObject *py_failobj = Py_None;
319 if (!PyArg_ParseTuple(args, "s|O:get", &key, &py_failobj))
321 py_value = (PyObject *)Trie_get(mp->trie, key);
323 py_value = py_failobj;
328 static char get_approximate__doc__[] =
329 "D.get_approximate(key, k) -> List of (key, value, mismatches) in D, allowing up to k mismatches in key.";
332 _trie_get_approximate_helper(const unsigned char *key, const void *value,
333 const int mismatches, void *data)
335 /* Append a tuple of (key, value) to data, which is a PyList. */
336 PyObject *py_list = (PyObject *)data,
337 *py_value = (PyObject *)value,
345 if(!(py_key = PyString_FromString((const char *)key)))
347 if(!(py_mismatches = PyInt_FromLong(mismatches))) {
353 if(!(py_tuple = PyTuple_New(3))) {
355 Py_DECREF(py_mismatches);
359 PyTuple_SetItem(py_tuple, 0, py_key);
360 PyTuple_SetItem(py_tuple, 1, py_value);
361 PyTuple_SetItem(py_tuple, 2, py_mismatches);
362 PyList_Append(py_list, py_tuple);
367 trie_get_approximate(trieobject *mp, PyObject *args)
373 if (!PyArg_ParseTuple(args, "si:get_approximate", &key, &k))
376 if(!(py_list = PyList_New(0)))
378 Trie_get_approximate(mp->trie, key, k,
379 _trie_get_approximate_helper, (void *)py_list);
380 if(PyErr_Occurred()) {
388 trie_nohash(PyObject *self)
390 PyErr_SetString(PyExc_TypeError, "trie objects are unhashable");
394 static PyMappingMethods trie_as_mapping = {
395 /* The first member of PyMappingMethods was redefined in Python 2.5. */
396 #if PY_VERSION_HEX < 0x02050000
397 (inquiry)trie_length, /*mp_length*/
399 (lenfunc)trie_length, /*mp_length*/
401 (binaryfunc)trie_subscript, /*mp_subscript*/
402 (objobjargproc)trie_ass_sub /*mp_ass_subscript*/
405 static PyMethodDef trieobj_methods[] = {
406 /* METH_O and METH_NOARGS require Python 2.2.
407 {"has_key", (PyCFunction)trie_has_key, METH_O,
409 {"has_prefix", (PyCFunction)trie_has_prefix, METH_O,
411 {"with_prefix", (PyCFunction)trie_with_prefix, METH_O,
413 {"keys", (PyCFunction)trie_keys, METH_NOARGS,
415 {"values", (PyCFunction)trie_values, METH_NOARGS,
419 {"has_key", (PyCFunction)trie_has_key_onearg, METH_VARARGS,
421 {"has_prefix", (PyCFunction)trie_has_prefix_onearg, METH_VARARGS,
423 {"with_prefix", (PyCFunction)trie_with_prefix_onearg, METH_VARARGS,
425 {"keys", (PyCFunction)trie_keys_noargs, METH_VARARGS,
427 {"values", (PyCFunction)trie_values_noargs, METH_VARARGS,
430 {"get", (PyCFunction)trie_get, METH_VARARGS,
432 {"get_approximate", (PyCFunction)trie_get_approximate, METH_VARARGS,
433 get_approximate__doc__},
434 {NULL, NULL} /* sentinel */
437 static PyObject *trie_getattr(PyObject *obj, char *name)
439 return Py_FindMethod(trieobj_methods, (PyObject *)obj, name);
443 static PyTypeObject Trie_Type = {
444 PyObject_HEAD_INIT(NULL)
449 trie_dealloc, /*tp_dealloc*/
451 trie_getattr, /*tp_getattr*/
456 0, /*tp_as_sequence*/
457 &trie_as_mapping, /*tp_as_mapping*/
458 trie_nohash, /*tp_hash */
462 _write_to_handle(const void *towrite, const int length, void *handle)
464 PyObject *py_handle = (PyObject *)handle,
471 if(!(py_retval = PyObject_CallMethod(py_handle, "write", "s#",
473 goto _write_to_handle_cleanup;
476 _write_to_handle_cleanup:
478 Py_DECREF(py_retval);
483 int _write_value_to_handle(const void *value, void *handle)
485 PyObject *py_value = (PyObject *)value,
486 *py_marshalled = NULL;
491 #ifdef Py_MARSHAL_VERSION
493 PyMarshal_WriteObjectToString(py_value, Py_MARSHAL_VERSION)))
494 goto _write_value_to_handle_cleanup;
496 if(!(py_marshalled = PyMarshal_WriteObjectToString(py_value)))
497 goto _write_value_to_handle_cleanup;
499 if(PyString_AsStringAndSize(py_marshalled, &marshalled, &length) == -1)
500 goto _write_value_to_handle_cleanup;
501 if(!_write_to_handle(&length, sizeof(length), handle))
502 goto _write_value_to_handle_cleanup;
503 if (length != (int)length)
504 goto _write_value_to_handle_cleanup;
505 if(!_write_to_handle(marshalled, (int)length, handle))
506 goto _write_value_to_handle_cleanup;
509 _write_value_to_handle_cleanup:
511 Py_DECREF(py_marshalled);
518 trie_save(PyObject *self, PyObject *args)
524 if(!PyArg_ParseTuple(args, "OO:save", &py_handle, &py_trie))
526 mp = (trieobject *)py_trie;
527 if(!Trie_serialize(mp->trie, _write_to_handle, _write_value_to_handle,
528 (void *)py_handle)) {
529 if(!PyErr_Occurred())
530 PyErr_SetString(PyExc_RuntimeError,
531 "saving failed for some reason");
539 _read_from_handle(void *wasread, const int length, void *handle)
541 PyObject *py_handle = (PyObject *)handle,
545 PyBufferProcs *buffer;
547 int bytes_read, bytes_left;
552 if(!(py_retval = PyObject_CallMethod(py_handle, "read", "i", length)))
553 goto _read_from_handle_cleanup;
554 if(!py_retval->ob_type->tp_as_buffer) {
555 PyErr_SetString(PyExc_ValueError, "read method should return buffer");
556 goto _read_from_handle_cleanup;
558 if(!(py_retval->ob_type->tp_flags & Py_TPFLAGS_DEFAULT)) {
559 PyErr_SetString(PyExc_ValueError, "no bf_getcharbuffer slot");
560 goto _read_from_handle_cleanup;
562 buffer = py_retval->ob_type->tp_as_buffer;
563 if(!buffer->bf_getreadbuffer) {
564 PyErr_SetString(PyExc_ValueError, "no bf_getreadbuffer");
565 goto _read_from_handle_cleanup;
570 while(bytes_left > 0) {
571 if((bytes_read = buffer->bf_getreadbuffer(py_retval,
572 segment, &retval)) == -1)
573 goto _read_from_handle_cleanup;
574 memcpy(wasread, retval, bytes_read);
575 wasread = (void *)((char *)wasread + bytes_read);
576 bytes_left -= bytes_read;
582 _read_from_handle_cleanup:
584 Py_DECREF(py_retval);
589 #define MAX_KEY_LENGTH 2000
591 _read_value_from_handle(void *handle)
594 char KEY[MAX_KEY_LENGTH];
596 if(!_read_from_handle((void *)&length, sizeof(length), (void *)handle))
598 if(length < 0 || length >= MAX_KEY_LENGTH)
600 if(!_read_from_handle((void *)KEY, length, (void *)handle))
602 return PyMarshal_ReadObjectFromString(KEY, length);
607 trie_load(PyObject *self, PyObject *args)
613 if(!PyArg_ParseTuple(args, "O:load", &py_handle))
616 if(!(trie = Trie_deserialize(_read_from_handle, _read_value_from_handle,
618 if(!PyErr_Occurred())
619 PyErr_SetString(PyExc_RuntimeError,
620 "loading failed for some reason");
624 if(!(trieobj = PyObject_New(trieobject, &Trie_Type))) {
628 trieobj->trie = trie;
629 return (PyObject *)trieobj;
632 static PyMethodDef trie_methods[] = {
633 {"trie", trie_trie, METH_VARARGS,
634 "trie() -> new Trie object."},
635 {"load", trie_load, METH_VARARGS,
636 "load(handle) -> trie object"},
637 {"save", trie_save, METH_VARARGS,
638 "save(handle, trie), save a trie object to a handle"},
639 {NULL, NULL, 0, NULL}
642 static char trie__doc__[] =
644 This module implements a trie data structure. This allows an O(M)\n\
645 lookup of a string in a dictionary, where M is the length of the\n\
646 string. It also supports approximate matches.\n\
649 trie Create a new trie object.\n\
650 save Save a trie to a handle.\n\
651 load Load a trie from a handle.\n\
658 Trie_Type.ob_type = &PyType_Type;
660 (void) Py_InitModule3("trie", trie_methods, trie__doc__);