+
+struct find_data {
+ void *value;
+ vector_index index;
+};
+
+static int vector_find_item(vector_index index, void *item,void *data) {
+ struct find_data *fd = (struct find_data*)data;
+ if ( fd->value != item ) {
+ return 0;
+ }
+ fd->index = index;
+ return 1;
+}
+
+vector_index vector_find(vector *pv,void *value) {
+ struct find_data fd = {
+ .value = value,
+ .index = pv->size
+ };
+ vector_iterate( pv, 0, vector_find_item, &fd );
+ return fd.index;
+}
+
+// Find surrounding indexes for a given item key in a sparse vector
+void *vector_bsearch(vector *pv,vector_index *index,const void *key,
+ int (*compare)(const void *key, const void *item)) {
+ vector_index lo = 0;
+ vector_index hi = pv->size;
+ if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) {
+ return 0;
+ }
+ hi++;
+ while ( lo < hi ) {
+ vector_index m = lo + ( hi - lo ) / 2;
+ void **slot = vector_next_used( pv, &m );
+ int c = compare( key, *slot );
+ if ( c == 0 ) {
+ *index = m;
+ return *slot;
+ }
+ if ( c < 0 ) {
+ hi = m;
+ } else {
+ lo = m + 1;
+ }
+ }
+ return 0;
+}
+
+// Iterator callback.
+static int checkunused(vector_index index,void *item,void *data) {
+ vector_index *last = (vector_index*) data;
+ if ( item == 0 ) {
+ (*last) = index;
+ return 1;
+ }
+ if ( *last > index ) {
+ // Only on the first iteration, with *last = vector_sie
+ if ( index == 0 ) {
+ (*last) = 1;
+ return 0;
+ }
+ *last = 0;
+ } else if ( index == (*last) ) {
+ (*last)++;
+ return 0;
+ }
+ return 1;
+}
+
+// Scan forward for the next unused vector slot
+vector_index vector_next_unused(vector *pv,vector_index index) {
+ vector_index unused = vector_size( pv );
+ vector_iterate( pv, index, checkunused, &unused );
+ return unused;
+}