bool *BKE_objdef_validmap_get(Object *ob, const int defbase_tot)
{
	bDeformGroup *dg;
	ModifierData *md;
	bool *vgroup_validmap;
	GHash *gh;
	int i, step1 = 1;
	//int defbase_tot = BLI_countlist(&ob->defbase);

	if (ob->defbase.first == NULL) {
		return NULL;
	}

	gh = BLI_ghash_str_new("BKE_objdef_validmap_get gh");

	/* add all names to a hash table */
	for (dg = ob->defbase.first; dg; dg = dg->next) {
		BLI_ghash_insert(gh, dg->name, NULL);
	}

	BLI_assert(BLI_ghash_size(gh) == defbase_tot);

	/* now loop through the armature modifiers and identify deform bones */
	for (md = ob->modifiers.first; md; md = !md->next && step1 ? (step1 = 0), modifiers_getVirtualModifierList(ob) : md->next) {
		if (!(md->mode & (eModifierMode_Realtime | eModifierMode_Virtual)))
			continue;

		if (md->type == eModifierType_Armature) {
			ArmatureModifierData *amd = (ArmatureModifierData *) md;

			if (amd->object && amd->object->pose) {
				bPose *pose = amd->object->pose;
				bPoseChannel *chan;

				for (chan = pose->chanbase.first; chan; chan = chan->next) {
					if (chan->bone->flag & BONE_NO_DEFORM)
						continue;

					if (BLI_ghash_remove(gh, chan->name, NULL, NULL)) {
						BLI_ghash_insert(gh, chan->name, SET_INT_IN_POINTER(1));
					}
				}
			}
		}
	}

	vgroup_validmap = MEM_mallocN(sizeof(*vgroup_validmap) * defbase_tot, "wpaint valid map");

	/* add all names to a hash table */
	for (dg = ob->defbase.first, i = 0; dg; dg = dg->next, i++) {
		vgroup_validmap[i] = (BLI_ghash_lookup(gh, dg->name) != NULL);
	}

	BLI_assert(i == BLI_ghash_size(gh));

	BLI_ghash_free(gh, NULL, NULL);

	return vgroup_validmap;
}

/* Set the vertex's unique ID in the log */
static void bm_log_vert_id_set(BMLog *log, BMVert *v, unsigned int id)
{
	void *vid = SET_INT_IN_POINTER(id);
	
	BLI_ghash_remove(log->id_to_elem, vid, NULL, NULL);
	BLI_ghash_insert(log->id_to_elem, vid, v);
	BLI_ghash_remove(log->elem_to_id, v, NULL, NULL);
	BLI_ghash_insert(log->elem_to_id, v, vid);
}

/* Set the face's unique ID in the log */
static void bm_log_face_id_set(BMLog *log, BMFace *f, unsigned int id)
{
	void *fid = SET_INT_IN_POINTER(id);
	
	BLI_ghash_remove(log->id_to_elem, fid, NULL, NULL);
	BLI_ghash_insert(log->id_to_elem, fid, f);
	BLI_ghash_remove(log->elem_to_id, f, NULL, NULL);
	BLI_ghash_insert(log->elem_to_id, f, fid);
}

/**
 * Return icon id of given preview, or create new icon if not found.
 */
int BKE_icon_preview_ensure(PreviewImage *preview)
{
	Icon *new_icon = NULL;

	if (!preview || G.background)
		return 0;

	if (preview->icon_id)
		return preview->icon_id;

	preview->icon_id = get_next_free_id();

	if (!preview->icon_id) {
		printf("%s: Internal error - not enough IDs\n", __func__);
		return 0;
	}

	new_icon = MEM_mallocN(sizeof(Icon), __func__);

	new_icon->obj = preview;
	new_icon->type = 0;  /* Special, tags as non-ID icon/preview. */

	/* next two lines make sure image gets created */
	new_icon->drawinfo = NULL;
	new_icon->drawinfo_free = NULL;

	BLI_ghash_insert(gIcons, SET_INT_IN_POINTER(preview->icon_id), new_icon);

	return preview->icon_id;
}

