###Bug###

I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check. Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.

###Suggestion for simplification###

If you created static inline functions like these:

static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...

Bug

I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check. Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.

Suggestion for simplification

If you created static inline functions like these:

static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...

###Bug###

I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.

###Suggestion for simplification###

If you created static inline functions like these:

static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...

###Bug###

I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check. Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.

###Suggestion for simplification###

If you created static inline functions like these:

static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...