[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: gEDA-user: pcb git segmentation fault in hid binary searchs
Here's a patch for the binary searches in actions.c and flags.c. I've
compiled and tested on Ubuntu, and it seems to work just fine. Also
added case insensitive search to the flags.c implementation as well.
Jason
On Sun, May 24, 2009 at 12:12 AM, Oblivian
<[1]oblivian@xxxxxxxxxxxxxxxxxxxxx> wrote:
DJ,
Thanks, I'll see what I can do to remove the linear search as well.
Jason
On Sun, May 24, 2009 at 12:07 AM, DJ Delorie <[2]dj@xxxxxxxxxxx>
wrote:
> I've tracked the problem to the binary search in hid_find_flag, when
strcmp
> gets a null value from the flags being searched. This may be a
recent
> change in glibc for Ubuntu and a test program that just does
strcmp("some
> string",NULL); segfaults for me. I've changed it to use bsearch for
now...
> my question is, is there a reason the stdlib bsearch function was
not used?
> I notice that qsort is used right above it. If there is no
complaint in
> changing the bsearch's in flags.c and actions.c, I'll submit a patch
for it.
No reason, go ahead.
> Also, question in actions.c... It appears that the binary search is
> performed and a linear search is done if the action was not found in
the
> binary search. Is there a reason for this or was it just overlooked
in the
> hid upgrade?
The binary search is case sensitive, the linear search isn't. What
we
might consider is a hash based on tolower(name) instead.
_______________________________________________
geda-user mailing list
[3]geda-user@xxxxxxxxxxxxxx
[4]http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
References
1. mailto:oblivian@xxxxxxxxxxxxxxxxxxxxx
2. mailto:dj@xxxxxxxxxxx
3. mailto:geda-user@xxxxxxxxxxxxxx
4. http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
diff --git a/src/hid/common/actions.c b/src/hid/common/actions.c
index 0f2dfb4..cdb011a 100644
--- a/src/hid/common/actions.c
+++ b/src/hid/common/actions.c
@@ -129,18 +129,28 @@ hid_deregister_action (const char *name, void **context)
}
static int
-action_sort (const void *va, const void *vb)
+action_comp (const void *va, const void *vb)
{
HID_ActionContext *a = (HID_ActionContext *) va;
HID_ActionContext *b = (HID_ActionContext *) vb;
return strcmp (a->action.name, b->action.name);
}
+static int
+action_case_comp (const void *va, const void *vb)
+{
+ HID_ActionContext *a = (HID_ActionContext *) va;
+ HID_ActionContext *b = (HID_ActionContext *) vb;
+ return strcasecmp (a->action.name, b->action.name);
+}
+
+
HID_Action *
hid_find_action (const char *name, void **context)
{
HID_ActionNode *ha;
- int i, n, lower, upper;
+ int i, n;
+ HID_ActionContext key, *res;
if (name == NULL)
return 0;
@@ -155,36 +165,35 @@ hid_find_action (const char *name, void **context)
all_actions[n].context = ha->context;
n++;
}
- qsort (all_actions, n_actions, sizeof (HID_ActionContext), action_sort);
+ qsort (all_actions, n_actions, sizeof (HID_ActionContext), action_comp);
}
- lower = -1;
- upper = n_actions;
- /*printf("search action %s\n", name); */
- while (lower < upper - 1)
+ key.action.name = malloc (strlen(name) + 1);
+ strcpy (key.action.name, name);
+
+ /* Case sensitive search */
+ res = bsearch (&key, all_actions, n_actions, sizeof (HID_ActionContext), action_comp);
+ if (res != NULL)
{
- i = (lower + upper) / 2;
- n = strcmp (all_actions[i].action.name, name);
- /*printf("try [%d].%s, cmp %d\n", i, all_actions[i].name, n); */
- if (n == 0) {
- if (context != NULL)
- *context = all_actions[i].context;
- return &(all_actions[i].action);
- }
- if (n > 0)
- upper = i;
- else
- lower = i;
+ free (key.action.name);
+ if (*context != NULL)
+ *context = res->context;
+ return &(res->action);
}
- for (i = 0; i < n_actions; i++)
- if (strcasecmp (all_actions[i].action.name, name) == 0) {
+ /* Case insensitive search */
+ res = bsearch (&key, all_actions, n_actions, sizeof (HID_ActionContext), action_case_comp);
+ if (res != NULL)
+ {
+ free (key.action.name);
if (*context != NULL)
- *context = all_actions[i].context;
- return &(all_actions[i].action);
+ *context = res->context;
+ return &(res->action);
}
+ free (key.action.name);
+
printf ("unknown action `%s'\n", name);
return 0;
}
diff --git a/src/hid/common/flags.c b/src/hid/common/flags.c
index 8aba3ab..3d9b31a 100644
--- a/src/hid/common/flags.c
+++ b/src/hid/common/flags.c
@@ -52,18 +52,28 @@ hid_register_flags (HID_Flag * a, int n)
}
static int
-flag_sort (const void *va, const void *vb)
+flag_comp (const void *va, const void *vb)
{
HID_Flag *a = (HID_Flag *) va;
HID_Flag *b = (HID_Flag *) vb;
return strcmp (a->name, b->name);
}
+static int
+flag_case_comp (const void *va, const void *vb)
+{
+ HID_Flag *a = (HID_Flag *) va;
+ HID_Flag *b = (HID_Flag *) vb;
+ return strcasecmp (a->name, b->name);
+}
+
+
HID_Flag *
hid_find_flag (const char *name)
{
HID_FlagNode *hf;
- int i, n, lower, upper;
+ int i, n;
+ HID_Flag key, *res;
if (all_flags == 0)
{
@@ -72,24 +82,30 @@ hid_find_flag (const char *name)
for (hf = hid_flag_nodes; hf; hf = hf->next)
for (i = 0; i < hf->n; i++)
all_flags[n++] = hf->flags[i];
- qsort (all_flags, n_flags, sizeof (HID_Flag), flag_sort);
+ qsort (all_flags, n_flags, sizeof (HID_Flag), flag_comp);
}
- lower = -1;
- upper = n_flags + 1;
- /*printf("search flag %s\n", name); */
- while (lower < upper - 1)
+ key.name = malloc (strlen(name)+1);
+ strcpy (key.name, name);
+
+ /* Case sensitive search */
+ res = bsearch (&key, all_flags, n_flags, sizeof (HID_Flag), flag_comp);
+ if (res != NULL)
{
- i = (lower + upper) / 2;
- n = strcmp (all_flags[i].name, name);
- /*printf("try [%d].%s, cmp %d\n", i, all_flags[i].name, n); */
- if (n == 0)
- return all_flags + i;
- if (n > 0)
- upper = i;
- else
- lower = i;
+ free (key.name);
+ return res;
}
+
+ /* Case insensitive search */
+ res = bsearch (&key, all_flags, n_flags, sizeof (HID_Flag), flag_case_comp);
+ if (res != NULL)
+ {
+ free (key.name);
+ return res;
+ }
+
+ free (key.name);
+
printf ("unknown flag `%s'\n", name);
return 0;
}
_______________________________________________
geda-user mailing list
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user