int BKE_icon_getid(struct ID* id)
{
	Icon* new_icon = NULL;

	if (!id || G.background)
		return 0;

	if (id->icon_id)
		return id->icon_id;

	id->icon_id = get_next_free_id();

	if (!id->icon_id){
		printf("BKE_icon_getid: Internal error - not enough IDs\n");
		return 0;
	}

	new_icon = MEM_callocN(sizeof(Icon), "texicon");

	new_icon->obj = id;
	new_icon->type = GS(id->name);
	
	/* next two lines make sure image gets created */
	new_icon->drawinfo = NULL;
	new_icon->drawinfo_free = NULL;

	BLI_ghash_insert(gIcons, SET_INT_IN_POINTER(id->icon_id), new_icon);
	
	return id->icon_id;
}

void UI_editsource_active_but_test(uiBut *but)
{
	extern void PyC_FileAndNum_Safe(const char **filename, int *lineno);

	struct uiEditSourceButStore *but_store= MEM_callocN(sizeof(uiEditSourceButStore), __func__);

	const char *fn;
	int lineno= -1;

#if 0
	printf("comparing buttons: '%s' == '%s'\n",
	       but->drawstr, ui_editsource_info->but_orig.drawstr);
#endif

	PyC_FileAndNum_Safe(&fn, &lineno);

	if (lineno != -1) {
		BLI_strncpy(but_store->py_dbg_fn, fn,
					sizeof(but_store->py_dbg_fn));
		but_store->py_dbg_ln= lineno;
	}
	else {
		but_store->py_dbg_fn[0]= '\0';
		but_store->py_dbg_ln= -1;
	}

	BLI_ghash_insert(ui_editsource_info->hash, but, but_store);
}

BME_TransData *BME_assign_transdata(BME_TransData_Head *td, BME_Mesh *bm, BME_Vert *v,
		float *co, float *org, float *vec, float *loc,
		float factor, float weight, float maxfactor, float *max) {
	BME_TransData *vtd;
	int is_new = 0;

	if (v == NULL) return NULL;

	if ((vtd = BLI_ghash_lookup(td->gh, v)) == NULL && bm != NULL) {
		vtd = BLI_memarena_alloc(td->ma, sizeof(*vtd));
		BLI_ghash_insert(td->gh, v, vtd);
		td->len++;
		is_new = 1;
	}

	vtd->bm = bm;
	vtd->v = v;
	if (co != NULL) VECCOPY(vtd->co,co);
	if (org == NULL && is_new) { VECCOPY(vtd->org,v->co); } /* default */
	else if (org != NULL) VECCOPY(vtd->org,org);
	if (vec != NULL) {
		VECCOPY(vtd->vec,vec);
		normalize_v3(vtd->vec);
	}
	vtd->loc = loc;

	vtd->factor = factor;
	vtd->weight = weight;
	vtd->maxfactor = maxfactor;
	vtd->max = max;

	return vtd;
}

static bool ghash_insert_link(
        GHash *gh, void *key, void *val, bool use_test,
        MemArena *mem_arena)
{
	struct LinkBase *ls_base;
	LinkNode *ls;

	ls_base = BLI_ghash_lookup(gh, key);

	if (ls_base) {
		if (use_test && (BLI_linklist_index(ls_base->list, key) != -1)) {
			return false;
		}
	}
	else {
		ls_base = BLI_memarena_alloc(mem_arena, sizeof(*ls_base));
		ls_base->list     = NULL;
		ls_base->list_len = 0;
		BLI_ghash_insert(gh, key, ls_base);
	}

	ls = BLI_memarena_alloc(mem_arena, sizeof(*ls));
	ls->next = ls_base->list;
	ls->link = val;
	ls_base->list = ls;
	ls_base->list_len += 1;

	return true;
}

static void strand_shade_get(Render *re, StrandShadeCache *cache, ShadeSample *ssamp, StrandSegment *sseg, StrandVert *svert)
{
	StrandCacheEntry *entry;
	StrandPoint p;
	int *refcount;
	GHashPair pair = strand_shade_hash_pair(sseg->obi, svert);

	entry= BLI_ghash_lookup(cache->resulthash, &pair);
	refcount= BLI_ghash_lookup(cache->refcounthash, &pair);

	if (!entry) {
		/* not shaded yet, shade and insert into hash */
		p.t= (sseg->v[1] == svert)? 0.0f: 1.0f;
		strand_eval_point(sseg, &p);
		strand_shade_point(re, ssamp, sseg, svert, &p);

		entry= MEM_callocN(sizeof(StrandCacheEntry), "StrandCacheEntry");
		entry->pair = pair;
		entry->shr = ssamp->shr[0];
		BLI_ghash_insert(cache->resulthash, entry, entry);
	}
	else
		/* already shaded, just copy previous result from hash */
		ssamp->shr[0]= entry->shr;
	
	/* lower reference count and remove if not needed anymore by any samples */
	(*refcount)--;
	if (*refcount == 0) {
		BLI_ghash_remove(cache->resulthash, &pair, (GHashKeyFreeFP)MEM_freeN, NULL);
		BLI_ghash_remove(cache->refcounthash, &pair, NULL, NULL);
	}
}

static void internalAdd(struct bArgs *ba, const char *arg, int pass,
                        int case_str, BA_ArgCallback cb, void *data, bArgDoc *d)
{
	bArgument *a;
	bAKey *key;

	a = lookUp(ba, arg, pass, case_str);

	if (a) {
		printf("WARNING: conflicting argument\n");
		printf("\ttrying to add '%s' on pass %i, %scase sensitive\n",
		       arg, pass, case_str == 1 ? "not " : "");
		printf("\tconflict with '%s' on pass %i, %scase sensitive\n\n",
		       a->key->arg, (int)a->key->pass, a->key->case_str == 1 ? "not " : "");
	}

	a = MEM_callocN(sizeof(bArgument), "bArgument");
	key = MEM_callocN(sizeof(bAKey), "bAKey");

	key->arg = arg;
	key->pass = pass;
	key->case_str = case_str;

	a->key = key;
	a->func = cb;
	a->data = data;
	a->doc = d;

	BLI_ghash_insert(ba->items, key, a);
}

/* OB_DUPLIVERTS - FONT */
static Object *find_family_object(const char *family, size_t family_len, unsigned int ch, GHash *family_gh)
{
	Object **ob_pt;
	Object *ob;
	void *ch_key = SET_UINT_IN_POINTER(ch);

	if ((ob_pt = (Object **)BLI_ghash_lookup_p(family_gh, ch_key))) {
		ob = *ob_pt;
	}
	else {
		char ch_utf8[7];
		size_t ch_utf8_len;

		ch_utf8_len = BLI_str_utf8_from_unicode(ch, ch_utf8);
		ch_utf8[ch_utf8_len] = '\0';
		ch_utf8_len += 1;  /* compare with null terminator */

		for (ob = G.main->object.first; ob; ob = ob->id.next) {
			if (STREQLEN(ob->id.name + 2 + family_len, ch_utf8, ch_utf8_len)) {
				if (STREQLEN(ob->id.name + 2, family, family_len)) {
					break;
				}
			}
		}

		/* inserted value can be NULL, just to save searches in future */
		BLI_ghash_insert(family_gh, ch_key, ob);
	}

	return ob;
}

static void gpu_parse_functions_string(GHash *hash, char *code)
{
	GPUFunction *function;
	int i, type, qual;

	while ((code = strstr(code, "void "))) {
		function = MEM_callocN(sizeof(GPUFunction), "GPUFunction");

		code = gpu_str_skip_token(code, NULL, 0);
		code = gpu_str_skip_token(code, function->name, MAX_FUNCTION_NAME);

		/* get parameters */
		while (*code && *code != ')') {
			/* test if it's an input or output */
			qual = FUNCTION_QUAL_IN;
			if (gpu_str_prefix(code, "out "))
				qual = FUNCTION_QUAL_OUT;
			if (gpu_str_prefix(code, "inout "))
				qual = FUNCTION_QUAL_INOUT;
			if ((qual != FUNCTION_QUAL_IN) || gpu_str_prefix(code, "in "))
				code = gpu_str_skip_token(code, NULL, 0);

			/* test for type */
			type= 0;
			for (i=1; i<=16; i++) {
				if (GPU_DATATYPE_STR[i] && gpu_str_prefix(code, GPU_DATATYPE_STR[i])) {
					type= i;
					break;
				}
			}

			if (!type && gpu_str_prefix(code, "sampler2DShadow"))
				type= GPU_SHADOW2D;
			if (!type && gpu_str_prefix(code, "sampler2D"))
				type= GPU_TEX2D;

			if (type) {
				/* add paramater */
				code = gpu_str_skip_token(code, NULL, 0);
				code = gpu_str_skip_token(code, NULL, 0);
				function->paramqual[function->totparam]= qual;
				function->paramtype[function->totparam]= type;
				function->totparam++;
			}
			else {
				fprintf(stderr, "GPU invalid function parameter in %s.\n", function->name);
				break;
			}
		}

		if (function->name[0] == '\0' || function->totparam == 0) {
			fprintf(stderr, "GPU functions parse error.\n");
			MEM_freeN(function);
			break;
		}

		BLI_ghash_insert(hash, function->name, function);
	}
}

static void debug_data_insert(SimDebugData *debug_data, SimDebugElement *elem)
{
	SimDebugElement *old_elem = BLI_ghash_lookup(debug_data->gh, elem);
	if (old_elem) {
		*old_elem = *elem;
		MEM_freeN(elem);
	}
	else
		BLI_ghash_insert(debug_data->gh, elem, elem);
}

/**
 * Removes the hash for quick lookup of channels, must
 * be done when adding/removing channels.
 */
void BKE_pose_channels_hash_make(bPose *pose) 
{
	if (!pose->chanhash) {
		bPoseChannel *pchan;
		
		pose->chanhash = BLI_ghash_str_new("make_pose_chan gh");
		for (pchan = pose->chanbase.first; pchan; pchan = pchan->next)
			BLI_ghash_insert(pose->chanhash, pchan->name, pchan);
	}
}

static ListBase *edge_isect_ls_ensure(GHash *isect_hash, ScanFillEdge *eed)
{
	ListBase *e_ls;
	e_ls = BLI_ghash_lookup(isect_hash, eed);
	if (e_ls == NULL) {
		e_ls = MEM_callocN(sizeof(ListBase), __func__);
		BLI_ghash_insert(isect_hash, eed, e_ls);
	}
	return e_ls;
}

/* assign only one texid per buffer to avoid sampling the same texture twice */
static void codegen_set_texid(GHash *bindhash, GPUInput *input, int *texid, void *key)
{
	if (BLI_ghash_haskey(bindhash, key)) {
		/* Reuse existing texid */
		input->texid = GET_INT_FROM_POINTER(BLI_ghash_lookup(bindhash, key));
	}
	else {
		/* Allocate new texid */
		input->texid = *texid;
		(*texid)++;
		input->bindtex = true;
		BLI_ghash_insert(bindhash, key, SET_INT_IN_POINTER(input->texid));
	}
}

static unsigned int *imb_thread_cache_get_tile(ImThreadTileCache *cache, ImBuf *ibuf, int tx, int ty)
{
	ImThreadTile *ttile, lookuptile;
	ImGlobalTile *gtile, *replacetile;
	int toffs= ibuf->xtiles*ty + tx;

	/* test if it is already in our thread local cache */
	if((ttile=cache->tiles.first)) {
		/* check last used tile before going to hash */
		if(ttile->ibuf == ibuf && ttile->tx == tx && ttile->ty == ty)
			return ibuf->tiles[toffs];

		/* find tile in hash */
		lookuptile.ibuf = ibuf;
		lookuptile.tx = tx;
		lookuptile.ty = ty;

		if((ttile=BLI_ghash_lookup(cache->tilehash, &lookuptile))) {
			BLI_remlink(&cache->tiles, ttile);
			BLI_addhead(&cache->tiles, ttile);

			return ibuf->tiles[toffs];
		}
	}

	/* not found, have to do slow lookup in global cache */
	if(cache->unused.first == NULL) {
		ttile= cache->tiles.last;
		replacetile= ttile->global;
		BLI_remlink(&cache->tiles, ttile);
		BLI_ghash_remove(cache->tilehash, ttile, NULL, NULL);
	}
	else {
		ttile= cache->unused.first;
		replacetile= NULL;
		BLI_remlink(&cache->unused, ttile);
	}

	BLI_addhead(&cache->tiles, ttile);
	BLI_ghash_insert(cache->tilehash, ttile, ttile);

	gtile= imb_global_cache_get_tile(ibuf, tx, ty, replacetile);

	ttile->ibuf= gtile->ibuf;
	ttile->tx= gtile->tx;
	ttile->ty= gtile->ty;
	ttile->global= gtile;

	return ibuf->tiles[toffs];
}

void tracks_map_insert(TracksMap *map, MovieTrackingTrack *track, void *customdata)
{
	MovieTrackingTrack new_track = *track;

	new_track.markers = MEM_dupallocN(new_track.markers);

	map->tracks[map->ptr] = new_track;

	if (customdata)
		memcpy(&map->customdata[map->ptr * map->customdata_size], customdata, map->customdata_size);

	BLI_ghash_insert(map->hash, &map->tracks[map->ptr], track);

	map->ptr++;
}

/**
 * Generate a PreviewImage from given file path, using thumbnails management, if not yet existing.
 */
PreviewImage *BKE_previewimg_cached_thumbnail_read(
        const char *name, const char *path, const int source, bool force_update)
{
	PreviewImage *prv = NULL;
	void **prv_p;

	prv_p = BLI_ghash_lookup_p(gCachedPreviews, name);

	if (prv_p) {
		prv = *prv_p;
		BLI_assert(prv);
	}

	if (prv && force_update) {
		const char *prv_deferred_data = PRV_DEFERRED_DATA(prv);
		if (((int)prv_deferred_data[0] == source) && STREQ(&prv_deferred_data[1], path)) {
			/* If same path, no need to re-allocate preview, just clear it up. */
			BKE_previewimg_clear(prv);
		}
		else {
			BKE_previewimg_free(&prv);
		}
	}

	if (!prv) {
		/* We pack needed data for lazy loading (source type, in a single char, and path). */
		const size_t deferred_data_size = strlen(path) + 2;
		char *deferred_data;

		prv = previewimg_create_ex(deferred_data_size);
		deferred_data = PRV_DEFERRED_DATA(prv);
		deferred_data[0] = source;
		memcpy(&deferred_data[1], path, deferred_data_size - 1);

		force_update = true;
	}

	if (force_update) {
		if (prv_p) {
			*prv_p = prv;
		}
		else {
			BLI_ghash_insert(gCachedPreviews, BLI_strdup(name), prv);
		}
	}

	return prv;
}

static void strand_shade_refcount(StrandShadeCache *cache, StrandSegment *sseg, StrandVert *svert)
{
	GHashPair pair = strand_shade_hash_pair(sseg->obi, svert);
	GHashPair *key;
	int *refcount= BLI_ghash_lookup(cache->refcounthash, &pair);

	if (!refcount) {
		key= BLI_memarena_alloc(cache->memarena, sizeof(GHashPair));
		*key = pair;
		refcount= BLI_memarena_alloc(cache->memarena, sizeof(int));
		*refcount= 1;
		BLI_ghash_insert(cache->refcounthash, key, refcount);
	}
	else
		(*refcount)++;
}